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

 

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

(21), 3400965/18-24 (22) 25.02.82 (46) 15.04.84. Бюл,¹-14 (72) 10.С. Каневский, Н.Е.Куц, Б.А. Некрасов и О.А. Федотов (71) Киевский ордена "Ленина политехнический институт им. 50-летия Великой Октябрьской Социалистической революции (53) 681.3(088.8) (56) 1 Патент США ¹3588460, кл. Я 06 F 7/38, 1968.

2. Патент США №3702393, кл. G 06 F 7/38, опублик. 1973 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки памяти, арифметические блоки и блок управления, причем выход -го (i =2-Зр/2Г,2 - объем входной выборки) блока памяти подключен к первому входу i-го арифметического блока, вторые входы всех арифметических блоков являются входами весо выл коэффициентов устройства, выход

3p/2Ã-ro арифметического блока является выходом устройства, о т л и— ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит

1+ ) р/2(коммутаторов, причем первые информационные входы первого и второго коммутаторов подключены к информационному входу устройства, выход первого коммутатора подключен к информационному входу первого блока памяти, выход которого подключен к второму информационному входу второго коммутатора, выход второго коммутатора подключен к первому входу первого арифметического блока, выход первого арифметического блока подключен к второму информационному входу первого коммутатора и к первому информационному входу третьего коммутатора, выход (1+1)-го коммутатора подключен к информационному входу i-го блока памяти, выход i-ro арифметического блока подключен к вторым информационным входам (i+1)-ro и (i +2)-ro коммутаторов, первый управляющий выход блока .управления подключен к первому управляющему входу второго коммутатора, второй управляющий выход блока управления подключен к первому управляющему входу первого коммутатора и к входам управления запись/считывание всех блоков памяти, третий управляю- а щий выход блока управления подключен к вторым входам первого и второго коммутаторов, а также к управляющим входам всех остальных коммутаторов, С адресные выходы первой группы блока управления с номерами от 2 до р, кроме номеров р+2-21, и р+3-2j

-() = 1- ) р/2 () подключены к первой Ю группе адресных входов 1-ro блока 00 памяти, (j+1) -я группа адресных выходов блока управления подключена к второй группе адресных входов j-го блока памяти, причем блок управления содержит генератор тактов, (р+1)- 3 разрядный счетчик тактов, счетчик циклов, сумматор по модулю два, два элемента И-ИЛИ, элемент НЕ и )р/2(-1 групп по три адресных коммутатора, причем выход генератора тактов подключен к входу счетчика тактов, выходы нулевого и первого разрядов (со стороны младших разрядов) счетчика тактов являются соответственно первым и вторым управляющими выходами блока управле1086437 ния и подключены к входам сумматора по модулю два, выходы разрядов с второго по р-й счетчика тактов являются адресными выходами первой группы блока управления с второго по р-й соответственно, выход сумматора по модулю два подключен к первым. входам первых групп первого и второго элементов И-ИЛИ, выход р-ro разряда счетчика тактов подключен к первым входам вторых групп первого и второго элементов И-ИЛИ,выход младшего разряда счетчика циклов подключен к второму входу второй группы первого элемента И-ИЛИ, к второму входу первой группы второго элемента И-HJIH и к входу элемента

НЕ, выход элемента НЕ подключен к второму входу первой группы первого элемента И-ИЛИ и к второму входу второй группы второго элемента

И-ИЛИ, выходы элементов И-ИЛИ яв1

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

Известно устройство для выполнения быстрого преобразования Фурье, содержащее последовательно соединенные запоминающие и арифметические блоки (1), Наиболее близким к изобретению

10 является устройство для выполнения быстрого преобразования Фурье, содержащее последовательно соединенные блок памяти и арифметические. блоки, а также блок управления 1 21.

Недостатком известных устройств является их сложность, обусловлен-, ная низкой эффективностью использования блоков. Арифметические блоки и блоки памяти простаивают 50% времени работы всего устройства.

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

Поставленная цель достигается

25 тем, что устройство для выполнения быстрого преобразования фурье, содержащее блоки. памяти, арифметические блоки и блок управления, причем выляются адресными выходами второй группы блока управления, выход (р+2-21)-го разряда счетчика тактов подключен к информационным входам с номерами (2(i)+4)d6 и (2(i+ê)+

+5)tnod6 (где к 1,2,3) к-го адресного коммутатора (i-1)-й группы, выход (р+3-2i)-го разряда счетчика тактов подключен к информационным входам с номерами $2(i+re)+1)mod 6 и, $2(i+re)+2) mod 6 к-го адресного коммутатора (i -1)-й группы, выход сумматора по модулю два подключен к информационным входам с номерами

f2(i+K))t110c1 6 и $2(i+re)+3)tncd6 Й-го адресного коммутатора (3 1)-й группы, выходы разрядов счетчика циклов подключены к управляющим входам всех адресных коммутаторов, выходы адресных коммутаторов (i-1)-й группы являются адресными выходами (i +1)-й группы блока управления.

2 ход i-ro (i =2- 1 р/2 (, 2 — объем входной выборки ) блока памяти подключен к первому входу i-го арифметического блока, вторые. входы всех арифметических блоков являются входами весовых коэффициентов устройства, выход 1р/2(-го арифметического блока является выходом устройства, содержит 1+ ) р/2(коммутаторов, причем первые информационные входы первого и второго коммутаторов подключены к информационному входу устройства, „выход первого коммутатора подключен к информационному входу первого блока памяти, выход которого подключен к второму информационному входу второго коммутатора, выход второго коммутатора подключен к первому входу первого арифметического блока, выход первого арифметического блока подключен к второму информационному входу первого коммутатора и к первому информационному входу третьего коммутатора, выход (i+1)-го коммутатора подключен к информационному входу i-ro блока памяти, выход )-го арифметического блока подключен к вторым информационным входам (» +1)-ro и (i+2)-го коммутаторов, 3 1Ь864 первый управляющий выход блока управления подключен к первому управляющему входу второго коммутатора, второй управляющий выход блока управления подключен к первому управляющему входу первого коммутатора и к входам управления запись/считывание всех блоков памяти, третий управляющий выход блока управления подключен к вторым входам первого и второго коммутаторов, а также к управляющим входам всех остальных коммутаторов, адресные выходы первой группы блока управления с номерами от 2 до р, кроме номеров р+2-2 и р+3-21, (y =1-) р/2(), подключены к первой груп15 пе адресных входов j-ro блока памяти, (j+1) ÿ группа адресных выходов блока управления подключена к второй группе адресных входов g-ro блока памяти, причем блок управления содержит генератор тактов, (р+1)-разрядный счетчик .тактов, счетчик циклов, сумматор по модулю два, два элемента И-ИЛИ, элемент И-НЕ и )р/2(-1 групп по три .25 адресных коммутатора, причем выход генератора тактов подключен к входу счетчика тактов, выходы нулевого и первого разрядов (со стороны младших разрядов) счетчика тактов являются соответственно первым и вторым управ-ЗО ляющими выходами блока управления и подключены к входам сумматора по модулю два, выходы разрядов с второго по р-й счетчика тактов являются адресными выходами первой группы- блока 35 управления с второго по р-й соответственно, выход сумматора по модулю два подключен к первым входам первьм

Ф групп первого и второго элементов

И-ИЛИ, выход р-го разряда счетчика 40 тактов подключен к первым входам вторых групп первого и второго элементов И-ИЛИ, выход младшего разряда счетчика циклов подключен к второму входу второй группы первого эле- 45 мента И-ИЛИ, к второму входу первой. группы второго элемента И-ИЛИ и к входу элемента НЕ, выход элемента НЕ, подключен к второму входу первой группы первого элемента И-ИЛИ и к 50 второму входу второй группы второго элемента И-ИЛИ,выходы элементов И-ИЛИ являются адресными выходами второй группы блока управления, выход (р+2-

2i)-го разряда счетчика тактов под- 55 ключен к информационным входам с номерами 2(i+z)+4(tnod6 и (2 (i+K)+5)

tttee!6 (где к=1,2,3(к-го адресного

37 4 коммутатора (t-1)-й группы, выход (р+3-2 i) -ro разряда счетчика тактов подключен к информационным входам с номерами t2 (i+к)+1)юлос76 и (2(!+к)+

+2)вод6 к-го адресного коммутатора) (t -1)-й группы, выход сумматора по модулю два подключен к информационным входам с номерами.(2 к

«(t+x))tttod 6 и(2 (1+к) +3)вехиб к-го адресного коммутатора (1-1)-й группы, выходы разрядов счетчика циклов подключены к управляющим входам всех адресных коммутаторов, выходы адресных коммутаторов (1-1)-й группы являются адресными выходами (i+1)-й группы блока управления.

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

Устройство содержит генератор 1 тактов, блок 2 управления, блоки

3, 1-3 р/2 . памяти, арифметические блоки 4,1-4.)p/2(, коммутаторы 5, 15. )р/2(, 6, счетчик 7 тактов, сумматор по модулю два 8, адресные коммутаторы 9 элементы 10 и 11 И-ИЛИ, счетчик 12 циклов, элемент 13 НЕ.

Устройство работает следующим образом.

Выполнение алгоритма, как видно из фиг.2, состоит в вычислении р=

= 60/ Ì =5 итераций, каждая из которых содержит К/2 16 базовых операций вида

Е,51» ЕД Е,. s,. а =a +at+ и, и tt яЯ

< (1! е,ь+ к е,s е,s м s,n а + — =ot -a + Ф г1 Z и 25 гдеап- операнды, ь — номер узла графа — номер итерации (S =1, 2,...,р); — номер выходной последовательности, Операции (1) выполняются арифметическими блоками 4, каждый из которых может состоять, например, из сумматора-вычитателя и умножителя комплексных чисел.

Выполнение алгоритма быстрого преобразования Фурье над 32-точечными массивами потребует jp/2(=3 каскада, а также шестиразрядный счетчик

7 тактов. Примем, что шаг работы устройства образуют четыре такта работы счетчика 7, цикл работы уст ройства — 812=16 шагов. В исходном

0,1 и+ И )92ï

2Р

5 10864 положении счетчик 7 тактов, счетчик

12 циклов находятся в нулевом состоянии. С началом работы импульсы с генератора 1 тактов поступают на вход

1,О счетчика 7, исходные данныеа„ последовательности С =1 поступают на вход устройства. Частота поступления исходных данных в 4 раза меньше частоты генератора 1 тактов. Первый цикл работы устройства состоит в i0

1,О записи исходных данных са"о по а в блок 3, 1 памяти первого каскаца,счиÎ,1 6,1 тывании операндова,о1 предыдущей

М.— р

15 йоследовательности 6 =О из блока

3. 1 памяти для выполнения второй итерации, а также в записи результатов о,а выполнения второй итерации 20

0,2 0,2 и

tl+

22 в блок 3,2 памяти второго каскада.

Для этого в первом такте каждого шага (номер такта соответствует сос25 тоянию 0-го и 1-го разрядов счетчика 7 тактов плюс единица) операнд

0,1

of 4 считывается нз блока 3.1 памяти

n+ по адресу А „„2„ (а+ 1 и поступает

Й 1 30 через коммутатор 6 в арифметический блок 4.1, где выполняется операция

Во втором такте каждого шага операнд и считывается из блока 3.1 па01 п мяти. по адресу А „„„2„. (п1 и через

40 коммутатор 6 поступает также в арифметический блок 4. 1. При этом на входах управления записью/считыванием блоков 3.1-3 ) р/2(памяти присутствует значение О, которое соответствует режиму считывания.

На управляющих входах коммутатора

6 в первом такте присутствует код

37 б

ОС, во втором — код 10. Эти значения разрешают прохождение операндов с выхода блока 3.1 памяти на вход арифметического блока 4. 1.

В третьем такте каждого шага исходный операндс»" последовательности п (=1 через коммутатор 5.1 поступает на вход блока 3. 1 памяти и эаписываетcs с замещением по адресу АЗ иск(n). Ïðî10 ( хождение операндаа1 на вход блока и

3.1 памяти обеспечивает код 10 на управляющих входах коммутатора 5. 1, запись операнда of1„0 в блок памяти 3. 1 разрешает значение 1 на входе управления записью/считыванием, В этом же такте на каждом шагу результат выполнения базовой операции и второй итерации последовательнос0,2 и ти И =О появляется на выходе арифметического блока 4,1 и, пройдя через коммутатор 5.2, запишется в блок 3.2 памяти второго каскада по адресу 32 ит "

В четвертом такте каждого шага на выходе арифметического блока 4. 1 появляется результат выполнения ба0,2 зовой операции о1 который, пройдя

11+—

22 через коммутатор 5,2, запишется в блок 3. 2 дамвти ло адРесУ Яб Д „т (о+У)

На управляющем входе коммутатора 5.2 при этом присутствует нулевое значение.

Адреса формируются из разрядов счетчика 7 тактов, выходов элементов И-ИЛИ,коммутаторов 9, на управляющих входах которых присутствует код 000.

0,2

Записью результата а 31 з ак анчивается первый цикл работы устройства .

Сигнал переполнения счетчика 7 тактов изменяет состояние счетчика 1 2 циклов на 00 1 .

В таблице приведены состояния на управляющих входах коммутаторов

5 ° 1; 6 ; 5, 2 - 5 . 3 на входе управл ения записью/считыванием блоков памяти, выполняемые при этих состояниях функции .

1086437

Коммутатор 5.1

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

0 х

Прохождение результатов выполнения,1-й итерации с с выхода арифметиД.!.,1

n „+L. у

1 2 ческого блока 4.1 на вход блока памяти. 3.1

Коммутатор 6

Цля выполне0

Коммутаторы 5.2-5, р/2Г

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

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

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

Ч1 Ч2

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

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

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

Прохождение операнда а„ с выхода блока памяти

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

Прохождение операнда a „

8,1 с выхода блока памяти 3,.1 на вход арифметического блока

4.1

C,о

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

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

4.1

Прохождение операндов a i с выхода блока памяти

М\

3.1 на вход арифметического блока 4. 1

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

Прохождение операндов с выхода арифметического блока j-ro каскада на вход блока памяти (i+1)-ro каскада ния второй итерации

1086437

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

Вход управления записью/считыванием блоков памяти 3.1-3 ) р/2(Выполняемая функция

Состояние

Разрешение считывания

Разрешение записи

50

Второй цикл работы устройства состоит в выполнении первой итерации алгоритма быстрого преобразования Фурье над последовательностью в первом каскаде и трееьей ите15 рации последовательности. C =0 — во втором каскаде. Для этого в первом

q,à такте каждого шага .операнд О„ + 1 с входа устройства через коммутатор 6 поступает s арифметический

20 блок 4. 1, где выполняется операция а 1 %,.во втором каскаде

a,î

fl+ HlZ в каждом первом такте шага выпол-, няется считывание операнда с)„

О,2 блока пайнтИ 3.2 по адРесУА„д Здт + — ),25

" 1 2) который затем поступает в арифметический блок 4.2, где выполняется

0,2 операция и „ 29 1)) ;. Во втором ь+й 2 такте каждого шага операнд а1„0 считывается из блока 3. 1 памяти по адресу ))лечит 1ит("") H через ком мутатор 6 поступает на вход арифметического блока 4. 1 во втором каска- де выполняется считывание операнда

a„ из блбка 3.2 памяти по адресу о,г

Я 3 ()l) v передача его в арифметиснигит ческий блок 4.2. В третьем такте каждого шага результаты выполнения базовых операций e„ < > p проидя 40

1,) 0 9 через коммутаторы 5. 1 и 5.2, записываются в блоки 3 1 и 3,2 памяти по адресам Я (n) Во (n) соответственЗе1NT 3.Эит но. В четвертом такте каждого шага результаты выполнения базовых опе- 45

1 1 . 0,3

Раций 1 с4 „,пройдя через комму-. и+ — и+—

2 23 таторы 5. 1 и 5,2, записываются в блоки 3. 1 и 3 2 памяти по адресам

Аз <„(n+H(2), А> (n+N/2 ) соответственно.

Сигнал переполнения счетчика 7 тактов изменяет состояние счетчика

12 циклов на 010.

Третий цикл работы устройства состоит в считывании операндов и .записи - результатов выполнения четвертой итерации последовательности

5=0, считывании операндов и записи результатов выполнения второй итерации последовательности 9 =1, а также в записи первой половины исходных данных последовательности 0 =2 и т.д.

Записью результатов

0 4- 1 г заканчивается третий цикл работы устройства. Сигнал переполнения счетчика

7 тактовых импульсов изменяет состояние счетчика 12 циклов на 011.

Четвертый цикл работы устройства состоит в выполнении пятой итерации над последовательностью =0 в третьем каскаде, третьей итерации над последовательностью 0 =1 во втором каскаде и первой итерации над последовательностью К =2 в первом каскаде. Выполнение первой итерации последовательности 8 =2) аналогично выполнению первой итерации последовательности В 1.

Пятый цикл работы устройства (состояние счетчика 12 циклов 100) состоит в выполнении считывания результа-. тов вычисления алгоритма быстрого преобразования фурье последовательнос-. ти ь 0 из блока памяти 3.3, считывании операндов и записи результатов вычисления четвертой итерации последовательности 6=1, считывании операндов и записи результатов вычисления второй итерации последовательности

g,=2, а также в записи первой половины исходных данных очередной последовательности 0=3

Шестой цикл работы устройства состоит в выполнении пятой итерации над последовательностью 0 =1 в третьем"каскаде, третьей итерации над последовательностью 6 =2 во втором каскаде и первой итерации над последовательностью 0=3 в первом каскаде.

Сигнал переполнения счетчика 7 тактовых импульсов изменяет состояние счетчика 12 циклов на 000. Дальнейшее выполнение. циклов устройства аналогично первым шести. Адресация для

11, v0864 операндов следующих последовательностей повторяется с периодом 3.

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

1086437

Филиал ППП "Патент", г.Ужгород, ул.Проектнан, 4

1086437

ВНИИПИ Заказ 2243/46

Тираж 699 Подписное