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

Изобретение относится к вычисли- - тельной технике и может быть использовано в специализированных пооиес- сорах быстрого преобразования Фурье (БПФ) высокой производительности;

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

На фиг, 1 представлена функщгональ ная схема устройства; на фиг.2 - схема блока сумматоров; на фиг.З - временные диаграммы работы.

Устройство содержит три суммато- ра-вычитателя (блока двухточечного ДПФ) 1-3, регистр 4, бло;х 5 сумматоров, блок б-синхронизации. Блок сумматоров (фиг.2) содержит сумматоры 7 и 8 вычитательЭ, умножитель 30 на 1/85 умножитель. П на 1/16 и ум- , ножитель 12 на 1/8,

Устройство работает след;7юш,им образом.

Операнд f(О) поступает на второй вход третьего сумматора-вычитателя, а операнды f() и f(2) поступают соответственно на входы сумматора-вы читателя, выход суммы которого f(l)- + f(2) соединен с рег;и стром 4. Сумма f(l)-i-f(2) через регистр 4 без изменения поступает на входной рематора 7, сдвинутое по четыре разря- . да вправо, т.е. 050703125 X поступает на вход сумматора 8, -на вход второго сумматора приходит значе- 5 ние X . Значение суммы 1,0703125Х с выхода сумматора; сдвинутое на три разрягта вправо, т.е. О,1337890625 X поступает на вход вы- читателя,, тта другой вход которого 10 приходит знячениа К , На вы- читателя получаем значение 0.8662109375 X , что соответствует в епггчине х в данной интерпретации с соответствующей точностью. ход вьгчитателя является выходом блока сумматоров о Таким oбpaзo все устройство реахгизует вычисления по формулам (21

F(0) f(0) + f() + f(2); 20 F(1)f(0)f()+f(2)+j Й f(1)-f(2); : (2) F(2)f(0)(l)+f(2)l -j f(l)-f(2)f.; Устройство управляется стандарт- 25 HbD блоком 6 синхронизации. Умножители {фиг.2} осуществляют сдвиги информационных разрядов; умножитель )0 на три разряда вправо /.-Sj, умножитель 11 на четыре разряда вправо гистр сумматора-вычнтателя З.и в ви- зо (2-4)j умножитель 12 на три разряда де 1/2 t f (1 )-i-f (2)1 поступает на вправо (2-3). Физически это представ- входной регистр вычигателя того же бл о к а 5 пр ич ем рез ул ь тат F (О) - f | О ) - +f()+(2) поступает на вькод уст- , ройства, а результат F(0) + l/2 If (1 ) (2) поступает на вход cyi iMaTopaляет собой жестко фиксированную ком- мутг.гггио информационных выходов одного регистра храпения с соответствующими инфopмaп {oнньгми выходами другого )егистра.

вычитателя 1, на выходе которого по лучается

F((0)-l/2 f(l)+f(2) J +

+j f(O-f(2)l.

Результат f(l)f(2) с выхода сумматора-вычитателя 2 поступает на вход блока 5 сумматоров.; на вьЕн;оде которого получается величина ( / -f(2) дКоторая на вход сум.матора-выч.йтателя 1 , на выходе которого появляется значение р

F(2)f(0)l/2 rf(l)-f(2)(№ -f(2) .

Блок сумматоров работает следующим образомо

Входной операнд X разрядностью п поступает на вход сумматора 7, .ка другой вход этого сумматора поступает значение операнда К ,сдвинутое на три разряда вправо т,е, 0„125 К „ Значение суммы 1,125 X с вькода сум

матора 7, сдвинутое по четыре разря- да вправо, т.е. 050703125 X поступает на вход сумматора 8, -на вход второго сумматора приходит значе- ние X . Значение суммы 1,0703125Х с выхода сумматора; сдвинутое на три разрягта вправо, т.е. О,1337890625 X поступает на вход вы- читателя,, тта другой вход которого приходит знячениа К , На вы- читателя получаем значение 0.8662109375 X , что соответствует в епггчине х в данной интерпретации с соответствующей точностью. вьгчитателя является выходом блока сумматоров о Таким oбpaзo все устройство реахгизует вычисления по формулам (21

F(0) f(0) + f() + f(2); F(1)f(0)f()+f(2)+j Й f(1)-f(2); : (2) F(2)f(0)(l)+f(2)l -j f(l)-f(2)f.; Устройство управляется стандарт- HbD блоком 6 синхронизации. Умножители {фиг.2} осуществляют сдвиги информационных разрядов; умножитель )0 на три разряда вправо /.-Sj, умножитель 11 на четыре разряда вправо (2-4)j умножитель 12 на три разряда вправо (2-3). Физически это представ-

ляет собой жестко фиксированную ком- мутг.гггио информационных выходов одного регистра храпения с соответствующими инфopмaп {oнньгми выходами другого )егистра.

блоке ре;1лизуется функция Х

t

f-

согласно выражению

х():хЬ-г и-1 (1я )1}Точность представления значения константы .8660254 в данной

. - 11

ив:терпретации соответствует 2 ( О.;86б2 09375 этого вполне достаточ- йо пии фиксированном формате в 8 и 16 разр::,цов ,еепк учесть,что умножение осу-- ществляется на константу меньше 1 . За счет последовательного аппаратурного с/двигЕ с подсуммированием повь шается точность умножения (в условиях огра- н.н енА-гой разр.ядной сетки реальных машин по сравнению с умножением по принципу одноврененньк сдвигов и сведения результатов. Если разрядность равна 8.3 то однотфеменный сдвиг на 10 разрядов ( 2 °)выходит за границу чувствительности однобайтной разности а при последовательных сдви3 1

ax с подсуммированием также происходит обрезание младших разрядов, но предварительно, в процессе последовательных сложений, вьшолняются переносы в старшие разряды и вероятность получения более точного резуль-, тата при заданной разрядности, соответственно, повьшзается. Так, при длине операнды в восемь разрядов рбиГ

зультат прямого умножения на

, оЧ o i согласно выражению 1 / - -

при с оответствует 0,8671875 (точное значение 0,8660254), а при

F{0)

20680 4

вьтолненни J -2- 11 )J} резул%- ч ат 0,866211. На диаграмме (фиг.ЗУ показана синхронизация работы -функциональных узлов, составляющих уст- 5 ройство. Ковейерный режим показан с дискретностью до одного такта пол- . ного суммирования, хотя реально квантование для обеспечения конвейер- ности доводится до такта минимальной 10 функциональной операции (например, времени хранения выборки, внутрен е- го такта сложений и т.д.)(в)

1/

lllli

I «4J

Ч-)

N

IQ