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

 

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

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

РЕСПУБЛИК

„„5U „„1462354

Аf (sg 4 G 06 F 15/332

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 3976435/24-24 (22) 19. 11.85 (46) 28.02.89. Бюл. У 8 (71) Институт технической кибернетики

АН БССР (72) С.Н. Демиденко, В.С. Кончак, Э.Б. Куновский и П.M. Чеголин (53) 681.32(088.8) (54)(57) УСТРОЙСТВО ДЛЯ БЫСТРОГО ДЕЙ

СТВИТЕЛЬНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее синхронизатор, первый и второй выходы которого подключены к счетным входам соответственно первого и второго счетчиков адреса, информационные выходы которых подключены к адресным входам соответственно блока постоянной памяти и блока памяти, третий и четвертый выходы синхронизатора подключены соответственно к входу чтения блока постоянной памяти и входу чтения записи блока памяти, выход которого подключен к информационным входам первого и второго входных регистров и является информационным выходом устройства, выход блока пос-: тоянной памяти подключен к информационному входу регистра, тактовый вход которого подключен к пятому выходу синхронизатора, шестой и седьмой входы которого подключены к тактовым

Изобретение относится к цифровой вычислительной технике и может быть использовано в системах и устройствах цифровой обработки информации в качестве преобразователей временной последовательности действительных входам соответственно первого и второго входных регистров, умножитель и два сумматора, о т л и ч а ю щ е ес я тем, что, с целью .упрощения устройства, оно содержит первый, второй и третий мультиплексары, выходы которых подключены соответственно к первым входам первого и второго,сумматоров и информационному входу блока памяти; выход первргп.входного регистра подключен к вторым входам первого и второго сумматоров, выходы которых подключены соответственно к первому и второму информационным входам третьего мультиплексора, третий информационный вход которого является информационным входом устройства, вход: второго входного регистра подключен к первым информационным входам первого и второго мультиплексоров и первому .входу умножителя, выход которого подключен к вторым информационным входам первого и второго мультиплексоров, управляющие входы которых р подключены соответственно к восьмому. © и девятому выходам синхронизатора, . десятыи выход которого подключен к управляющему входу третьего мульти- C0 плексора, а выход регистра подключен к второму входу умножителя. отсчетов входного сигнала в частотную последовательность.

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

На фиг. 1 показана структурная схема устройства; на фиг. 2 — граф

Ь з 14 алгоритма быстрого преобразования

Фурье.(БПФ), реализованный в устройстве; на фиг. 3 — временные диаграммы работы устройства.

Устройство содержит синхронизатор

1, счетчик 2 адреса, блок 3 постоянной памяти, счетчик 4 адреса, входной регистр 5, регистр 6, вхоцной регистр

7, блок 8 памяти, умножитель 9, первый 10 и второй 11 мультиплексоры, первый 12 и второй 13 сумматоры,тре тий мультиплексор 14, информационные, вход 15 и выход 16.

Граф алгоритма БПФ (фиг. 2) приве-. ден для исходного. массива длиной в

16 значений. На фиг. 2 обозначены входная последовательность 17, выходная последовательность 18 коэффици" . ентов Фурье, операции 19, применяе:мые в алгоритме.

Рассмотрим работу устройства.Вы; полнение БПФ в нем включает три эта,: :па: вход исходной информации, вычис, ление коэффициентов Фурье и вывод результатов преобразования.

На этапе ввода используются только синхронизатор 1, счетчик 4, блок 8 памяти и мультиплексор 14. По сигналам синхронизатора 1 счетчик 4 адреса формирует и передает на блок 8 памяти последовательность адресов, по которым в него записывается ис ходная информация, поступающая через мультиплексор 14 с входа 15.

Этап вычисления коэффициентов

Фурье включает несколько шагов. На первом шаге в соответствии с алгоритмом выполняются операции сложения и вычитания отсчетов. Синхронизатор 1 передает в счетчик 4 сигнал, по которому в последнем формируется и передается на блок 8 памяти код адреса первого операнда, представляющего собой некоторый i-й входной отсчет (i = О, 1,..., М/2 - 1). Считанный из блока 8 памяти операнд фиксируется в первом входном регистре 5. С выхода последнего цифровой код поступает на входы первого 12 и второго

13 сумматоров. На счетчике 4 по сигналу синхронизатора 1. формируется код адреса второго операнда, являющегося (i + N/2)-м входным отсчетом.

С выхода блока 8 оперативной памяти

; значение операнда поступает на входной регистр 7 и фиксируется в нем.

Отсюда цифровой код попадает на входы мультиплексоров 10 и 11. На управляющие входы последних с синхронизатора

62354

1О

20.

ЗО

1 поступает сигнал, вызывающий передачу этой информации на входы первого 12 и второго 13 сумматоров. Сумматор 12 осуществляет сложение операндов, поступающих на его входы, а сумматор 13 — вычитание. второго операнда из первого. С выходов сумматоров

12 и 13 результаты поступают соответственно на входы мультиплексора 14.

По сигналам с синхронизатора 1 эти данные последовательно передаются в блок 8 памяти и фиксируются по адресам операндов, считанных из него в начале выполнения шага. Аналогичным путем происходит обработка остальных пар отсчетов на первом шаге алгоритма.

Выполнение второго шага включает только операции сложения-вычитания и происходит в целом подобно первому шагу. Однако в данном случае иными являются коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом, так же, как и на преды» дущем шаге, выбираются такие пары операндов, над которыми надо производить операции сложения и вычитания).

Кроме того, на данном шаге присутствуют операнды, над которыми не требуется производить какие-либо преобразования (с номерами N/2 и 3N/4).

Эти отсчеты не считываются из блока

8 и не подвергаются обработке.

Третий и последующий шаги алгоритма содержат операции не только сложения-вычитания, но и умножения на тригонометрические весовые коэффициенты. Третий шаг включают два подшага. Выполнение первого из них, содержащего только операции сложениявычитания, в целом подобно отработке первого и второго шага преобразования. Функционирование устройства на втором подшаге происходит следующим образом. По сигналам с синхронизатора 1 счетчик 4 последовательно формирует коды адресов, по которым из блока 8 памяти считывается очередная пара операндов, которая записывается во входные регистры 5 и 7 (считываемые операнды А и В выбираются такими, над которыми должна быть выполнена пара операций вида А+СВ и

А-СВ, где С вЂ” весовой коэффициент; для представленного на фиг. 2 алгоритма при Б 16 это отсчеты с но1462354

5 мерами8и10, 9и11, 12и14, 13 и 15). Одновременно по сигналу из . синхронизатора счетчик 2 адреса формирует и передает на блок 3 постоянной памяти код адреса, по которому из него считывается и фиксируется в регистре 6 значение соответствующего весового коэффициента (в том случае, когда по алгоритму требуется умножение на удвоенный весовой коэффициент, такое удвоенное значение и хранится в блоке 3 постоянной памяти). С выхода регистра 6 код коэффициента передается на вход первого сомножителя умножителя 9, на вход второго сомножителя которого с выхода регистра 7 поступает значение второго операнда.

Результаты умножения через мультиплексоры 10 и 11, управляемые синхронизатором 1, поступают на вторые входы сумматоров 12 и 13, на первые входы которых подается код операнда с выхода первого входного регистра 5.

В сумматоре 12 .происходит сложение,,- а в сумматоре 13 - вычитание операндов. Результаты из сумматоров 12 и

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

На этом заканчивается отработка устройства третьего шага алгоритма.

Последующие шаги вплотьдо (и-1)-ro подобны третьему шагу алгоритма и выполняются в целом аналогично опи5 санному (но с другими значениями весовых коэффициентов и операндов).

Последний, и-й шаг алгоритма содержит операции сложения-вычитания и сложения-вычитания с умножением.

Первые выполняются аналогично отработке таких операций на первом mare, а вторые — на третьем шаге. После окончания n-ro шага преобразования, являющегося последним на этапе вычисления коэффициентов Фурье в блоке 8 оперативной памяти получают набор искомых значений, порядок следования которых отличается от нормального вследствие специфики алгоритма.

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

2б выходных отсчетов осуществляются на этапе вывода. Здесь счетчик по сигналам с синхронизатора 1 формирует коды адресов в порядке, обеспечивающем считывание из блока 8 и выдачу на выход коэффициентов действительного преобразования Фурье в нормаль- ной последовательности, т.е. а,а °

° ° ° ° viz Ь 1 ° ° ° ° b N(-1462354

Пр

Редактор А. Огар

Заказ 715/49 Тирах 667 Подписное

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

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

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

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

Техред Л. Олийнык Корректор С. Черни