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

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

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

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

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

Однако это устройство требует большого объема оборудования.

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

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

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

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

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

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

92754

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

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

Арифметическое устройство для быстрого преобразования Фурье содержит (фиг.1) два входных регистра 1 25 и 2 чисел, входной регистр 3 весового коэффициента, умножитель 4, регистры 5 и 6, сумкатор 7, коммутатор 8 (слагаемых), выходшле регистры 9-12 (результатов), выходной коммутатор 13 и блок 14 синхронизации. Последний содержит (фиг,2) генератор 15 тактовых импульсов, счетчик 16 тактов, дешифратор 17, узел 18 постоянно.й памяти и элемент ИЛИ 19.

Таблица кодировки постоянного запоминающего устройства имеет следующий вид.

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

А,-В,+c,W; Аи,8, ;

ReA;Ree,.RgC;.RgW-l C; , Irr,8, + (pC;In,,-RgW:, «e,,. l eBrf eC;-ReVvtI C,. ln,A. + , Im8;-ReCrI W-l C, , где В; , С, - исходные отсчеты А,, Aj,- преобразованные отсчеты Vj - весовой коэффициент; «.-,, N - количество отсчетов в исходном массивеj - действительная часть; - мнимая часть числа. Рассмотрим работу устройства при вьшолнении базовой операции. Будем считать, что прием информации в регистры осуществляется в момент прихода заднего фронта синхроимпульса. На временной диаграмме показана работа устройства по тактам. Импуль сы, показанные незаштрихованными прямоугольниками, никакой смысловой нагрузки не несут, они подаются в промежуток времени, необходимый для загрузки устройства. Заштрихованные прямоугольники показывают импульсы, необходимые для работы ус ройства. Первые пять тактов являютс холостыми, т.е. во время этих такто полезная информация на выход не под ется, но в дальнейшем вначале каждо го такта при непрерывном поступлении данных на вход устройства на вы ходе появляются соответствующие результаты, цикл работы устройства составляет четыре такта. Б конце первого такта по сигналу с выхода блока 14 синхронизации во входной р гистр 1 чисел принимается действительная часть ВрС; исходного отсчета Cj , во входной регистр весового коэ фициента 3 - действительная часть Rg W весового коэффициента , Во втором такте выполняется умно жение в умножителе 4 и произведение RgCjRgW по сигналу из блока 14 пр нимается в регистр 5. По этому же сигналу в регистр 3 принимается мнимая часть Ip,W весового коэффици

ента Vi/ , а по сигналу из блока 14 в регистр 2 чисел - действительная часть RgВ; исходного отсчета В .

В третьем такте выполняется.умножение, и произведение IniW по сигналу с блока 14 принимается в регистр 5, по этому же сигналу в регистр 6 принимается произведение Kg С; Rg vv и в регистр 3 - мнимая часть весового коэффициента W, во входной регистр 1 чисел по сигналу с блока 14 принимается мнимая исходного отсчета С. В четвертом такте в т ножителе 4 выполняется умножение, и произведе ние 1т С -l VJno сигналу из блока 14 принимается в регистр 5 слагаемых, по этому же сигналу в регистр 6 принимается произведение , а во входной регистр 3 - действительная часть Fg л весового коэффициента W . По сигналу из блока 14 во входной регистр 2 принимается мнимая часть 1„В; исходного отсчета В;, Коммутатор 8 по сигналу из блока 14 подключает к входу сумматора 7 выход входного регистра 2 чисел. Сумматор 7 по сигналам из блока 14 выполняет операцию сложения в первой половине четвертого такта, а операцию вычитания - во второй половине. Соответстве «г, сумма RgW; по сигналу из блока 14 принимается в регистр 9 в середине четвертого такта, а разность НрВ,- RgC;-RgW - по сигналу из блока 14 в конце четвертого такта в регистр 10. В пятом такте в умножителе 4 выполняется умножение, и произведение ImC;Rg сигналу из блока 14 принимается в регистр 5,,произведение IrnC; Ir,,W по этому же сигналу принимается в регистр 6, а во входной регистр 3 - действительная часть . Во входной регистр 1 по сигналу из блока 14 принимается действительная часть FgC,4i следующего исходного отсчета 0;+,. Коммутатор 8 по сигналу из блока 14 подключает к входу сумматора 7 вькод входного регистра 2. Сумматор 7 по сигналам из блока 14 выполняет операцию сложения в первой половине пятого такта и операцию вычитания - во второй половине. Соответственно, в середине пятого такта сумма j -ь RgC; по сигналу из блока 14 принимается в регистр 11, а в конце пятого такта

разность , - RgCI W no сигналу из блока 1Д принимается в регистр 12.

В шестом такте в умножителе 4 выполняется умножение и произведение , Rg по сигналу из блока 14 принимается в регистр 5, в регистр 6 по этому сигналу принимается произ-ведение ГГУ, С; Р гистр 3 - мнимая часть 1 весового коэффициента. Во второй регистр 2 по сигналу из блока 14 принимается действительная часть РеВ,, исходного отсчета В,-. Коммутатор 8 по сигналу из блока 14 подключает к выходу сумматора 7 объединенный выход регистров 9-12 результатов. Сумматор 7 По сигналам из блока 14 выполняет операцию вычитания в первой половине шестого такта и операцию сложения - во второй. В первой половине шестого такта по сигналу из блока 14 из регистра 9 выдается сумма RgBj+RgC(.RgW, и после выполнения вычитания на выходе сумматора появляется действительная часть преo6pa3OBaHfforo отсчета КрА, + +RgC; .RgW-I C;-I.W, которую по сигналу из блока 14 коммутатор 13 подает на выход устройства и которая по сигналу из блока 14 запишется в регистр 9. Последняя запись не является необходимой цяя функционирования устройства. Она введена с целью упрощения блока 14. Во второй половине шестого такта по сигналу из блока 14 из регистра 10 выдается разность KgB; - SgC, .В , и в конце такта по сигналу из блока 14 в регистр 10 принимается сумма ,-RgC. .R,wi ,.

В седьмом такте в умножителе 4 выполняется умножение, и произведение , по сигналу из блока 14 принимается в регистр 5, в регистр 6 по этому же сигналу - произведение Ре(Ч( е « ° входной регистр 3 - мнимая часть весового коэффициента . Во входной регистр 1 по сигналу из блока 14 принимается мнимая часть 1 С;, исходного отсчета . Коммутатор 8 по сигналу из блока 14 подключает к выходу сумматора 7 объединенный выход регистров 9-12 результатов. Сумматор 7 по сигналам из блока 14 выполняет операцию сложения и операцию вычитания соответственно в первой и второй половинах седьмог-о такта. В первой половине седьмого такта по сигналу из блока 14 из регистра 1 1 выдается + 5 +RgC;,, и после выполнения сложения на выходе сумматора появляется мнимая часть преобразованного отсчета , -bRgC;- , R,W, , которую по сигналу из блока 14 коммутатор 13 подает на выход устройства и которая по сигналу из блока 14 запишется в регистр 11.

Последняя запись не является необходимой для функционирования устройства, она введена с целью упрощения блока 14.

Во второй половине седьмого такта по сигналу из блока 14 из регистра 12 выдается разность ,e-i m i 0 и в конце такта по сигналу из блока 14 в регистр 12 принимается разность

.Зi-R,,C,.RgW.I,A,,, .

в восьмом такте в умножителе 4 выполняется умножение, и произведение 1 С, W по сигналу из блока 14 поднимается в регистр 5, в регистр 6 по этому же сигналу принимается произведение 1п,С,- , а

0 в регистр 3 - действительная, часть PgW весового коэффициента . Во входной регистр 2 по сигналу из блока 14 принимается мнимая часть ,, исходного отсчета ,. Коммутатор 8

5 по сигналу из блока 14 подключает к входу сумматора 7 выход входного регистра 2 чисел-. Сумматор 7 выполняет операции сложения и вычитания в первой и второй половинах такта

0 соответственно. В первой половине восьмого такта по сигналу из блока 14 (по заднему фронту) в регистр 9 принимается сумма BgB.+BgCj -RgW , из регистра 10 на выход устройства

5 по сигналу из блока 14 выдается действительная часть ВрА,. Коммутатор 13 по сигналу из блока 14 пропускает ее на выход устройства. Во второй половине восьмого такта по сигмалу из блока 14 в регистр 10 принимается разность НеВ;,,-„ RgW.

В первой половине девятого такта по сигналу из блока 14 в регистр

11принимается сумма ,„ RgW, 5 по сигналу из блока 14 из регистра

12на выход устройства вьщается мни мая часть ,-,преобразованного от счета А,,и по сигналу из блока 14

во второй половине в регистр 12 принимается разность

lm8urReC;,, ,

Работа остальных элементов устройства аналогична рассмотренной для пятого такта.

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

Таким образом, по сравнению с иэвестньм предлагаемое устройство более быстродейственно, оно имеет четыре такта работы при непрерывном

поступлении данных (такт работы устройства есть такт работы умножителя) , в то время как известное устройство имеет шесть тактов работы (такт работы устройства есть такт

работы умножителя).

..gq« ..,,.,

; Ж

Г6

15

/7

-- -

- -

. 2

23 S 67В3 10

II ImCi KeCi; ГтС.,.2

RtBi I

IirsSf

JE3

KeW mW IfnW KfW ffW feW mW

У , V77 7Щ V77 Vm W7X WA Щ WA W

, ftfi-I wl f.faX, ,.:f l ffCi,, , ..1

-. V77 V77 VTA W7 W7 ,777X V77}, V77)( PT

IKeCiffV KtC,Ir,w-,C:: w --i/ fCi W-ij:f., ., /:,

ff r m w/ m Ш Ш :

± ,±., - -t- - - + - - - Ш I r/--; f%v

7/77: /7

, ,llfC,,, ,i

ШХ. iU7 g 1TZ.

JH-l

feSi- Ci-ffW KfA,.,

// л /( 0 /ет rt /. /) /

, I. n. ; t: I r.

JZL

nL

1 ГAV/2 i1

J

rn

ImS,:,

feS,.

KeBi.t

WA W7

V////X////A

1

eSi.rfeCiH/leW Remits g

Ш7 ) ГУ;

y/r7A./f(4r,.;//fr(V|

::Ci lmW

I SrfeCiJr W I .,

,,-nfrVi

. i. ЯУ I

ЯеА; //77/), T/7/ J