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

 

Изобретение относится к вычислительной технике, предназначено для вычисления дискретного преобразования Фурье (ДПФ) и процедуры цифровой фильтрации и может быть использовано в системах цифровой обработки сигналов. Цель изобретения - упрощение устройства. В состав устройства входят входной умножитель 4, блоки постоянной памяти 5,6,20, регистры 7.I, 8.I (I=1,N

N - размер преобразования), 12.I, 14.I мультиплексоры 3, 9.I, 13.I, умножители 10.I, сумматоры 11.I, генератор тактовых импульсов 15, счетчик 16, дешифратор 17, элементы ИЛИ 18, И 25, ВЫХОДНОЙ УМНОЖИТЕЛЬ 21. ИМЕЮТСЯ ТАКЖЕ ИНФОРМАЦИОННЫЕ ВХОДЫ 1,2, ВЫХОД СВЕРТКИ 22, ВЫХОД ДПФ 23, ВХОДЫ ЗАДАНИЯ РЕЖИМА 19, 24. 1 ИЛ.

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

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

РЕСПУБЛИК

„„Я0„„1573459 A1 (51)5 G 06 F 15/332

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

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

IlO ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4400976/24 24 (22) 15.02.88 (46) 23.06.90. Бюл. № 23 (71) Житомирский филиал Киевского политехнического института им. 50-летия

Великой -Октябрьской социалистической революции (72) 10.Ñ.Êàíåâñêèé и Д.В.Корчев (53) 681.32 (088.8) (56) Уильямс. Ф. Цифровая интегральная микросхема для фильтрации видеосигналов. — Электроника, 1983, ¹ 20, . с.74-79, рис.4.

Авторское свидетельство СССР № 1196894, кл. G 06 F 15/332, 1984.

2 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ И

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

Фурье (ДПФ) и процедуры цифровой фильтрации и может быть использовано в системах цифровой обработки сигналов. Цель изобретения — упрощение устройства. В состав устройства входят входной умножитель 4, блоки постоянной памяти 5,6,20, регистры

7.i, 8.i (i-1,N; N -размер преобразования), 12,i, 14.i, мультиплексоры

1573459

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

<1«ильтрации и может быть использовано в системах цифровой обработки сигна- 15

Аов.

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

На чертеже изображена структурная

Схема устройства. 20

Устройство содержит первый информационный вход 1, второй информационный вход 2 (входной), мультиплексор

3, входной умножитель 4=, (входной) блок 5 постоянной памяти, блок 6 по- 25 стоянной памяти весовых коэффициентов, регистры 7.i (i=1 М) весовых коэффициентов, регистры 8,i весовых

«коэффициентов, мультиплексоры 9.i весовых коэффициентов, умножители 10.1, 30

Сумматоры 11.i, регистры 12.i, мультиплексоры 13.i передачи данных, Двухвходовые регистры 14., генератор

15 тактовых импульсов, счетчик 16, дешифратор 17, элемент ИЛИ 18, вход

19 задания режима, блок 20 постоян«<ой памяти, выходной умножитель 21, выход 22 свертки, выход 23 ДПФ, вход

24 задания режима, элемент И 25.

Рассмотрим работу устройства в режиме вычисления ДПФ, которое определяется выражением

F, = С„Т„ С„Х„, (2) где Т„(0z

" < 2«

-(й-«1

2<1 (N-2)

W2N

W2N

2 Ог

W2N 2 <<

8((° ° °,W „ )°.

2<<»» 2N

Для описания примера работы устройства примем И=4. В этом случае выражение (2) имеет вид

Е«< = Е «< ХН о -< -4 -9

WSW8 в Ws о -< -4 8 8 в 8 а < о

8 8 8 8

-9 -а -1 О.

"В "8 "8 8

«

1 в о

1

М8

F(0) Х(0)

Х(1)

Х(2)

Х(3) F(1) 4

F(2)

F(3) 3,9. .<,13.1 умножители 10,i, сумматоры 11.i генератор тактовых импульсов .15, счетчик 16, дешифратор 17, элементы ИЛИ 18, И 25, выходной умножиБудем полагать, что сумматоры

11. i осуществляют операцию суммирования операндов при нижнем уровне на управляющем входе и операцию пересылки операнда с первого входа на выход при высоком уровне на управляющем входе. Регистры 14.i осуществлятель 21. Имеются также информационные входы 1,2, выход свертки 22, выход

ДПФ 23, входы задания режима 19,24.

1 ил. где Х (— исходный комплексный вектор размерности N с элементами

X(v); результирующий комплексный вектор размерности N с элементами F(k), Š— матрица весовых коэффициен« тов размерности N N с элементами W„=exp(-j 2» nk/N), 1= 4:.1 .

Выражение (1) можно записать в следующем виде: теплицева матрица вида (N-«1 (»<-21 -о

2«("«2<< 2«

С<,, — диагональная матрица

I ют прием информации с первого входа при нижнем уровне на управляющем входе и с второго входа при высоком уровне на управляющем входе. При нижнем уровне на входе 19 устройства производится вычисление ДПФ, а при верхнем вычисляется свертка. ИнфорВторой такт.

° С первого выхода блока 6 поступа1-4 еэ значение Ы,, с второго выхода

W . В регистрах 7.1-7 ° 4 значения

У М8 И 1 1 8 cooTBe ствеHHG.

В регистре 8.1 значение Wб . С выхо-1 да блока 5 поступает значение Ws

На входе 2 устройства значение Х(1).

На выходе мультиплексора 3 значение

X(1) Ws. На управляющих входах мультиплексоров 9.1-9.4 нижний логический уровень. На выходах мультиплексоров

9.1-9.4 значения Ws, Ws; W1 ; 14 4 соответственно ° На выходах умножителей 10.1-10.4 значения Х(1) 11

x(l) w8, х(1). w ; .х(1) ь соответственно. В регистрах 12.1-12.4 значения Х(0). WS, Х(0) ° V ; Х(0)- М5

20 Х(0) Ws соответственно. На выходах сумматоров 11. 1-11. 4 значения Х(0) W, +

+Х(1) Ws, Х(0) Ws +Х(1) ° И8, Х(0) Ws+

+X(1) ° Ws, X(O) ° Ws +X(1) Ws соответственно.

25 Третий такт.

С первого выхода блока 6 поступает

9 -1 значение Ws с второго выхода — И

В регистрах 7.1-7.4 значения М

-4, 4 9

Ы8, И8 W8 соответственно В регистрах 8.1 и 8.2 значения 418 и 48 — 4 -9 соответственно. На выходе блока 5 значение Ws. На входе 2 устройства

4 значение Х(2). На выходе мультиплексора 3 значение Х(2) W ; На управля4 °

35 ющих входах мультиплексоров 9.1-9.4 нижний логический уровень. На выходах мультиплексоров 9.1-9.4 значения

-4, -1 0 -1

У, И„ ; W ; W соответственно. На выходаь умножителей 10.1-10.4 значе40 ния X(2) ° W8, Х(2). WS, Х(2) Ws, Х(2)"

x Ws соответственно. В регистрах 12.t12. 4 значения Х(0) И +Х(1) К8, X(0) W 8 +

+X(t) W8f; Х(0) И +X(l } Ws, X(0) Ы 9+

+X(1) W s соответственно. В сумматоран з

45 11. 1-11.4 значения X(0) Ws+Õ(1)И8+

+X(2) Ws X(0) W s +Х(1) И +X(2) Ws, х(О) ма +x(1) ws +х(2) ws х(0) ° Ms +

+Х(1) И8 +Х(2) Ms соответственно.

-3 з

Четвертый такт.

С первого выхода блока 6 поступает

-9 значение Ws, с второго выхода — знао чение W . .В регистрах 7.1-7.4 значе-98 -4 — 1 о ния У ; W» W» Ws соответственно.

B регистрах 8.1-8.3 значения W

-4, -9

Ws; Ws соответственно. На выходе

4 блока 5 значение М8, на входе 2 устройства значение Х(3), на выходе мультиплексора 3 значение Х(3). На управляющих выходах мультиплексоров

5 1573459 мация с входа 2 устройства через умножитель 4 и мультиплексор 3 поступает без дополнительных тактировок, хотя для повышения быстродействия за сче т увеличения тактовой частоты целесообразно ее протактировать после мультиплексора 3 или умножителя 4.

Поскольку данная тактировка не наpys!ает принципов работы устройства, мы ее не будем учитывать в дальнейшем описании работы устройства. На входе

24 устройства нижний логический уровень. При наличии нижнего логического уровня на управляющих входах регистров 7.i и 8. они производят прие информации (при наличии синхроимпульса). При верхнем логическом уровне на управляющих входах этих регистров они находятся в режиме хранения информации. Информация во все регистры записывается положительным фронтом синхросигнала. Все мультиплексоры осуществляют передачу информации с первого входа на выход при нижнем уровне на управляющем входе, а с вто.рого входа — при высоком уровне на управляющем входе. Считаем, что в регистры 7 ° 1, 7. 2, 7.3, 7.4 произведена предварительная запись информации

Ws, Ws, Ws, М . Все операнды в регистрах и арифметические операции над ними комплексные.

Первый такт.

На управляющих входах сумматоров

14.i в этом такте присутствует верхний логический уровень. С .первого выхода блока G поступает значение

-1 —.9

Ws, с второго выхода блока 6 — W> с выхода блока 5 постоянной памяти—

И8, на вход 2 устройства — Х(0). С выъода умножителя 4 снимается значение X(0)W, которое через мультиплексор 3 поступает на первые входы умно-жителей 10 ° 1-10.4. На управляющих входах мультиплексоров 9.1-9.4 нижний логический уровень, который поступает с соответствующего выхода счетчика

16. Поэтому на выходах мультиплексоров 9.1-9.4 будут значения W,,W

-4 -9

W, Ws, поступающие на вторые входй соответствующих умножителей 10.11Î.4. На выходах умножителей 10.11 0.4 будут значения Х(0). И =Х(0) У8; х(0) ° У8 ws =х(О) ыб, х(О) ° ws vs =

-Х(0) Ы- ; Х(0). Vs Wg =X(0). Ws .

На выходах сумматоров 11. 1-11 ° 4 о 1 имеются значения Х(0)- Ws, Х(0) ° У

Х(0) W, Х(0) W8 соответственно.

1573459

9.1- 9.4 нижний логический уровень.

На выходах мультиплексоров 9.1-9.4

-9, 4 -1 значения Ы, W ; И, MS соответс!твенно. На выходах умножителей 10.110.4 значения Х(3) И g Х(3)- WS, Х(3)»

< WS, Х(З) W» соответственно. В реги8, 9 страх 12.1-12.4 значения Х(0) 4 +

+Х(1) MS+X(2) WS, X(0) ° WS +Х(1) WS+

+Х(2) Ы, Х(0) Ws +Х(1 ) WS +Х(2) М ь 10

Х(0) И +Х(1) WS +Х(2) Ws соответственно. На выходах сумматоров 11.11,, 1,4 значения X(0) WS+X(1) WS+X(?) W +

+(Х(3) Ma, X(0) W +X(1) Ws +Х(2) WS+

+Х(3) M8S, Х(0) Ws +X(1) Ws+X(2) Ws+

+Х(3) Ms Х(0) WB +Х(1) М8 +Х(2) M>+

+Х(3) Ws соответственно. На управля- . ющие входы регистров 14.1 — 14.4 поступает верхний логический уровень, разрешающий запись информации в них по

Второму входу.

Пятый такт.

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

На управляющих входах мультиплексоров

9.i верхний логический уровень, поэтому весовые коэффициенты на вторые фходы умножителей поступают с регистров 8.i, Последовательность поступле- 30

Ния весовых коэффициентов аналогична описанной ранее. В регистры 7.i осуществляется загрузка весовых коэффипиентов для следующего массива данных в последовательности, приведенной для регистров 8.i при вычислении предыду35 щего массива. В регистрах 14.1-14.4 значения Х(0) M>+X(1) (4 +Х(2) WS+

+Х(3) WS Х(О) Ы8 +Х(1) W, +Х(г) W<+

+Х(3) WS, Х(0) WS +Х(1) MS+X(2) WS+

+Х(3) Wв, X(0) WS +Х(1) И +Х(2) WS+

+Х(3) W,1,, На выходе блока 20 постоянной памяти значение W, которое поступает на второй вход умножителя 21. На первый вход умножителя 21 поступает значение из регистра 14.4, B результате о 9 произведения получаем Х(0) W4+X(1) W„+

+X(2) M4+X(3) W4=F (3) которое посту- 50 пает на выход 23 устройства. На управляющих входах регистров 14. I-14.4 нижний логический уровень °

Шестой такт.

Аналогичен второму такту. Содержимое регистров 14.i сдвигается на один регистр. На выходе регистра 14.4 значение X(0) WS +Х(1) MS+X(2) Ws+X(3) Ws.

На выходе 23 устройства результат умножителя 21 равный X(0) И4 +Х(1) И4+ з .()

Седьмой такт.

Аналогичен третьему такту. В ре-1 гистре 14.4 значение X(0) У .+Х(1) WS+

+Х(2) WS+X(3) MS. На выходе блока 20

I постоянной памяти значение И . На вью ходе 23 устройства значение Х(0) W<+

+Х(1) И +Х(2) И4+Х(3) W =F(1) .

Восьмой такт.

Аналогичен четвертому такту. На выходе блока 20 постоянной памяти о значение Ма. На выходе устройства значени X(0) Ы4 +Х(1) M +X(2) W++

+Х(3) W,=F(0).

Дальнейшая работа устройства в режиме вычисления ДПФ продолжается по описанному ранее алгоритму.

При реализации процедуры цифровой фильтрации устройство должно вычислить выражение вида

К 4

y(k) = > X(k-п)h(n)p р=о где h(n) — коэффициент импульсной характеристики фильтра.

На второй управляющей вход 24 подают верхний логический уровень и в течение N тактов производят загрузку коэффициентов импульсной характеристики фильтра в регистры 7.i и 8.i параллельно.

После этого на управляющий вход

19 подается верхний логический уровень. Входные отсчеты поступают на вход 1 устройства. Результаты свертки снимаются с выхода 22 устройства.

Мультиплексоры 13.i передают информацию с второго входа. Коэффициенты импульсной характеристики предварительно записываются в регистры 7.i u

8.i параллельно. При этом состояние на управляющих входах мультиплексоров 9.i может быть любым. Результаты свертки формируются в регистрах 12.i по мере поступления входных отсчетов.

Их продвижение по систолической линейке обспечивается мультиплексорами i3.i.

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

Устройство для вычисления дискретного преобразования Фурье и свертки, содержащее М (где N — размер преобразования) умножителей, N сумматоров, N регистров первой группы, дешифратор, счетчик и генератор тактовых

1573459

Составитель А. Баранов

Техред M.Õoäàíè÷ Корректор M.Ìàêñèìèøèíåö

Редактор Н.Лазаренко

Заказ 1б43

Тираж 568

Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 импульсов, выход которого подключен к счетному входу счетчика, информационный выход которого подключен к входу дешифратора, выход i-ro (i=1,N) умножителя подключен к первому входу

i-го сумматора, выход j-ro (j=1,N-1) регистра первой группы подключен к первому информационному входу (j+1)го регистра первой группы, а установочный вход счетчика является первым входом задания режима устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения, оно содержит три блока постоянной памяти, вторую, третью и четвертую группы из N регистров каждая, первую и вторую группы из N мультиплексоров, входной умножитель, выходной умножитель, элемент

И, элемент ИЛИ и мультиплексор, выходы j-х регистров второй и третьей групп подключены к информационным входам (j+1)-х регистров соответственно второй и третьей групп, а выходы i-х регистров второй и третьей групп подключены соответственно к первому и второму информационным входам i-ro мультиплексора первой груп.пы, выход которого подключен к первому входу i-го умножителя, второй вход которого подключен к выходу мультиплексора, первый информационный вход которого является первым информационным входом устройства, вторым инфор,мационным входом которого является первый вход входного умножителя, выход которого подключен к,второму информационному входу мультиплексора, выход i-го сумматора подключен к второму информационному входу i-горегистра первой группы и информационному входу i-го регистра четвертой группы, выход которого подключен к первому информационному входу i-го мультиплексора второй группы, а выход j-ro регистра четвертой группы подключен к второму информационному входу (j+1)-ro мультиплексора второй

45 группы, выход 1-ro мультиплексора второй группы подключен к второму входу i-ro сумматора, второй информационный вход первого мультиплексора второй группы является. входом логического нуля устройства, выходом свертки которого является выход N-ro регистра первой группы, выход первого блока постоянной памяти подключен к второму входу входного умножителя, первый и второй выходы второго блока постоянной памяти подключены к информационным входам первых регистров соответственно второй и третьей групп, выход третьего блока постоянной памяти подключен к первому входу выходного умножителя, второй вход которого подключен к выходу N-го регистра первой группы, первый выход дешифратора подключен к первому входу элемента

ИЛИ, выход которого подключен к тактовым входам регистров первой группы, второй выход дешифратора подключен к первому входу элемента И, выход которого подключен к входу синхронизации

i ro сумматора, вторые входы элемента И и элемента ИЛИ соединены с управляющим входом i-го мультиплексора второй группы, тактовыми входами i-x регистров второй и третьей групп, управляющим входом мультиплексора и подключены к первому входу задания режима устройства, выходом дискретного преобразователя Фурье которого является выход выходного умножителя, выход переполнения счетчика подключен к управляющему входу i-го мультиплексора второй группы, информационный выход счетчика подключен к адресным входам первого и третьего и первому адресному входу второго блоков постоянной памяти, второй адресный вход которого является вторым входом задания режима устройства, а выход генератора тактовых импульсов подключен к тактовому входу i-ro регистра четвертой группы.