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

(21) 4480506 (22) 05,09.8 (46) 23.08.9 Бюл. Мф 31 ное конструкто бюро с опытным Белорусском го ситете им. В,И ашевич, В.М.Пр 71) Специал ологическое ско-техпроизс удар ст.Ленина иходьк кл СЬ ОСУДАРСТВЕННЫЙ КОМИТЕТО иэОБРетениям и ОТКРытиямРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ водством привенном универ(54) УСТРОИСТВОДЛЯ РЕАЛИЗАЦИ 11 БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 57) Изобретение относится к вычисительной технике и может быть испольовано для цифровой обработки сигнаов. Цель изобретения - повьпдениеыстродействия. Укаэанная цель достиается за счет того, что устройствоодержит блоки оперативной 1, 2 иостоянной 3 памяти, первьп 1, второйоммутаторы 13, 11, счетчики 14, 15,онвейерные регистры 6, 7, сдвигающий счетчик 17, умножитель 4, блок 8инхронизации и блок 16 элементов И,ретин, четвертьп 1 коммутаторы 12, 10,акапливающий сумматор 5 и сумматорычитатель 9. 2 ил,Изобретение относится к вычислительной технике и может быть использовано для решения задач цифровой обработки сигналов.Цель изобретения - повьппение быстродействияНа фиг.1 приведена функциональнаясхема устройства; на фиг.2 - примерреализации блока синхронизации.10Устройство содержит (фиг. 1) первый1 и второй 2 блоки оперативной памяти, блок 3 постоянной памяти, умножитель 4, накапливающий сумматор 5,первый 6 и второй 7 конвейерные регистры, блок 8 синхронизации, сумматор-вычитатель 9, четвертый 10, второй 11, третии 12 и первыи 13 коммутаторы, первый 14 и второй 15 счетчики, блок 16 элементов И и сдвигающий счетчик 17,Блок синхронизации (фиг.2) содержит первый 18, второй 19 и третий 20триггеры, генератор 21 синхроимпульсов, однорйэрядньй счетчик 22, двухразрядный счетчик 23, дешифратор 28,элемент ИЛИ 24, а также первый 25,второй 26, третий 27, четвертьп 1 29,пятый 30, шестой 31, седьмой 32,восьмой 33, девятый 34, десятый 35,одиннадцатый ЗЬ, двенадцатый 37,тринадцатый 38 и четырнадцатый 39элементы И, первую группу У 1 выходов40, 41, вторую группу У 2 выходов 4244, третью группу УЗ выходов 45-53,вход 54 запуска, вход 55 останова ивход 56 признака режима работы. Блоки оперативной 1, 2 и постоянной 3 памяти содержат по 2 М ячеек, 40 где И - длина реализации, счетчики 14 и 15 содержат и+1 разрядов, где и = 1 оКХ, сцвигающий счетчик 17 является и-разрядным. Блок 16 И является группой иэ и элементов И, первые входы которых соединены с и-разрядным выходом первого счетчика 14, вторые входы соединены с и-разрядным выходом сдвигающего счетчика 17 в двоично-инверсном порядке. На первой итерации счетчик 17 и блок 16 элементов И блокированы нулями, находящимися в счетчике 17, после первой итерации с выхода переноса второго счетчика 15 в итерационной регистр 17 вдвигается единица, вследствиен н55 чего на второй итерации с выходаблока 1 Ь элементов И на адресный вход 3 постоянной памяти поступает значение старшего разряда первого счетчика 14 и т д.Первый 13 и третий 12 коммутаторыпредставляют собой группу из и мультиплексоров на два входа, причем первый информационный вход первого мультиплексора первого коммутатора 13соединен с выходом нулевого разрядапервого счетчика 14, второй информационный вход указанного мультиплексора - с выходом первого разряда второго счетчика 15, первый информационный вход второго мультиплексора первого коммутатора 13 - с выходом первого разряда первого счетчика 14, второй информационный вход указанногокоммутатора - с выходом второго разряда второго счетчика 15 и т.д., первый информационный вход и-го мультиплексора первого коммутатора 13 соединен с выходом и-го разряда первогосчетчика 14, второй информационныйвход указанного мультиплексора - свыходом нулевого разряда второго счетчика 15.Первый информационный вход первогомультиплексора третьего коммутатора12 соединен с выходом первого разрядавторого счетчика 15, второй информационный вход указанного мультиплексора - с выходом нулевого разряда первого счетчика 14, первый информационный вход второго мультиплексора третьего коммутатора 12 - с выходом второго разряда второго счетчика 15,второй информационный вход указанного мультиплексора - с выходом первогоразряда первого счетчика 14 и т.д.,первыи информационный вход и-го мультиплексора третьего коммутатора 12соединен с выходом нулевого разрядавторого счетчика 15, второй информационный вход укаэанного мультиплексора - с. выходом и-го разряда первогосчетчика 14,Устройство работает следующим образомм.Информация в двоично-инверсномпорядке, отдельно мнимая и действительная части, занесена во второйблок 2 оперативнои памяти, первый 14и второй 15 счетчики и сдвигающийсчетчик 17 обнулены.Вьполнение итерации быстрого преобразования Фурье заключается в последовательном выполнении в устройстве операция вида В+А 14, где А и Воперанды, извлекаемые из блока оперя724684 10 1520 25 30 35 40 45 50 55г 16 тинной цамя т, Ы - эк сионе цциа.п.цыи ожтел, извлекаемый из блока постояццои памяти. Злеецтарцая операция БПФ осуществляется за четыре такта. В устройстве реализован конвейерный принцип обработки, т.е. данные, подготовленные за четыре такт, первого этапа, заносятся в память за четыре такта второго этапа, а данные, подготовленные на втором этапе, заносятся в память на третьем этапе и т.д., причем после завершения каждой последующеи итерации происходит переключение блоков оперативной памяти (на первой итерации информация считывается из второго блока 2 оперативной памяти, а результаты записываются в первый блок 1 оперативной памяти, на второй итерации, наоборот, считывается из первого 1, эаносится во второи 2) К 1,2=К В +(К А соя(31 - 1 А з гпЯС);м 1 1,2=1 В +(К А зз.пЫс + 1 ЛсозЯ).На выходе 42 блока 8 синхронизации формируется управляющий код, поступающий на управляющие входы первого 13 и третьего 12 коммутаторов, в результате чего к выходам коммутато - ров подключаются их вторые информационные входы. Адреса для считывания операндов формируются ца инфор,ационном выходе первого счетчика 14, адреса для записи операндов формируются на информационном выходе второго счетчика 15, При переключении блоков оперативной памяти изменяются управляющие коды на управляющих входах коммутаторов, в результате чего на адресные входы блоков оперативной памяти поступают либо адреса записи, либо считывания.В первом такте по управляющим сигналам, поступающим с выхода 44 блока 8 синхронизации, из второго блока 2 оперативной памяти считывается действительная часть операндов К А, которая через первый информационный вход коммутатора 10 заносится в регистр 6 и через второй информационный вход коммутатора 11 заносится через первый вход в умножитель 4, на второй вход которого из блока 3 постоянной памяти поступает косинусная составляющая экспоненциального множителя, Во втором такте результат умножения КЕ А созес выхода умножителя 4 заносится в предварит льцо обцу.елцьц накапливающий сумматор 3, одновременно из второго блока 2 оперативной памяти считывается мнимая часть оерада 1 А, которая через первй информационный вход коммутатора 10,и второй информационный вход коммутатора 11 записывается через первый вход в умцожитель 4, на второй вход которого из блока 3 постоянной памяти поступает синусная составляющая экспо енциальог о множителя.В третьем такте результат умножения 1 АзгпЯ с с выхода умножителя 4 заносится в накапливающий сумматор 5, вместе с этим из второго блока 2 оперативной памяти считывается действительная часть следующего операнда Ке В и заносится в регистр 7. Одновременно на второй вход умножителя 4 из блока 3 постоянной памяти поступает косинусная составляющая экспоненциального множителя и происходит умножение мнимой части операнда 1, А, занесенной в умножитель 4 во втором такте, на косинусную составляющую экспоненциального коэффициента 1 А соя(3 СЩВ четвертом такте из регистра 7 действительная часть операнда К В заносится в сумматор-вычитатель 9, и выполняется операция сложения, затем из второго блока 2 оперативной памяти считывается мнимая часть операнда 1 В и заносится в регистр 7, вместе с тем в предварительно обнуленный накапливающий сумматор 5 заносится результат умножения 1 А созЯ 1 с выхода умножителя 4 и из регистра 6, через первый информационный вход коммутатора 11 записывается через первый вход в умноютель 4 значение действительной части операнда К А, на второй вход умножителя 4 поступает значение синусной составляющей экспоненциального коэффициента, а также производится запись в первый блок 1 оперативной памяти действительной части первой точки Кр 1 Кр В + + (К А сояЫС - 1 А з 1 пЯ.) злеементарного преобразования с выхода сумматора-вычитателя 9. На первом такте второго этапа обработки сумматор-вычитатель 9 производит операцию вычитания между теми же операндами, и в первый блок 1 оперативной памяти заносится значение действительной части второй точкиК 2 = К В - (К А совы -1 А в 1 псХ)е е еэлементарного преобразования, вместе с тем в накапливающий сумматор 5 с выхода умножителя 4 записывается ре 5 зультат умножения Кв А в 1 ЯТ, полученный в предыдущем такте обработки, и из второго блока 2 оперативной памяти считывается значение действительной части операнда К А, которое заносится в регистр 6 через первый информационный вход коммутатора 10, и через второй информационный вход коммутатора 11 записывается через первый вход в умножитель 4, на второй вход которого поступает значение косинусной составляющей экспоненциального множителя из блока 3 постоянной памяти.В следующем такте в сумматор-вычитатель 9 из регистра 7 через первый вход заносится значение мнимой части операнда 1 В, через второй вход в сумматор-вычитатель 9 заносится значене 1 А сова С+КА впЯ 25 с выхода накапливающего сумматора 5, затем сумматор-вычитатель 9 заполняет операцию сложения, и значение мнимой части первой точки 11 = 1 В + + (К А вдпЯ+ + 1 А совЯй) злеементаркого преобразования заносится в первый блокоперативной памяти, а также иэ второго блока 2 оперативной памяти извлекается значение мнимой части операнда 1 А и через35 перньй информационньв вход коммутатора 10 и второй информационный вход кочмутатора 11 записывается через первый вход в умножитель 4, на второй вход которого поступает синусная 40 составляющая экспоненциального множителя из блока 3 постоянной паияти, вместе с тем в предварительно обнуленный накапливающий сумматор 5 за носится результат умножения К А соЯс, 5 полученный в предыдущем такте.В третьем такте второго этапа элементарного преобразования из второго блока 2 оперативной памяти считывается действительная часть операн 50 да К В и через первый информационный вход коммутатора 10 заносится в регистр 7, в накапливающий сумматор 5 с выхода умножителя 4 заносит 1ся значение 1 А вдаЯС, полученное в предыдущем такте, на второй вход55 умиожителя 4 из блока 3 постоянной памяти поступает косинусная составляющая экспоненциальной Функции в предьдущеи такте через первый вход в уиножитель было занесено значение 1А ), сумматор-вычитатель 9 производит операцию вычитания между операндами, занесенкыии в него в предыдущем такте, и в первый блок 1 оперативной памяти заносится значение мнимой части второй точки элементарного преобразования 12 = 1 , В -(К А вдпЯС + 1 А совЯТ).В четвертом такте в сумматор-вычитатель 9 через его первый вход из регистра 7 заносится значение К В через второй вход в сумматор-вычитатель 9 заносится содержимое накапливающего сумматора 5, сумматор-вычитатель производит операцию сложения и в первый блок 1 оперативной памяти, записывается значение действительной части Кр 1 = КВ + (К А совЯ1 А вдпЯТ), затеи из второго блока 2 оперативной памяти считывается значение мнимой части операнда 1, В и через первый вход коммутатора 10 заносится в регистр 7, с выхода умножителя 4 значение 1 А сов Ие, полученное в предыдущем такте, заносится в накапливающий сумматор 5. Из регистра 6 через первый информационный вход коммутаторачерез первый вход умножителя 4 заносится значение действительной части КЕ А операнда, на второй вход умножителя поступает значение синусной составляющей экспоненциальной функции из блока 3 постоянной памяти. В дальнейшем до конца итерации обработка происходит аналогично второму такту обработки.После считывания из второго блока 2 оперативной памяти значений действительной и мнимой частей последней пары точек первой итерации и их обработки в течение четырех тактов происходит запись результатов в первый блок 2 оперативной памяти, затем по сигналам, поступающим с выходов 43 и 44 блока 8 синхронизации, происходит переключение блоков оперативной памяти, первый 1 - для чтения, второй 2 - для записи. Импульс, поступающий с выхода переноса второго счетчика 15, поступает на вход сдвигающего счетчика 17, что приводит к тому, что его содержимое сдвигается ка один разргд вправо, а младший разряд заполняется единицей. Преобразованный код с информационного выхода счетчика 17 поступает на второй вход блока 16 эле 1672468ментов И, что приводит к преобразованию кодов, по тупающих на адресный вход блока 3 постоянной памяти,.Все последующие итерации выполняются5 аналогично первои.Блок 8 синхронизации работает следующим образом. 11 риходящий на Вход 54 блока 8 синхронизации пусковой импульс устанавливает первый триггер 18 и через элемент 1 ШИ 24 второй триггер 19. Уровень логической единицы с выхода первого триггера 18 поступает на управляющий вход генератора 21 синхроимпульсов и рдзреп 1 ает его работу, уровень логической единицы с выхода второго триггера 19 открывает элемент И 33, через первый вход которого с первого выхода генератора 21 синхроимпульсов поступают тактовые импульсы на выход 4 1 блока синхронизации, уровень логической единицы с выхода второго триггера 19 сбрасывает третий триггер 20., С третьего выхода генератора 21 синхроимпульсов тактовые импульсы поступают на вход двухразрядного счетчика 23, с четвертого выхода генератора импульсы поступают нд входы элемента И 30.30На первом и втором выходах,ГГву 1- разрядного счетчика 23 последовательно формируются коды соответствующих тактов. На первом такте уровень логического нуля с первого выхо 35 да счетчика 23 поступает на второй инверсный вход элемента И 30, ца первый инверсный вход которого поступает уровень логического нуля с второго выхода счетчика 23, в результате че 40 го тактовый импульс с четвертого выхода генератора 21 синхроимпульсов проходит на выход 46 блока синхронизации, На выходе элемента И 38 формируется уровень логической единицы,45 который поступает на первый вход элемента И 39, на второй вход которого поступают тактовые импульсы с четвертого выхода генератора 21, в результате чего на выходе 53 блока синхронизации формируется импульс50 записи в умножитель 4Затем двухразрядный счетчик 23 переходит в следующее состояние. ВО время второго такта уровень логической единицы с первого выхода двухраз- э 5 рядного счетчика 23 поступает через второй выход блока синхронизации на управляющие входы блока 3 постоянной пдмят ,вбор сов/ЯГВ) ц цдка 1 Яивдющегс льджорд 5 (с Ожеце/вычитание) и цд перые входы э.емецтов И 34, 35, цд Вторые входь которых Нос гупдютсицхро 1 м 11 ульес пятого выхода ген ераторд 21 сицхромпуьеов, с выхода элемента И 34 нд Выход 48 блокасинхроциздциц постуцдют импульсы записи в сумматор-вычитдтель 9, с выхода элемента И 35 - им 11 ульсь обнуления цдкдпливднщего умматорд 5, УроВЕНЬ ЛОГИЧЕСКСИ ЕДИНИЦЫ С ИНВЕРСНОГО выхода третьего триггера 20 поступает на вход одноразрядного счетчика 22, а также ца второй вход элемента И 26, цд второй вход которого поступаетровень логического нуля с инверсного выхода второго триггера 9, в результате чего отпирается элем 1 т И 25 и через его второй вход ца вьход 51 Олоед еицхроц 3:ции цдчиндОт поступатьимпульсы записи В накапливающий сум:дтор 5,ВО время третьего такта уровень логической ед 1 НГГцы с второго выхода двухрдзрядного счетчикд 23 открывает элемент И 31, через который тактовые импульсы с четвертого выхода генератора 21 синхроимпульсов поступают через выход ч 7 блока синхронизации нд вход записи регистра 7, Этот же уровень логической едГццць Устанавливает третий триггер 20. Уровень логическогоУля на первом Выходе двухрдзрядного счетчика 23 здкрывдет э,г 1 е".ец И 38, уровень логическог нуля с выхода этогс элемента блокирует прохождение синхроимпульсовчерез элемент И 39 цд выход 53.Во Время четвертого такта уровеньлогического нуля с инверсного Выходатриггера 20 открывает эле 1:ент И 32,в результате чего чер, Выход 40блока синхронизации проходят сицхроимпульсы с е рв ОГО ВЬ 1 хо,:, 1 ге 11 ерд; Ора21 сицхроимпульсов,На первых трех тдктдх элемецт И 36блокирОВдн урОВнем ;101 ичес 1;ОГО нуляс выхода третьего триггерд 20, начетвертом такте уровень логическойед;11 иц 1 с выхода указанного триггераотпирает элемент И 36, который Всвою Очередь открывает элемент 11 27,с выхода которого синхроимпульсы, поступающие на его второй вход с второго выходд генератора 2 1 синхроимпульсов, поступают на вход дешифрдтора28, с первого либо второго выхода ко 1672468торого через выходы 43 и 44 блока синхронизации импульсы записи поступаютна первый 1 либо второй 2 блоки оперативной памяти. Выбор блоков оперативной памяти осуществляется по импульсам, поступающим с выхода одноразрядного счетчика 22. Эти же импульсы через выход 42 блока синхронизации поступают на управляющие входы первого 10, третьего 12 и четвертого 13 коммутаторов. На четвертомтакте импульс с выхода элемента И 29через выход 50 блока синхронизациипоступает на управляющий вход второго коммутатора 11,До конца одной итерации блоксинхронизации работает аналогично,В конце итерации импульс, поступающий на вход 56 блока синхронизации,сбрасывает второй триггер 19, уровень логического нуля с выхода второго триггера 20 блокирует прохождение тактовых импульсов с первого выхода генератора 21 синхроимпульсовчерез элемент И 33 на выход 41 блокасинхронизации, Затем в течение четырех тактов на соответствующем выходеблока синхронизации формируются импульсы записи в блок оперативной памяти, Уровень логической единицы синверсного выхода второго триггера19 поступает на вход элемента И 26,с выхода которого уровень логической единицы поступает через элементИЛИ .4 на вход второго триггера иустанавпивает его, уровень логической единицы с выхода второго триггера 19 поступает на вход третьеготриггера 20 и сбрасывает его, уровень логической единицы с инверсноговыхода третьего триггера 20 поступает на вход одноразрядного счетчика22 и пе; еводит его в следующее состояние. Уровень логической единицы с выхода счетчика 22 поступает на управляющий вход дешифратора 28, в результате чего второй его выход подключается к входу. Этот же импульс поступает на выход 42 блока синхронизации, в везультате чего происходит переключение блоков оперативной памяти. Если на первой итерации информация считывалась из второго блока оперативной памяти, а запись производилась в пеовый блок, то на второй итерации инйормация считывается из пер 10 15 20 г 5 30 35 40 45 50 55 вого блока, а запись происходит во второй блок оперативной памяти.В дальнейшем блок синхронизации работает аналогично описанному. Формула из обретения Устоойство для реализации быстоого поеобразования Фурье, содержащее пе рвый блок опе рат ив ной п амя ти, два коммутатора, два счетчика, сдвигающий счетчик, блок постоянной памяти, блок элементов И, умножитель, первый конвейерный регистр и блок синхронизации, причем адресный вход первого блока оперативной памяти соединен с выходом первого коммутатора, первый и второй информационные входы которого соединены соответственно с информационными выходами первого и второго счетчиков, счетные входы которых соединены соответственно с первым и вторьм выходами первой группы блока синхронизации, вход запуска которого является входом запуска устройства, управляющий вход первого коммутатора и вход чтения-записи первого блока оперативной памяти соединены соответственно с первым и вторьм выходами второй группы блока синхронизации, первый выход третьей группы которого соединен с входом чтения блока постоянной памяти, адресный вход которого соединен с выходом блока элементов И, первый и второй входы которого соединены соответственно с информационными выходами первого счетчика и сдвигающего счетчика, счетный вход и выход переноса которого соединены соответственно с выходом переноса второго счетчика и выходом останова блока синхронизации, первый и второй информационные входы умножителя соединены соответственно с выходом блока постоянной памяти и выходом второго коммутатора, первый информационный вход которого соединен с выходом первого конвейерного регистра, вход записи которого соединен с вторьм выходом третьей группы блока синхронизации, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия. оно содержит второй блок оперативной памяти, второй конвейерный регистр, третий и четвертый коммутаторы, накапливающий сумматор и сумматор-вычитатль, выход которого соединен с.Данко Техред Л Сердюкона Корректор О.Кранцо едак Заказ 2841 Тираж 388 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКИТ СССР 113035, Москва, Ж, Раушская наВ д, 4/5 твенно-издательский комбинат "Патент", г.ужгород, ул . Гагарина,101 Пр информационными входами первого и второго блокон оперативной памяти и является выходом устройства, адресный вход и вход чтения-записи второго5 блока оперативной памяти соединены соответственно с выходом третьего коммутатора и третьим выходом второй группы блока синхронизации, вход признака режима работы которого соединен 10 с выходом переноса первого счетчика, информационный выход которого и информационный выход второго счетчика соединены соответстненно с первым и вторым информационными входами третье.15 го коммутатора, управляющий вход которого соединен с первым ныходом второй группы блока синхронизации и управляющим входом четвертого коммутатора, первый и второй информационные входы и выход которого соединены соответственно с выходами первого и второго блоков оперативной памяти и информационными входами первого и второго конвейерных регистров, вход записи ивьвод нторого конвейерного регистрасоединены соответственно с третьимвыходом третьей группы блока синхронизации и первым информационным входом сумматора-вычитателя, второй информационный вход, вход синхронизации и вход вида операции которогосоединены соответственно с выходомнакапливающего сумматора, четнертыии пятым ныходами третьей группы блока синхронизации, с шестого по девятый выходы третьей группы которогосоединены соответственно с управляющщ входом второго коммутатора, свходом синхронизации и входом обнуления накапливающего сумматора и свходом синхронизации умножителя,выход которого соединен с информационным входом накапливающего сумматора, второй информационный вход второго коммутатора соединен с выходомчетвертого коммутатора.