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

 

1. УСТЮЙСТВО ДЛЯ БЫСТРОГО ; ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый, второй, третий и четвертый входные регистры, регистр весового коэффициента, множительный , первый сумглатор, первый и второй коммутаторы, первый и второй регистры слагаемых и блок управления, причем выходы первого и второго входных регистров соединены с первым и вторым информационными входами первого коммутатора соответственно, первый вход устройства соединен с информационным входом регистра весового коэффициента, первый и второй выходы блока управления соединены с управляющими входами первого и второго коммутаторов соответственно , отличающееся тем, что, сцелью упрощения устройства , оно содержит второй сумматор и .третий регистр слагаемых, причем информационные входы первого, второго , третьего и четвертого вход- . ных регистров объединены и являются вторым входом устройства, выходы третьего и четвертого входных регистров соединены с первьам и вторым информационными входами второго коммутатора соответственно, выход которого соединен с первым информационным входом второго сумматора , выход которого является выходом устройства, выход первого коммутатора соединен с первым информаци онньтм входом множительного блока, йыход которого соединен с инфор-мационными входами первого и второго регистров слагаемых, выходы которых соединены соответственно с первым информационным входом пер-, вого сумматора и информационным входом третьего регистра слагаемых, выход которого соединен с вторым-информационным входом первого сумматора выход которого соединен с вторым информационным в.ходом второго сумматора , первый и второй выходы блока управления соединены с управляю (Л .щими входами второго и первого сумматоров соответственно, управляющие входы первого, второго,третье- / .го и четвертого входных регистров и регистра весового коэффициента подключены к третьему, четвертому, пятому, шестому и седьмому выходам блока управления соответ : твенно, восьмой выход блока управлен-ия сое- 4;а динен с управляющим входом первоЬЭ го регистра слагаемых, девятый выход блока управления соединен с ,уп-- равляющими входами второго и треto тьего регистров слагаемых. 2. Устройство nd П.1, о т л и CD ч а ющ е е с я тем, что, блокуп ,равления содержит генератор импульсов , счетчик, дешифратор, первый; ;второй и третий элементы ИЛИ,причем .выход генератора импульсов соединен .с входом счетчика, выходы которого объединены с первым и вторым выходами блока соответственно и с входами дешифратора, первый,второй, третий и -четвертый выходы которого являются третьим, четвертым, пятым и шестым выходами блока .и соединены с входами первого элемента ИЛИ, выход которого является седьмым вы

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

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

РЕСПУБЛИК

„„80„„1042029

3(Я) 6 06 Г 15/332

»

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

Н ABTOPCHQMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬП ИЙ. (21) 3367987/18-24 (22) 23.12.81 (46) 15.09.83. Бюл. У .34 (72) Ю.С.Каневский, С.Э.Котов, Н.Е.Куц, Б.А.Некрасов и О.А.Федотов (71) Киевский ордена Ленина политехнический институт им. 50-летия

Великой Октябрьской социалистической революции (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

9 399859, кл. G 06 F 7/38е 1971.

2. Авторское свидетельство СССР

9 7 361 3, кл. G 06 F 15/332, 1977 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый, второй, третий и четвертый входные регистры, регистр весового коэффициента, множительный блок, 1 первый сумматор, первый и второй коммутаторы, первый и второй регистры слагаемых и блок управления, причем выходы первого и второго вход« ных регистров соединены с первым и вторым информационными входами пер"

soro коммутатора соответственно, первый вход устройства соединен с информационным входом регистра ве сового коэффициента, первый и второй ныходы блока управления соединены с управляющими входами первого и второго коммутаторов соответственно, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит второй сумматор и .третий регистр слагаемых, причем информационные входы первого, второго, третьего и четвертого входных регистров объединены и являются Вторым Входом устройствае Вы ходы третьего и четвертого входных регистрон соединены с первым и вто рьнл информационными входами второго коммутатора соответственно, выход которого соединен с первым информационным входом второго сумматора, выход которого является выходом устройства, выход первого коммутатора соединен с первым информаци.онным входом множительного блока, выход которого соединен с инфор- ° мационными входами первого и второго регистров слагаемых, выходы которых соединены соответственно с первым информациОнным входом пер-, вого сумматора и информационным входом третьего регистра слагаемых, выход которого соединен с вторым информационным входом первого сумматора, выход которого соединен с вторым информационным входом нторого сумматора, первый и второй ныходы блока

O управления соединены с управляю:щими входами второго и первого сумматоров соответстненно, управляю щие входы первого, второго,третье- / го и четвертого входных регистров и регистра весового коэффициента и подключены к третьему, четвертому, пятому, шестому и седьмому выхо- дам блока управления соответственное носьмой выход блока управления сое- . динен с управляющим входом перво- 4 го регистра слагаемых, девятый выход блока управления соединен с,управляющими входами второго и третьего регистрон слагаемых.

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что, блок уп,.равления содержит генератор импульсов, счетчик, дешифратор, первый;

:второй и третий элементы ИЛИ,причем .выход генератора импульсов соединен «

;с входом счетчика, выходы которого объединены с первым и вторым выходами блока соответственно и с входами дешифратора, первый, второй, третий и -четвертый выходы которого являются. третьим, четвертым, пятым и шестым выходами блока и соединены с входами первого элемента ИЛИ, выход которого является седьмым вы1042029 ходом блока, второй и четвертый вымоды дешифратора соединены с нходами второго элемента ИЛИ, выход которого является восьмым выходом

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

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

Недостатком указанного устройства является.его сложность.

Наиболее близким к изобретению является устройство для быстрого преобразования Фурье, содержащее четыре входных регистра, два регистра несоной функции, два коммутатора, блок управления, сумматор, два регистра слагаемых, блок умножения, четыре регистра,произведений, причем входы входных регистров являются входами устройства, а вымоды соединены с коммутатором слагаемым, выход которого соединен с входом сумматора, выход которого является выходом устройства и соединен с входами первого и второго регистров с11агаемых, выходы которого соединены с входами коммутато" ра сомножителей, выход которого соединен с входом блока умножения, выход которого соединен с входами первого-четвертого регистров произведений, выходы которых соединены с нходами коммутатора слагаемым, входы устройства являются входами регистров несовой функции, выходы которых соединены с входами коммутатора слагаемых сомножителей, выходы блока управления соединены с управляемыми входами коммутаторов 32).

Недостатком данного устройства. является. также его сложность.

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

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

2 емых и блок управления, причем выходы первого и второго входных регистров соединены с первым.и вторым информационными входами коммутатора соответственно, первый вход устройства соединен с информационным входом регистра весового коэффициента, первый и второй входы блока управления соединены с управляющими входами первого и второго коммутаторон соответственно, содержит второй сумматор и третий регистр слагаемым, причем информационные входы первого, второго, третьего и четвертого нходных регистров объединены и являются вторым входом устройства, выходы третьего и четнертого входных регистров соединены с первым и вторым информационными входами второго коммутатора соответственно, выход которого соединен с первым информацион20 ным входом нторого сумматора, выход которого является выходом устройства, выход первого коммутатора соединен. с первым информационным входом множительного блока, выход которого

25 соединен с информационными входами первого и второго регистров слагаемых, выходы которых соединены со- отнетственно с первым информационнымвходом первого сумматора и информаЗО ционным входом третьего регистра слагаемых, выход которого соединен с вторым информационным входом первого сумматора, выход которого соединен с вторым информационным вмо дом второго сумматора, первый и нторой выходы блока управления соединены с управляющими входами второго и первого сумматоров соответственно, управляющие входы первого, второго, третьего и четвертого входных регистров и регистра весового коэффициента подключены к третьему, четвертому, пятому, шестому и седьмому выходам блока управления соответственно, восьмой выход блока управления

45 соединен с упранляющим входом первого регистра слагаемых, девятый выход блока управления соединен с управляющими нходами второго и третьего регистров слагаемых.

Хроме того, блок управления Содержит генератор импульсов, счетчик, дешифратор, первый, второй

1042029

50 и третий элементы ИЛИ, причем вы,ход генератора импульсов соединен с входом счетчика, выходы которого соединены с первым и вторым выходами блока соответственно и .с входами дешифратора, первый, второй, третий и четвертый выходы которого являются третьим, четвертым, пятым и шестым выходами блока и соединены с входами первого элемента ИЛИ, выход которого яв- 10 ляется выходом блока, второй и четвертый выходы дешифратора соединены с входами второго элемента

ИЛИ, выход которого является восьмым выходом блока, первый и третий выходы дешифраторы соединены с входами третьего элемента ИЛИ, выход которого является девятым выходом блока.

На фиг.1 представлена схема предлагаемого устройства; на фиг.2 тоже, блока управления;.на фиг.З структура сигналов управления.

Устройство содержит входные регистры 1-4, регистр 5 весового коэффициента, коммутаторы б и 7,, множительный блок 8,регистры 9, .10 и 11 слагаемых, сумматоры 12 и

13, блок 14 управления, генератор-15 импульсов, счетчик 16, стробируемый дешифратор 17, выходы 21 — 26 блока управления, элемент ИЛИ 18 с выходом

27, элемент ИЛИ 19 с выходом 28, элемент ИЛИ 20 с выходом 29, входы 30 и 31 устройства, выход 32 устройства.

Устройство выполняет операции БПФ 35 за восемь тактов, причем блок 14 управления формирует на своих выходах 21-29 сигналы структура которых изображена на фиг.3.

Устройство выполняет операцию БпФ 40 по основанию 2: . =6- +С %1

А „=Ь,.-С е

ReA-=РеВ.+Rec Pew -3 С.Э 45

i i i mirn

Д А. =3 Ц. +РеС. 3 w1+3 С,. Ре и

ReA. =Реб.-РеС.Rew +3 С.э ча

1+1 i i mim э д. =э . п .+„= „,В;-Рес;З„,w-3 С, pew, где В;„ С вЂ” исходные отсчетыу А;, А; - преобразования отсчетами а1 вЂ, весовой коэффициент, j 2 i а =e где М вЂ” количество отсчетов в массиве.

В первом такте по сигналу с выхода 23 блока 14 управления во.вход- 60 ной регистр 1 принимаются величины:

Яе С„, в регистр 5 весового коэффициейта по сигналу с выхода 29 принимаются величина Rem, коммутатор 6 по сигналу с выхода 21 блока 14 подключает вход регистра 1 ко входу множительного блоКа 8, выполняется умножение, и на выходе блока .8 формирует;ся произведение РеС; Ре а1.

Во втором такте по сигналу с выхода 27 блока 14 это произведение принимается в регистр 9, в регистр 2 по сигналу с выхода 24 принимается величина J С;, в регистр 5 по сигналу с выхода 29 принимается величина Э э1, коммутатор 6 по сигналу с выхода 21 блока 14 подключает выход регистра 2 ко входу множитель-ного блока 8, выполняет умножение, и на выходе блока 8 формируется про- изведение 3„„С1-З„,ч4 .

В третьем такте по сигналу с выхода 28 блока 14 произведение

З„,С„-Э„,w принимается в регистр 10, содержимое регистра 9 (МС; Реж" ) переписывается в регистр 11,.в регистр 3 по сигналу с выхода 25 блока 14 принимается величина Реб;, коммутатор 7 по сигналу .с выхода 22 блока 14 подключает выход регистра 3 ко.входу сумматора 13. Сумма.тор 12, на управляющий вход кото-. рого поступает сигнал с выхода 22 блока 14, выполняет вычитание.и формирует величину Рес" Reel — 3 С. - 3 и

i nl i tel а на выходе сумматора 13, выполняющего сложение, формируется величина

ReA.=RaB,.+(ReL Rew -3 C;3 w ) роме того коммутатор 6 подключает выход Регистра 1 ко входу множительного блока 8, и на его выходе формируется произведение РеС.. д1.

В четвертом такте по сигналу с выхода 27 блока 14 произведениЕ

Рес;-3 w принимается в регистр 9, в регистр 4 по сигналу с выхода 26 принимается величина Э„ В, в регистр

5 по сигналу с выхода 29 принимаеТся величина Ке й", коммутатор б подключает выход регистра 2 ко входу множительного блока 8, на выходе которого формируется произведение Э„,с; ° Rew . Сумматор 12 выполняет операцию. вычитания и «на выходе, формирует разность РеС;. Rew -дщС; - J w, а на выходе сумматора 13, выйолняющего вычитание, формируется величина РеА;+ =РеВ„-(Rec," Reer -7 С; 7 чч ).

В пятом такте йроизведение

З С„. Re w принимается в регистр,10, содержимое регистра 9 (ReC- -3 чч )

1 ПЪ переписывается в регистр 11 суме

I матор 12 формирует сумму ReC;.3„,ж +

+л С; Рея(, коммутатор 7 подключает выход регистра 4 ко входу сумматора 1.3, на выходе которого формируется сумма J Л;=?„„6„-+(ReC; 3 w +

+ Э„„C. +Rew ) . 1 роме того, в регистр 1 принимается величина ReC;S, в регистр 5 — величина. Rewed+ r, коммутатор 6 подключает выход регистра 1

f042029

Г (t

1 ко входу ;ноыительпого блока 8, на выходе, которого, формируется произведение. пЕ C. ре, 4..

В шестом такте это произведение принимается в регистр 9, сумматор формирует Величину З,„,А;,=3,„6„—. т(М С„. 3 а " 1 С; Речу ) . Кроме того, в регйстр 2 прйнимается величина .. а в регистр 5 — величина

3„. щ +1, коммутатор 6 подкпочает выход регистра ? ко входу мнояительного блока 8р HB выходе которого фор иируется проиэведение 3 С. д щ" . +1 "rn

Таки|. оооаэом, BB вхо ЗО устройства поступс ет последовательность исходных отсчетов,ReCi,a C,., Re6;,3 9,, I

ReCi+,,3 с;,„,Re8,, Э„,B;+Ä i%a вход 31 устройства - последовательность весовых коэффиииентов,Rye,Ý wi 3

m

il

Re/.,,3 Л.,З A. ReA. ReA.,3„,4; 2, О

3„.„ Ã

Технический эффект изобретения заключается в экономии регистров за счет введения одного сумматора.

1042029 й®0 1 2 g Ф йи7Р

11

25 . И1.5

Составитель В.Горохов редактор М.Келемеш Техред M.Íàäü Корректор A.Тяско

Закаэ 7130/50 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий

113035, Москва, Ж-35, Раушская наб., a. 4/5

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