Арифметическое устройство для быстрого преобразования фурье Советский патент 1986 года по МПК G06F17/10 

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

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

На фиг. 1 изображена структурная схема арифметического устройства (АУ) для БПФ; на фиг. 2 - пример реализации устройства управления, обеспечивающего подачу синхронизирующего сигнала в шину синхронизации. Арифметическое устройство содержит четыре регистра (мнолсимого) l-A четыре регистра (множителя) 5-8, четыре умножителя , четыре cyMi-ta- тора-вычитателя ,четьфе регистра 17-20 результата (суммирования), коммутатор 21, группу 22 регистров с регистрами 22.1-22.4, сумматор 23, регистры 24 и 25, группу 26 регистров с perHCTpaNm 26,1-26,45 группу 2 регист|ров с регистрами 27,1-27.4, сумматор 28, тактовый вход и вход 29 кода операции,

На фиг, 2 представлен пример реализации устройства 30 управления, содержащего генератор 3 импульсов. двухразрядньй счетчик 32 импульсов, постоянное запоминающее устройство 33 микрокоманд, регистр 34 микрокоманд ,

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

Операнды для выполнения базовой операции поступают на первьй вход устройства в следующей последователь ности: Rex:(i), ImXj(i), Rex; ( i+2);, 1тх-(1+2), на .второй вход устройства Rex ;(i+l), (i + l), Rex; (i+3) , lmx:(), причем информация, поступающая на второй вход устройства, задержана на один такт относительно информахщи, поступающей на первьй вход устройства.

В первой половине первого такта операнды Relxj (i) 5 Re Wj, ImW j-й базовой операции записаны в регистры 1, 2, 5 и 6 соответственно, в регистры 3, 4, 7 и 8 записываются нули В з пюжнтелях 9-12 вьтчисляются произведения Rex-(i) , Rex j ( i) x ImWi, 0,0.

Bo второй половине первого такта на сумматорах 3 и 14 происходит пропуск операнда и гголожительнъм пе

5

0

5

0

5

5

репадом -ла синхровходе регистров 17 и 18 выполняется прием результатов

Rex,(i)PeW , Rex: ( i)-ImW соот, (i)ReW , Rex: (i) ImW j j .) j

ветственно.

В первой половине второго,такта операнды Imxj(i), , ReWj, Rex I (1+2), ReW, ImW j принимаются соответственно в регистры 1,2,5,6, 3,4,7 и 8.

В умножителях 9-12 вычисляются соответственно произведения IrnxjCi)) ImW, Ii-nxi(i) ReWj , Rexj(i+) ReWJ Rexj(i+l ) - ImW:,

Bo второй половине второго т°акта на сумматорах 13-16 выполняются операции Вычитание, Сложение, Пропуск операнда (00,01,11) и в регистры 17-20 записываются результаты выполнения операций на сумматорах 13- 16 соответственно

Rexj(i) ReW- - ImXj (i) ImW: RePj(i); ,

Rex-(i) ImWJ + Imx.(i) ReW- IinPj (i); . , Rex-(i+l) ReWj ; Rex(i+i) ImWj В первой половине третьего такта операнды Rex;(i+2),, ReW , ImW: f

-rrri-f т-тт1 т тт1-

ImWj , IniWj , ReW: записьшаются в рег истры 1-,2,4,5,6,3,4,7 и 8 соответственно. В умножителях 9-12 вычисляются произведения ,Rex; (i-f-2) xReWJ V Rex (i+2) - ImW Imxjd+l)- i , Imxjd+l) ReWj(i+l), В регистр 22.1 записывается значение RePj (i).

Ъо второй половине третьего такта на сумматорах 13-16 производятся операции Сложён.ие, Сложение, Вычитание, Сложение и результаты выпол-. нения этих операций записываются в регистры 17-20 соответственно

RePj (i) -ь Rex;(i + 2) ReWj %

ImPj (i) + Rex-(i + 2) ImWj ;

Rex,(i+0 ReW; - 1тх-д+1)х

xlmWp ReP: (i+O;

Rexj (;i+l) ImW j Tmx (ijfReW ImPj (i-s-l) .

В регистр 22,2 записывается значение ImPj (i).

Б первой половине следующего чет- Bep foro такта операнды lmx(i+2), ImWJ,. , Rex-(i+3), ReWJ f базовой операции записьшаются в регистры 1, 2, 5, 6, 3, 4, 7 и 8„ Б умножителях 9-12 вычисляют- ся произведения Imxj (i+2), , Imxj (i-i-2) . ReWJ/ Rex j (i+3) ReWj , Rexj ().ImWy В регистр 22.3 за- .писывается Б1еР;(1+).

:i+i)

Во второй половине четвертого такта на сумматоре 13 производится операция Вычитание, на сумматорах 14- 16 - Сложение. Результаты записываются в регистры 17-20 соответственно

RePj (i) + Rex- (i+2)- ReW- - - Imx (i+2) .ImW . RePj (i) +

, ri-r,/ ,

+ RePj (i+2) ;

ImP;(i) + Rex i(i+2). ImWrV

)

J

+ Imx (iH-2)«ReW: ImP. (i) + + ImPj(H-2);U,

RePjCi+l) + Rexj (i + 3). ReWj, , ImPj(i+l) + Rex.(i+3)-ImWj l В регистр 22.4 записывается ImP: (i+

В первой половине пятого такта операнды Imxj(L+3), IroWJ ReW. 3a- писываются в регистры 3, 4, 7 и 8 соответственно. В умножителях 11 и 12 выполняется умножение ,

Imxj(i + 3) ImWJ Imxj(i+3) Rew. В регистры 1, 2, 5 и 6 поступают исходные операнды (j+l)-H базовой операции Rexj,(i), ReWj, , ImW, соответственно. В умножителях 9 и 10 выполняется.операция умножения Rexj)-ReWj ,, Rexj,(i) ImWj t, . На сумматоре 23 происходит операция Вычитание- 2RePj(i)-rReF;(i) ReP:(i+2)1

RePj(i) - кЦ(Ь2) Информация на первый вход сумматора 23 поступает с регистра 22 сдвинутой на 1 разряд влево. Результат записывается в регистр 24.

Далее работа умножителей 9-12, регистров 1-8, 17-20, 22,24, 25 и 26 и сумматоров 13-16 аналогична описанной, поэтому при описании работы устройства в последующих тактах будем упоминать только прием в регис ры действительных и мнимых частей произведений P(i) : ReP: (i) , IniP; (i), ReP-(i+l), ImPj (i+I) и т.д.

Во втором полутакте на Сумматорах 13-16 вычисляются значения соот- ветственно Rel.|(i) ReWj, + О, vlmWiV, + 0; RePj (i+1) + Rex- (i + 2)« Iinxj(i+3) ImPj(i+l) + + Rexj(i + 3) - Imx (i+3) - ImPj(i4-i) + ImPj (i+3) . Результаты произведенных операций на сумматорах 13-16 записываются соответственно в регистры 17-20. На сумматоре 23 производится формирование разности 2lTnP (i) - lmP;(i) ImPj (1-ь2) , в регистр 27.4 записывается результат ImPj (i) - ImPj(), в регистр 26.3 записывается ImPj(i) + ImP(i+2

В первой половине ишстого такта на сумматоре 23 производится формирование разности 2RePj() - -fRePj(i+l) + RePj(i-f-3) , которая записывается в регистр 26.1, сумма RePj (i+) -f- ReP (i + 3) записывается в регистр 27.1. В регистр 26.4 производится перепись информации из регистра 25 RePj (L) + ReP (i-f2) . На сумматоре 28 производится вычисление Rex-(i) ReP;(i) + ReP: (i+2)J + (i-)-l) + RePj (i-ьЗ) .

Bo второй половине шестого такта на сумматоре 23 формируется разность ImPj(i-i-l) - IraP (i-t-3), которая записывается в регистр 27.3. В регистр 27.2 записывается сумма ImP;(JL-«-l) + + ImP; (L-f3) . В регистр 26.2 из регистра 24 переписывается ReP; (i) -ReP; (i-t-2y. На сумматоое 28 вычисляется ImxjCi) imPj (i) + ImP- (i+ +2) -f lmPjri+n + ImPj(i-f3).

В первой половине седьмого такта на сумматоре 28 вычисляется Rex-(i+ -fl) RePj(i) - RePj(i+2) + + imPj Ci+1) - ImPj (-+-3) , В регистр 22.1 записывается значение RePj.,,(i).

Во второй половине седьмого такта на сумматоре 28 вь1числяется Imx-(i + ) iniPj (i) - ImPj- (i+2) + + RePjCi+l) + RePj () . В регистр

22.2записывается ImP.Ci) .

В первой половине восьмого такта на сумматоре 28 вычисляется Rex-(1+ + 2) RePj (i) + RePj(i+2) (i+1) + RePj (i-t3). B регистр

22.3записывается ReF.-,.j (i+1).

Bo второй половине восьмого такта на сумматоре 28 вычисляется ImXj(i+2) LimPj (i) + ImP, (i+2)j - ImPj (i+l) + + ImPj (i+3)..

В регистр 22.4 записывается IniPj-,,(i+l).

В первой половине следующего девятого такта на сумматоре 28 вычисляется Rexj(i+3) RePj(i) -RePj(i+2)- imPj (i+1) - ImPj (i+3)

Bo второй половине девятого такта на сумматоре 28 вычисляется. Imxj (i+3) imPj (i) - ImP (i+2) - (i+1) - RePj (i+3) .

Далее работа устройства аналогична описанной.

Для получения всех результатов j-й базовой операции, начиная с момента поступления первого исходного операнда, требуется 9 тактов, в то

время, как цикл работы устройства 30 управления соответствует 4 тактам,

Устройство 30 управления работает следующим образомо

Импульсы, формируемые генератором 31, поступают на счетный вход счетчика 32 тактов, и на его выходах появляются серии импульсов соответствующей частоты и длительности. Сигналы с выходов счетчика 32 поступают на адресные входы постоянного запоминающего устройства 33 микрокоманд, которое вьщает в каж,цом полутакте микрокоманду на управление элементами АУ процессора БПФ в соответствии с их подключением к устройству управления. Счетчик 32 обеспечивает полностью работу устройства 30 управления, так как периодичность повторения управляющих сигналов на элементах АУ процессора БПФ - 4 такта.

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

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

входу девятого регистра, выход которого подключен к информационному входу второго регистра второй группы, выходы регистров второй и третьей групп подключены соответственно к

первому и второму входам второго сумматора, отличающее ся тем, что, с целью упрощения, оно содержит ком чутатор, выход которого подключен к информационному входу регистров

первой группы, второму входу второго сумматора, информационным входам первого и второго регистров третьей группы, информационным входам третьего регистра второй группы и десятого регистра, выход которого подключен к информационному входу четвертого регистра второй группы, первый, второй, третий и четвертый информа- ционнь е входы коммутатора соединены

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

которого является управляющий вход коммутатора.

Фиг. 2

Составитель А, Баранов Редактор Е. Копча Техред И.Попович Корректоре, Шекмар

Заказ 2987/52 Тираж 671Подписное

ВНИИПИ Грсударстленного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении вычислительных устройств, выполняющих алгоритм быстрого преобразования Фурье по основанию 4. Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что в состав устройства входят десять регистров, четыре умножителя, четыре сумматора-вычитателя, четыре регистра результата, коммутатор, три блока регистров по четыре регистра в каждом, два С5гмматора с соответствующими связями меяоду узлами устройства. 3 ил. с: (О ю 00 ий 00 4 С35