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

Изобретение относится к автомати ке и вычислительной технике и может быть использовано для вычисления спектра сигналов и их фильтрации в частотной области в системах связи, навигации, телеметрии и других обла тях техники. Известно устройство для выполнения быстрого преобразования .Фурье, которое содержит сумматоры и блок умножения на комплексный весовой коэффициент l , Наиболее близким техническим решением к изобретению является устро ствр для реализации алгоритма быстр го г1рербразования Фурье, содержащее четыре умножителя, шесть сумматоров регистры действительной и мнимой ча тей операндов, регистры действитель ной и мнимой частей весового коэффи циента, причем выходы регистров дай ствительной и мнимой частей весовог коэффициента соединены с первыми вх .дами умножителей с первого по четвертый, вторые входы которых соединены с выходами регистров действительной и мнимой частей первого и второго операндов, выходы с третьего по шестой.сумматоров соединены со сдвигающими входами регистров операндов 2, Недостатком известных устройств является низкое быстродействие из-з избыточного общего количества арифметрических операций. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство для реализации алгоритма быстрого преобразования Фурье, содержащее регистры действительной- и мнимой частей операнда, регистры действительной и мнимой частей-весового коэффициента, четыре умножителя и шесть сумматоров, причем входы регистров действительной и мнимой частей весового коэффициента являются входами дайстлительной и мнимой частей вессього коэффициента устройства,содержит два коммутатора и дешифратор, причем вход действительной части первого операнда устройства соединен с входом регистра действительной части операнда, входы мнимой части первого операнда и действительной части второго операнда устройства соединены с ин. формациоиными входами первого и второго коммутаторов,выход перво- го коммутатора подклнзчен к первьм входам первого и второго умножителей, выход второхо коммутатора подключен к входу регистра мнимой, части операнда, вход мвимой части второго операнда устройства соелинен с первыми входами третьего и четвер того умножителей, выход регистра действительной части весового коэффициента подключен к вторым входам первого и четвертого умножителей, а также к входу дешифратора, выход которого подключен к управляющим входам первого и второго коммутаторов, выход регистра мнимой части весового коэффициента подключен к вторым входам второго и третьего умножителей, выходы первого и третьего умножителей подключены к входам первого сумматора, выходы второго и четвертого умножителей подключены к входам второго сумматора, выход регистра действительной частиоперанда подключен к первым входам третьего и четвертого сумматоров, выход регистра мнимой части операнда подключен к первым входам пятого и шестого сумматоров, выход первого сумматора подключен к вторым входам третьего и четвертого сумматоров, выход второго сумматора подключен к вторым входам пятого и шестого сумматоров, выходы четвертого и шестого сумматоров являются выходами действительной и, мнимой частей первого результата устройства, выходы третьего и пятого сумматоров являются выходами действительной и мнимой частей второго результата устройства. На чертеже приведена функциональная схема устройства для реализации алгоритма быстрого преобразования Фурье. Устройство содержит коммутаторы 1 и 2, регистры 3 и 4 действительной и мнимой частей операнда, регистры 5 и б действительной и мнимой частей весового коэффициента, умножители 7-10, сумматоры 11-16, дешифратор 17, шину 18 мнимой части операнда А(к) шину 19 действительной части операнда Д4(к).шину 20 мнимой части операнда А(), шину 21 действительной части оп бранда Й|(), шину 22 мнимой части весового коэффициента, шину 23: действительной части весового коэффициента, ход 24 мнимой части операнда А.;, (j ) , выход 25 мнимой части операнда , (к) , выход 26 действительной части операнда , (j), выход 27 действительной части операнда A((k). Алгоритм работы устройства описывается следующим образом: , (j)iB (}) (K)W;p.. (1) А,Ч( )CB (р-Вц fK)WH , В- (i ) Г i i Р Р lReA((j)+ l-ReA(K), при в- fKb Р « ,А-(р + Г.1„А(к), (2) при означавт операцию комплексного сопряжения.

Выражения (1) и (2) представляют собой базовую операцию алгоритма БПФ

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

На (. -и итерации алгоритма БПФ на входы Г8-21 подаются два комплексных операнда А; (j) и А, (к), а значения весовых коэффициентов поступают на регистры 5 и 6 по входам 22 и 23, Если показатель р весового коэффициента W .равен нулю, то Re Wj 1, и в регистр 5 действительной части весового коэффициента запишутся все единицы. При этом на выходе дешифратора 17 сформируется логическая единица, которая поступает на управляющие входы коммутаторов 1 и 2 и выполняется коммутация операндов А| (j ) и (к) в соответствии с выражением (2), Если же показатель р весового коэффициента не равен нулю, то в двоичном представлении действительной части весового коэффициента будет всегда хотя бы один нуль, Поэтому на выходе дешифратора 17 будет логический нуль и коммутация операндов А (j ) и А(к) в соответствии с выражением (2) осуществляться не будет.

После выполнения коммутации резул тирующее значение операнда В(i)

записьтается в регистры 3 и 4, а значение операнда В(к) подается на входы умножителей 7-10. На выходах

умножителей 7-10 формируются одновременно четыре произведения

Re в,(к). , Re В); (к)lti,w , ImB, (к)--Rewg ,:5rn Bi(K)ImWf . На выходах сумматоров 12 и 11 образуются значения действительной и мнимой частей произведения двух комплексных чисел (K)W;J5

Re B,(K) В; (K)-Rew5 - ItTi В (к)- Гт |;B; (к) B;(K)-tniWS +

+ lni в ,(K).Re

в соответствии с выражен б1 (1)

сумматоры 15 и 13 образуют значения соответственно действительной и мнимой частей нового операнда () , С помощью сумматоров 16 и 14 фО1ж1ируется значение операнда ) , Результирующие значения операндов А д, (J), A. (к) поступают на выходы 24-27 устройства.

В зависимости от интерпретации знакового разряда сумматора 14 с выходов 25 и 27 снимаются сопряженные значения операнда А,,. (к) ,

Использование изобретения позволяет увеличить быстродействие устроства быстрого преобразования Фурье более чем в 2 раза по сравнению с прототипом. Это обусловлено тем, чт при вычислении спектра число базовы операций вида (1) и (2) уменьшается более чем в 2 раза по сравнению с числом базовых операций, используемьж в прототипе.

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее регистры действительной и мнимой частей операнда, регистры действительной и мнимой частей весового коэффициента, четыре умножителя и шесть сумматоров, причем входы регистров действительной и мнимой частей весового коэффициента являются входами действительйой и мнимой частей весового коэффициента устройства, о т л и чающеес я тем, что, с целью повьяиения быстродействия устройства, оно содержит два KOMN.yTaxopa и дешифратор, причем вход действительной части первого операнда устройства соединен с входом регистра действительной части операнда, входы мнимойчасти первого операнда и действительной части второго операнда устройства соединены .с информационными входами первого и второго коммутаторов, выход первого коммутатора подключен ,к первым входам первого и второго умножителей, выход второго KOMNiyTaTo pa подключен к входу регистра мнимой части операнда, вход мнимой части второго операнда устройства соединен с первыми входами третьего и четвертого умножителей, выход регистра действительной части весового коэффициента подключен к вторым входам первого и четвертого умножителей, а также к входу дешифратора, выход которого подключен к управляющим входам первого и второго коммутаторов, выход регистра мнимой части весового коэффициента подключен к вторым входам второго .и третьего умножителей, выходы первого и третье го умножителей подключены к входам первого сумматора, выходы второго и сл четвертого умножителей подключены к входам второго сумматора, выход регистра действительной части операнда подключен к первым входам третьего и четвертого сумматоров, выход регистра мнимой части операнда подключен к первым входам пятого и шее-, того сумматоров, выход первого сумматора подключен к втopы входам -ч1 третьего и четвертого сумматоров, X 4: ВЕлход второго сумматора подключен к j BTOptJM входам пятого и шестого сум- ; маторов, выходы четвертого и шестого ;:о сумматоров являются выходами действи- ; тельной и мнимой частей первого реэуль1 тата устройства, выходы третьего и L пятого сумматоров являются выходами действительной и мнимой частей второ го результата устройства.