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

 

Изобретение относится к вычислительной технике и может быть использовано в информационно-измерительных системах спектрального анализа . Цель изобретения - повьшение быстродействия устройства. Схема содержит двадцать мультиплексоров, четьфе накапливающих умножителя, четырнадцать регистров, четыре сумнатора-вычитателя, четыре блока сдвига. Алгоритм работы арифметического устройства для выполнения быстрого преобразования Фурье заключается в параллельном выполнении двух базбвых операций быстрого преобразования Фурье по основанию 2 вначале на текущей итерации алгоритма. При этом обработка комплексных данных производится сразу на двух итерациях алгоритма 2 ил. о Л

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

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

РЕСПУБЛИК (pe 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ j

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3776955/24-24 (22) 27.07.84 (46) 30.04.86. Бюл. И 16 (72) С.В.Аксененко и Н.Н.Еремеев (53) 681.32(088 .8) (56) Применение цифровой обработки сигналов/ Под ред. Э.Оппенгейма. М, Мир, 1978.

Electronic Design.- February 19, 1981, р.144. (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ

ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ (БПФ) (57) Изобретение относится к вычислительной технике и может быть использовано в информационно-измери„„SU„,, 1228114 А1 тельных системах спектрального анализа. Цель изобретения — повышение быстродействия устройства. Схема содержит двадцать мультиплексоров, четыре накапливающих умножителя, четырнадцать регистров, четыре сумматора-вы-. читателя, четыре блока сдвига. Алгоритм работы арифметического устройства для выполнения быстрого преобразования Фурье заключается в параллельном выполнении двух базбвых операций быстрого преобразования Фурье по основанию 2 вначале на текущей итерации алгоритма. При этом обработка комплексных данных производится сразу на двух итерациях алгоритма

2 ил.

5 228

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

Цель изобретения — повышение быстродействия устройства.

На фиг.1 приведена структурная схема арифметического устройства для выполнения БПФ; на фиг,2 — граф алгоритма.

Устройство содержит входы операндов 1-4 и входы коэффициентов

5-8, мультиплексоры 9-16, регистры

17-24; мультиплексоры 25-28, регистры 29-32, накапливающие умножители

33-36, мультиплексоры 37-44, сумматоры-вычитатели 45-48, блоки 49-52 сдвига, выходы операндов 53-56.

Алгоритм работы устройства заключается в параллельном выполнении двух базовых операций БПФ по основанию 2 вначале на текущей итерации алгоритма. При.этом обработка комплексных данных производится сразу на 2 двух итерациях алгоритма. На фиг.2 представлен направленный граф, поясняющий работу устройства.

Для каждой базовой операции БПФ выполняются следующие выражения: 30 бреу! =ReX1+ReX I+ReX2.- соя 9 +I мХ2 я п 0 (1)

1мУ1=1мХ1+1мХ2 cos 9 — ReX2 ° sin 8; (2)

ReY2=ReX1-ReX2 cos8 — IмХ2 ° sin8 (3)

1мУ2=1мХ1-IмХ2 ° cos9 + ReX2 "sin8 (4)

Легко видеть, что выражения (1-4) описывают выполнение базовой операции прямого БПФ для двух комплексных значений данных Х1 и Х2, Аналогично будет описано и выполнение базовой операции

БПФ для двух комплексных значений дан- 40 ных ХЗ и Х4. В этом случае в выражениях (1-4) изменятся индексы 1 на 3, а 2 на 4.

Таким образом, алгоритм работы устройства сводится к вычислению четырех значений комплексных данных на двух итерациях алгоритма БПФ по основанию 2, что соответствует выполнению группы из четырех базовых операций алгоритма, 50

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

Выполнение каждой. группы из четырех базовых операций БПФ производится за семь тактов работы устройства. 55

В пятом такте и-1-й группы в регистры 18, 19 и 22, 23 записываются комплексные данные второго и четверто114 2

ro числа (вторые операнды для двух базовых операций БПФ). Эти данные поступают из памяти, разбитой на четыре одинаковых массива с параллельным доступом (для хранения отдельно первых и вторых чисел комплек. сных данных), по входам 1-4 через мультиплексоры 10» 11 и 14, 15 и записываются соответственно в регистры 18, 19 и 22, 23.

В первом такте п oé группы базовых операций БПФ действительные части данных ReX2 и ReX4, находящиеся в регистрах 18 и 22, через мультиплексоры 25-28 подаются в умножители 33-36, где формируются и запоминаются произведения действительных данных на поворачивающиеся фазовые множители тригонометрических коэффициентов, находящихся в регистрах 29-32. В этом же такте в регистры 17,20 и 21, 24 записываются комплексные данные первого и третьего числа (первые операнды для двух базовых операций БПФ).

Во втором такте мнимые части данных IмХ2 и !мХ4, находящиеся в регистрах 19 и 23 через мультиплексоры

25 и 28 подаются в умножители 33-36, где формируются произведения мнимых частей данных на соответствующие фазавые множители. Сформированные произведения складываются или вычитаются с результатами предыдущих произведений и запоминаются. При этом в умножителе 33 будет сохраняться результат операции IмХ2 sin 9 +, + ReX2. cos 9, в 34 мХ2 ° соя 9 — Re/2 ° sin9, в 35 IMX4 si.n8 +

+ ReX4, соя8 и в 36 1мХ4.cos 9 — ReX4 ° sin9 .

В третьем такте действительные части данных ReXI и ReX3, находящиеся в регистрах 17 и 21 через мультиплексоры 37, 40 и 41,44 подаются на входы сумматоров-вычитателей 45-48, на другие входы которых через мультиплексоры 38, 39 и 42,43 подаются выходы умножителей 33-36. На сумматорах-вычитателях будут произведены операции согласно выражений (1) и (3), которыми завершается параллельное выполнение двух базовых операций БПФ на первой итерации алгоритма, но только дпя действительных частей данных. При этом на сумматоре-вычитателе 45 формируется результат ВеУ1 = ReX1 + ReX2.ñîÿ 9 +

+ 1мХ2<яХп 9, на 46 Реу2 = ReXI3 12 — ReX2 cos Π— IмХ2 sin 9, на 47

ReY3 =ReX3 + ReX4.ños8 + IмХ4 81ПО, на 48 КеУ4 = ВеХЗ вЂ” ReX4-cosA

-lмХ4 sine. Полученные результаты подаются на соответствующие блоки

49-52 сдвига, где происходит логический сдвиг на один бит в сторону младших разрядов (во избежание переполнений). В конце третьего такта эти сдвинутые данные передаются через мультиплексоры 9,13 и 10, 14 и записываются соотйетственно в регистры 17, 21 и 18, 22. ° С помощью этих двух последних операций осуществляется переход от одной итерации алгоритма к следующей в текущей группе базовых операций. При этом записываются только действительные части данных.

В четвертом такте устройство переходит к выполнению двух базовых операциЛ БПФ для следующей итерации, При этом в умножителях 33-36 будут выполнены те же операции, что и в такте 1, но с другими фазовыми множителями (сов 9 и sin 9 ). Параллельно с этим на сумматорах-вычитателях производятся операции согласно выражений (2)и (4), которыми завершается параллельное выполнение двух базовых операций БПФ на первой итерации алгоритма для мнимых значений данных.

При этом на сумматоре-вычитателе 45 формируется результат IмУ! = IмХ1 +

+ )мХ2 ° cos8 — ReX2 ° sin8, на 46

l мУ2 = l мХ I — l мХ2 ° соя & + ReX2 sin 8 на 47 lмУЗ = IмХЗ + 1мХ4.cos 8 — ReX4 sin9, на 48 lмУ4 = lмХЗ -

lмХ4 cos S + ВеХ4. sin 8.

Полученные результаты сдвигаются на один бит в сторону младших разрядов и через мультиплексоры 11, 12 и 15, 16 записываются соответственно в регистры 19,20 и 23, 24. С помощью этих двух последних операций осуществляется переход от одной итерации алгоритма к следующей в текущей группе базовых операций, но только для мнимых частей данных, На пятом такте в умножителях 3336 выполняются те же операции, что и в такте 2, но только с другими фазовыми множителями. Параллельно с этим в регистры 18, 19 и 22, 23 будут записаны комплексные данные второго и четвертого числа для следующей и+1-й группы базовых операций БПФ.

В шестом такте на сумматорах-вычитателях 45-48 производятся опера28114 4 ции в соответствии с выражениями (3) и (4). Результатами этих операций будут комплексные данные второго и четвертого числа. При этом на сумматоре 45 формируется результат

ВеУ2 = ReXI — ReX2 cosA — IмХ2.sin8 на 46 IмУ2 = IмХ! — lмХ2.cosa +

+ ReX2 ° sin 8 на 47 Веу4 = ReXY— — ReX4.cosA — 1W4 ° sinA, на 48

10 Iму4 = lмХЗ вЂ” IмХ4.cos8 + ReX4 з п ч .

После масштабирования на блоки сдвига

49-52 эти значения подаются на выходы 53-56.. для записи в память данных.

В седьмом такте на сумматорах-вычитателях 45-48 формируются результаты в соответствии с выражениями (1) и (2). При этом на сумматоре-вычитателе 45 будет ВеУI = ReX2 cos8 +

2< + +lмХ2 ° sin9 + ReXI, на 46 lмуl

=lмХI+1 мХ2 cos 9 — ReX2 sine . на 47 ReY3 = ReXÇ + ВеХ4 cos 8 +

+ lмХ2 sin9, на 48 1 му4 *= 1мХЗ

+ I мХ4.cos A - ВеХА sinA.

В следующем такте будет начато вы полнение n+I-й группы базовых опера- ций.

Формула изобретения

Арифметическое устройство для выполнения быстрого преобразования Фурье, содержащее два накапливающих ум: ножителя, шесть регистров, восемь мультиплексоров, первый и второй сум35 маторы-вычитатели, выходы которых подключены к информационным входам соответственно первого и второго блоков сдвига, о т л и ч а ю щ е е с я

40 тем, что, с целью повышения быстродействия, в него введены двенадцать мультиплексоров, два сумматора-вычитателя, два блока сдвига, два накапливающих умножителя и восемь регист45 ров, причем выходы первого и второго мультиплексоров подключены к информационным входам соответственно первого и второго регистров, информационные выходы которых подключены к первым информационным входам соот50 ветственно третьего, четвертого, пятого, шестого мультиплексоров, выходы которых подключены к первым входам соответственно первого, второго, третьего и четвертого накапливающих умножителей, выходы которых подключены соответственно: первого накапливающего умножителя — к первым информационным входам седьмого и

1228114 восьмого мультиплексоров, второгок вторым информационным входам седьмого и восьмого мультиплексоров, третьего — к первым информационным входам девятого и десятого мультиплексоров, четвертого накапливающего умножителя — к вторым информационным входам девятого и десятого мультиплексоров, выходы которых под- 10 ключены к.первым входам третьего и четвертого сумматоров-вычитателей, выходы которых подключены к информационным входам соответственно третьего и четвертого блоков сдвига, информа-15 ционные выходы которых подключены соответственно: третьего - к первым информационным входам первого и одиннадцатого мультиплексоров, а четвертого — к первым информационным входам второго и двенадцатого мультиплексоров, вторые информационные входы пятого и шестого мультиплексоров подключены к информационному выходу третьего регистра, информационный вход которого подключен к выходу двенадцатого мультиплексора, второй информационный вход которого соединен с первым информационным входом тринадцатого мультиплексора, выход которого подключен к информационному входу четвертого регистра, инфор мационный выход которого подключен к первым информационным входам четырнадцатого и пятнадцатого мультиплексоров, выходы которых подключены к вторым входам соответственно третьего и четвертого сумматороввычитателей, вторые информационные входы четырнадцатого и пятнадцато- 40 го мультиплексоров подключены к информационному выходу пятого регистра, информационный вход которого подключен к выходу шестнадцатого муль типлексора, первый информационный 45 вход которого соединен с вторым информационным входом второго мультиплексора, вторые информационные входы.трннадцатого и шестнадцатого мультиплексоров подключены к инфор- gp мационному выходу второго блока сдви га, информационный выход первого блока сдвига подключен к первым информационным входам семнадцатого и восемнадцатого мультиплексоров, выходы которых подключены к информационным входам соответственно шестого и седьмого регистров, информационные выходы которых подключены соответственно к первым и вторым информационным входам девятнадцатого и двадцатого мультиплексоров, выходы которых подключены к первым входам соответственно первого и второго сумматоров-вычитателей, вторые входы которых подключены к выходам соответственно седьмого и восьмого мультиплексоров, вторые информационные входы первого и семнадцатого мультиплексоров соединены и являются входом первого операнда устройства, вторые информационные входы третьего и четвертого мультиплексоров подключены к информационному выходу восьмого регистра, информационный вход которого подключен к выходу одиннадцатого мультиплексора, второй информационный вход которого соединен с вторым информационным входом восемнадцатого мультиплексора и является входом второго операнда устройства, входами третьего и четвертого операндов которого являются с6ответственно второй информационный вход второго, первый информационный вход тринадцатого мультиплексоров, вторые входы первого, второго, третьего и четвертого накапливающих умножителей подключены к информационным выходам соответственно девятого, десятого, одиннадцатого и двенадцатого регистров, информационные входы которых являются входами соответственно первого, второго, третьего и четвертого коэффициентов устройства, выходами первого, второго, третьего и четвертого операндов которого являются информационные выходы соответственно первого, второго, третьего и четвертого блоков сдвига.

1228114

ue.!

ИУ! РС17

ZmSe ImX д. г

Составитель А.Баранов

Техред И.Попович Корректор А. Обручар

Редактор Ю.Середа

Заказ 2288/50

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5 ъПроизводственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4