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

 

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

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

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

РЕСПУБЛИК

Н9) П1) 3(5)) .) 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 335 6015/18-24 (22) 07.07.81 (46) 07.03.84. Бюл. Р 9 (72) Б.А,Максимов, В.B.Ñóìàðîêîí и В.Ф,Черепов (53) 681 ° 3(088.8) (56) 1. Авторское свидетельство СССР

9 656070 кл. Cj 06 F 15/332, 1978.

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

Р 736113 кл. С, 06 F 15/332 1979 (прототип). (54)(57) 1, УСТРОЙСТВО ДЛЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее четыре входных регистра, первый сум матор, четыре регистра произведений дна регистра вектора поворота, коммутатор и блок управления, причем входы регистров вектора поворота яв ляются входами действительной и мни мой частей вектора поворота устройс ва, выходы реГистров произведений подключены к первой группе информационных вхрдов коммутатора, перный выход блока управления подключен к входам управления сдвигом регистров вектора поворота, второй ныход блока управления подключен к входам управления сдвигом входных регистров, третий выход блока управления подключен к управляющему входу коммутатора, о т л и ч а ю щ е е с я тем, что, с целью повьпаения быстродействия устройства, в него ннедены второй, третий и четвертый сумматоры, причем перный ныход коммута тора подключен к информационным входам первого и второго входных регистров второй выход коммутатора подключен к информационным входам третьего и четвертого входных регистров, выходы входных регистров подключены к первым информационным входам соответствующих сумматоров, выходы сумматоров подключены к информацион ным входам соответствующих регистров произведений, выходы регистров произнедений подключены к н торым информационным входам соотнетствую— щих сумма торов, последов а тельные выходы регистров вектора поворота подключены к соответствующим управляющим входам блока управления, четвертый выход блока управления подключен к входам задания режима сумматоров, пятый выход блока управ— ления подключен к входам упранления записью первого и третьего регистров произведений, шестой выход блока управления подключен к входам управления записью второго и четнертого регистров произведений, н торая и третья группы информационных входон являются входами первого и второго комплексных опероидов устройства, третий и четвертый выходы коммутатора являются выходами комплексного результата устройства.

2. Устройство по и. 1, о т л и ч а ющ е е с я тем, что блок управ— лен ия сос тои т из че тырехраз рядного регистра сдвига, трехразрядного счет. чика, двух элементов И и блока постоянной памяти, причем первые входы элементов И подключены к тактовому входу устррйства, выход первого элемента И подключен к управляющему входу регистра сдвига, ныход четвертого разряда регистра сдвига подключен к нходу его первого разряда, выход третьего разряда регистра сднига подключен к второму входу второго элемента И, выход второго элемента И подключен к входу счетчика, выход Переполнение счетчика подключен к второму входу первого элемента И, управляющие нходы блока управления подключены к первой группе адресных входов блока постоянной памяти, разрядные выходы регистра сдвига подключены к второй группе адресных входов блока постоянной памяти, ныходы блока постоянной памяти являются выходами блока управления.

1078433

Изобретение oTHacHToя к автоматике и вычислительной технике и предназначено для использования в аппарате. при спектрально-корреляционном анализе с игналоэ, Известно устройство для быстрого преобразования Фурье, содержащее четыре сумма тора „три мнОжитель ных блока„два су>люлатора-вычитателя и четыре регистра результата (1) .

Недостатком такого устройства является большой Обье оборудования, связанный с тем., чта во время выполнения Операции умножения четыре сумматора и дэа су>лматора-вычитателя бездействуют, кроме того, устройст- j 5 во ориентировано на выполнение только Одного алгоритма — прямого быстрого преобразования Фурье., HB IIá o>It близ к им решением к изобретению является устройство для быстрого Преобразования Фурье, содержащее четыре входных регистра, дэа регистра вектора поворота, коммутатор,. четыре регистра произведений, блок управления, коммутатор сомно>кителей,. блок умножения и регистры слагаемых f7).

Недос татксм из=-ес Tío-.о ус тройс тэа является малое быстродействие.

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

Нос таэле иная цель дос тигае тс я тем, чго в устройство для быстрого преобразования Фурье,. содер>кащее четыре входных регистра, п-.рэый сумматор, четыре регистра проиэвецений,. два регис".ðà вектора поворота. коммутатор и блок управления,. причем входы регистров эек гора;:-!O-.opoта являются входами действительной и мнимой частей вектора поворота yc T- 40 ройстэа, выходы регистров произве> ений подключены к первой группе информационных входов ко>лмуге.=-ора „. . Iep:=,bIé выход блока упраэлепк:-: подключен к входам управления сдвигом регис тров вектора пoeopoTa., второй выход >и;.;- d управления подключен к Входам поавления > вHl Ом нхснных рр гистроэ, третий выход блока управления подключ ен к управляющему входу коммутатора, введены второй, третий

И ЧЕт ВЕРТ;->и СУММатОРЫ, ПРИЧЕМ»ЕРВЫй

ВЫХОД КОМ:лУ Та TOPà ПОДКЛЮ"-.Еr» К ИифОР" мационным входам первого и второго входных регис тров, в торой выход коммутатора подключен к информационным входам треTbе> О и ч> твеpTOI o входных регистров, выходы э>::Одных регистров подключены к первым информационным

ВХОДаМ СоотНЕ ТС- :;; ЩНХ СУММа TOPOB i выходы с -мма торо;-. »:, дключены к инфар-60 ,мационным н> .Одам с .. От ветс твующих регистров произве» =-::;.,"". выходы регистр овэ IIpoи ")3е це!, >I>, грдк>>ючень! к э Topb>>i> информа>ционнк в>:евам состp ... .: тв„ющих у зла тopoe-. Соева. 1ОI;= ." е .—,",-.".", е вы ходы регистров вектора поворота подключены к соответствующим управляющим входам блока управления, четвертый выход блок а управ ле ни я подключен к входам задания режима сумматоров, пятый выход блока управления подключен к входам управления записью первого и третьего регистров произведений, шестой выход блока управления подключен к входам управления записью второго и четвертого регистров произведений, вторая и третья группы информационных входов являются входами первого и второго комплексных опероидов устройства, третий и четвертый выходы коммутатора являются выходами комплексного результата устройства.

Блок управления состоит иэ четырехразрядного регистра сдвига, трехраз рядно го счетчика, двух элементов И и блока постоянной памяти, причем первые входы элементов И подключены к тактовому входу устройства, выход первого элемента И подключен к управляющему входу регис тра. сдвига, выход четвертого разряда регистра сдвига подключен к входу его первого разряда, выход третьего разряда регистра сдвига подключен к второму входу второго элемента И, выход в торого элемента И подключен к входу счетчика, выход Переполнение счетчика подключен к второму входу первого элемента И, управляющие входы блока управления подключены к первой группе адресных входов блока постоянной памяти, разрядные выходы регистра сдвига подключены к второй группе адресных входов блока постоянной памяти, выходы блока постоянной памяти являются выходами блока управления, На фиг. 1 приведена функциональ— ная схема устройства; на фиг ° 2— схема блока управления.

yCTpoÉÑÒÂo СОСТОИТ HB eTbIpex Вхо ных регистров 1 — 4, четырех сумматоров 5 — 8, четырех регистров 9 — 1 2 произведений, коммутатора 13, блока 14 управления, двух регис тров 15 и 1 б вектора поворота, причем два информационных входа 17 и 18 регистров вектора поворота и четыре информационных входа 19-22 коммутатора являются входами устройства, а два выхода 23 и 24 коммутатора являются выходами устройства, Блок управления состоит из элементов И ?S и 26, четырехразрядного регистра 27 сдвига, трехразрядного счетчика 28 и блока 29 постоянной памяти, устройство выполняет следующие

Операции (прореживание по частоте) 1078433

ReA,„=Re А, + Re B;, J rn А ... = 3 rn А, + 3 m B „)

Р е В,, „= к е%, (,9 е А;- Р е 8, 1- 3 ъЪ, (, ) о А, - ) m B, ), 3w B<„° JmW,(Re ; -Яев, Re W; (3 А; - JynB, ), где А — первое входное комплексное число;

В< — второе входное комплексное число; вектор поворота.

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

В исходном состоянии регистры 9

12 произведений обнулены. Коммутатор 13 направляет в регистры 1 и 2 величину Rg A, а в регис тры 3 и 4 величину J щ A, . Суммируясь с нулевым содержимым регистров 9 — 12 на сумматорах 5 — 8, эти величины без изменения записываются в регистры 9 — 12 ° На этом первый такт работы устройства закончен . Коммутатор 13 направляет в регистры 1 и 2 входную величину Re B,, а в регистры 3 и 4 входную величину JmB<, и на сумматорах 5 — 8 образуются следующие величины: на сумматоре 5 - (geA, +ReB; ), на сумматоре 6 — (ReAI — ReB, ), на сумматоре 7 — (JmA „ + Ъ,В; ), на сумматоре 8 — QUA; — JnB, ), Величины с выходов сумма торов э ап исываю тс я в регистры 9 — 12. С выхода регистров 9 и 11 величины Re А; и JmB;„ равные соответственно (Re А, +ReB. ) и (JmA;+)тВ; ), через коммутатор 13 .подаются на выходы 23 и 24 устройства соответственно. На этом второй такт работы устройства закончен, Коммутатор слагаемых направляет величину с выхода регистра 10 в регистры 1 и 2, a -. выхода регистра 12 в регистры 3 и 4. Регистры 9 — 12 обнуляются. На этом третий такт работы устройства закончен.

Затем блок управления начинает операцию умножения, одновременно формируя на регистрах 9 — 12 четыре величины: (Re W; (ReA; — ReB;)), 1 3 Ф w, (R е А, — Я е В; ) ), 1 R е w; () и А, —

-Ъ В„)),(3 а; HmA; -J B; ) умножение длится на столько тактов, сколько разрядов регистров векторов поворота (в наиболее распространенном случае восемь разрядов), Частичные произведения формируются путем сдвигов в регистрах 1 — 4 и записываются в регистры 9 — 12, если соответс твующий ра з ряд регис тра век тора поворота равен единице.

Коммутатор 13 направляет величины с выхода регистра 10 в регистр 3, а с выхода регистра 12 в регистр 1.

Величины Re В „,, н Jm В „, q с выходов сумматоров 5 и 7 записываются в ре30

5

i5

65 гистры 9 .и 11. С выхода регистров 9 и 11 величины ке В;„и 3mB через коммутатор 13 подаются на выходы 23 и 24 устройства соответственно.

На этом последний такт работы устройства закончен.

Блок 14 управления работает следующим образом, В регистра 27 сдвига подается логическая единица, счетчик 28 тактов умножения сброшен в нуль, на всех выходах блока 29 постоянной памяти логические нули и, следовательно, не иницируется ни одна микрооперация, Через элемент И 25 первый тактовый импульс поступает на вход сдвигов регистра 27, логическая единица появляется на выходе регистра П и иэ блока постоянной памяти вызывает код микроопераций, необходимых на первом такте работы устройства.

Единица на входе регистра сбрасывается. Второй тактовый импульс сдвигает единицу из первого разряда регистра во второй, а в первый разряд принимается логический нуль с входа регистра и, таким образом, на всех выходах регистра за исключением выхода ц присутствуют нули. Наличие логической единицы на выходе с . вызы7 вает выполнение микроопераций, необходимых на втором такте работы устройства. Третий тактовый импульс сдвигает единицу из второго разряда регистра 27 в третий разряд. Начинается выполнение умножения, В зависимости от состояния (1 или 0 ) выходов блоков 15 и 16 на регистры 9 — 12 произведений либо подается сигнал э аниси, либо нет .

Тактовые импульсы с 4-го по 10-й не изменяют состояние регистра 27, так как счетчик, начиная с третьего тактового импульса, блокирует прохождение так товых имп ульсов на регистр 27. По этим тактовым импульсам происходит увеличение содержимого счетчика и сдвиги вправо во входных регистрах 1 — 4, На каждом из тактовых импульсов 4-10 в зависимости от сос тояния выходов регис тров 15 и 16 происходит либо нет запись частичных произведений в регистры 9-12.

При достижении счетчиком 28 двоичного кода 000 (переполнение счетчика) вновь разрешается прохождение тактовых импульсов на регистр 27 и единичное состояние переходит иэ третьего разряда регистра в четвертый разряд. Наличие единицы на выходе aqua регистра 27 вызывает выполнение микроопераций, необходимых на 11-м такте работы устройства, Последующие тактовые импульсы запускают сначала описанный процесс.

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

1078433

Злол ьч lГД 4 при наличии 8-разрядного умножения составляет 11 тактов вместо 34 тактов в известном устройстве. В случае применения в прототипе умножителя на сдвигах и сложениях предлагаемое устройство обеспечивает примерно в три раза более высокое быстродействие при меньшем количестве оборудования.

Фала,ч 1ХЛУ

&ола ХР 7Р для У,fX

6мокаи A7/g

0m дейча Я5

0m dacrwu lЮ

ВЙИИПИ Заказ 965/43

Тираж 699, Подпи сное

«Ю»

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