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

 

Изобретение относится к вычислительной технике, предназначено для вычисления свертки или корреляций двух цифровьпс последовательностей и может быть использовано в системах цифровой обработки сигналов и изображений. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что устройство для цифровой фильтрации содержит аналого-цифровые преобразователи 1 и 2, блок памяти 3, циклический регистр сдвига 4, состоящий из сдвигового регистра 5 и элемента НЕ 6, счетчик сдвигов 7, блок памяти коэффициентов 8, накапливающие сумматоры 9 и 10, элементы НЕ 11 и 2, оперативную память 13, состоящую из блока 14 памяти и буферного блока 15 памяти, блок 16 умножения по модулю целого числа, регистр 17 адреса, регистр 18 адреса этапа, дешифратор 19 и блок 20 памяти константы. 1 ил. (Л го со t

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„, 1297073 А1 ц 4 G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ /

Н ASTOPCHOMY С8ИДЕТЕЛЬСТВУ (21) 3965067/24-24 (22) 15.10.85 (46) 15.03.87. Бюл. 9 10 (71) Одесский политехнический институт (72) В.А. Власенко и Ю.М. Лалла (53) 681.32(088.8) (56) Авторское свидетельство СССР

М 800995, кл. G 06 F 15/332, 1981.

Авторское свидетельство СССР

ll - 744601, кл. G 06 F 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СВЕРТКИ (57) Изобретение относится к вычислительной технике, предназначено для вычисления свертки или корреляции двух цифровых последовательностей и может быть использовано в

\ системах цифровой обработки сигналов и изображений. Цель изобретения— повышение быстродействия. Поставленная цель достигается за счет того, что устройство для цифровой фильтрации содержит аналого-цифровые преобразователи 1 и 2, блок памяти 3, циклический регистр сдвига 4, состоящий из сдвигового регистра 5 и элемента

НЕ 6, счетчик сдвигов 7, блок памяти коэффициентов 8, накапливающие сумматоры 9 и 10, элементы НЕ ll и 2, оперативную память 13, состоящую из блока 14 памяти и буферного блока

15 памяти, блок 16 умножения по модулю целого числа, регистр 17 адреса, регистр 18 адреса этапа, дешифратор

19 и блок 20 памяти константы. 1 ил.

1 1297073

Изобретение относится к вычислительной технике, предназначено для вычисления свертки или.корреляции двух цифровых последовательностей и может быть использовано в системах 5 цифровой обработки сигналов и изображений.

Цель изобретения — повышение быстродействия устройства.

На чертеже изображена структурная схема устройства (пример конкретного выполнения для .случая ИИ ).

Устройство вычисляет свертку двух последовательностей с помощью числового преобразования вида

Y,-T (T„h„"T Х„); M-N, (1) где

Т„-П (R 91„.; ) (I .,® Т ® Т.„.-; ); го

Т„ -М и (1 „,e Т„ЕТ„.; )(R „;.,@

1с1

®I„i- ): где ф — определяет левое кронекеровское произведение матриц, т.е. АЭВ=j АЬ,, ;

Т„ и T - соответственно прямое и

I обратное теоретико-числовое преобразование Рейдера х„ ч "{mod F }{t, -2 " (mod F >, - диагональные матрицы весоNi вых коэффициентов вида

RÄ %diag(I К .... К;,, ..., 35

К„;, diag(0, И, 2 Б

tt-1 (1) 11 ).

Аналогично выражению (4) определяются

° 3 матрицы R . .с учетом замены показатей лей степеней на отрицательные;

В матрице К „ использована симм 45 волическая запись j вместо, где числО <Ф. берется равным a=g, N, =(Р -1)/N"; g — первообразный корень (т.е. g(F - 1).=1 шой Р, и ф! mod F 50

t при любом кфР -1). Кроме того, чтобы

1 в разложении (2) матрицы Т и Т„ соответствовали преобразованию Рейдера (3), необходимо выбрать первообразный корень g, удовлетворяющий условию

g «2(mod F ) (5) Таким образом, в случае вычислений согласно выражению (2) возможно увеличение размерностей обрабатываемых последовательностей с N =N=

t+y

=2 в устройстве прототипе до

N =M=N, где n=(log (F -1)) ((х)—

М ак н ближайшее целое число меньше х), при этом за счет того, что в выражении (2) матрицы Т и Т являются преобч м разованиями Рейдера (3), которые вычисляются без умножений, число умножений-уменьшается с W =1+3 2

t ч (в случае сохранения структуры процессора) до М„ =1+3(п-1). Например, в случае F =257 имеем W„=1+3 2 =25;

W =1+3(2-1)=4, отсюда, W„/W„=6,25; при Р„=65537, W„/W 49/7=7.

Для случая M=N

Т (Т ®I )R (1 ЯТ);

Т ", -(1„@Т„ )R ",(ò„ а 1„)

В этом случае при к-3, F =257 имеем 2 с

N=l6, N =256, d.==g. Для удовлетворения условия (5) g выбирается равным

g=27 отсюда d-=27.

При t 4, Р 65537 имеем N=32, N =1024, d=g, тогда, g 8053, отсюда

< 41054.

Устройство для вычисления свертки содержит аналого-цифровые преобразователи 1 и 2, блок 3 оперативной) памяти, циклический сдвиговый регистр 4, состоящий иэ сдвигового регистра 5 и элемента НЕ 6, включенного в цепь обратной связи, идущей с выхода старшего разряда сдвигового регистра 5 на вход его младшего разряда через элемент б, счетчик сдвигов 7, блок 8 памяти коэффициентов, накапливающие сумматоры 9 и 10, элементы НЕ 11 и 12, оперативную память

13, состоящую из блока 14 (оперативной) памяти и буферного блока 15 (оперативной) памяти, блок умножения

16 по модулю целого числа, регистр

17 адреса, регистр 18 адреса этапа, дешифратор 19 (двоичной инверсии адреса), блок 20 памяти (весовых) коэффициентов.

Устройство работает следующим образом.

Аналого-цифровые преобразователи

1 и 2 преобразуют аналоговые сигналы

+ в числовой код разрядностью 2 +1 бит, которые запоминаются в блоке 3 oneа ративной памяти. Числовые последова1297073 4 тельности записываются в блок 3 оперативной памяти в последовательном порядке, занимая соответственно ячейки памяти с адресами для сигнала

X(n) с 0 по N -1 и для сигнала h(n)

2 с N по 2N -1. С учетом порядка за 2 9 писи сигналов X(n) и h(n) в устройстве сначала вычисляется теоретикочисловое преобразование X(k), затем

H(k) . f0

На первом этапе вычислений проис ходит вычисление преобразований Рейдера Т от соответствующих блоков входных данных. Каждое преобразование Т вычисляется по быстрому алго- 15 и ритму с прореживаннем по времени.

Алгоритм с прореживанием по времени требует перестановки адресов входных данных по закону двоичной инверсии.

Перестановка данных на входе позволя-20 ет исключить данную операцию иэ процесса вычислений введением дешифратора 19 двоичной инверсии адреса.

При этом преобразование N чисел производится за log N итераций, в каждой25 иэ которых вычисляется N/2 величин вида

А„+2 Bk

А -2 В1с (7) к

Для вычисления первого преобразо- 30 вания Т из блока 3 оперативной паИ мяти считывается последовательность

Х,ii) i=0, I -1 с адресами отсчетов

О, М, 2N,..., (N- l )N. Дешифратор 19 двоичной инверсии адреса определяет 35 считывание необходимых пар чисел А к. и В„ с учетом перестановки чисел

Х,(i) по закону двоичной инверсии, Пары чисел А и В„ из блока 3 оперативной памяти через циклический сдвиговый регистр 4 передаются в накапливающие сумматоры 9 и 10. Причем, в соответствии с выражением (7), первое число А передается без сдвига, а второе число В сдвигается в циклическом сдвиговом регистре 4 на т разрядов влево, что эквивалентно умножению на 2 . Сумматоры 9 и 10 осуществляют соответственно операции сложения и вычитания. Справедливость правил арифметики по модулю F обесс печивается с помощью элемента НЕ 6, обеспечивающего цикличность сдвигов

Х при умножении на 2, и элементов НЕ

)1 и 12, предотвращающих возникнове- ние режима генерации при наличии единиц во всех разрядах. С выхода сумматоров 9 и 10 результаты записываются в блок 13 памяти. Блок 8 памяти коэффициентов определяет необходимое число сдвигов r, требуемых для вычисления преобразования Т по быстн рому алгоритму, и представляет собой конечный автомат, определяющий к число r согласно правилу r=(2 . i) в

imod N, где k — номер этапа вычислений; i — номер итерации на k-м этапе, э=О, М72-1. Управление сдвигами в циклическом сдвиговом регистре 4 осуществляется счетчиком сдвигов 7, в который предварительно записывается нужное число сдвигов из блока 8 памяти коэффициентов. В блок 14 оперативной памяти записываются и считываются результаты промежуточных вычислений (7). Промежуточные результаты, записанные в него, снова подаются на вход циклического сдвигового регистра 4. Операция (7) повторяется N/2-log N pan до

2 полного завершения преобразования

Тц. Окончательный результат преобразования Т„Х поступает в блок

15 буферной памяти емкостью в N x т (2 +1) разрядных слов. При вычислении второго преобразования Т с н блока 3 оперативной памяти считывается последовательность чисел Х (1), i=0 N-1 с адресами отсчетов 1, 1+N

1+2М, ..., 1+(И-1)Н. При этом процесс вычисления преобразования Т Х н Н,1 полностью аналогичен предыдущему.

Одновременно, пока блок 14 оперативной памяти участвует в следующем преобразовании, буферный блок 15 оперативной памяти осуществляет обмен с блоком 16 умножения по модулю целого числа, в котором происходит умножение результатов первого преобразования на соответствующие весоР вые коэффициенты с, определяемые из диагональной матрицы R а в выражении (6) ° Последовательность весовых коэффициентов 8 записана в блоке

20 памяти весовых коэффициентов ем- костью N /2x(2 +1) разрядных слов.

2.

Порядок подачи коэффициентов в блок 16 умножения определяется регистром 18 адреса этапа следующим образом. После каждого определения

Х4„=Т Х„.„блок из N отсчетов результата преобразования необходимо умножить на соответствующий блок е весовых коэффициентов . В этом случае величина показателя Р, а, следовательно, и соответствующий адрес

1297073 его хранения, равны p=ij т.е. для л последовательности Х„(i) i, j=O,N-1 имеем рай(0,j,r,..., (N-1) j $.

Результат умножения с блока 15 буферной оперативной памяти записы- 5 вается в блок 3 оперативной памяти по тем же адресам, по которым происходило считывание последовательности ,Х ь(1) °

Аналогично рассмотренному происхо- 10 дит вычисление преобразований Т„ последовательностей Х .(i), i,j=O, N-1, считываемых с блока 3 оперативной памяти по адресам j, j+N, j+2N, j+(N-1)И, умножение результа-ов пре-. образований Т Х, Х, на соответстN,J p вующие коэффициенты d. и запись результатов обратно в блок 3 оперативной памяти по тем же адресам. Таким образом, первый этап вычислений завершается вычислением Ы раз преобразований Рейдера Т, второй этап умножением результатов преобразоваР ний на весовые коэффициенты d. и записью промежуточных результатов в блок 3 оперативной памяти.

На третьем этапе вычисляются N преобразований Рейдера Т от промежул N точных данных Х„2, записанных в блоке 3 оперативной памяти после первых двух этапов вычислений. Считывание из блока 3 оперативной памяти послел довательностей X (i) i j O N-1 на третьем этапе выйолняется по адресам

jN, jN+I jN+2, ..., jN+N-1. После 35 вычисления каждого преобразования

T„X» данные с буферного блока 15 ойеративной памяти записываются обратно в блок 3 оперативной памяти по тем же адресам.

После данного этапа заканчивается вычисление преобразования Т 2 Х 2, N N

Аналогичным образом выполняется вы2 числение преобразования Т 2hN с учетом того что адресация данных после- 5

2 довательности ЬИ сдвинута íà N относительно адресов данных последовательности X

После вычисления преобразований

Х„2=Т„2Х„2и л„2=T„2h 2 на четвертом

50 (Ч этапе осуществляется поэлементное ! умножение последовательностей Х„2 и л л л

Н„2 . При этом пары чисел Х „и Н„ соответственно с адресами i и i+N

i=O, N2-1 поступают иэ блока 3 опе5„ ративной памяти на блок Iб умножения по модулю целого числа. Резульл тат умножения Х.: через буферный блок 1

15 оперативной памяти записывается обратно в блок 3 оперативной памяти по адресу i Таким образом, после данного этапа вычислений по адресам

О, N -1 в блоке 3 оперативной памяти записана последовательность Y ц2

=-Т„,2Х Т 2hÄ2, ц2

На пятом — седьмом этапах вычисляется обратное преобразование Y ц

-!

=T,,Y„2, которое выполняется в .обратном порядке относительно прямого преобразования Т 2, т.е ° на пятом этапе вычисляется N обратных преобразований Рейдера Т„ от последовательносл тей Y, (i), i, j:=О, N-1, считываемых из блока 3 оперативной памяти по адресам jN, jN+1, jN+?, ..., jN+N-1.

При этом каждое обратное преобразование Рейдера Т выполняется таким

М же образом, как и прямое, за исключением того, что коэффициенты циклического сдвига становятся равными

N-r, так как 2 =- 2 (mod F ).

Результаты преобразований Z

N,4 л

=T Y„ „. записываются в буферный

1 блок 15 оперативной памяти, с помощью которого во время вычисления ! следующего преобразования Т проN изводится умножение последовательности Zö, на соответствующие весо— P -P вые коэффициенты a . Так как ц2*!

: — d. (mod Р ), то из блока 20 памяти весовых коэффициентов в блок 16 умножения по модулю целого числа подаются числа из того же множества к коэффициентов с -,k=O Н /2-1, которые использовались в прямом преобразовании Т„2. При этом только регистр

18 адреса этапа меняет адресацию вы2 зона с К-го адреса íà N /2-К с учетом

2 знака т,е., если N --ркМ /2, то, ц2, (mod Р, ) и, если N -p>N /2, р N -Е

К /2 — Р то d =д. (mod Р ) . Результаты

- / т умножения d. Z .(i) записываются в

1 блок 3 оперативной памяти по тем же адресам, по которым происходило считывание Y (i). Ha этом заканчиваются

J пять!й и шестой этапы вычислений.

На последнем — седьмом этапе выполняется вычисление преобразований

"!

Рейдера Т„последовательностей

Z„ (i.), i,j=0,N-1, считываемых из блока 3 оперативной памяти по адресам !

j „j+N, j+2N...., j+N-1. Результаты

1297073

Формула изобретения

Составитель 10. Ланцов

Редактор Т. Парфенова Техред Л.Сердюкова Корректор Л. Пилипенко

Заказ 783/53 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская набей д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 преобразований Y . =T K . записывай() )(о,й ются в блок 3 оперативной памяти по тем же адресам, по котс)рым происходило считйвание. Таким образом, после этой части вычислений в блоке 3 оперативной памяти по адресам О, N -I содержится результат циклической свертки (4 -1 т(й)= X(i)h(c k-i>„a), k=O, N -I (=О {l l)

<Х>„2 — эквивалентно Х mod N

Предлагаемое устройство может вычислять циклическую корреляцию

И -1 с, Y(k) X(i)h(k+1 » ) (12)

I * O

В этом случае поэлементное умножение производится для пар чисел Х и Й.;

2 ° с адресами соответственно i и 2N -x где i=1, N -l. (адрес первой пары чисел Х и Й не меняется). Это осу0 ществляется на четвертом этапе вычислений инверсией адресов чисел 11„ регистром 18 адреса этапа и не тре- . бует дополнительных операционных затрат.

Устройство для вычисления свертки, содержащее первый и второй анало30 го-цифровые преобразователи, выходы которых объединены и подключены к информационному входу первого блока памяти, выход которого подключен к первому входу блока умножения по модулю целого числа и первому информационному входу циклического сдвигового регистра, выход которого подключен к входам первого и второго накапливающих сумматоров, выходы которых

„40 объединены и подключены к информационному входу второго блока памяти, информационный выход которого подключен к информационному входу блока буферной памяти, информационный вы45 ход которого подключен к первому входу блока умножения по модулю целого числа и информационному входу второго блока памяти, информационный выход которого подключен к второму информационному входу циклического сдвигового регистра, выходы переноса первого и второго накапливающих сумматоров подключены к входам соответственно первого и второго элементов НЕ, выходы которых подключены к входам младших разрядов соответственно первого и второго накапливающих сумматоров, выход регистра адреса подключен к адресному входу второго блока памяти и адресному входу блока памяти коэффициентов, выход которого подключен к информационному входу счетчика сдвигов, информационный выход которого подключен к входу управления сдвигом циклического сдвигового регистра, выход умножителя по модулю целого числа подключен к информационному входу буферного блока памяти, информационный выход которого подключен к информационному входу первого блока памяти, а входы первого и второго аналого-цифровых преобразователей являются соответственно первым и вторым информационными входами уст- . ройства, отличающееся тем, что, с целью повышения быстродействия, в него введены блок памяти константы, дешифратор и регистр адреса этапа, первый, второй и третий информационные выходы которого подключены соответственно к адресному входу блока памяти константы, первому адресному входу первого блока памяти и входу дешифратора, выход ко- . торого подключен к второму адресному входу первого блока памяти, а выход блока памяти константы подключен к второму входу блока умножения по модулю целого числа.