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

 

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

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

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

РЕСПУБЛИК (19) (11) 3(51) 5 06 F 15 332

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3486981/18-24 (22) 30. 08, 82 (46) 07. 03. 84, Бюл. )) 9 (72) Г.В ..Зайцев и Н, Е, Нагулин (53) 681.3 (088.8) (56) 1. Оппенгейм Э. Применение циф роной обработки сигналов.

М., Мир, 1980, фиг, 5.23, 2, Авторское свидетельство СССР

9 421994, кл, C) 06 F 15/332, 1971 (прототип). (54 ) (57 ) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

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

ФУРЬЕ, содержащее регистры действительной и мнимой частей операнда, регистры действительной и мнимой частей весового коэффициента, четыре умножителя и шесть сумматоров, причем входы регистров действительной и мнимой частей весового коэффициента являются нходами действитель))ой и мнимой частей весового коэффициента устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, оно содержит два коммутатора и дешифратор, причем вход действительной части первого операнда устройства соединен с входом регистра дей=твительной части операнда, входы мнимойчасти первого операнда и дейстнительной части второго операнда устройства соединены с информационными входами первого и второго коммутаторон, выход первого коммутатора подключен ,к первым входам первого и второго умножителей, выход второго коммутатора подключен к входу регистра мнимой части операнда, вход мнимой части второго операнда устройства соединен с первыми входами третьего и четвертого умножителей, ныход регистра действ ительной части весового коэффициента подключен к вторым входам первого и четвертого умножителей, а также к входу дешифратора, выход которого подключен к управляющим входам первого и в торого коммутаторов, выход регистра мнимой части весового коэффициента подключен к вторым входам второго и третьего умножителей, выходы первого и третьего умножителей подключены к входам первого сумматора, выходы второго и четвертого умножителей подключены к входам второго сумматора, выход регистра действительной части операнда подключен к первым входам третьего и четвертого сумматоров, выход Я регистра мнимой части операнда подключен к первым входам пятого и шестого сумматоров, выход первого сумматора подключен к вторым входам третьего и четвертого сумматоров, выход второго сумматора подключен к вторым входам пятого и шестого сумматоров, выходы четвертого и шестого сумматоров являются выходами действительной и мнимой частей первого резуль1 тата устройства, выходы третьего и пятого сумматоров являются ныходами действительной и мнимой частей нторо го реэультата устройства.

1078434

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

10 коэффициент (1$, Наиболее близким техническим решением к изобретению является устрой ство для реализации алгоритма быстрого преобразования Фурье, содержащее 15 четыре умножителя, шесть сумматоров, регистры действительной и мнимой частей операндов, регистры действительной и мнимой частей несоного коэффициента, причем выходы регистрон дей- 2О ствительной и мнимой частей несового коэффициента соединены с первыми входами умножителей с первого по четвертый, вторые входы которЫх соединены с выходами регистрОв действи- 25 тельной и МННМоА частей перного и второго операндов, выходы с третьего по шестой сумматоров соединены со сднигающими входами регистров операндов j2J.

Недостатком известных устройств является низкое быстродействие из-за избыточного общего количества арифметрических операций, Цель изобретения - поньпаение быстродействия устройстна, Поставленная цель достигается тем, что устройство для реализации алгоритма быстрого преобразования Фурье, содержащее регистры действительной и мнимой частей операнда, регистры действительной и мнимой частей весового коэффициента, четыре умножителя и шесть сумматоров, причем входы регистров дейстнительной и мнимой частей ве- 45 сового коэффициен-а являются входами дейст ;ительной и мнимой частей весового коэффициента устройства, содержит дна коммутатора и дешифратор, причем вход действительной 50 части первого операнда устройства соединен с входом регистра действительной ласти операнда, входы мнимой части первого операнда и дейстнительной части второго операнда устройства соединены с ин. формационными входами первого и второго коммутаторов, выход перво го коммутатора подключен к первым входам первого и второго умножителей, выход второго коммутатора под- <() ключен к входу регистра мнимой.части операнда, нхоц мнимой части второго операнда устройства соединен с первыми нхолами третьего и четвер того умножителей, выход регистра действительной части весового коэффициента подключен к вторым входам первого и четнертого умножителей, а также к входу дешифратора, выход которого подключен к управляющим входам первого и второго коммутаторов, выход регистра мнимой части весового коэффициента подключен к вторым входам второго и третьего умножителей, выходы первого и третьего умножителей подключены к входам первого сумматора, выходы второго и четвертого умножителей подключены к входам второго сумматора, выход регистра действительной части операнда под- ключен к первым входам третьего и четвертого сумматоров, выход регистра мнимой части операнда подключен к первым входам пятого и шестого сум-маторов, выход первого сумматора под-ключен к вторым входам третьего и четвертого сумматоров, выход второго сумматора подключен к вторым нходам пятого и шестого сумматоров, выходы четвертого и шестого сумматоров являются выходами действительной и мнимой частей первого результата устройства, выходы третьего и пятого сумматоров являются выходами действительной и мнимой частей второго результата устройства.

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

Фурье.

Устройство содержит коммутаторы 1 и 2, регистры 3 и 4 действительной и мнимой частей операнда, регистры 5 и б действительной и мнимой частей весового коэффициента, умножители 7-10, сумматоры 11-1б, дешифратор 17, шину 18 мнимой части операнда А;(к), шину 19 действительной части операнда A»(к),,шину 20 мнимой части операнда A ()> шину 21 действительной части операнда А (), шину 22 мнимой части весового коэффициента, шину 23.действительной части весового коэффициента, вы од ход 24 мнимой части операнда A. (»), выход 25 мнимой части операнда

А; (й), выход 26 действительной части операнда A»« (j), выход 27 действительной части операнда A», (k).

Алгоритм работы устройства описывается следующим образом:

А»ч» ())=В» (i)+ i (к)Фн, . (1)

А„, » (к)= (В (j )-В @)Wg) где В,(> fA;(I), при р40

L Re A < (j )+ 1 Qe A„(xc), при р=О

А; (к), при рФО

1rnA» (j )+1.1„,А„(»»), (2) при р= означает операцию комплексного со пряжения.

1078434

ВНИИПИ Заказ 965/43 . Тираж 669 Подписное

Филиал ППП "Патент", r. Ужгород, ул,.Проектная, 4

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

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

На (, -й итерации алгоритма БПФ на входы 18-21 подаются два комплексных операнда й, () и A, (к), а значения весовых коэффициентов поступают на регистры 5 и 6 по .входам 22 и 23.

Если показатель р весового коэффициента W> равен нулю, то ((е Ъ = 1, Р

TeVI 0 и в регистр 5 действительной

О части весового коэффициента запишутся все единицы. При этом на выходе дешифратора 17 сформируется логическая единица, которая поступает на 15 управляющие входы коммутаторов 1 и 2, и выполняется коммутация операндов и () и А; (к) в соответствии с выражением (2) . Если же показатель р весового коэффициента не равен нулю, то в двоичном представлении действительной части весового коэффициента будет всегда хотя бы один нуль. Поэтому на выходе дешифратора 17 будет логический нуль и коммутация операндов А< () и А (к) в соответствии с выражением (2 ) осущес твля тьс я не будет.

После выполнения коммутации резуль тирующее значение операнда В„ (j ) записывается в регистры 3 и 4, а значение операнда В, (к) подается на входы умножителей 7-10. На выходах умножителей 7-10 формируются одновременно четыре произведения Е В„ (к) ГЕ@, РЕ В (к) 3п W„, 1 В; (к) . Яе щ, 3 В (к) Im Wl

На выходах сумматоров 12 и 11

М образуются значения действительной и мнимой частей произведения двух комплексных чисел В,((к) Ml>

Re (в;(к) ччн„ =(е B „(K) Re Як„

1m В (к)

im В; (к) W „)= Re В; (к) Lm W> +

+ tw В; (к) Re W „

В соответствии с выраженИЙ (1) сумматоры 15 и 13 образуют значения соответственно действительной и мнимой частей нового операнда A g,t (g) .

С помощью сумматоров 16 и 14 форйируется значение операнда А<+ ((к) .

Результирующие значения операндов

А;, (j), A<+, (к) поступают на выходы 24-27 устройства.

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

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