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

 

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

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

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

РЕСПУБЛИН (11 4 G 06 F 15/332

У ь

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3820178/24-24 (22) 30 ° 11.84 (46) 30.05.86. Бюл . N - 20 (71-) Киевский ордена Ленина политехнический институт им. 50-летия

Великой Октябрьской социалистической революции (72) Ю.С. Каневский, Н.Е. Куц, Б.А. Некрасов и В.В. Чечь (53) 681.32(088.8) (56) Авторское свидетельство СССР

Р 467356, кл. G 06 F 15/332, 1974.

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

N 999061, кл. G 06 F 15/332, 1982. (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ

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

„„Я0„„1234846 А 1 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении вычислительных устройств, выполняющих алгоритм быстрого преобразования Фурье по основанию 4. Цель изобретения — упрощение устройства. Поставленная цель достигается тем, что в состав устройства входят десять регистров, четыре умножителя, четыре сумматора-вычитателя, четыре регистра результата, коммутатор, три блока регистров по четыре регистра в каждом, два сумматора с соответствующими связями между узлами устройства. 3 ил.

348

М 12

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

Фурье (БПФ) по основанию 4, Цель изобретения — упрощение устройства.

На фиг. 1 изображена структурная схема арифметического устройства (АУ) для БПФ; на фиг. 2 — пример реализации устройства управления, обеспечивающего подачу синхронизирующего сигнала в шину синхронизации.

Арифметическое устройство содержит четыре регистра (множимого) 1-4„ четыре регистра (множителя) 5-8, четыре умножителя 9 — 12, четыре сумматора-вычитателя 13 — lб,четыре регистра 17-20 результата. (суммирования), коммутатор 21, группу 22 регистров с регистрами 22.1-22,4, сумматор 23, регистры 24 и 25, группу 26 регистров с регистрами 26 . 1-26 . 4, группу 27 регистров с регистрами 27.1-27,4, сумматор 28, тактовый вход и вход 29 кода операции.

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

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

Операнды для выполнения базовой операции поступают на первый вход устройства в следующей последователь ности: Rex (i), Тнх„(i), Бех (i+2)., !

Imx-(i+2) на второй вход устройства

) - »

Rex; (i+1), Тпй. (i+1), Rex; (i+3), Хтпх (i+3), причем информация, поступающая на второй вход устройства, задержана на один такт относигельно информации, поступающей на первьгй вход устройства.

В первой ттоловине первого такта операнды Кех (i), Ке11,, ImW 1-й базовой операции записаны в регистры 1, 2, 5 и б соответственно, в регистры 3, 4, 7 и 8 записываются нули

В умножителях 9-12 вычисляются прог изведения Бех (1) REAM ., Бех,()

» ТиЯ -, 0,0.

Во второй половине первого такта на сумматорах 13 и 14 происхоцит пропуск операнда и положительным пе46 2 репадом «а синхровходе регистров 17 и !8 выполняется прием результатов

Rex; (г ) РеW ., Rex (i) ImW соот! J ветственно.

В первой половине в1орого,такта операнды Imx (i), ТгЯ!, ReW;, Rex (i+2)Ä RåW„., ImW> ïðèHHìàþòñÿ

1 соответственно в регистры 1,2,5,6, 3,4,7 и 8.

В умножителях 9-12 вычисляются соответственно произведения Тшх„.(ь)» ImWj Тгпхj(i) ReWj, Rex (i+!) .!

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

Rex (i) ReW. — Imx (i) ImW 1 . J j 1

= ЕеР (ч.), Rex (i) Хгй7 + Imx (i) ReW.

imp (i)

Кех (1+1) ReW>, Бех (i+1) ImW

В первой половине третьего такта операнды Кех (i+2), ReW ., ImW., ) 144 ) j

ТпЮ, Ттп{1! ., ReW записываются в

) регистры 1,2.,4,5,6,3,4,7 и 8 соответственно. Б умножителях 9-12 вычисляются произведения Rex (i+2)<

» Re!ò ° Rex (i+2) ° ImW1, Хтпх (i+ I )» х Хпй ", Imx, (i+ ) ReW (з.+1) . В регис . р 2?, 1 записывается значение

ReP (»)

Во второй половине третьего такта на сумматорах 13-16 производятся операции "Сложение", "Сложение", "Вычитание", Сложение" и результаты выполнепия этих операций записываются в регистры 17-20 соответственно теР;(1.) + Rex>(i+2) ReW;

ХшР, (i) + Rex (i+2) ImW."

Гех (1+1) ReW4," — Imx ° i+1)»

ImW = ReP: {i+i);

Пех (i+i) EmW + Imx>(i+!)»

) 11

» ЙеЫ = ImP. (i+1)

В регистр 22.2 записывается значение ТшР1 (i).

Б первой половине следующего четвертого такта операнды Imx> ь+2), Хпт11, „КеМ;, Вех - (i+3), ReW

ImM> j-й базовой операции записываются в регистры l, 2, 5, б, 3, 4, 7 и 8„ Б умножителях 9-12 вычисляютН2 ся произведения Emx (i+2) Хпй!

Imx„ (i+2) ° ReW,, Rex>(i+3) ° ReW

Вех (i+3) ° ImM;, В регистр 22.3 за,писывается КеР (i+1) .

3 12348

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

1 2

ReP (i) + Rex (i+2) ReW

° 1 2 1 °

Imx (i+2) ° 1тп11 = ReP (i) +

+ КеР (i+2);

) . ) )

ХтпР (i) + Rex „ (1+2) ° ImWI +

+ Imx (i+2) ° ReW" = ImP. (i) +

+ ТтпР (I+2);

ReP (i+1) + Rex J (i+3) ReW J, ХтпР„ (i+1) + Rex„. (i+3) ImW) .

В регистр 22.4 запйсывается ImP„(i+1)

В первой половине пятого такта операнды Етпх (i+3), ImW„, ReW записываются в регистры 3, 4, 7 и 8 соответственно. В умножителях 11 и

12 выполняется умножение

Imx (i+3) ImW", Imx (i+3) ReW

) )

В регистры 1, 2, 5 и 6 поступают исходные операнды (j +1) -й базовой операции Rex;„(i), ReW„„, ImW „ соответственно. В умножителях 9 и !0 выполняется. операция умножения

Rex„,,(i) ReWJ„Rex „(i) Тп)11 „. Ela сум. маторе 23 происходит операция "Вычитание"

2ReP; (i) — (РеР (i) РеР (i+2)j

= ReP (i) — ReP (i+2) .

J 1

Информация на первый вход сумматора 23 поступает с регистра 22 сдвинутой на разряд влево. Результат записывается в регистр 24.

Далее работа умножителей 9-12, регистров 1-8, 17-20, 22,24, 25 и

26 и сумматоров 13 — 16 аналогична описанной, поэтому при описании работы устройства в последующих тактах будем упоминать только прием в регист.4 ры действительных и мнимых частей произведений P(i): ReP (i), ImPJ (i), J

ReP (i+1), ImP (i+I) и т.д.

Во втором полутакте на сумматорах 13-16 вычисляются значения соот- 4 нетстненно RePJ„(i) ReWJ„ + О, Rex „(i)

«?птМ!+(+ 0; РеР (,i+1) + Рех (i+2)» .! ) )

» ReM " — Imx (i+3) ImW; ImP (i+1)+

), ) „-, )

+ Rex (i+3) ReW — Imx. i+3) imW)

) )

ImP (i+1) + ImP (i+3) . Результаты

1 J произведенных операций на сумматорах 13-16 записываются соответственно в регистры 17-20. На сумматоре 23 производится формирование разности

2ImP (i) — (ТтпР, (i) + ImP„(i+2) l, в регистр 27.4 записывается результат ImP„ (i) — 1тпР (i+2), н регистр

26.3 записывается Тп)Р (i) + ?тпР (i+2) 46 4

В первой половине шестого такта на сумматоре 23 производится формирование разности 2RePJ(i+I)

-(ReP

RePJ (i+1} + ReP (i+3) записывается

) в регистр 27.!. В регистр 26.4 про-. изводится перепись информации из регистра 25 ГеР) (i) + RePJ {i+2). На сумматоре 28 производится вычисление

Rex (i) = (ReP;(i) + RePJ(i+2)) +

+(ReP.(1+!) + ReP, (т+3)J

Во второй половине шестого такта на сумматоре 23 формируется разность

ImP (i+1) — ImP (i+3), которая записывается в регистр 27.3. В регистр

27.2 записывается сумма Т)пР (+I) +

+ ImP (i+3) . В регистр 26.2 из ре-! гистра 24 переписывается ReP (i}

J — ReP (i+2}. На сумматоре 28 вычисJ ляется Imx {i} = (ImP {i} + ImP (i+

+2}) + (ImP (i+1} + ImP (i+3}j .

„) )

В первой половине седьмого такта на сумматоре 28 вычисляется Рех (i+

+1} = (ReP (i} — ReP)(i+2}) +

+ (ImPJ .i+I } — ImP (i+3)j . В регистр 22.1 записывается значение

ReP „(i) .

Во второй половине седьмого такта на сумматоре 28 вычисляется Imx (i+

+1) = (Хп)Г; (i) — ТтпР (i+2)) +

+ (ReP (i+I) + ReP;(i+3) . В регистр

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

1Ф)

В первой половине восьмого такта на сумматоре 2 8 вычисляется Rex (i +

+2) = (РеР (1.) + ReP) (i+2) !—

--),1 (ReP (i+1) + ReP (i> 3)) . В регистр

22.3 записывается КеР (i+1).

Во второй полови)те восьмого такта на сумматоре 28 вычисляется Imx (i+2)=

J — (ImPJ { i) + ImP {i+2)J — (Хп)Р (i+1)+

+ ?тпР (т+3)) .

В регистр 22.4 записывается

ХтпР „(i+1) .

Б первой половине следующего девятого такта на сумматоре 28 вычисляется Rex, +3) = (ReP (i)

ReP, (i+?)g — (ImP (i+1) — ImP (i+3)) ! J

Во второй полонине девятого такта на сумматоре 28 вычисляется

ImxJ (i+3) = jImPJ (i) — ?п)Р (1+2)) — (КеР (i+1) — RePJ (i+3)g .

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

Для получения всех результатов

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

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

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

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

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

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

L с п<.-рвыми входами соответственно первого, второго, третьего и четвертого сумматоров-вычитателей и подключены к выходам соответственно первого, второго, третьего и четвертого регистров результата, а выходы первого, второго, третьего и четвертого ум«ожителей подключены к вторым входам соответственно первого, второго, ".ретьего и четвертого сумматороввычитателей, выход второго сумматора ягляется выхо,цом результата устройства, тактовые входы регистров с первого по десятый регистров результата с первого по четвертый, регистров первой., второй и третьей групп, управляющие входы сумматоров-вычитателей с первого по четвертый объединены и являются тактовым входом устройс.тва, входом задания кода операции которого является управляющий вход коммутатора.

1234846

Фиг. 2

Составитель А. Баранов

Техред И.Попович Корректор С. Шекмар

Редактор Е. Конча

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

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

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

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