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

ОП ИСАНИЕИЗОБРЕТЕН ИЯ К ЯВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Соцналнстнческнх респубики(23) Приори осударственный комитетСовета Министров СССРоо делам нааоретенийн открытий(71) Заявитель бе дена Ленива ин(54) УС ТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА СТРОРЭ ПРЕОБРАЮВАНИЯ ФУРЬЕвходы первого и третьего сумматоров объедииены соответственно с третьими входамн второго н четвертого сумматоров, а входы четвертого и пятого преобразователей кодов являются соответственно первым и вторым входамиустройства.Недостатком устройства являются большиеаппдратурные затраты.Вычислительная процедура алгоритма БПФукаэанного устройства описывается следующейсистемой уравнений:а 1 + во), - вго) г = С,а - в 1 о+ вг 11 г = (31;аг + Вгю + Во 1 г = Сг,аг - вго - во 1 г = дг,где а + аг = А; в + вг = В - н . дныекомплексные переменные;ю+ о. = Ф - комплекснц оэффнциент;С ычи щенне устронства в него вводят вы Причем перзый и диненц соотнетст н пяти о преобра орой входы вычи Цель изобретения - упр Это достигается тем, чт читатель и пятый сумматор второй входы последнего с венно с входамн четвертог зователей кодов, первцй н Изобретение относится к вычислительной технике и может быть использовано при построении специализированных цифровых вычислительных машин для получения амплитудных спектров при спектральной обработке сигналов. 5Известно устройство 1, реализующее ал. горитм быстрого преобразования Фурье (БПФ), соде жащее сумматоры, вычитатели, регистры сдвига, блоки оперативной и постоянной памяти Это устройство обладает относительно небольшими аппаратными затратами, но име. ет низкое быстродействие.Наиболее близким по технической сущности и достигаемому эффекту к изобретению является устройство 2, содержащее девять преобразователей кодов, четыре сумматора, выхо ды которых являются выходами устронства, и три умножнтеля. Причем выходы умножителей соединенц соответственно с входами первого, второго н третьего преобразователей кодов, первые выходы которых соединены соог. 2 О ветственно с первым входом первого суммато- ра, с вторым входом первого сумматора и вторым входом третьего.сумматора, вторые вы. ходы второго н третьего преобразователей кодов соелннены с вторыми входами соответствен. но второго н четвертого сумматоров, третьи 25(Х) х,формула изобретения рого нять ра, в ства, дине рого вые в с пер вхол трет тателя являются соответственно первым и вто.рьм входами для ввода констант и соединенысоответственно с входами шестого и седьмогопреобразователей кодов, выходы вьчитателяи пятого сумматора соединены соотве 1 ственнос входами восьмого и девятого преобразователей конов, выходы восьмого и девятого, сель.мого и четвертого, шестого и пятого 1 реобразовагелей кодов, соединены с первым и вторымвходами соответственно первого, второго и тре.гьего умножителей. Приэтом первые входывторого и третьего сумматбров объединены исоединены с вторым выходом первого преобра.зователя кодов, первые входы первого и четвер.того сумматоров соединены между собой, атретьи Входы первого и третьего сумматоровявляются соответственно третьим и четвертым 5входамн устройства,В данном устройстве используется изменен.ное представление комплексных чисел. Комплексные числа представлены не действитель.ной и мнимой составляющими, а суммой и разностью действительной и мнимой частейа = а + 82 а 2 а - аг;В = В + Вг, Вг = В - Вгод = г +г г, Л = о -гс 7 = с + сг, с 3 с - сг,д 7 д+дг; И д - д,. 25При этом вычислительная процедура алго.ритма БПФ принимает видс а + вг + (в + вг) ( - огг);д - а" - в 1 ь 6. - . (в + в 3) (ь - о 2);с 2 - а 3 + вгг - +(в 1 + вэ) ( ь - г 2);дг аг - .Вгы + -"(В + 1) ( ы 2)Для введенного представления операндоввычислительная процедура БПФ отличается отпримененной в известном устройстве тем, чтосрдержнт три операции умноже.ия вместо четырех, З 5Полученные на последнем этапе алгорит.ма ЬПФ результаты представлены также суммой. и разностью действительной и мнимой частей, В дальнейшем комплексные реэульта. ты Х = х + )хг обычно преобразуются со. гласно следующей формуле: Еслн х = х + хг, ХФ = х - хг, то Как видно из последнего выражения, принятое представление комплексных чисел не усложняет окончательную обработку результатов преобразования для вычисления амплитудного спектра.Структурная схема предлагаемого устройства представлена на чертеже и содержит вы. читатель 1, преобразователи 2 - О кодов, ум. ножмтелй 1 - 13 и сумматоры 14 - 18.Работает устройство следующим образом.На входы 19 н 20 устройства поступают соотяетственно коэффициенты щф и г, пред. ставленные в дополнительном коле. На вхо ды 21, 22, 23, 24 в дополнительном коде посту. пают соответственно операнды в, вг, а", зг, ко. торые прелилрпге.оромастабионь (для тго чтбы прпьол:е вычи.лительной процедуры алгоритма БПФ не бы,о пере полнения числового диапазона). Коэффициентыи фг поступают на вычитатель 1, кото. рый выполняет операцию- Д, Опе.пилы в и в 3 поступают на сумматор 8, котор, вы. влияет операцию в + Вг, Кроме того, числа ", Л, в), вг поступают на входы соответст. венно преобразователей 7, 8, 5, 6, которые вы. полняюг перекодировку этих чисел из дополни. тельного кода в прямой, Разность о - Л и сумма в + в 3 с выходов вычитателя 1 и сумматора 8 поступают соответственно на преобразователи 9 и О, которые преобразуют их в прямой код. На умножитель 12 числа"г и в поступают в прямом коде соответственно с выходов преобразователей 8 и 5. На умножитель 13 числа И и В 7 поступают в прямом коде соответственно с выходов преобразователей 7 и 6. На умножнтель 1 числа (Л - г) и (в + вг) поступают в прямом коде соответственно с выходов преобразователей 9 н 10. С выходов умножителей1, 12, 13 соответствен. но на преобразователи 2, 3, 4 поступают в прямом кодероизведения-(В + в) о -- М); ВЛ; вгь. Преобразователи 2, 3, 4 имеют выходы 25 - 30. На выходы 25, 27, 29 соответственно преобразователей 2, 3, 4 числа поступают в дополнительном коде, но с тем же знаком, с которым они поступали на входы этих преобразователей На их выходы 26, 28, ЗО чис. ла поступают также в допОлнительном коде, но с противоположным знаком. Входы 23, 24 устройства, выходы 25- -30 преобразовател, й 2, 3, 4 и входы сумматоров 14 - 17 соединены так, что на выходы 31, 32, 33, 34 сумматоров и всего устройства выдаются в дополнительном коде соответственно величины С, д, Сг, дг, т,е. результаты вычислительной процедуры алгоритма БПФ,Таким образом, введение вычитателя и сумматора, а также описанное соединение всех блоков позволяют устранить один умножитель н один блок преобразования кодов. Данное техническое решение позволяет сократить аппа. ратурные затраты устройства для реализации алгоритма быстрого преобразования Фурье, ориентированного на амплитудный спектр, на0 - 20%. Устройство для реализации алгоритма быстKреобраэования Фурье, содержащее де.преобразователей кодов, четыре с чматоыходы которым являются выходами устройи три умножителя, выходы которых соены соответсвепно с входами первнз, втои третьего преобразователей кодов, перыходы которых соедсны соотает твенно вьм вхолоч первгго сумматора. Втоыч ом первого сумматора и вторьм холом его смча 1 ора, втор,ох и р еть о рорганон,( ,н, орлм ах;.о.,ичетнгртго сумматоров, третьи входы первого н третьего сумматоров объединены соответс. венно с третьими входами второго и четвертого сумматоров, а входы четвертого и пятого пре. образователей кодов являются соответственно первым и вторым входами устройства, откричав- ф целься тем, что, с целью упрощения устройст ва, в него введены вычнтатель и пятый с";- матор, первый и второй входы которого сх, иены с входамк соответственно четвертого и пятого преобразователей кодов, первый н вто. вв рой входы вычитателя являются соответственно первым н вторым входами для ввода констант и соединены соответственно с входами шеестго и седьмого преобразователей кодов, выходы вычитателя и пятого сумматора соединены соответственно с входами восьмого и девятого 1 преобразователей кодов, выходы восьмого и девягого, седьмого и че 1 вертого, шести, пятого преобразователей кодов соединены первым и.вторым вхоЛами соответственно н-; вого, второго н третьего умножителей, пр, этом первые входм второго и третьего сумматоров объединены и соединены с вторым выхо. дом первого преобразователя кодов, первые входы первого и четвертого сумматоров соедииены между-собой, а третьи входы первого и третьего сумматоров являются соответственно эетьнм и четвертым входами устройства.,Исто.н,1 кн информации, принятые во внимание нри экспертизе:1, Специализированный процессор для быстрого решения задач гармонического анализа, Электроника 3 Ж 13, 1968, т, 41.2. Патент США Ж 3591784, кл. б 06 Г 7/38, 1972,607213 Составитель И. ГрибковТеггред О. Луговая Корректор А. Гриценко Тираж 826 1 одннгное Редактор Т. Юрчнкова Заказ 2584/36 ОН 1 И 11 И Гчгула 1)гтаг нного комитета г гггегэ Мггг гг трав г г ГР по ке.гии изобретений и открмтнй 11 ЗМ 5, Мгн ква, К 15 Ратгнгкан ггзб, з 416 Филиал 1111 И 11 ггт нтг Ужгорггз. У,г 1 роек г нан 4