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

 

); с,. ч, т

> ииатенть т.: .. - ., а, .;., „.л г»»Я,Яще щд>>»)уо "

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К ЯВТОРСКОМУ СВИДЕЛЛЬСТбУ (61) Дополнительное к авт. саид-ву(22) Заявлеио01.12.75 (21) 2195261/18-24 с присоединением заявки ph (23) Приоритет— (43) Опубликовано15.05. 78.бюллетень № 18 (4б) Дата опубликования описаниями.Î .73.

Союз Советских

Соцналнстнческнх

Республнк

0 ) 607213 (Sl) М. Ыл.

$06 P7/38

Гасударственный комитет

Совета тйнннотроа СССР оо делам нзооретеннй н открытий (53) УДК681.З25 (088.8) (72) Авторы изобретения

В. В. Коломейхо, И. Г. Мороз-Подворчан и В. Д, Петушак

Ордена Ленина институт кибернетика АН Украинской CCP (71) Заявитель (54) УСТРОЙСТВО ЛЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА

БЫСТРОРЭ ПРЕОБРАЮВАНИЯ ФУРЬЕ

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

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

Наиболее близким по технической сущности и достигаемому эффекту к изобретению является устройство (2j, содержащее девять преобразователей кодов, четыре сумматора, выходы которых являются выходами устронства, и три умножителя. Причем выходы умножителей соединены соответственно с входами первого, второго н третьего преобразователей кодов, первые выходы которых соединены coor 20 ветственио с первым входом первого суммато- ра, с вторым входом первого сумматора и

BT0pblM входом третьего.сумматора, вторые выходы второго и третьего преобразователей кодов соединены с вторыми входами соответствен. нс Ròîðoãl) и ч<.т))). рто) о сумматоров, третьи входы первого и третьего сумматоров объединены соответственно с третьими входами второго и четвертого сумматоров, а входы четвертого и пятого преобразователей кодов являются соответственно первым и вторым входами устройства.

Недостатком устройства являются большие аппдратурные затраты.

Вычислительная процедура алгоритма БПФ укаэанного устройства описывается следующей системой уравнений: а) + sou); — вг))) г = С), Bl — B)u) l + 82u)г = d1, + вгм | + alu» = Сг, аг — B>u) — BI u) 2 = dl, где а) + jag = А; ei + вг =  — и ходные комплексные переменные;

))) + ju). = W — комплексны:, оэффнциент;

Cl + jC = С; dl - jd, = D — результаты вычислительной процедуры алгоритма

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

Это достигается тем, что в него вводят вычитатель и пятый сумматор. Причем перзый и второй входы последнего соединены соответственно с входамн четвертого н пятого преобразователей кодов, перви)й и второй входы вычи6072!3 (><) lxl + xj

Если х < = xi

{Х)Формула изобретения

S5

60 тателя являются соответственно первым и вторйм входами для ввода констант и соединены соответственно с входами шестого и седьмого преобразователей кодов, выходы вь>читателя и пятого сумматора соединены соответственно с входами восьмого и девятого преобразователей кодов, выходы восьмого и девятого, седьмого и четвертого, шестого и пятого преобразовагелей кодов, соединены с первым и вторым входами соответственно первого, второго и третьего умножителей. При этом первые входы второго и третьего сумматоров объединены и соединены с вторым выходом первого преобразователя кодов, первые входы первого и четвертого сумматоров соединены между собой, а третьи входы первого и третьего сумматоров являются соответственно третьим и четвертым >г входами устройства.

В данном устройстве используется измененное представление комплексных чисел. Комп. лексные ч8сла представлены не действительной и мнимой составляющими, а суммой и разностью действительной и мнимой частей

8i = 8i + 82, 82 а> — 82, в =- в; + вг, вг = Bi — вг,.

<9j=<9jk 0>21 ОЭ2 <9> 0>2>

cT = cj + сг, Сг = Cj — сг, dI 4i + 42, И di — 42. 25

При этом вычислительная процедура алгоритма БПФ принимает вид с > 8 + 82) (0> I — 0> 2), d4j - 8 < — в! <9< --. >2-(8 j + 83) (0> < — <9 2); сг - 8$ + вг<9j — + (81 + в3) (<9 i — <92);

42 8Х вЂ”. 8)<9 j + Q(8 I + 82) (0> i 0>2) °

Для введенного представления операндов вычислительная процедура БПФ отличается от примененной в известном устройстве тем, что срдержнт три операции умноже.::ия вместо четы! рех. з5

Полученные на последнем этапе алгоритма ЬПФ результаты представлены также суммой. и разностью действительной и мнимой частей. В дальнейшем комплексные результаты Х = х> + )хг обычно преобразуются согласно следующей формуле:

+ хг, xf = х> — хг, то

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

Структурная схема предлагаемого устройства представлена на чертеже и содержит вычитатель 1, преобразователи 2 — !О кодов, умножмтелй Il — 13 и сумматоры !4 — 18.

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

На входы 19 н 20 устройства поступают соотзетственно коэффициенты 0»" и «> 2, представленные в дополнительном коде. На входы 21, 22, 23, 24 в дополнительном коде поступают соответственно операнды в <, вг, а . гг, кот<>рые прели I!>II I<ëüïî <>1>омас<птаб>онгнь< (для z<>I <> чтобы <>!»<»ь<»о.!k;ejjj<циенты,» и <> 2 «оступа» т на вычитатель 1, который выполняет операцию 0> > — «Д, 0,»< выи лняет операцию Bi a вг, Кроме того, числа

0>;, «Л, в), вг поступают на входы соответственно преобразователей 7. 8, 5, 6, которые выполняюг перекодировку этих чисел из дополнительного кода в прямой. Разность 0» — 0Я и сумма Bi + в2 с выходов вычитателя 1 и сумматора 18 поступают соответственно на преобразователи 9 и !О, которые преобразуют их в прямой код. На умножитель 12 числа 0>"г и Bi поступают в прямом коде соответственно с выходов преобразователей 8 и 5. На умножитель

13 числа И и 87 поступают в прямом коде соответственно с выходов преобразователей 7

И 6. На уМНОжитЕЛЬ 1! ЧИСЛа (0»" — «> г) И (Bi + вг) поступают в прямом коде соответственно с выходов преобразователей 9 н !0. С выходов умножителей 11, 12, 13 соответственно на преобразователи 2, 3, 4 поступают в прямом коде произведения - (в> + в ) (0> i— — 0>2); Bi«> г; вг<0*>. Преобразователи 2, 3, 4 имеют выходы 25 — 30. На выходы 25, 27, 29 соответственно преобразователей 2, 3, 4 числа поступают в дополнительном коде, но с тем же знаком, с которым они поступали на входы этих преобразователей На ><х выходы 26, 28, ЗО числа поступают также B дополнительном коде, но с противоположным знаком. Входы 23, 24 устройства, выходы 25- -30 преобразовател, и 2, 3, 4 и входы сумматоров 14 — 17 соединены так, что на выходы 31, 32, 33, 34 сумматоров и всег>о устройства выдаются в дополнительном коде соответственно величины С >; 4 I; Сг, 4г, т.е. результаты вычислительной процедуры алгоритма БПФ.

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

i 0 — 20%.

Устройство для реализации алгоритма быстрого преобразования Фурье, содержагцее денять преобразователей кодов, четыре с>, чматора, выходы которым являются выходами устрой ства, и три умножителя, выходы которых соединены соответс<вепно с входами перв<но, второго и третьего преобразователей кодов, первые выходы кот<>рых соед>«<еиы соответ<.тве><><о

С IIPPB>>IM ВХОДОЧ ПЕРИОГО СУММатОРа. Вто!>Ь>Ч входом первого сумматора и вторым >I <>l<>M третьего cóì÷à îðç, вт >рь«вь<о гь< и«р» >

И TPPT>,<.f<> ЦР«><>f>83<>k<,i> . И; 0 «

«>тОРЬ<МИ Вi< I;l II Е<«0< >, < «>.,I>k

607213 четнгрт >го сумматоров, третьи входы верного н третьег0 сумматоров объединены соответсвенно с третьими входами второго и четвертого сумматоров, а входы четвертого и пятого преобразователей кодов являются соответственно первым и вторым входами устройства, отличааи4е ся тем, что, с целью упрощения устройст. ва, в него введены вычнтатель и пятый с ";матор, первый и второй входы которого сх. иены с входамк соответственно четвертого и пятого преобразователей кодов, первый н вто- рой входы вычитателя являются соответственно первым н вторым входами для ввода констант и соединены соответственно с входами шестого и седьмого преобразователей кодов, выходы вычитателя и пятого сумматора соединены соответственно с входами восьмого и девятого % преобразователей кодов, выходы восьмого и б девятого, седьмого и че1вертого. шест<и, пятого преобразователей кодов соединены первым и.вторым входами соответственно н -; вого, второго н третьего умножителей, пр : этом первые входм второго и третьего сумматоров объединены и соединены с вторым выходом первого преобразователя кодов, первые входы первого и четвертого сумматоров соедииены между-собой, а третьи входы первого и третьего сумматоров являются соответственно э--таим и четвертым входами устройства..

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

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

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

607213

Составитель И. Грибков

Танкред О. Луговая Корректор А. 1риценко

Тираж 826 Подпнгное

Редактор Т. Юрчнкова

Заказ 2584 36

ЫН11И11И Г rr ударгга нигио к >митета (>неra Ми и тров << ГР ио де. ли изобретений и открмтий

1 18035, Mrí ива, >К 3 Рау игкан изб, з 41. >

Филиал ill ill «11ит ит ° < Уж!ирод. v.r (!роек1иан 4