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

соединен с выходом ( + 3)-го элемента задержки на N/4 тактов и с входом (В + 4)-го элемента задержки на N/4 тактов, десятый информционньй вход К -го коммутатора содинен с выходом восьмого элемента задержки на N/4 тактов, первый, второй, третий и четвертый выходы 1 -го коммутатора соединены соответственно с первьм входом первого сумматора i -го арифметического блока, информационным входом первого умножителя на минус единицу арифметического блока , третьи входом первого сумматора -го арифметического блока, информационным входом второго умножителя на минус единицу i -го арифметического блока, выход первого умножителя j -го арифметического блока

соединен с входом- первого элемента задержки на тактов и первым информационным входом ( 1) го коммутатора, выход второго умножтеля J -го арифметического блока соединен с входом элемента задержки на 2N/4 тактов, управляющие входы первого и второго умножителей на минус единицу i -го арифметического блока и первого и второго умножителей на мнимую единицу -го арифметического блока соединены с I -м выходом распределителя импульсов и управляющим входом i -го коммутатора, вход первого элемента задержки на тактов соединен с первым информационным входом первого коммутатора и является входом устройст ва.

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ШСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОС-, НОВАНИЕМ 4, содержащее Л коммутаторов где М 6og N , а N -размерность преобразования Фурье, М арифметических блоков, причем i -и (i 1,2,..., М ) арифметический блок содержит первый, второй и третий умножители на минус единицу, .первый и второй умножители на мнимую единицу, первый и второй сумматоры, первые входы которых объединены, вторые входы первого и второго сумматоров соединены с выходами соответственно первого умножителя на минус единицу и первого умножителя на мнимую единицу, информационные входы которых объединены, третий вход первого сумматора соединен с входом третьего умножителя на минус единицу, выход которого соединен с третьим входом второго сумматора, четвертые входы первого и второго сумматоров соединены с выходами соответственно BTOiJoго умножителя на минус единицу и второго умножителя на мнимую единицу, информационные входы которых объединены, при этом j -и ( j 1 , 2,...,M -1) арифметический блок дополнительно содержит первый и второй умножители, первые входы которых соединены с выходами соответственно первого и второго сумматоров j -го арифметического блока, вторые входы первого и второго умножителей j -го арифметического блока соединены соответственно с j -м входом задания первого коэффициента устройства и с j -м входом задания S второго коэффициента устройства, выходы первого и второго сумматоров в М -м арифметическом блоке являются выходами устройства, отличающееся тем,- что, с целью упрощения, оно содержит распределитель импульсов, четыре элемента задержки на N/4 тактов по восемь элементов задержки на W /4 тактов для каждого К ( К 2, 3. ..,W, эо ел по одному элементу задержки на 2N/4 тактов для каждого К , причем Р -и ( i 2,3,4) информационный &0 4 со вход -го коммутатора соединен с выходом (С -1)-го элемента задержки на N/4 тактов и с входом С -го элемента задержки на N/4 тактов, пятый информационный вход -го коммутатора соединен с выходом че-увер- того элемента задержки на тактов, шестой информационный вход К го коммутатора соединен с выходом элемента задержки на N/4 тактов и с входом элемента вадержки на 2 N/4 тактов, ( Р 5) -и информационный вход К -го коммутатора

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

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

На фиг. 1 приведена блок-схема устройства; на фиг. 2 - схема работы коммутаторов; на фиг. 3 - блоксхема арифметического блока.

Предложенное устройство содержит элемент задержки 1 на N/4 тактов, коммутатор 2, вход 3 задания коэффициентов, арифметический блок 4, элемент задержки 5 на N/8 тактов, элемент задержки 6 на 2N/8 тактов, коммутатор 7, вход задания 8 коэффициентов, арифметический блок 9, элемент задержки 10 на 1 такт, элемент задержки 11 на 2 такта,, коммутатор 12, арифметический блок 13, распределитель импульсов 14, Арифметический блок содержит умножитель 15 на минус единицу, умножитель 16 на мнимую единицу, умножитель 17 на минус единицу, сумматор 18, умножитель 19.

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

Обрабатываемые отсчеты последовательно загружаются в элемент задержки 1. После прихода отсчета с номером 3N/4 коммутатор 2 соединяет входы первого, второго, третьего и четвертого элементов задержки 1 с входами арифметического блока

4, который начинает вычислять первую /итерацию БПФ. В нем в течение первых N/4 периодов следования входных отсчетов вьтолняются операции согласно формулам

E )

F()Nj

где Е, F - сигналы на первом и втором выходе арифметического блока соответственно.

А, В, С, D - сигналы на первом, втором, третьем и четвертом уходах арифметического блока соответственно;

- wJ--exp(),

3

где К - индекс, зависящий от позиции данного элементарного вычисления в алгоритме.

Через N/4 периодов следования входных отсчетов (после прихода отсчета с номером N) коммутатор 2 соединяет второй, третий, четвертый и пятый элементы задержки 1,соответственно с первым, вторым, третьим и четвертым входами арифметического блока 4, который в течение последующих N/4 периодов следования входных отсчетов выполняет операции согласно формулам

2К

E-(A-64C-D1W N ;

гх F.(A-i8-C4jD)Vj;

В процессе вычисления по формулам (1) и (2) поворачивающие коэффициенП ° «К Tt TJ

ты W f , Wj, ; W ц W поступают в арифметический блок 4 с входов

3задания коэффициентов с периодом, равным периоду следования входных отсчетов - T-f,. Переключения в коммутаторе 2 и арифметическом блоке

4происходят по сигналам с распределителя импульсов 14,

Отсчеты с выхода арифметического блока 4 поступают на элементы задержки 5 и 6. Через 3N/16 тактов после начала вычисления арифметическим блоком 4 второй итерации БПФ коммутатор 7 реализует коммутацию по схеме, изображенной на фиг,2а, где справа указаны входы арифметического блока 9, которьш в течение времени N выполняет операции согласно формуле (1), Через N/16 тактов коммутатор 7 реализует коммутацию по схеме, изображенной на фиг. 26, при этом арифметический блок 9 в течение времени N Tf|/16 , выполняет операции согласно формуле (2). Еще через N/16 тактов процедура вычислений начинается сначала с использованием схем коммутации, приведенных на фиг.2в и г. Коэффициенты W , W , W поступают в арифметический блок 9 с входа 8 задания козффициентоз.

С выхода арифметического блока 9 второго каскада отсчеты поступают на элементы задержки третьего каскада и так далее до М -го каскада. Порядок работы каждого из них пол853494

ностью аналогичен работе второго каскада. Отличается только частота переключений. Пе1}иод работы комму- татора и арифметического блока для 5 i-ro каскада составляет N Т)/4 . Для последнего каскада период переключений коммутатора 12 и арифметического блока 13 равен Т. Арифметический блок работает

0 следующим образом.

На вход первого сумматора 18 входные отсчеты А и С поступают непосредственно, а отсчеты В и D через умножители 15 на минус единицу, которые при вычисленных по формуле (1),при этом управляющий сигнал отсутствует,не изменяют ни действительную, ни мнимую части входных отсчетов, обеспечивая

0 выполнение операции A + B + C + D, а при вычислениях по формуле (2), при этом присутствует управляющий сигнал, меняют их знаки на противоположные, обеспечивая выполнение

5 операции А-В + С- D. С выхода первого сумматора 18 результат поступает на вход первого умножителя 19, на второй вход которого подаются поворачивающие коэффициенты Wji, при вычислениях по формуле (1) и wl

при вычислениях по формуле (2). Результат перемножения дает искомое Е.

На вход второго сумматора 18 отсчет А поступает непосредственно, 5 отсчет В - через первый умножитель

16на мнимую единицу, который при вычислениях по формуле (1), управляющий сигнал отсутствует,реализует умножение на j, а при вычислениях

0 по формуле (2), управляющий сигнал присутствует, реализует умножение на - j; отсчет С - через умножитель

17на минус единицу, отсчет D через второй умножитель 16 на мнимую единицу, который при вычислениях по формуле (1) реализует умножение на - j, а при вычислениях по формуле (2) реализует умножение на j. С выхода второго сумматора 18 результат

0 поступает на вход второго умножителя 19, на второй вход которого подаются поворачивающие коэффициенты W,, при вычислениях по формуле (1) и W при вычислениях по формуле (2). Результат перемножения дает F.

I 13

сгзгШгСРтПЗ-4

/3

:/

r

/г f

/

/

-

/

- f

/