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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ COBETCHHX

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

РЕСПУБЛИК (51)5 G 06 F 15/332

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

ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

В устройстве реализован алгоритм быстрого преобразования Фурье с замещением и прореживанием по времени (3,1), а также конвейерный принцип обработки информации. Выполнение итерации быстрого преобразования Фурье заключается в последовательном выполнении операции вида А + BW, или (21) 4651410/24 (22) 14.02.89 (46) 23.08.91. Бюл. ll- 31 (71) Специальное конструкторскотехнологическое бюро с опытным производством при Белорусском государственном университете им. В.И.Ленина (72) А.Н.Карташевич, В.,И.Приходько и А.А.Фомин (53) 681.32(088.8) ,(56) Авторское свидетельство СССР

N 1056206, кл. G 06 F 15/332, 1981.

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

М- 1164730, кл.. С Об F 15/332, 1983.

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

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

На фиг.1 приведена структурная схема предлагаемого устройства для реализации быстрого преобразования

Фурье, на фиг.2 — структурная схема блока синхронизации; на фиг.3— временная диаграмма работы устройства для реализации быстрого преобразования Фурье.

Устройство для реализации быстрого преобразования Фурье (см. фиг.1) содержит блок (оперативной) памяти 1, умножитель 2, коммутатор 3, блок постоянной памяти 4, счетчик 5, регистр сдвига 6, блок синхронизации 7, буферный блок памяти 8, сумматор-вычи„„Я2 „„1672469 À1

2 (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач цифровой обработки сигналов. Цель изобретения — повышение быстродействия. Поставленная цель достигается эа счет того, что в состав устройства входят блок памяти 1, умножитель 2, коммутатор 3, блок постоянной памяти 4, счетчик 5, регистр сдвига 6, блок синхронизации /, буферный блок памяти 8, сумматор-вычитатель 9, накапливающий сумматор 10, сумматор 11 и накапливающий сумматор 12. 3 ил . татель 9, накапливающий сумматор 10, сумматор 11, накапливающий сумматор

12. Блок синхронизации (см. фиг.2) содержит триггер 13, трехраэрядный счетчик 14, генератор синхроимпульсов 15, дешифратор 16, элемент И 17, элемент НЕ 18, коммутатор 19, элементы И 20-24.

Re = Re А «+ (Re В cos Ис — Е m В х .хs C3t) Iml < =ImA «+ (ReB. sin

Ы вЂ” экспоненциальный множитель, хранящийся в блоке постоянной памяти.

Устройство для реализации быстрого преобразования Фурье работает следующим образом, ." исходном состоянии счетчик 5 10 обнулен, Все разряды регистра сдвига

6 обнулены. Информация расположена в блоке оперативной памяти 1 в двоичноинверсном порядке,. По приходу импульса на первый Х устроистна блок 15 синхронизации ) начинает генерировать управляющие сигналы для реализации устройст1 ом алгоритма быстрого преобразования Фурье с зашемлением и прореживанием по времени. Во время перво-20 го такта = третьего выхода У4. блока синхронизации / на управляющий вход блока оперативной памяти 1 приходят импульсы, по которым из блока оперэтивной памяти считывается действи- 25 тельная часть первого операнда Re 1.0 и заносится в первую ячейку буферной блока памяти 8 (блок памяти S содержит четыре ячейки и служит для организации конве.".ера) по импульсам, по- 30 ступаюшим на ее управляющий вход со вто1, го ж:.хода У< блока синхронизации

/. Затем из бпока памяти 8 считывается занесенное эка ение Re 1.0 и записыва тся через умножитечь 2 пульс:;, поступающим на его управляющий вход с первого выхода У блока синхронизации /. Через другой вход умножителя 2 записьцьается значение косинусной составляющей экспоненциаль- р

40 ного множителя, считываемое из блока постоянной памяти 4. Во время второго такта из блока оперативной памяти 1 по адресу, сформированному на выходе коммутатора 3, с помощью адресного 45 сумматора 11 считывается значение мнимой части первого операнда Im 1,.0 и заносится во вторую ячейку блока буферной памяти 8 по импульса;, поступающим с первого выхода блока синхрониза1;ии / на управляющие входы умножителя 2 и первого накапливающего сумматора 10. С выхода умножителя значение произведения Ке 1.0 cog(Jt записывается в первый накапливающий сумматор 10. Затем из блока памяти 8 считывается мнимая часть первого операнда Im 1.0 и заносится в умножитель 2. Через его другой вход заносится значение множителя, которое считывается из блока постоянной памяти 4. Адрес для считывания значения тригонометрических составляющих экспоненциальных множителей формируется на выходе второго накапливающего сумматора 12. Во время третьего такта иэ блока оперативной памяти 1 считывается значение действительной части второго операнда Re 2.0 и заносится в третью ячейку блока памяти 8. Это же значение считывается иэ блока памяти 8 и по импульсу на первом выходе

У блока синхронизации 7 заносится в сумматор-вычитатель 9 через его первый вход. С выхода умножителя 2 значение произведения Im 1. 0 sining t заносится в первый накапливающий сумматор 10, с выхода которого значение (Re 1.0 cos(d t + Im 1..0 sin t) через второй вход заносится в сумматор-вычитатель 9, который выполняет операцию сложения. Затем из первой ячейки блока памяти 8 считывается значение действительной части первого операнда Re 1.0 и через первый вход заносится в умножитель 2, :ерез другой вход которого заносится значение синусной составляющей экспоненциального множителя. Затем с выхода сумматора-вычитателя 9 значение действительной части первой преобразованной точки Re 1.1 записывается в блок оперативной памяти 1. Во время четвертого такта импульсом на первом выходе

У< блока синхронизации / обнуляется первый накапливающий сумматор 10. Иэ блока оперативной памяти 1 считывается значение мнимой части второго опеI ранда Тв 2.0 и заносится в четвертую ячейку блока памяти 8. Затем с выхода умножителя 2 в первый накапливающий сумматор 10 заносится произведение

Re 1.0 s n43 t, полученное в предыдущем такте. Сумматор-вычитатель выполняет операцию вычитания. Затем из блока памяти 9 считывается значение мнимой части первого операнда Im 1.0 и заносится в умножитель 2. Через другой вход в умножитель 2 заносится значение косинусной составляющей

° экспоненциального множителя из блока постоянной памяти 4. С выхода сумматора-вычитателя 9 значение действительной части второй преобразованной точки Re 2.1 заносится в блок оперативной памяти 1. Во время пятого такта из блока оперативной памяти 1

После считывания из блока оперативной памяти 1 2N значений, обработки их как описано vbwe и занесения в блок оперативной памяти 1 по тем же адресам импульс с второго выхода счетчика 5 поступает на вход регистра сдвига 6. В результате в регистр вдвигается нуль. Измененный код с первого выхода (инверсный) вход второго накапливающего сумматора 12 и далее вторая итерация вьп олняются аналогично первой. После завершения и-й итерации на втором выходе регистра сдвига формируется уровень логической 1, которьп» поступает на второй вход Х блока синхронизаz ции. Устройство переходит в режим ожидания до прихода следующего импульса на вход Х ., Блок синхронизации работает следующим образом. По приходу запускающего импульса на первый вход Х < блока синхронизации 7 устанавливается триггер 13. Уровень логической "1" с выхода триггера 13 поступает на первьп вход генератора синхроимпульсов 15 и разрешает его работу. Тактовые импульсы с первого выхода генератора 15 поступают на вход счетчика 14, на первом выходе которого формируются импульсы, которые через второй вход элемента И 17 поступают на второй выход У блока синхронизации и являются импульсами записи в блок буферной памяти. Эти же импульсы поступают на первыи вход дешифратора 16, на второй и третий входы которого поступают значения двух следующих разрядов счетчика 16.

На первом и втором выходе дешифратора

16 формируются коды, которые через пятый выход У6 поступают на второй вход адресного сумматора 11, С первого выхода счетчика 14 импульсы поступают также на вход элемента 18 и управляющий вход коммутатора 19, на второй (инверсньп ) вход коммутатора

19 поступают импульсы с третьего выхода счетчика 14, на первый вход коммутатора 14 поступают импульсы с второго выхода счетчика 14, на выходе элемента 18 и коммутатора 19 формируются коды адреса для записи и считывания блока памяти 8. Импульсы с второго выхода счетчика 14 поступают на второй выход Уэ блока синхронизации и являются импульсами считывания из блока памяти 8„ С первого

16/2469

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

8 по импульсу на втором выходе У> блока синхронизации /. Вместе с этим из четвертой ячейки блока памяти 8 считывается значение мнимой части второго операнда ?т 2.0 и по импульсу на первом выходе Y блока синхронизации / заносится в сумматор-вычитатель 9 через его первый вход. С выхода умножителя 2 значение произведения Im 1.0 созИ t заносится в первый накапливающий сумматор 10, с выхода которого значение (Re 1.0 sin< t+

+ Im !.0 созЯ t) заносится через второй вход в сумматор-вычитатель 9, который выполняет операцию сложения.

Затем из перв<ай ячейки блока памяти 20

8 считывается значение действительной части третьего операнда Re 3.0 и через первый вход заносится в умножитель 2, на другой вход которого поступает значение синусной составляю- 25 щей экспоненциального множителя из блока постоянной памяти 4. Затем с выхода сумматора-вычитателя 9 значение мнимой части первой преобразованной точки Im 1.1 заносится в блок 30 оперативной памяти 1. Во время шестоl

ro такта импульсом на выходе Y бло2 ка синхронизации / обнуляется г ервый накапливающий сумматор 10, Hs блока оперативной памяти 1 считывается значение мнимой части третьего операнда Im 3.0 и заносится во вторую ячейку блока памяти 8. Затем с выхода умножителя 2 в первый накапливающий сумматор 10 заносится значение 40

Re 3.0 з ОЯс, полученное в предыдущем такте. Сумматор-вычитатель 9 выполняет вычитания над операндами, занесенными в него во время пятого такта. Затем из второй ячейки блока 4> памяти 8 считывается значение мнимой части третьего операнда ?ш 3 0 и заносится в умножитель 2. Через другой вход с выхода блока постоянной памяти 4 в умножитель 2 заносится значение синусной составляющей экспоненциального множителя. С выхода сумматора-вычитателя 9 значение мнимой части второй преобразованной точки Im 2.1 заносится в блок оперативной памяти 1. Таким образом осуществляется элементарное преобразование.

В дальнейшем (до конца итерации) обработка происходит как описано выше.

1622469

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

20, 23 и 24, а также на вторые входы элементов 21 и 22 На второй вход элемента 20 гос. упают такговые импу::сы первого выхода генератора 15„

На выходе элемента 20 ф.рмируются импульсы записи в умножитель 2. С вто oro выхода генератора 15 импульсы лостуггают па первый вход элемента

21, «з «ьгс<.,-.. которого формируются импульсы занесения в накапливающий сумматор 10, с третьего выхода генсрагора 15 им. ..-льсы на первый вход элемента ?2„ на,ретий вход которого по тупают импульсы с третье;о вьгсода с летчика 1 ., аа выходе элемента 22 формируются импульсы обнуления накапгивающего сумматога 10, с четвертого вых ла геке -lToocl иглпульсы поступают на второй вход элемента 24, на выходе ко r oo: о формируютгя и..— пульс.- зсч е. ня в сумматор-вычитатель 9 Выходы элементов 20-2 об епинены и являются первым выхо;;зм

Yg блока синхронизации. На второй

«ход элемента 23 = итог;го чхода Х блока синхр< изации поступает урогei ь, которы; разрешает -tevxe esHc. импул сог занес ния в блок оперативной памяти !;а трет и" вьа o Y блока пн:.рони ", зии, 1 а - етьертый выход блока сш хронизации поступают с третьего выхода счетчика 14 тактовые имгульсь для счет - ика 5. 11осле завершениг и-й итерации на второй вход Х блока синхронизации приходит импульс с второго выхода регистра сдвига 6.

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

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

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

45 ля, входу управления считыванием бпоха постоянной памяти, входу управления записью/считыванием блока памяти и счетному входу счетчика, выход первого разряда которого подключен к тактовому входу регистра сдвига, последовательный выход которого подключен к входу останова блока синхронизации, вход запуска которого является входом запуска устрой-тва, параллельньш выход регистра сдвига подключен к управляющему входу коммутатора, выход которого подключен к адресному входу блока памяти, а выход блока постоянной памя ги подключен к первому информационно.гу вход умножит:.ля, о т л и ч а ю щ е е с я тем, что, с цельк повышения быстродействия, в него введены буферный блок памяти, два накапливаняух сумматора, сумматор и сумматор-вычнтатель, выход которого является информационным вы;одом устройства и подключен к информационному входу блока гамяти, выход которого подключен к информационному вхс:. у буферного бло са .амяти, выход которого подключен к нс сому информа злонному входу сумматора-вычитателя и в-.орому информационному входу умножителя, выход которого подключен к ин.зормзционному в; .>ду первого накап:ивающ го сумматора, выход которого подключен к второму информационному входу сумматора-вычитателя, управляющий вход которого соединен с входом синхронизации первого накапливающего сумматора и подключен к первому выходу блока синхронизации, второй и пятый выходы которого подключены соот" ветс гвенно к входу синхронизации буферного блока памяти и первому входу сумматора, выход которого подключен к информационному входу коммутатора, гараллельный выход регистра сдвига подключен к информационному входу второго накапливающего сумматора, выход которого подключен к адресному входу блока постоянной памяти, информационный выход и выход второго разряда счетчика подключены соответственно к второму входу сумматора и входу синхронизации второго накапливающего сумматора„!

672469

У3

У2

Фиг. 2

1672469

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

Техред И.Сердюкова Корректор М.Демчик

Редактор Т.Шагова

Заказ 284 1 Тира к 388 Подписное

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

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

Производственно-издательский комбинат "Патент",. г. Ужгород, ул. Гагарина, 101