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

(71) Киевский ордена "Ленина политехнический институт им. 50-летия Великой Октябрьской Социалистическойреволюции(54)(57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки памяти, арифметическиеблоки и блок управления, причем выход 1-го (1=2-3 р/2 Г,2- объем входной выборки) блока памяти подключенк первому входу 1-го арифметическогоблока, вторые входы всех арифмети"ческих блоков являются входами весовьм коэффициентов устройства, выход1 р/21-го арифметического блока является выходом устройства, о т л и -ч а ю щ е е с я тем, что, с цельюупрощения устройства, оно содержит1+ 1 р/2 коммутаторов, причем первыеинформационные входы первого и второго коммутаторов подключены к информационному входу устройства, выход первого коммутатора подключен к информационному входу первого блока памяти,выход которого подключен к второмуинформационному входу второго коммутатора, выход второго коммутатора подключен к первому входу первого арифметического блока, выход первогоарифметического блока подключен квходу п информа утатора а по к второму информационному ервого коммутатора и к первому ционному входу третьего комм выход (1+1)-го коммутатор д лючен к информационному входу 1-го блока памяти, выход 1-го арифметического блока подключен к вторым информационным входам (1+1)-го и (1+2)-го коммутаторов, первый управляющий выход блока управления подключен к первому управляющему входу второго коммутатора, второй управляющий выход блока управления подключен к первому управляющему входу первого коммутатора и к входам управления запись/считывание всех блоков памяти, третий управляю- а щий выход блока управления подключен к вторым входам первого и второго коммутаторов, а также к управляющим входам всех остальных коммутаторов, адресные выходы первой группы блокауправления с номерами от 2 .й- до р, кроме номеров р+2-21, и р+3-21 ( =1 3 р/2) подключены к первой СР группе адресных входов 1-го блока 00 памяти, (+1) -я группа адресных выходов блока управления подключена к второй группе адресных входов 1-го блока памяти, причем блок управления фф содержит генератор тактов, (р+1)- ф 3 разрядный счетчик тактов, счетчик циклов, сумматор по модулю два, два элемента И-ИЛИ, элемент НЕ и 1 р/2 -1 групп по три адресных коммутатора, причем вьмод генератора тактов подключен к входу счетчика тактов, выходы нулевого и первого разрядов (со стороны младших разрядов) счетчика тактов являются соответственно первым и вторым управляющими выходами блока управле1086437 ния и подключены к входам сумматорапо модулю два, выходы разрядов свторого по р-й счетчика тактов являются адресными выходами первойгруппы блока управления с второгопо р-й соответственно, выход сумматора по модулю два подключен к первым.входам первых групп первого и второго элементов И-ИЛИ, выход р-горазряда счетчика тактов подключенк первым входам вторых групп первого и второго элементов И-ИЛИ,выходмладшего разряда счетчика цикловподключен к второму входу второйгруппы первого элемента И-ИЛИ, квторому входу первой группы второгоэлемента И-ИЛИ и к входу элементаНЕ, выход элемента НЕ подключенк второму входу первой группы первого элемента И-ИЛИ и к второмувходу второй группы второго элементаИ-ИЛИ, выходы элементов И-ИЛИ яв 1Изобретение относится к автоматике и вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье в устройствахфцифровой обработки сигналов.Известно устройство для выполнения быстрого преобразования Фурье, содержащее последовательно соединенные запоминающие и арифметические блоки 1Наиболее близким к изобретению10 является устройство для выполнения быстрого преобразования Фурье, содержащее последовательно соединенные блок памяти и арифметические. блоки,а также блок управления 1 21.15Недостатком известных устрдйств является их сложность, обусловлен-, ная низкой эффективностью использования блоков. Арифметические блоки и блоки памяти простаивают 50% времени работы всего устройства.Целью изобретения является упрощение устройства.Поставленная цель достигается25 тем, что устройство для выполнения быстрого преобразования фурье, содержащее блоки. памяти, арифметические блоки и блок управления, причем выляются адресными выходами второйгруппы блока управления, выход(р+2-21)-го разряда счетчика тактовподключен к информационным входамс номерами 2(1+к)+41 еод 6 и 2(1+к)++51 вЫ 6 (где к 1,2,3) к-го адресного коммутатора (1-1)-й группы,выход (р+Э)-го разряда счетчикатактов подключен к информационнымвходам с номерами 2(1,+к)+13 вод 6и,1 2(+к)+2 1 еад 6 к-го адресногокоммутатора О -1)-й группы, выходсумматора по модулю два подключенк информационным входам с номерами2(1+к)1 щод 6 и 2(+к)+ЗФод 6 Й-гоадресного коммутатора (1-1)-й группы, выходы разрядов счетчика цикловподключенык управляющим входамвсех адресных коммутаторов, выходыадресных коммутаторов (1-1)-йгруппы являются адресными выходами(1+1)-й группы блока управления. 2ход 1-го (1=2-р/2 ,2 - объем входной выборки ) блока памяти подключен к первому входу 1-го арифметического блока, вторые. входы всех арифметических блоков являются входами весовых коэффициентов устройства, выход 1 р/2 -го арифметического блока является выходом устройства, содержит 1+ 1 р/2 коммутаторов, причем первые информационные входы первого и второго коммутаторов подключены к информационному входу устрой" ства, выход первого коммутатора подключен к информационному входу первого блока памяти, выход которого подключен к второму информационному входу второго коммутатора, выход второго коммутатора подключен к первому входу первого арифметического блока, выход первого арифметического блока подключен к второму информационному входу первого коммутатора и к первому информационному входу третьего коммутатора, выход (1+1)-го коммутатора подключен к информационному входу 1-го блока памяти, выход -го арифметического блока подключен к вторым информационным входам (1+1)-го и (1+2)-го коммутаторов,31 Ь 864 первый управляющий выход блока управления подключен к первому управляющему входу второго коммутатора, второй управляющий выход блока управления подключен к первому управляющему входу первого коммутатора и к входам управления запись/считывание всех блоков памяти, третий управляющий выход блока управления подключен к вторым входам первого и второго коммутаторов, а также к управляющим входам всех остальных коммутаторов, адресные выходы первой группы блока управления с номерами от 2 до р , кроме номеров р+2-2 и р+3-2 р (1 =1-3 р/2), подключены к первой груп 15 пе адресных входов 1-го блока памяти, +1)-я группа адресных выходов блока управления подключена к второй группе адресных входов -го блока памяти, причем блок управления содержит ге- нератор тактов, (р+1)-разрядный счетчик,тактов, счетчик циклов, сумматор по модулю два, два элемента И-ИЛИ, элемент И-НЕ и р/21 -1 групп по три.25 адресных коммутатора, причем вьмод генератора тактов подключен к входу счетчика тактов, выходы нулевого и первого разрядов (со стороны младших разрядов) счетчика тактов являются соответственно первым и вторым управ-ЗО ляющими выходами блока управления и подключены к входам сумматора по модулю два, выходы разрядов с второго по р-й счетчика тактов являются адресными выходами первой группы- блока 35 управления с второго по р-й соответственно, выход сумматора по модулю два подключен к первым входам первьм групп первого и второго элементов И-ИЛИ, выход р-го разряда счетчика 40 тактов подключен к первым входам вторых групп первого и второго элементов И-ИЛИ, выход младшего разряда счетчика циклов подключен к второму входу второй группы первого эле мента И-ИЛИ, к второму входу первой группы второго элемента И-ИЛИ и к входу элемента НЕ, выход элемента НЕ . подключен к второму входу первой группы первого элемента И-ИЛИ и к 50 второму входу второй группы второго элемента И-ИЛИ,выходы элементов И-ИЛИ являются адресными выходами второй группы блока управления, выход (р+2- 2)-го разряда счетчика тактов под ключен к информационным входам с номерами2(1+к)+4 водб и 1 2 (1+к)+5 афтаб (где к=1,2,3( к-го адресного 37 4коммутатора (1-1)-й группы, выход (р+3-21)-го разряда счетчика тактов подключен к информационным входам с номерами 2 (1+к)+11 вос 36 и2(%+к)+ +2 водб к-го адресного коммутатора 1 (1.-1)-й группы, выход сумматора по модулю два подключен к информационным входам с номерами.2 к (1+к)вод 6 и 2 (1+к) +Звех 36 к-го адресного коммутатора (1-1)-й группы, выходы разрядов счетчика циклов под" ключены к управляющим входам всех адресных коммутаторов, выходы адресных коммутаторов (-1)-й группы являются адресными выходами (1+1)-й группы блока управления.На фиг.1 представлена функциональная схема устройства; на фиг.2 - граф алгоритма быстрого преобразования Фурье над 32-точечными массивами данных.Устройство содержит генератор 1 тактов, блок 2 управления, блоки 3, 1-3 3 р/21 . памяти, арифметические блоки 4, 1-4.1 р/2, коммутаторы 5, 1- 5. 1 р/2, 6, счетчик 7 тактов, сумматор по. модулю два 8, адресные коммутаторы 9 элементы 10 и 11 И-ИЛИ, счетчик 12 циклов, элемент 13 НЕ,Устройство работает следующим образом.Выполнение алгоритма, как видно из фиг.2, состоит в вычислении р= = 608 =5 итераций, каждая из которых содержит К/216 базовых операций видаа,М ЕД а,5,.6= а+о+ и и и 25%1,11Ю,Ь+ й Ю,5 Д,б М б дс + - =с -а + Фг 1 2 з г 1 и 25гдеап- операнды,ь - номер узла графа;- номер итерации (э =1, 2, р);1 - номер выходной последовательности.Операции (1) выполняются арифметическими блоками 4, каждый из которых может состоять, например, из сумматора-вычитателя и умножителя комплексных чисел.Выполнение алгоритма быстрого преобразования Фурье над 32-точечными массивами потребует 3 р/2=3 каскада, а также шестиразрядный счетчик 7 тактов, Примем, что шаг работы устройства образуют четыре такта работы счетчика 7, цикл работы устфройства - й/2=16 шагов. В исходномО,1 И (2(о 2 Р 35 Ф 10864 положении счетчик 7 тактов, счетчик 12 циклов находятся в нулевом состоянии. С началом работы импульсы с генератора 1 тактов поступают на вход1,О счетчика 7, исходные данныеа последовательности С =1 поступают на вход устройства. Частота поступления исходных данных в 4 раза меньше частоты генератора 1 тактов. Первый цикл работы устройства состоит в 01,О записи исходных данных са 1(О по а "( в блок 3,1 памяти первого каскаца,счи 0(1 О(1тывании операндова ,с 1при 1М. -.р15 йоследовательности 6 =0 из блока 3. 1 памяти для выполнения второй итерации, а также в записи результатов о ,авыполнения второй итерации 200,2 0,2о(.2в блок 3,2 памяти второго каскада.Для этого в первом такте каждого шага (номер такта соответствует сос 25 тоянию 0-го и 1-го разрядов счетчика 7 тактов плюс единица) операнд0,1Ю 4 считывается нз блока 3,1 памятии+ т2по адресу А2 а+ -и поступаетЙ 30 через коммутатор 6 в арифметический блок 4.1, где выполняется операция Во втором такте каждого шага операнд бсчитывается из блока 3.1 па 01омяти. по адресу А 2, Ь 1 и через40 коммутатор 6 поступает также в арифметический блок 4. 1. При этом на входах управления записью/считыванием блоков 3.1-3 3 р/21 памяти присутствует значение О, которое соответствует режиму считывания. На управляющих входах коммутатора6 в первом такте присутствует код 37 бОС, во втором - код 10. Эти значенияразрешают прохождение операндов свыхода блока 3.1 памяти на вход арифметического блока 4. 1.В третьем такте каждого шага исходный операнда( последовательностии1=1 через коммутатор 5.1 поступаетна вход блока 3. 1 памяти и записывается с замщни по адресуАЗ ск(п 1.ПРО 10(хождение операндао на вход блокаи3, 1 памяти обеспечивает код 10 науправляющих входах коммутатора 5. 1,запись операнда О 1 п(0 в блок памяти 3. 1разрешает значение 1 на входе управления записью/считыванием,В этом же такте на каждом шагу результат выполнения базовой операциид второй итерации последовательнос 0,2оти 0 =0 появляется на выходе арифметического блока 4,1 и, пройдя черезкоммутатор 5.2, запишется в блок 3.2памяти второго каскада по адресуДп 1.В четвертом такте каждого шагана выходе арифметического блока 4, 1появляется результат выполнения ба 0,2зовой операции о 1 1,( который, пройдя1+ мм 22через коммутатор 5,2, запишетсяв блок 3. 2 ламяти ло аЛРеоу Я( т мт( тя)На управляющем входе коммутатора 5.2 Япри этом присутствует нулевое значение.Адреса формируются из разрядовсчетчика 7 тактов, выходов элементов И-ИЛИ,коммутаторов 9, на управляющих входах которых присутствует код 000,о,гЗаписью результата 631 заканчивается первый цикл работы устройства.Сигнал переполнения счетчика 7 тактов изменяет состояние счетчика 12циклов на 001.В таблице приведены состоянияна управляющих входах коммутаторов51; 6; 5,2 " 5.3 на входе управ"ления записью/считыванием блоковпамяти, выполняемые при этих состояниях функции,,+21 гческого блока 4.1 на вход блока памяти 3.1 Коммутатор 6 О 0 Цля вы- полне 0 0 Коммутаторы 5.2-5.р/2 Г Выполняемая функция О Состояние управляющих входов Состояние управляющих входов Ч 1Ч 2 Состояние управляющего входа Прохождение исходных данных Выполняемая функция й,1 Прохождение операнда.ю с выхода блока памяти 3.1 на вход арифметического устройства 4.1 Прохождение операнда а8,1 с выхода блока памяти 3,.1 на входарифметического блока 4.1 И,о Прохождение операндов ФмЙР второй половины входной последовательности устройства на входарифметического блока 4.1 Прохождение операндов афс выхода блока памяти3.1 на вход арифметического блока 4. 1 Прохождение операндов свыхода арифметическогоблока -го каскада навход блока памяти 1-гокаскада Прохождение операндовс выхода арифметическогоблока 1-го каскада на входблока памяти О +)-гокаскада ниявторойитерации1086437 10Продолжение таблипы Вход управления записью/считыванием блоков памяти 3.1-3 1 р/2 Выполняемая функция Состояние Разрешение считывания 0 Разрешение записи 10 50 Второй цикл работы устройства состоит в выполнении первой итерации алгоритма быстрого преобразования фурье над последовательностьюв первом каскаде и трееьей ите 15 рации последовательности 1 =0 - во втором каскаде. Для этого в первом1,а такте каждого шага операнд б 1 с входа устройства через коммутатор 6 поступает в арифметический20 блок 4. 1, где выполняется операция а 1щ , во втором каскаде1,Ои+ й 2в каждом первом такте шага выпол-, няется считывание операнда а +рго,а блока памяти 3,2 по адресу,.АдтЗдть+ Э 25 который затем поступает в арифметический блок 4.2, где выполняется0,2 . 5 фоперация Ю2 Э Ю;, Во второмь+й 2такте каждого шага операнд д О считывается из блока 3. 1 памяти по адресу Асцит 1 ит "1 и через коммутатор б поступает на вход арифметического блока 4, 1 во втором каска- де выполняется считывание операнда б из блбка 3.2 памяти по адресу о,гЯф 3 (и 1 и передача его в арифметисцигитческий блок 4.2. В третьем такте каждого шага результаты выполнения базовых операций цф 1 т проидя 4011 0,3з через коммутаторы 5. 1 и .2, записываются в блоки 3, 1 и 3, 2 памяти по адресам Я (о 1 А (п 1 соответственЗе 1 итЗ,эитно. В четвертом такте каждого шага результаты выполнения базовых опе. 0,раций 6р,пройдя через комму-.и+и+ -г 23 таторы 5. 1 и ,2, записываются вблоки 3. 1 и 3 2 памяти по адресамя, ,(мяг), я ,(п+ и)а)соответственно.Сигнал переполнения счетчика 7тактов изменяет состояние счетчика12 циклов на 010.Третий цикл работы устройствасостоит в считывании операндов и.записи"результатов выполнения четвертой итерации последовательности 1=0, считывании операндов и записи результатов выполнения второй итерации последовательности 9 =1, а также в записи первой половины исходных данных последовательности Г =2 и т.д.Записью результатов д Э дзО,Ф 1,2 заканчивается третий цикл работы устройства. Сигнал переполнения счетчика 7 тактовых импульсов изменяет состояние счетчика 12 циклов на 011.Четвертый цикл работы устройства состоит в выполнении пятой итерации над последовательностью Ф =0 в третьем каскаде, третьей итерации над последовательностью 0 =1 во втором каскаде и первой итерации над после" довательностью 6 =2 в первом каскаде, Выполнение первой итерации последовательности 8 =2 аналогично выполнению первой итерации последовательности 9 1.Пятый цикл работы устройства (состояние счетчика 12 циклов 100) состоит в выполнении считывания результа-. тов вычисления алгоритма быстрого преобразования фурье последовательнос-. ти 6 0 из блока памяти 3,3, считывании операндов и записи результатов вычисления четвертой итерации последовательности 6=1, считывании операндов и записи результатов вычисления второй итерации последовательности =2, а также в записи первой половины исходных данных очередной последовательности 0=3.Шестой цикл работы устройства состоит в выполнении пятой итерации над последовательностью 1 =1 в третьем"каскаде, третьей итерации над последовательностью=2 во втором каскаде и первой итерации над последовательностью 1=3 в первом каскаде,Сигнал переполнения счетчика 7 тактовых импульсов изменяет состояние счетчика 12 циклов на 000. Дальнейшее выполнение. циклов устройства аналогично первым шести. Адресация для11 , 90864 операндов следующих последовательностей повторяется с периодом 3,Упрощение конструкции предлагаемого устройства по сравнению,с извест 37 12ным (при равной производительности) обусловлено одновременной загрузкой большего числа блоков, т.е. большей эффективностью их использования,