Арифметическое устройство для выполнения быстрого преобразования Фурье Советский патент 1986 года по МПК G06F17/10 

f

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

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

На фиг.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 представлен направленный граф, поясняющий работу устройства.

Для каждой базовой операции БПФ выполняются следующие выражения:

Rey ReXl+ReXl+ReX2.. cose +1мХ2-з1пе:( 1мУ1 1мХ1-ИмХ2 Созе - ReXZ-sinG ; (2) ReY2 ReXl-ReX2.cose - 1мХ2-з1пв ;(3) 1мУ2 1мХ1-1мХ2 со5е + ReX2 sin0 ; (4)

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

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

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

Вьтолнение каждой- группы из четырех базовых операций БПФ производится за семь тактов работы устройства. В пятом такте n-1-й группы в регистры 18, 19 и 22, 23 записываются комплексные данные второго и четверто28П4

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

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

Во втором такте мнимые части данных 1мХ2 и 1мХ4, находящиеся в регистрах 19 и 23 через мультиплексоры 25 и 28 подаются в умножители 33-36, где формируются произведения мнимых - частей данных на соответствующие фа- зовые множители. Сформированные произведения складываются или вычитаются с результатами предьодущих произведений и за поминаются. При этом 35 в умножителе 33 будет сохраняться результат операции lMX2-sinS +, + ReX2cos е , в 34 1мХ2cos б - - ReX2.sine , в 35 lMX4.sin8 + + ReX4,cos0 и в 36 1мХ4-созв - 40 - ReX4- sine .

В третьем такте действительные части данных ReXl и НеХЗ, находящиеся в регистрах 17 и 21 через мультиплексоры 37, 40 и 41,44 подаются на входы сумматоров-вычитателей 45-48, на другие входы которых через мультиплексоры 38, 39 и 42,43 подаются выходы умножителей 33-36. На сумма- торах-вычитателях будут произведе- 50 ны операции согласно вьфажений (1) и (3), которыми завершается парал- лельное вьтолнение двух базовых операций БПФ на первой итерации алгоритма, но только для действительных 55 частей данных. При этом на еуммато- ре-вычитателе 45 формируется результат Reyi ReXI 4 ReX2.cose + + lMX2tsine , на 46 НеУ2 ReXI30

31

-ReX2 cose- 1мХ2.з1п0, на kl РеУЗ ReX3 + ЕеХ4,созв + 1мХ4-з1п9, на 48 КеУ4 РеХЗ - ReX4.cose -1мХ4 31п8. Полученные результаты подаются на соответствующие блоки 49-52 сдвига, где происходит логический сдвиг на один бит в сторону младших разрядов (во избежание переполнений). В конце третьего такта эти сдвинутые данные передаются через мультиплексоры 9,13 и 10, 14 и записьюаются соответственно в регистры 17, 21 и 18, 22. С помощью этих двух последних операций осуществляется переход от одной итерации алгоритма к следующей в текущей группе базовых операций. При этом записываются только действительные части данных.

В четвертом такте устройство пе- реходит к вьтолнению двух базовых операций БПФ для следующей итерации. При этом в умножителях 33-36 будут выполнены те же операции, что и в такте 1, но с другими фазовыми мно- жителями (cos б и зin 0) ..Параллельно с этим на сумматорах-вычитателях производятся операции согласно выражений (2)и (4), которыми завершается параллельное выполнение двух базо вых-операций БПФ на первой итерации алгоритма для мнимых значений данных При этом на сумматоре-вычитателе 45 формируется результат 1мУ1 1мХ1 + + 1мХ2.соз8 - ReX2.3ine , на 46 1мУ2 1мХ1 - 1мХ2-соз9 + ReX2.3in0 на 47 1мУЗ 1мХЗ + 1мХ4.созе

-R.X4.3in9 , на 48 1мУ4 1мХЗ -1мХ4,-созЭ + НеХ4. sin0.

. Полученные результаты сдвигаются на один бит в сторону младших разрядов и через мультиплексоры 11, 12 и 15, 16 записываются соответственно в регистры 19,20 и 23, 24. С помощью этих двух последних операций осуществляется переход от одной итера- ции алгоритма к следующей в текущей группе базовых операций, но только для мнимых частей данных.

На пятом такте в умножителях 33- 36 выполняются те же операции, что и в такте 2, но только с другими фазовыми множителями. Параллельно с этим в регистры 18, 19 и 22, 23 будут записаны комплексные данные второго и четвертого числа для следующей n+1-й группы базовых операций БПФ.

В шестом такГе на сумматорах-вычитателях 45-48 производятся опера

1

j

0 5 „

5

144

ции в соответствии с выражениями (З) и (4). Результатами этих операций будут комплексные данные второго и четвертого числа. При этом на сумматоре 45 формируется результат Rey2 ReXl - - 1мХ2.з1пе , на 46 1мУ2 1мХ1 - 1мХ2.созв + + ReX2.3in0 , на 47 Rey4 . ReXY - - ReX4.co3e - 1мХ4.з1п0, на 48 мУ4 1мХЗ - 1мХ4.созб + ВеХ4.з1п9. После масштабирования на блоки сдвига 49-52 эти значения подаются на выходы 53-56. для записи в память данных.

В седьмом такте на сумматорах-вычитателях 45-48 формируются результаты в соответствии с выражениями (1) и (2).- При этом на сумматоре-вы- читателе 45 будет Reyi + + 1мХ2 з1пб + ReXl, на 46 1мУ1 1мХ1 + ГмХ2.со80 - ReX2 sin9 на 47 Rey3 ReX3 + НеХ4.соз в + + lMX2 sin6, на 48 1 мУ4, 1мХЗ -f- 4 1мХ4«со8б - ReX4,sin8.

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

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

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

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

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

Imft- lmXI фиг. Z

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

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

Заказ 2288/50Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д. 4/5

. ™ ™ ™ - - -вРИв-«--и1 ,„ 1 - ц, -IJ -г , Л-,

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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