Устройство для вычисления свертки

етение относится к вычистехнике, предназначеноения свертки или коррецифровых последовательожет быть использовано в Ваш СУДАРСТВЕНКЫЙ КОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ ВТОРСКОМУ СВИДЕ 965067/24-245.10.855.03.87. Бюл. У 10есский политехничес(57) Изобрлительнойдля вычислляции двухностей и м системах цифровой обработки сигналови изображений. Цель изобретения -повышение быстродействия, Поставленная цель достигается за счет того,что устройство для цифровой фильтрации содержит аналого-цифровые преобразователи 1 и 2, блок памяти 3, цилический регистр сдвига 4, состоящииз сдвигового регистра 5 и элеиентаНЕ 6, счетчик сдвигов 7, блок памятикоэффициентов 8, накапливающие сумматоры 9 и 10, элементы НЕ 11 и 2, оперативную память 13, состоящую изблока 14 памяти и буферного блока15 памяти, блок 16 умножения по иодулю целого числа, регистр 17 адреса,регистр 18 адреса этапа, дешифратор19 и блок 20 памяти константы. 1 ил.Таким образом, в случае вычислений согласно выражению (2) возможно увеличение размерностей обрабатываемых последовательностей с М =М=Фс 1=2 в устройстве прототипе до М =М=М , где п= 1 о 8 (Р -1)(х- М 1 С 11 иближайшее целое число меньше х), при этом за счет того, что в выражении (2) матрицы Т и Т являются преобИ 11разованиями Рейдера (3), которые вычисляются без умножений, число умножений уменьшается с М =1+3 2ч(в случае сохранения структуры процессора) до 11=1+3(п). Например, в случае Р =297 имеем И=1+3 2 =25; У =1+3(2-1)=4, отсюда, Я/М=6,25; при Г=65537, И/111 =49/7=7.Лля случая М=1 Р 1297073Изобретение относится к вычислительной технике, предназначено для вычисления свертки или корреляции двух цифровых последовательностей и может быть использовано в системах 5 цифровой обработки сигналов и изображений.Цель изобретения - повышение быстродействия устройства.На чертеже изображена структурная 10 схема устройства (пример конкретного выполнения для,случая МщМ ).Устройство вычисляет свертку двух последовательностей с помощью числового преобразования видаУ-Т (Т ЬТ Х)1 М-М , (1) гдеТ П (К Е 1 - )(1 ч Т1)1го Т-Мй (1 ,Е ТЕ 1, )Р ,1 с 191 я; 1 ),где 9 - определяет левое кронекеровское произведение матриц,т.е. АЭВ=( АЬ;Т и Т- соответственно прямое и 1обратное теоретико-числовое преобразование РейдераТЧ ссй Р 11 С, 21 сса Р 1Е . " диагональные матрицы весой 1вых коэффициентов видайа(1; КК.35 К;, Иа(О, М, 2 М11-1( 1) М ).Аналогично выражению (4) определяются матрицы К . с учетом замены показатеЙ 1лей степеней на отрицательные;В матрице К 1 использована симм 45 волическая запись 1 вместо, где число ы. берется равным о=8"д; М=(Р -1)/М"; я - первообразный корень (т.е. 8(Г - 1).=1 шой Р, и я ф шой Р 50 при любом каР -1). Кроме того, чтобы1 в разложении (2) матрицы Т и Т соответствовали преобразованию Рейдера (3), необходимо выбрать первообразный корень я, удовлетворяющий условию= 2(шой Г ) (5) Т с(Т 9 1) К(1 У Т);Т ", -(1 ТР ",(Та 1)В этом случае при к. 3, Р =257 имеем2 ф сМ=16, М =256, ы =я. Для удовлетворения условия (,5) я выбирается равнымя=27, отсюда Ы.=27.При С с 4, Р 65537 имеем М=32,М =1024, с=8, тогда, я 8053, отсюдаа 41054,Устройство для вычисления свертки содержит аналого-цифровые преобразователи 1 и 2, блок 3 оперативной) памяти, циклический сдвиговыйрегистр 4, состоящий иэ сдвиговогорегистра 5 и элемента НЕ 6, включенного в цепь обратной связи, идущей свыхода старшего разряда сдвиговогорегистра 5 на вход его младшего разряда через элемент б, счетчик сдвигов 7, блок 8 памяти коэффициентов,накапливающие сумматоры 9 и 10, элементы НЕ 11 и 12, оперативную память13, состоящую из блока 14 (оперативной) памяти и буферного блока 15(оперативной) памяти, блок умножения16 по модулю целого числа, регистр17 адреса, регистр 18 адреса этапа,дешифратор 19 (двоичной инверсии адреса), блок 20 памяти (весовых) коэффициентов.Устройство работает следующим образом.Аналого-циФровые преобразователии 2 преобразуют аналоговые сигналы+в числовой код разрядностью 2 +1 бит,которые запоминаются в блоке 3 опеаративной памяти. Числовые последова"тельности записываются в блок 3 оперативной памяти в последовательном порядке, занимая соответственно ячейки памяти с адресами для сигнала Х(п) с 0 по М -1 и для сигнала Ь(п)2с М по 2 М -1, С учетом порядка за 2писи сигналов Х(п) и Ь(п) в устройстве сначала вычисляется теоретикочисловое преобразование Х(1 с), затем Н(1 с) . 10На первом этапе вычислений происсодит вычисление преобразований Рейдера Тот соответствующих блоков входных данных, Каждое преобразование Т вычисляется по быстрому алгойритму с прореживаннем по времени, Алгоритм с прореживанием по времени требует перестановки адресов входных данных по закону двоичной инверсии. Перестановка данных на входе позволяет исключить данную операцию иэ процесса вычислений введением дешифратора 19 двоичной инверсии адреса. При этом преобразование М чисел производится за 1 ое М итераций, в каждой 25 иэ которых вычисляется М/2 величин видаА+2 В 1 сА -2 В 1 с(7)Для вычисления первого преобразо вания Т из блока 3 оперативной памяти считывается последовательность Х,11), тщО, 1- с адресами отсчетов О, М, 2 М(М)М. Дешифратор 19 двоичной инверсии адреса определяет 35 считывание необходимых пар чисел Ак. и В с учетом перестановки чисел Х, по закону двоичной инверсии, Пары чисел А и В из блока 3 оперативной памяти через циклический сдвиговый регистр 4 передаются в накапливающие сумматоры 9 и 10. Причем, в соответствии с выражением (7), первое число А передается без сдвига, а второе число В сдвигается в циклическом сдвиговом регистре 4 на т разрядов влево, что эквивалентно умножению на 2 . Сумматоры 9 и 1 О осуществляют соответственно операции сложения и вычитания. Справедливость правил арифметики по модулю Р обесс печивается с помощью элемента НЕ 6, обеспечивающего цикличность сдвигов при умножении на 2 , и элементов НЕ 11 и 12, предотвращающих возникнове ние режима генерации при наличии единиц во всех разрядах. С выхода сумматоров 9 и 10 результаты записываются в блок 13 памяти. Блок 8 памяти коэффициентов определяет необходимое число сдвигов г, требуемых для вычисления преобразования Т по быстн рому алгоритму, и представляет собой конечный автомат, определяющийк число г согласно правилу г=(2, ) в вос 1 М, где 1 с - номер этапа вычислений; д - номер итерации на 1 с-м этапе, тщО,72-1. Управление сдвигами в циклическом сдвиговом регистре 4 осуществляется счетчиком сдвигов 7, в который предварительно записывается нужное число сдвигов из блока 8 памяти коэффициентов. В блок 14 оперативной памяти записываются и считываются результаты промежуточных вычислений (7). Промежуточные результаты, записанные в него, снова подаются на вход циклического сдвигового регистра 4, Операция (7) повторяется М/2.1 ое М раз доЯполного завершения преобразования Т,. Окончательный результат преобразования ТХ поступает в блок 15 буферной памяти емкостью в М(2 +1) разрядных слов. При вычислении второго преобразования Т сн блока 3 оперативной памяти считывается последовательность чисел Х (с), =О, Мс адресами отсчетов 1, 1+М, 1+2 М.1+(М)М. При этом процесс вычисления преобразования Т Хн н,ф полностью аналогичен предыдущему. Одновременно, пока блок 14 оперативной памяти участвует в следующем преобразовании, буферный блок 15 оперативной памяти осуществляет обмен с блоком 16 умножения по модулю целого числа, в котором происходит умножение результатов первого преобразования на соответствующие весовые коэффициенты сс , определяемые из диагональной матрицы Ка в выражении (6)Последовательность весовых коэффициентов Ю записана в блоке 20 памяти весовых коэффициентов ем-костью М /2 к(2 +1) разрядных слов,й.Порядок подачи коэффициентовв блок 16 умножения определяется регистром 18 адреса этапа следующим образом. После каждого определенияХ 4=Т Х.блок из М отсчетов результата преобразования необходимо умножить на соответствующий блокевесовых коэффициентов с . В этом случае величина показателя Р, а, следовательно, и соответствующий адресего хранения, равны р=Ц, т,е. длялпоследовательности Х , 1-.1=0 Иимеем рЕ 0,1,г,(И 1)1Результат умножения с блока 15буферной оперативной памяти записывается в блок 3 оперативной памятипо тем же адресам, по которым происходило считывание последовательностиХ, (ю.).Аналогично рассмотренному происходит вычисление преобразований Т последовательностей Х .(х), ,3=0, И,считываемых с блока 3 оперативнойпамяти по адресам 1, .1+И 1+2 М,1+(И)И, умножение результатов пре-.образований Т Х, Х , на соответстй 4 рвующие коэффициенты д. и запись результатов обратно в блок 3 оперативной памяти по тем же адресам. Такимобразом, первый этап вычислений завершается вычислением И раз преобразований Рейдера Т , второй этапумножением результатов преобразоваРний на весовые коэффициенты Ы и записью промежуточных результатов вблок 3 оперативной памяти.На третьем этапе вычисляются Ипреобразований Рейдера Т от промежул йточных данных Х, записанных в блоке 3 оперативной памяти после первыхдвух этапов вычислений. Считываниеиз блока З.оперативной памяти послелдовательностей Х, 1,3=0, Инатретьем этапе выйолняется по адресам3 И, 1 И+1, 1 И+2, , 3 И+И. После 35вычисления каждого преобразованияТХ данные с буферного блока 15ойеративной памяти записываются обратно в блок 3 оперативной памяти потем же адресам.40После данного этапа заканчиваетсявычисление преобразования ТХ ,м цАналогичным образом выполняется выРчисление преобразования Т ЬМ с учетом того что адресация данных после9Ядовательности ЬИ сдвинута на Иотносительно адресов данных последовательности Х ,После вычисления преобразованийХ=ТХаи Й=ТЬна четвертом50этапе осуществляется поэлементноеумножение последовательностей Х ил л лНр . При этом пары чисел Х и Нсоответственно с адресамии +И=0, Ипоступают иэ блока 3 опе 55ративной памяти на блок 1 б умножения по модулю целого числа. Резульлтат умножения Т.: через буферный блок 15 оперативной памяти записывается обратно в блок 3 оперативной памяти по адресу х, Таким образом, после данного этапа вычислений по адресам О, Ив блоке 3 оперативной памяти записана последовательность Уц =Тл Х, "Т а Ьц чНа пятом - седьмом этапах вычисляется обратное преобразование Уц=Т ,У, которое выполняется в обратном порядке относительно прямого преобразования Т а, т.ена пятом этапе вычисляется М обратных преобразований Рейдера Т от последовательнослтей У, , ,:=О, И, считываемых из блока 3 оперативной памяти по адресам 1 И, 3 И+1, 1 И+2, , 1 М+И. При этом каждое обратное преобразование Рейдера Т выполняется такимцже образом, как и прямое, за исключением того, что коэффициенты циклического сдвига становятся равными И-г, так как 2 =- 2 (шой Р ).Результаты преобразований 2ц,4л=Тц Узаписываются в буферный1блок 15 оперативной памяти, с помощью которого во время вычисления- следующего преобразования Т производится умножение последовательности 2 ц, на соответствующие весо - Рвые коэффициенты с- , Так как Ыц:-с (шов Р ), то из блока 20 памяти весовых коэффициентов в блок 16 умножения по модулю целого числа подаются числа из того же множестваккоэффициентов с. ,1=О, И/2-1, которые использовались в прямом преобразовании Т. При этом только регистр 18 адреса этапа меняет адресацию вызова с К-го адреса на И /2-К с учетом2знака т,е если М -ркИ /2, тоца- в , (шос 1 Р,. ) и, если И -рМ /2,р ц-ел 2ц-Р ц/ц - ато с =д. (той Р ). Результаты- /умножения Ы 2 .(1) записываются в блок 3 оперативной памяти по тем же адресам, по которым происходило считывание У (д), На этом заканчиваются пятьй и шестой этапы вычислений.На последнем - седьмом этапе выполняется вычисление преобразований"Рейдера Т последовательностей 2 (1.), 1,1=0,И, считываемых из блока 3 оперативной памяти по адресам8 1297073 формула изобретения Составитель Ю. Ланцов Редактор Т. Парфенова Техред Л.Сердюкова Корректор Л, ПилипенкоЗаказ 783/53 Тираж 673 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская набей д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 преобразований У . =Т Е . записывай, ц оются в блок 3 оперативной памяти потем же адресам, по которым происходило считывание. Таким образом, послеэтой части вычислений в блоке 3 оперативной памяти по адресам О, М -)содержится результат циклическойсверткий,%сХ - эквивалентно Х шой БПредлагаемое устройство можетвычислять циклическую корреляциюНй с,У(1 с)Х(1)Ь(1 с+3 )) (12)те ОВ этом случае поэлементное умножениепроизводится для пар чисел Х и Й.;Яс адресами соответственно д и 20 -,где д=1 р М -1 (адрес первой пары чисел Х и Й не меняется). Это осуОществляется на четвертом этапе вычислений инверсией адресов чисел Нрегистром 18 адреса этапа и не тре- .бует дополнительных операционныхзатрат. Устройство для вычисления свертки, содержащее первый и второй анало 30 го-цифровые преобразователи, выходы которых объединены и подключены к информационному входу первого блока памяти, выход которого подключен к первому входу блока умножения по мо дулю целого числа и первому информационному входу циклического сдвигового регистра, выход которого подключен к входам первого и второго накапливающих сумматоров, выходы которых40 объединены и подключены к информационному входу второго блока памяти, информационный выход которого подклю" чен к информационному входу блока буферной памяти, информационный вы 45 ход которого подключен к первому входу блока умножения по модулю целогочисла и информационному входу второгоблока памяти, информационный выходкоторого подключен к второму информационному входу циклического сдвигового регистра, выходы переноса первогои второго накапливающих сумматоровподключены к входам соответственнопервого и второго элементов НЕ, выходы которых подключены к входам младших разрядов соответственно первогои второго накапливающих сумматоров,выход регистра адреса подключен к адресному входу второго блока памяти иадресному входу блока памяти коэффициентов, выход которого подключен кинформационному входу счетчика сдвигов, информационный выход которогоподключен к входу управления сдвигомциклического сдвигового регистра,выход умножителя по модулю целогочисла подключен к информационномувходу буферного блока памяти, информационный выход которого подключенк информационному входу первого блока памяти, а входы первого и второгоаналого-цифровых преобразователейявляются соответственно первым ивторым информационнымн входами уст- .ройства, отличающеесятем, что, с целью повышения быстродействия, в него введены блок памятиконстанты, дешифратор и регистр ареса этапа, первый, второй и третийинформационные выходы которого подключены соответственно к адресномувходу блока памяти константы, первому адресному входу первого блока памяти и входу дешифратора, выход ко- .торого подключен к второму адресномувходу первого блока памяти, а выходблока памяти константы подключен квторому входу блока умножения по модулю целого числа,