Устройство для реализации быстрого преобразования Фурье Советский патент 1991 года по МПК G06F17/14 

t/1

С

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

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

Цель изобретения - повышение быстродействия„

На фиг01 приведена структурная схема предлагаемого устройства для реализации быстрого преобразования Фурье; на фиг02 - структурная схема блока синхронизации; на фиг03 - временная диаграмма работы устройства для реализации быстрого преобразования Фурье о

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

В устройстве реализован алгоритм быстрого преобразования Фурье с замещением и прореживанием по времени (3,1), а также конвейерный принцип обработки информации. Выполнение итерации быстрого преобразования Фурье заключается в последовательном выполнении операции вида А + BW, или

Re , г Re A ± (Re В- cog CO t - I m В XSJJ1G3 t)

Ьп.л ImA + (ReB-sinQc +ImB coscJc),

11

о

xl ГО

о ю

где А и В - операнды, хранящиеся в

блоке оперативной памяти; СО - экспоненциальный множитель, хранящийся в блоке постоянной памяти„ Устройство для реализации быстрого преобразования Фурье работает следующим образомс

; исходном состоянии счетчик 5 обнулен,. Все разряды регистра сдвига 6 обнуленыс Информация расположена в блоке оперативной памяти 1 в двоично- инверсном порядке г По приходу импульса на первый Х устройства блок силхронизации / начинает генерировать управляющие сигналы для реализации устройстьом алгоритма быстрого преобразования Фурье с защемлением и прореживанием по временно Во время перво го такта с третьего выхода Y. блока синхронизации 7 на управляющий вход блока оперативкой памяти 1 приходят импульсы, по которым из блока оперативной памяти считывается действительная часть первого операнда Re КО и заносится в первую ячейку буферной блока памяти б (блок памяти 8 содержит четыре ячейки и служит для организации конве.°.ра) по импульсам, поступающим на ее управляющий вход со BToi- ro ыхода V2 блока синхронизации /с Затем чз б пока памяти 8 считывается занесенное значение Re КО и записывается через умножитель 2 по импульс -г-, поступающим на его управляющий вход с первого выхода Y блока синхронизации Ч. Через другой вход умножителя 2 записывается значение косинусной составляющей экспоненциального множителя, считываемое из блока постоянной памяти 4. Во время второго такта из блока оперативной памяти 1 по адресу, сформированному на выходе коммутатора 3, с помощью адресного сумматора 11 считывается значение мнимой части первого операнда Im 1„0 и заносится во вторую ячейку блока буферной памяти 8 по импульсах, поступающим с первого выхода блока синхро- низа1;ии / на управляющие входы умножителя 2 и первого накапливающего сумматора 10„ С выхода умножителя значение произведения Re КО cjogCOt записывается в первый накапливающий сумматор 10„ Затем из блока памяти 8 считывается мнимая часть первого операнда 1га КС и заносится в умножитель 2„ Через его другой вход зано10

15

20

25

30

35

40

45

50

55

сится значение множителя, которое считывается из блока постоянной памяти 4. Адрес для считывания значения тригонометрических составляющих экспоненциальных множителей формируется на выходе второго накапливающего сумматора 120 Во время третьего такта из блока оперативной памяти 1 считывается значение действительной части второго операнда Re 2.0 и заносится в третью ячейку блока памяти 8„ Это же значение считывается из блока памяти 8 и по импульсу на первом выходе Y блока синхронизации / заносится в сумматор-вьгчитатель 9 через его первый вход о С выхода умножителя 2 значение произведения Im КО sin CO t заносится в первый накапливающий сумматор 10, с BbiXOfla которого значение (Re КО с о SCO с + In. КО sin CO с) через второй вход заносится в сумматор-вьгчитатель 9, который выполняет операцию сложения Затем из первой ячейки блока памяти 8 считывается значение действительной части первого операнда Re КО и через первый вход заносится в умножитель 2, через другой вход которого заносится значение синусной составляющей экспоненциального множителя. Затем с выхода сум- матора-вычитателя 9 значение действительной части первой преобразованной точки Re К1 записывается в блок оперативной памяти 1„ Во время четвертого такта импульсом на первом выходе Y блока синхронизации У обнуляется первый накапливающий сумматор 10„ Из блока оперативной памяти 1 считывается значение мнимой части второго операнда 1га 2„0 и заносится в четвертую ячейку блока памяти 8„ Затем с выхода умножителя 2 в первый накапливающий сумматор 10 заносится произведение Re КО sinCO с. полученное в предыдущем такте о Сумматор-вычитатель выполняет операцию вычитания. Затем из блока памяти 9 считывается значение мнимой части первого операнда Im КО и заносится в умножитель 20 Через другой вход в умножитель 2 заносится значение косинусной составляющей «экспоненциального множителя из блока постоянной памяти 40 С выхода сумматора -вьгчитателя 9 значение действительной части второй преобразованной точки Re 2„1 заносится в блок оперативной памяти 1 Во время пятого тактг из блока оперативной памяти 1

считывается значение действительной части третьего операнда Не и заносится в первую ячейку блока памяти 8 по импульсу на втором выходе УЭ блока синхронизации 7. Вместе с этим из четвертой ячейки блока памяти 8 считывается значение мнимой части второго операнда Im и по импульсу на первом выходе Y2 блока синхронизации / заносится в сумматор-вычи- татель 9 через его первый вход С выхода умножителя 2 значение произведения Im 100 с заносится в первый накапливающий сумматор 10, с выхода которого значение (Re 1jO (X) 4 Im 1.0 cosoOt) заносится через второй вход в сумматор-вычитатель 9, который выполняет операцию сложения„ Затем из первс и ячейки блока памяти 8 считывается значение действительной части третьего операнда Re 300 и через первый вход заносится в умножитель 2, на другой вход которого поступает значение синусной составляющей экспоненциального множителя из блока постоянной памяти 40 Затем с выхода сумматора-вычитателя 9 значение мнимой части первой преобразованной точки Im 1 о 1 заносится в блок оперативной памяти 10 Во время шестого такта импульсом на выходе У2 блока синхронизации 7 обнуляется первый накапливающий сумматор 10.„ Из блока оперативной памяти 1 считывается значение мнимой части третьего операнда Im ЗоО и заносится во вторую ячейку блока памяти 80 Затем с выхода умножителя 2 в первый накапливающий сумматор 10 заносится значение Re ЗоО sijiCOt, полученное в предыдущем такте о Сумматор-вычитатель 9 выполняет вычитания над операндами, занесенными в него во время пятого такта Затем из второй ячейки блока памяти 8 считывается значение мнимой части третьего операнда Im 3,0 и заносится в умножитель 20 Через другой вход с выхода блока постоянной памяти 4 в умножитель 2 заносится значение синусной составляющей экспоненциального множителя С выхода сумматора-вычитателя 9 значение мнимой части второй преобразованной точки Im 2U1 заносится в блок оперативной памяти 1„ Таким образом осуществляется элементарное преобразование„ В дальнейшем (до конца итерации) обрботка происходит как описано выше.

После считывания из блока оперативной памяти 1 2N значений, обработки их как описано выше и занесения в блок оперативной памяти 1 по тем же адресам импульс с второго выхода счетчика 5 поступает на вход регистра сдвига 6, В результате в регистр вдвигается нуль,. Измененный код с

первого выхода (инверсный) вход второго накапливающего сумматора 12 и далее вторая итерация выполняются аналогично первой0 После завершения n-й итерации на втором выходе ре5 гистра сдвига формируется уровень логической 1, который поступает на второй вход Хо блока синхронизации Устройство переходит в режим ожидания до прихода следующего им0 пульса на вход

Блок синхронизации работает следующим образом. По приходу запускающего импульса на первый вход X, блока синхронизации 7

5 устанавливается триггер 13„ Уровень логической 1 с выхода триггера 13 поступает на первый вход генератора синхроимпульсов 15 и разрешает его работу. Тактовые импульсы с первого

0 выхода генератора 15 поступают на вход счетчика 14, на первом выходе которого формируются импульсы, которые через второй вход элемента И 17 поступают на второй выход YJ блока

- синхронизации и являются импульсами записи в блок буферной памяти„ Эти же импульсы поступают на первый вход дешифратора 16, на второй и третий входы которого поступают значения

0 двух следующих разрядов счетчика 16„ На первом и втором выходе дешифратора 16 формируются коды, которые через пятый выход Yg поступают на второй вход адресного сумматора 11 ., С перво-

5 г° выхода счетчика 14 импульсы поступают также на вход элемента 18 и управляющий вход коммутатора 19, на второй (инверсный) вход коммутатора 19 поступают импульсы с третьего

0 выхода счетчика 14, на первый вход коммутатора 14 поступают импульсы с второго выхода счетчика 14, на выходе элемента 18 и коммутатора 19 формируются коды адреса для записи и

5 считывания блока памяти 8. Импульсы с второго выхода счетчика 14 поступают на второй выход УЗ блока синхронизации и являются импульсами считывания из блока памяти 80 С первого

выхода счетчика 14 импульсы поступают также на первые входы элементов

20,23 и 24, а также на вторые входы элементов 21 и 22 На второй вход элемента 20 посгупают тактовые им- пу- -сы первого выхода генератора 15„ Ия выходе элемента 20 формируются импульсы записи в умножитель 2. С второго выхода генератора 15 импульсы поступают на первый вход элемента

21,ai иьгчг,.-- которого формируются импульсы занесения в накапливающий сумматор 10, с третьего пькода генератора 15 имт гльсы на первый вход элемента 12, на вход которого по тупают импульсы с третьего выхода счетчика 1 , .та выходе элемента 22 формируются импульсы обнуления накапливающего сумматора Ю, с четвертого выя та гйке; 1Т1 ра импульсы поступают на лторсй вход элемента 24, на рмходе хо-про; о Формируются ИУ- пульс - з- ч се ия в сумматор-вычнта- тель 9 Выводы элементов 20-2А объединены к являются первым выхо;;тм Y блока еинхронк-зацмио На яторой «ход рчемеита 21 L втор .го пхеда Х блока синхронизации поступает yponeii котор ь-i раяретает аг охождени. импу,/ сог- занесения в бпок оперативней памяти I ,з третий вы o;i Y. блока глч- /ронит, цп(1э 1;а четвертый выход Y блока синхронизации поступают с третьего выхода счетчика 14 тактовые импульсы для счетчика 5 После завершение n-й итерации на второй вход Х2 блока синхронизации приходит импульс

с второго выхода регистра сдвига 6 Этот импульс сбрасывает триггер 13, закрывает элемент 1/, а блок синхронизации переходит в режим ожидания до прихода следующего импульса запуска на первый вход

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

в

16/2469

ля,

входу управления считыванием бло

0

0

5

0

5

0

5

0

пня записью/считыванием блока памяти и счетному входу счетчика, выход первого разряда которого подключен к тактовому входу регистра сдвига, последовательный выход которого подключен к входу останова блока синхронизации, вход запуска которого является входом -запуска устроиттна, параллельный выход регистра сдьига подключен к управляющему входу коммутатора, выход которого подключен к адресному входу блока памяти, а выход блока постоянной памяти подключен к перво iy информационному входу умножитс-лт, отличающееся тем, что, с целью повышения быстродействия, в чего введены буферный блок памяти, два накапливающих сумматора, суммл- тор и сумматор-вычитатель, выход которого является информационным выходом устройства и подключен к информационному нходу блока памяти, выход которого подключен к информационному вхс чу буферного гамяти, выход котэро: о ПОДКЛ;ОЧРК к пер (ому информационному входу суммат ора-вьгччтателя и второму информационному входу умножителя, зыход которого подключен к информационному иг.оду первого накап- лнваюпкго сумматора, выход которого подключен к второму информационному входу сумматора-вычитателя, управляющий вход которого соединен с входом синхронизации первого накапливающего сумматора и подключен к первому выходу блока синхронизации, второй и пятым выходы которого подключены соответственно к аходу синхронизации буферного блока памяти и первому входу сумматора, выход которого подключен к информационному входу коммутатора, параллельный выход регистра сдвига подключен к информационному входу чторсго накапливающего сумматора, выход которого подключен к адресному входу блока постоянной памяти, информационный выход и выход второго разряда счетчика подключены соответственно к второму входу cvMMaTopa и входу синхронизации второго накапливающего сумматора,,

SA

Јл

9J(

tx

bWli)

п

л

U

п

и

и

Фиг.3