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

(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ тателя являются соответствонно первым и нторЫм входами для ввода констант и соединены соответственно с входами шестого и седьмого преовразователей кодов, выходы вычитателя и пятою сумматора соединены соответственно с входами восьмого и девятого преобразователей кодов, выходы восьмого и девятого, седьмого и четвертого, шестого н пятого преобразователей кодов,соединены с первым и вторым входами соответственно первого, второго и третьего умножителей. При этом первые входы второго и третьего сумматоров объеаннены н сс едннены с вторым выходом первого преобра зователя кодов, первые входы первого и четвертого сумматоров средннены между собой, а третьи входы первого и третьего сумматоров являются соответстпеино третьим и четвертым входами устройства. В данном устройстве используется измененное представление комплексных чисел. Комплексные числа |федставлены не действитель ной н мнимой составляющими, а суммой н разностью действительной и мнимой частей а ai -f 82; aj at - aj; в1 Bi 4 Вг; в BI - Bj; o)i «oi-f (1); () 1-Ш2, d cj - cj; cT ci -f ct; df di-fdi: d « di-dj. При этом вычнслительная процедура алгоритма БПФ прииимает вид с . aV+ -(- 4-(в + eS) ( - О)); d - a1 - в1ю - -(в + в) (w, - wz); с а -f в( -tW + в) (й)1 - о)2); dj - a - sSa + + u%) (u)T - MI). Для введенного представления операндов вычислительная процедура БПФ отличается от прнмеиеикой в известном устройстве тем, что содержит три операции умноже ;ия вместо четы рм. Пш1учеиные на последнем этапе алгорнтма БПФ результаты представлены также суммой, и разностью действительной и мнимой частей. В дальнейшем комплексные результаты X Xi + JX2 обычно преобразуются согласио следующей формуле: (X)/xfTl5 Если х xi -f- xj; X xi (x)- ДiEEJ5IF

Как видно из последнего выражения, принятое представление комплексных чисел не усложняет окончательную обработку результатов преобразования для вычисления амплитудного спектра.

Структурная схема предлагаемого устройства представлена на чертеже и содержит вычитатель t, преобразователи 2-10 кодов, ум ножителн И -13 и сумматоры 14-18.

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

На входы 19 и 20 устройства поступают соответственно коэффициенты о и , представленные в дополнительном коле На вхо ды 21. 22, 23. 24 в дополнительном коде поступают соответстпенно операнды в, в , а, з, коФормует изобретения

Устройство для реализации алгоритма быстрого преобразования Фурье, содержаи1ее девять преобразователей кодов, четыре сумматора, выходы которых являются выходами устрой ства. и три умножителя, выходы которых соединены соответс1веино с входами первого, втоpoiO и третьего преобразователен колов, первые выходы которых соединены соигветгтвеино с первым входом первого сумматора, i вторым входом первого сумматора и вторым 1(лом третьего сумматора, вт(1ры1 )-i,i нтчркго и третьего прсоЛрнчпц.ц .ти Kniipi м, i.u.tii.

с вторыми ВМ) l;i и С()| : Hi 1 . I in ,11 Bl Г I 1 т(фые предвари rtvibMt) 11рома1-1 1габн кшгжы (для Tort) чтобы при ны110. вычислительной процедуры алгоритма Ы1Ф не было пере полнения числового диапазона). Коэффициенты м)| и (Л 11оступан)т на вычигатель 1, который выполняет операцию (o. Операнды и в поступают на сумматор 18, который выполняет операцию в f в1 Кроме того, чис.па оЛ, , в1, в поступают на входы соответственно преобразователей 7. 8, 5, 6, которые выполняют перекодировку этих чисел из дополнительного кода в прямой. Разность о) - ьД и сумма в7 -4- в с выходов вычитателя 1 и сумматора 18 поступают соответственно на преобразователи 9 и 10, которые преобразуют нх в прямой код. На умножитель 12 числа w н вТ поступают в прямом коде соответственно с выходов преобразователей 8 и 5. На умножитель 13 числа ш и в поступают в прямом коде соответственно с выходов преобразователей 7 н 6. На умножитель 11 числа (оЛ - ) и (в + Вг) поступают в прямом коде соответственно с выходов преобразователей 9 н 10. С выходов умножителей II, 12, 13 соответственно на преобразователи 2, 3, 4 поступают в прямом коде произведения |( + в) (wl - - coi); в(,). Преобразователи 2, 3, 4 имеют выходы 25-30. На выходы 25, 27, 29 соответственно преобразователей 2, 3, 4 числа поступают в доцатиительном коде, но с тем же знаком, с которым они поступали на входы этих преобразователей На их выходы 26. 28, 30 числа поступают также в допблнительном коде, но с противоположным знаком. Входы 23, 24 устройства, выходы 25- -30 преобразователей 2, 3, 4 и входы сумматоров 14-17 соединены так. что иа выходы 31, 32, 33, 34 сумматоров и всего устройства выдаются в дополнительном коде соответственно величины d. т.е. результаты вычислительной процедуры алгоритма БПФ. Таким образом, введение вычитателя н сумматора, а также описанное соединение всех блоков позволяют устранять один умножитель н одии блок преобразования кодов Данное техническое решение позволяет сократить аппаратурные затраты устройства для реализации алгоритма быстрого преобразования Фурье, ориентированного иа амплитудный спектр, ма 10-20%.

четнертого суммагоров, третьи входы перииго и т( сумматоров (ХЗ-ьединены ссютветсвенно с третьими входами второго и четвертого сумматоров, а входы четвертого и пятого преобразователей кодов являются соответственно первым и вторым входами устройства, отличающееся тем, что, с целью упрощения устройства, в него аведены вычитатель и пятый сумматор, первый и второй входы которого ctx. йены с входами соответственно четвертого к пятого преобразователей кодов, первый и второй входы вычитателя являются соответственно первым и вторым входами для ввода констант и соединены соответственно с входами uiecroго и седьмого преобразователей кодов, выходы вычитателя и пятого сумматора соединены соответственно с входами восьмого и девятого преобразователей кодов, выходы восьмого и

дeвяtoгo, седьмого и четвертого, шестого ,пятого преобразоват&пей кодов с(№дйнень перяым и вторым вхоЛами соответственно nvf вого. второго н третьего умножителей, этом первые входы второго и третьего сумматоров объединены и соединены с вторым выходом первого преобразователя кодов, первые входы первого н четвертого сумматоров соединены между собой, а третьи входы первого и третьего сумматоров являются соответственно н четвертым входами устройства.

.шн ннформацйн. принятые во внимание при экспертизе:

1.Специализированный процессор для быстрого решения задач гармонического анализа еЭлектроника № 3, 1968, т. 41.

2.Патент США J 3591784, кл. G 06 F 7/38, 1972.