Устройство для вычисления свертки Советский патент 1987 года по МПК G06F17/14 

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

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

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

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

Y Т и -IM

(Т Ь„гт Х„);

(1)

где

т.-п (%®V- )(I..);

)( + i®

М П (I „.i®T,

®IVM где

)

ч.

® - определяет левое кронеке- ровское произведение матриц, т. е. А®В { ; cooTBeTCTBeliHo прямое и обратное теоретико-числовое преобразование Рейдера

,j 2 (modF);i,j 67lM; 3) Т„ s {modP }Jt: 2 (modF) ,

(I,®T,)R-;a( I)

В этом случае при , F 257 имеем 25 , N 256у . Для удовлетвореNI

- диагональные матрицы весовых коэффициентов вида К

(I i.i ,

к N-1 . Nf-l

.i-r

К..,

(4)

.1 -diag(0, N , 2 N , ...,

(N - -1) ).

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

«

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

использована сим. J

В матрице К н

N

волическая запись j вместо , число d. берется равным

(F g - первообразный корень (т.е. g(F -D sl mod F и mod F

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

g ft-- ) 2(modF,). (5)

НИН условия (5) g выбирается равным , отсюда оС 27.

При t«4, F 65537 имеем , N 1024, , тогда, , отсюда

30 i 41054.

Устройство для вычисления свертки содержит аналого-цифровые преобразователи Г и 2, блок 3 оперативной) памяти, циклический сдвиговый

35 регистр 4, состоящий из сдвигового регистра 5 и элемента НЕ 6, включенного в цепь обратной связи, идущей с выхода старшего разряда сдвигового регистра 5 на вход его младшего раз40 ряда через элемент 6, счетчик сдвигов 7, блок 8 памяти коэффициентов, накапливающие сумматоры 9 и 10, эле-, менты НЕ 11 и 12, оперативную память 13, состоящую из блока Г4 (оператив45 ной) памяти и буферного блока 15 где (оперативной) памяти, блок умножения NO 16 по модулю целого числа, регистр 17 адреса, регистр 18 адреса этапа, дешифратор 19 (двоичной инверсии ад50 реса), блок 20 памяти (весовых) коэффициентов .

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

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

55 1 и 2 преобразуют аналоговые сигналы в числовой код разрядностью бит, которые запоминаются в блоке 3 оперативной памяти. Числовые последоваТаким образом, в случае вычислений согласно выражению (2) возможно увеличение размерностей обрабатываемых последовательностей с N

N

2

N

.

в устройстве прототипе до где (F -1)(х Mixwc t

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

имеем W5 l+3 2 25;

в случае

0

(, отсюда, W,,25; при b 65537, W,,. Для случая

T..(T,®I«)R,.(I,®T,); j

ч.

(I,®T,)R-;a( I)

В этом случае при , F 257 имеем 25 , N 256у . Для удовлетворетельности записываются в блок 3 оперативной памяти в последовательном порядке, занимая соответственно ячейки памяти с адресами для сигнала Х(п) с О по N -1 и для сигнала h(n) 5 с N по 2N -1. С учетом порядка записи сигналов Х(п) и h(n) в устройстве сначала вычисляется теоретико- числовое преобразование X(k), затем H(k).W

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

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

ВЙ.ЮТСЯ и считываются результаты про межуточных вычислений (7). Промежуточные результаты, записанные в неПерестановка данных на входе позволя-20 го, снова подаются на вход цикличесет исключить данную операцию из процесса вычислений введением дешифратора 19 двоичной инверсии адреса. При этом преобразование N чисел прокого сдвигового регистра 4. Операц (7) повторяется N/2-log N раз до полного завершения преобразования Т. Окончательный результат преоб-

изводится за итераций, в каждой разования поступает в блок из которых вычисляется N/2 величин 15 буферной памяти емкостью в Nх

/ о

вида

(2 +1) разрядных слов. При вычислении второго преобразования Т с блока 3 оперативной памяти считыва

А,+2 Bk

-.- (modF,)

Для вычисления первого преобразо- 30 ется последовательность чисел Х (i),.

, N-1 с адресами отсчетов 1, 1+N, 1+2N, ..., 1+(N-1)N. При этом процесс вычисления преобразования Т X

вания Т из блока 3 оперативной пап

мяти считывается последовательность Xj,(i), , К-1 с адресами отсчетов О, N, 2N,...,(N-ON. Депшфратор 19 двоичной инверсии адреса определяет считывание необходимых пар чисел А и В с учетом перестановки чисел Xjj(i) по закону двоичной инверсии. Пары чисел А и В из блока 3 оперативной памяти через циклический сдвиговый регистр 4 передаются в накапливающие сумматоры 9 и 10. Причем, в соответствии с выражением (7), первое число А передается без сдвига, а второе число В сдвигается в циклическом сдвиговом регистре 4 на г разрядов влево, что эквивалентно умножению на 2 . Сумматоры 9 и 10 осуществляют соответственно операции сложения и вычитания. Справедливость правил арифметики по модулю F. обеспечивается с помощью элемента НЕ 6, обеспечивающего цикличность сдвигов при умножении на 2, и элементов НЕ

40

11 и 12, предотвращающих возникнове- ние режима генерации при наличии единиц во всех разрядах. С выхода сумматоров 9 и 10 результаты записываютN N,f

полностью аналогичен предащущему.

35 Одновременно, пока блок 14 оперативной памяти участвует в следующем преобразовании, буферный блок 15 оперативной памяти осуществляет обмен с блоком 16 умножения по модулю целого числа, в котором происходит умножение результатов первого преобразования на соответствующие весовые коэффициенты ci. , определяемые из диагональной матрицы в выр.а жении (6). Последовательность весовых коэффициентов Ы записана в блоке 20 памяти весовых коэффициентов ем- i костью NV2«() разрядных слов. Порядок подачи коэффициентов d в блок 16 умножения определяется регистром 1В адреса этапа следующим образом. После каждого определения блок из N отсчетов результата преобразования необходимо умножить на соответствующий блок весовых коэффициентов ct . В этом случае величина показателя Р, а,следовательно , и соответствующий адрес

50

ся в блок 13 памяти. Блок 8 памяти коэффициентов- определяет необходимое число сдвигов г, требуемых для вычисления преобразования Т по быстрому алгоритму, и представляет собой конечный автомат, определяющий число г согласно правилу г(2. i) -imod N, где k - номер этапа вычислений; i - номер итерации на k-м этапе, , N/2-1. Управление сдвигами в циклическом сдвиговом регистре 4 осуществляется счетчиком сдвигов 7, в который предварительно записывается нужное число сдвигов

ВЙ.ЮТСЯ и считываются результаты промежуточных вычислений (7). Промежуточные результаты, записанные в некого сдвигового регистра 4. Операция (7) повторяется N/2-log N раз до полного завершения преобразования Т. Окончательный результат преоб-

разования поступает в блок 15 буферной памяти емкостью в Nх

/ о

(2 +1) разрядных слов. При вычислении второго преобразования Т с блока 3 оперативной памяти считываi 0, N-1 с адресами отсчетов 1, 1+N, 1+2N, ..., 1+(N-1)N. При этом процесс вычисления преобразования Т X

0

N N,f

полностью аналогичен предащущему.

5 Одновременно, пока блок 14 оперативной памяти участвует в следующем преобразовании, буферный блок 15 оперативной памяти осуществляет обмен с блоком 16 умножения по модулю целого числа, в котором происходит умножение результатов первого преобразования на соответствующие весовые коэффициенты ci. , определяемые из диагональной матрицы в выр.а жении (6). Последовательность весовых коэффициентов Ы записана в блоке 20 памяти весовых коэффициентов ем- i костью NV2«() разрядных слов. Порядок подачи коэффициентов d в блок 16 умножения определяется регистром 1В адреса этапа следующим образом. После каждого определения блок из N отсчетов результата преобразования необходимо умножить на соответствующий блок весовых коэффициентов ct . В этом случае величина показателя Р, а,следовательно , и соответствующий адрес

0

его хранения, равны , т.е. для

последовательности X;-(i), i,,N-l имеем pelO,j ,r , . . ., (N-1) j J.

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

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

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

JN, jN+l, jN+2jN+N-1. После

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

После данного этапа заканчивается вычисление преобразования Т 2 X а. Аналогичным образом выполняется вы

числение преобразования Т ЬК том того,

с уче

;, ЧТО адресация данных после- довательности hN сдвинута на N относительно адресов данных последовательности X ..о

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

Х, на четвертом

,

этапе осуществляется поэлементное

I -,л

умножение последовательностей Х и . При этом пары чисел Х, и Н соответственно с адресами i и i+N , , поступают из блока 3 оперативной памяти на блок 16 умножения по модулю целого числа. Результат умножения через буферный бло

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

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

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

J

Т гYjj) , которое выполняется в .обратном порядке относительно прямого преобразования , т.е. на пятом этапе вычисляется N обратных преобразований Рейдера Т от последовательнос

тей Y. (i), i,, N-15 считываемых из блока 3 оперативной памяти по адресам JN, JN+1, JN+2, ..., JN+N-1.

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

j. j,3j 2 Е2 (mod F ) .

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

-1 л

Т Y N KiJ

N,J

записываются в буферный блок 15 оперативной памяти, с помощью которого во время вычисления следующего преобразования 1 производится умножение последователь K,J

ности Zi, i на соответствующие весо, -р

Так как

dL-

вые .коэффициенты dг ci (njod F. ) J то из блока 20 памяти весовых коэффициентов в блок 16 умножения по модулю целого числа подаются числа из того же множества коэффициентов oL ,, , которые использовались в прямом преобразовании Т,5. При этом только регистр 18 адреса этапа меняет адресацию вызова с К-го адреса на N /2-К с учетом знака т.е., если N /2, то

(,od F,. ) и, если N%-7,NV2,

fji-P №/1- р

то ( oL(mod F). Результаты

умножения d- Z .(i) записываются в блок 3 оперативной памяти по тем же адресам, по которым происходило счи

тывание Y.(i). На этом заканчиваются пятый и шестой этапы вычислений.

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

Zj(i), i,,N-l, считываемых из блока 3 оперативной памяти по адресам За J+N, J+2N, .,., J+N-1. Результаты

преобразований Y . Т Z .записываются в блок 3 оперативной памяти по тем же адресам, по котсфым происходило считывание. Таким образом, после этой части вычислений в блоке 3 опе- ративной памяти по адресам О, N содержится результат циклической свертки

М -1

Y(k)

но

X(i)h(), , N -l

(П)

.1

- эквивалентно X mod N

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

Y(k)|Z X(i)h( ) (12) В этом случае поэлементное умножение производится для пар чисел Х и Н с адресами соответственно i и 2N -i, где , N -I (адрес первой пары чисел X и Н не меняется). Это осуществляется на четвертом этапе вычислений инверсией адресов чисел Н регистром 18 адреса этапа и не требует дополнительных операционных затрат.

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

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

буферной памяти, информационный вы

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

.5

fO

5

20

25

30

З ,0

45

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

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