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

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ШСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОС-, НОВАНИЕМ 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) -и информационный вход К -го коммутатора

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК ()9) (! !) (5!)4 G 06 F 15/332

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3723748/24-24 (22) 21. 02. 84 .:(46) 15. 10.85. Бюл. ф 38 (72) М. Б. Свердлик и А.А. Назаренко (71) Одесский ордена Трудового Красного Знамени политехнический институт (53) 681.32(088.8) (56) Батиаров А.В., Тищенко Г.Д.

Реализация устройств цифровой обработки сигналов на основе алгоритмов

БПФ. Зарубежная радиоэлектроника, 1975, У 9.

Рабинер А., Гоулд Б. Теория и применение цифровой обработки сигналов.

Пер. с англ. M.: Мир, 1978. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С ОС

НОВАНИЕ!! 4, содержащее М коммутатооовгде М = 4g 4 М, а и -размерность преобразования фурье, М арифметических блоков, причем i -й (i

1,2,..., М ) арифметический блок содержит первый, второй и третий умножители на минус единицу, .первый и второй умножители на мнимую единицу, первый и второй сумматоры, первые входы которых объединены, вторые входы первого и второго сумматоров соединены с выходами соответственно первого умножителя на минус единицу и первого умножителя на мнимую единицу, инфо.)мационные входы которых объединены, третий вход первого сумматора соединен с входом третьего умножителя на минус единицу, выход которого соединен с третьим входом второго сумматора, четвертые входы первого и второго сумматоров соепинены с выходами соответственно втофо- го умножнтеля на минус единицу и второго умножителя на мнимую единицу, информационные входы которых объединены, при этом j -й (j =1, 2,...,В -1) арифметический блок дополнительно содержит первый и второй умножители, первые входы которых соединены с выходами соответственно первого и второго сумматоров -го арифметического блока, вторые входы первого и второго умножителей

-го арифметического блока соединены соответственно с -м входом задания первого коэффициента устройства и с j -м входом задания второго коэффициента устройства, выходы первого и второго сумматоров в М -м арифметическом блоке являются выходами устройства, о т л ич а ю щ е е с я тем; что, с целью упрощения, оно содержит распределитель импульсов, четыре элемента задержки на И /4 тактов по восемь элементов задержки на М /4 такк тов для каждого )((К = 2, 3...,М), по одному элементу задержки на

2М/4" тактов для каждого К, причем 0 -й (g = 2,34) информационный вход j -ro коммутатора соединен с выходом ((, -1)-го элемента задержки на М /4 тактов и с входом Р -го элемента задержки на К/4 ° тактов, пятый информационный вход 1 -го коммутатора соединен с выходом четвертого элемента задержки на Ц/4 тактов, шестой информационный вход K—

ro коммутатора соединен с выходом элемента задержки на bl/4 тактов к и с входом элемента вадержки на

2.И /4» тактов, (e + 5) -й информационный вход К -ro коммутатора

1185349 и =екр (- j 2 К IК1, соединен с выходом (8 + 3)-ro элемента задержки на М/4 тактов и с к входом (В + 4)-го элемента задержки на М /4 тактов, десятый информак ционный вход k -го коммутатора соединен с выходом восьмого элемента задержки на 0 /4 " тактов, первый, второй, третий и четвертый выходы

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

1-го арифметического блока, третьим.

1 входом первого сумматора > -го арифметического блока, информационным входом второго умножителя на минус единицу 1 -ro арифметичес— кого блока, выход первого умножителя 1 -го арифметического блока

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

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

Предложенное устройство содержит элемент задержки 1 на И/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. 30 соединен с входом первого элемента задержки на М /4 " тактов и первым информационным входом (1 + 1)го коммутатора, выход второго умножителя 1 -го арифметического блока соединен с входом элемента задержки на 2 Н /4(j ") тактов, управляющие входы первого и второго умножителей на минус единицу -го арифметического блока и первого и второго умножителей на мнимую единицу < --го арифметического блока соединены

1 с 1 -м выходом распределителя импульсов и управляющим входом 1 --го коммутатора, вход первого элемента задержки на 9/4 тактов соединен с первым информационным входом первого коммутатора и является входом устройст— ва.

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

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

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

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

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

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

Через N/4 периодов следования входных отсчетов (после прихода

5 отсчета с номером N) коммутатор

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

2К 15 = -аС-13) и „; ьк

F-- (5-jB-c ig) vl N

В процессе вычисления по формулам (1) и (2) поворачивающие коэффициено к, к 3к поступают в арифметический блок 4 с входов

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

4 происходят по сигналам с распределителя импульсов 14. Отсчеты с выхода арифметического блока 4 поступают на элементы задержки 5 и 6. Через 3N/16 тактов после

30 начала вычисления арифметическим блоком 4 второй итерации БПФ коммутатор 7 реализует коммутацию по схеме, изображенной на фиг,2а, где справа указаны входы арифметического блока 9, который в течение времени N T> /16 выполняет операции согласно формуле (1). Через N/16 тактов коммутатор 7 реализует коммутацию по схеме, изображенной на фиг. 2б, при этом арифметический блок 9 в течение времени N Т0/16 выполняет операции согласно формуле (2) . Еще через N/16 тактов процедура вычислений начинается сначала 45 с использованием схем коммутации, приведенных на фиг.2в и r. Коэффио к як зк циенты W>, И, М» W ïîñòóïàþò в арифметический блок 9 с входа

8 задания коэффициентоз. 50

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

Порядок работы каждого из них пол- 55 ностью аналогичен работе второго каскада. Отличается только частота переключений. Период работы коммутатора и арифметического блока для

i-го каскада составляет N T>/4

Для последнего каскада период переключений коммутатора 12 и арифметического блока 13 равен T„.

Арифметический блок работает следующим образом.

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

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

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

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

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

19, на второй вход которого подаются поворачивающие коэффициенты Wц при

" ЭК вычислениях по формуле (1) и W q при вычислениях по формуле (2). Результат перемножения дает F

1!85349

ФиИ

Фиг. д

ВНИИПИ Заказ 6367/46 Тирак 709 Подписное

Филиал ППП "Патент", r.Óàrîðîä, ул.Проектная 4