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

ния и подключены к входам сумматора по модулю два, выходы разрядов с второго по р-й счетчика тактов являются адресными выходами первой группы блока управления с второго по р-й соответственно, выход сумматра по модулю два подключен к первым входам первых групп первого и второго элементов И-ИПИ, выход р-го разряда счетчика тактов подключен к первым входам вторых групп первого и второго элементов И-ИЛИ,выход младшего разряда счетчика циклов подключен к второму входу второй группы первого элемента И-ИЛИ, к второму входу первой группы второго элемента И-ИЛИ и к входу элемента НЕ, выход элемента НЕ подключен к второму входу первой группы первого элемента И-ИЛИ и к второму входу второй группы второго элемент И-ИЛИ, выходы элементов И-ИЛИ являются адресными выходами второй группы блока управления, выход (p+2-2i)-ro разряда счетчика тактов подключен к информационным входам с номерамиC2(i+K)+4}nwd6 и 2(1-«-к)-«+5 pifld6 (где ,2,3) с-го адресного коммутатора (1-1)-й группы, выход (p-b3-2t)-ro разряда счетчика тактов подключен к информационным входам с номерами C2(v+K) + l3mod6 и. (i+K) 6 к-го адресного коммутатора (1-1)-й группы, выход сумматора по модулю два подключен к информационным входам с номерами t2(i-i-K)mocl6 и 2(i+K) k-ro адресного коммутатора (-1)-й группы, выходы разрядов счетчика циклов подключены к управлякнцим входам всех адресных коммутаторов, выходы адресных Коммутаторов (1-1)-й группы являются адресными выходами (1+1)-й группы блока управления.

УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ. БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки памяти, арифметические блоки и блок управления, причем вы- , ход 1-го ( , объем входной выборки) блока памяти подключен к первому входу -го арифметического блока, вторые входы всех арифметических блоков являются входами весоч вых коэффициентов устройства, выход р/2С-го арифметического блока является выходом устройства, отличающееся тем, что, с целью упрощения устройства, оно содержит 1+ Р/2 коммутаторов, причем первые информационные входы первого и второго коммутаторов подключены к информационному входу устрбйства, выход первого коммутатора подключен к информационному входу первого блока памяти, выход которого подключен к второму информационному входу второго коммутатора, выход второго коммутатора подключен к первому входу первого арифметического блока, выход первого арифметического блока подключен к второму информационному входу первого коммутатора и к первому информационному входу третьего коммутатора, выход (-i+1)-ro коммутатора подключен к информационному входу 1-го блока памяти, выход i-ro арифметического блока подключен к вторым информационным входам (i+1)-ro и (п+2)-го коммутаторов, первый управляющий выход блока управления подключен к первому управляющему входу второго коммутатора, второй управляющий выход блока управления подключен к первому управляющему входу первого коммутатора и к входам управления запись/считывание всех блоков памяти, третий управляющий выход блока управления подключен к вторым входам первого и второго коммутаторов; а также к управляющим входам всех остальных коммутаторов, адресные выходы первой группы блока управления с номерами от 2 до р, кроме номеров p+2-2j, и p+3-2j

Изобретение относится к автомати и вычислительной технике и предназн чено для выполнения алгоритма быстр го преобразования Фурье в устройств цифровой обработки сигналов. Известно устройство для выполнениЯ быстрого преобразования Фурье содержащее последовательно соединен ные запоминающие и арифметические блоки 13 Наиболее близким к изобретению является устройство для выполнения быстрого преобразования Фурье, содержащее последовательно соединенны блок памяти и арифметические блоки, а также блок управления С23. Недостатком известных устройств является их сложность, обусловленная низкой эффективностью использования блоков. Арифметические блоки и блоки памяти простаивают 50% времени работы всего устройства. Целью изобретения является упрощение устройства. Поставленная цель достигается тем, что устройство для выполнения быстрого преобразования Фурье, содержащее блоки, памяти, арифметическ блоки и блок управления, причем выход -го ( , объем входной выборки ) блока памяти подключён к первому входу t-ro арифметического блока, вторые входы всех арифметических блоков являются входами весовых коэффициентов устройства, выход }p/2f -го арифметического блока является выходом устройства, содержит Н jр/2 коммутаторов, причем первые информационные входы первого и второго коммутаторов подключены к информационному входу устройства, .выход первого коммутатора подключен к информационному входу первого блока памяти, выход которого подключен к второму информационному входу второго коммутатора, выход второго коммутатора подключен к первому входу первого арифметического блока, выход первого арифметического блока подключен к второму информационному входу первого коммутатора и к первому информационному входу третьего коммутатора, выход (i+1)-ro коммутатора подключен к информационному входу i-го блока памяти, выход -го арифметического блока подключен к вторым информационным входам (i+1)-ro и (v+2)-ro коммутаторов. управляющий выход блока управления подключен к первому управляющему входу второго коммутатора, второй управляю1ций выход блока управления подключен к первому управляющему входу первого коммутатора и к входам управления запись/считьшание всех блоков памяти, третий управляющий выход блока управления подключен к вторьм входам первого и второго коммутаторов, а также к управляющим входам всех остальных коммутаторов, адресные выходы первой группы блока управления с номерами от 2 до р , кроме номеров p+2-2j и p+3-2jj (j ), подключены к первой группе адресных входов j-ro блока памяти (+1)-я группа адресных выходов блока управления подключена к второй группе адресных входов j-ro блока памяти причем блок управления содержит ге нератор тактов, (p+t)-разрядный счетчик .тактов, счетчик циклов, сумматор по модулю два, два элемента И-ИЛИ, элемент И-НЕ и p/2f -1 групп по три адресных коммутатора, причем выход генератора тактов подключен к входу счетчика тактов, выходы нулевого и первого разрядов (со стороны младших разрядов) счетчика тактов являются соответственно первым и вторым управляющими выходами блока управления и подключены к входам сумматора по модулю два, выходы разрядов с второго по р-й счетчика тактов являются адресными выходами первой группы блока управления с второго по р-й соответственно, выход сумматора по модулю два подктоочен к первым входам первых групп первого и второго элементов И-ИЛИ, выход р-го разряда счетчика тактов подключен к первым входам вторых групп первого и второго элементов И-ШШ, выход младшего разряда счетчика циклов подключен к второму входу второй группы первого элемента И-ИЛИ, к второму входу первой группы второго элемента И-ИЛИ и к вхо ду элемента НЕ, выход элемента НЕ подключен к второму входу первой группы первого элемента И-ИЛИ и к второму входу второй.группы второго элемента И-ИЛИ,выходы элементов И-ИЛИ являются адресными выходами второй группы блока управления, выход (р+22г)го разряда счетчика тактов подключен к информационным входам с но мерами ( 2(i+K)+4ftnoel6 и 2 (1-ьк)+53 moiJ6 (где ,2,3( к-го адресного 10 37 коммутатора ({-1)-й группы, выход (p+3-2i)-ro разряда счетчика тактов подключен к информационным входам с номерами 2 (i+k) + и 2(+к)-«+2 то 3б k-ro адресного коммутатора (1-1)-и группы, выход сумматора по модулю два подключен к информационным входам с номерамио f2 х (i+K)mod 6 и 2 (I+K) +3j «iod6 к-го адресного коммутатора (1-1)-й группы, выходы разрядов счетчика циклов подключены к управляющим входам всех адресных коммутаторов, выходы адресных коммутаторов (1-1)-й группы являются адресными выходами (1+1)-й группы блока управления. На фиг.1 представлена функциональная схема устройства; на фиг.2 граф алгоритма быстрого преобразования Фурье над 32-точечными массивами да-нных. Уст)ойство содержит генератор 1 тактов, блок 2 управления, блоки 3,1-ЗЗр/2С. памяти, арифметические блоки 4,t-4.p/2, коммутаторы 5,15. р/2, 6, счетчик 7 тактов, сумматор по модулю два 8, адресные коммутаторы 9 элементы 10 и Т1 И-ИЛИ, счетчик 12 циклов, элемент 13 НЕ. Устройство работает следующим образом.: Выполнение алгоритма, как видно из фиг.2, состоит в вычислении р 86g2N 5 итераций, каждая из которых содержит базовых операций вида N «,S,n где dp- операнды} г - номер узла графа, S - ном,ер итерации (s 1, 2,, . .,р); I - номер выходной последовательности. Операции (1) выполняются арифметическими блоками 4, каждый из которых может состоять, например, из сумматора-вычитателя и умножителя комплексных чисел. Выполнение алгоритма быстрого преобразования Фурье над 32-точечными массивами потребует каскада, а также шестиразрядный счетчик 7 тактов. Примем, что щаг работы устройства образуют четьфе такта работы счетчика 7, цикл работы устройства - шагов. В исходном положении счетчик 7 тактов, счетчик 12 циклов находятся в нулевом состоянии. С началом работы импульсы с генератора 1 тактов поступают на вход счетчика 7, исходные данные«jj последовательности поступают на вход устройства. Частота поступления исходных данных в 4 раза меньше частоты генератора 1 тактов. Первый цикл работы устройства состоит в . запи:си исходных данных по в блок 3.1 памяти первого каскаца.счи0,1 0.1 тывании операндов а ,о( предьщуще I йоследовательности 6 0 из блока 3.1 памяти для вьшолнения второй итерации, а также в записи результатов 0,2 „0,2 выполнения второй итераци в блок 3.2 памяти второго каскада. Для этого в первом такте каждого шага (номер такта соответствует состоянию 0-го и 1-го разрядов счетчика 7 тактов плюс единица) операнд 0,1 с .у. считывается из блока 3.1 памя п+ по адресу (l поступает через коммутатор 6 в арифметический блок 4.1, где выполняется операция n..п Во втором такте каждого шага операнд считывается из блока 3.1 памяти, по адресу через коммутатор 6 поступает также в арифметический блок 4.1. При этом на входах управления записью/считывание блоков 3.1-3 p/2t памяти присутствует значение О, которое соответствует режиму считывания. На управляющих входах коммутатора 6 в первом такте присутствует код . ОС, во втором - код 10. Эти значения разрешают прохождение операндов с выхода блока 3.1 памяти на вход арифметического блока 4.1. В третьем такте каждого шага исходный операнде последовательности 1 через коммутатор 5.1 поступает на вход блока 3.t памяти и записывается с замещением по адресуД .(пЬПрохождение операндаа на вход блока 3.1 памяти обеспечивает код 10 на управляющих входах коммутатора 5.1, запись операнда блок памяти 3.1 разрешает значение 1 на входе управления записью/считыванием. В этом же такте на каждом шагу результат выполнения базовой операции dj второй итерации последовательности в 0 появляется на выходе арифметического блока 4.1 и, пройдя через коммутатор 5.2, запишется в блок 3.2 памяти второго каскада по адресу Лз, четвертом такте каждого шага на выходе арифметического блока 4.1 появляется результат выполнения ба 1 который, пройдя зоной операции сц через коммутатор 5,2, запишется .., в блок 3.2 памяти по адресу .2ит() На управляющем входе коммутатора 5. при этом присутствует нулевое значение. Адреса формируются из разрядов счетчика 7 тактов, выходов элементов И-ИЛЙ ,коммутаторов 9, на управляющих входах которых- присутствует код 000. Записью результата заканчивается первый цикл работы устройства. Сигнал переполнения счетчика 7 тактов изменяет состояние счетчика t2 циклов на 001. В таблице приведены состояния на управляющих входах коммутаторов 5.1; 6; 5.2 - 5.3 на входе управления записью/считыванием блоков памяти, выполняемые при этих состояниях функции.

.т

управляющих входов

О

О 1

1

Состояние управляющих входов VI V2

О

О

О

Состояние управляющего входа

-----

Коммутатор 5.1

Выполняемая функция

X

прохождение исходных данных

Прохождение результатов выполнения ,1-й итерации д,. с выхода арифметип ..N I 2 ческого блока 4.1 на вход блока памяти 3 . Г

Коммутатор 6

Г функция

Вьтолняемая

С,1 Прохождение операнда,

с выхода блока памяти 3.1 на вход арифметического устройства 4.1

Прохождение операнда а с вьргода блока памяти 3.. 1 на вход арифметического блока 4.1

J Л

Прохождение операндов сх .

П4М

второй половины входной последовательности устройства на вход арифметического блока 4.1

Прохождение операндов а с выхода блока памяти 3.1 на вход арифметического блока 4.1

Коммутаторы 5.2-5.3p/2L

Вьтолняемая функция

Прохождение операндов с выхода арифметического блока i-го каскада на ВХОД блока памяти 1-го х каскада

Прохождение операндов с выхода арифметического блока i-ro каскада на вход блока памяти (i-H)-ro каскада Вход управления записью/считьгоанием Состояние j

О Второй цикл работы устройства состоит в выполнении первой итерации алгоритма быстрого преобразования Фурье над последовательностью в первом каскаде и итерации последовательности- t 0 - во втором каскаде. Для этого в первом такте каждого шага операнд ...fiiy с входа (стройства через коммутатор 6 поступает в арифметический блок А .J, где выполняется операUHHC.J.W, во втором каскаде в каждом первом такте шага выполняется считывание операнда блока 3.2 па адресу;А, который затем поступает варифметический блок 4.2, где выполняется операция ,-3 Во втором -to такте каждого шага операнд с считывается из блока 3.1 памяти по адресу АСЧИТ ИТ и через коммутатор 6 поступает на вход арифметического блока 4.1 во втором каска де выполняется считьгоание операнда о(г( из 3.2 памяти по адресу Л 3 JhJ и передача его в арифметический блок 4.2. В третьем такте каждого шага результаты выполнения базовых операций ,а пройдя через коммутаторы 5.1 и 2, записы ваются в блоки 3,1 и 3,2 памяти по адресам А, . -.(nljAf (nf соответствен но. В четвертом такте каждого шага результаты выполнения базовых oneраций а с ,., пройдя через комм таторы 5.1 и 5,2, записываются в блоки 3.1 и 3;2 памяти по адресам .1.г(). ( соответственно. . Сигнал переполнения счетчика 7 тактов изменяет состояние счетчика 12 циклов на 010. Третий цикл работы устройства состоит в считывании операндов и .записи -результатов выполнения чет1086437

10 Продолжение таблицы

Разрешение считывания блоков памяти 3.1 ЗЗр/2 Выполняемая функция шение записи вертой итерации последовательности , считывании операндов и записи результатов выполнения второй итерации последовательности 1, а в записи первой половины исходных данных последовательности 2 Я Записью результатов и J заканчивается третий цикл работы устройства. Сигнал переполнения счетчика 7 тактовых импульсов изменяет состояние счетчика 12 циклов на 011. Четвертый цикл работы устройства состоит в выполнении пятой итерации над последовательностью t 0 в третьем каскаде, третьей итерации над последовательностью во втором каскаде и первой итерации над последовательностью И 2 в первом каскаде. Выполнение первой итерации последовательности С 2 аналогично выполнению первой итерации последовательности С 1. Пятый цикл работы устройства (состояние счетчика 12 циклов 100) состоит в выполнении считывания результа-. тов вычисления алгоритма быстрого преобразования Фурье последовательности из блока памяти 3.3, считывании операндов и записи результатов вь1числения четвертой итерации последовательности Е 1, считывании операндов и записи результатов вычисления второй итерации последовательности , а также в записи первой половины исходных данных очередной последовательности . Шестой цикл работы устройства состоит в выполнении пятой итерации над последовательностью в третьем каскаде, третьей итерации над последовательностью- 2 во втором каскаде и первой итерации над последовательностью Е 3 в первом каскаде. Сигнал переполнения счетчика 7 тактовых импульсов изменяет состояние счетчика 12 циклов на 000. Дальнейшее выполнение циклов устройства аналогично первым шести. Адресация для

tt. 108643712

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