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

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

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

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

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

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

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

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

на входе устройства.

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

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

содержащем два входных регистра

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

коэффициента,.информационный вход

которого является вторым входом

устройства, выход множительного

.блока соединен с информационным

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

соединен со счетным входом счетчика тактов, выходы которого соединены с адресными входами блока памяти, кроме того, выходы младших разрядов счетчика тактов соединеьал с

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

соответственно, второй и четвертый выходы дешифратора соединены с входами приема первого и второго входных регистров чисел соответственно а также с входами элемента ИЛИ, выход которого соединен с входами приема первого и второго регистров слагаемых и-регистра весового коэффициента, первый выход блока памяти соединен с управляющим входом сумматора, второй выход блока памяти соединен с управляющим входом коммутатора. Кроме того, с целью обеспечения равномерной выдачи результатов устройство дополнительно содержит четыре выходных регистра, информаци онные входы которых объединены и соединены с выходом сумматора, вход приема первого выходного регистра и вход выдачи четвертого выходного регистра соединены с третьим выходо блока памяти, вход выдачи первого выходного регистра и- вход приема четвертого выходного регистра соединены с четвертым выходом блока памяти, входы приема второго и четвертого выходных регистров соединен соответственно с пятым и восьмым выходами блока памяти, входы выдачи второго и третьего выходных регистров соединены соответственно с шестым и седьмым выходами блока памяти. На фиг.1 представлена структурна схема устройства; на фиг. 2 - струк турная схема устройства, обеспечивающего равномерную выдачу результа TOBJ на фиг. 3 - структурная схема блока управления; на фиг. 4 - временная диаграмма, иллюстрирующая работу устройства; на фиг. 5 блок-схема алгоритма функционирования блока управления. Арифметическое устройство для быстрого преобразования Фурье содер жит два входных регистра 1 и 2 чисел, информационные входы которы объединены и являются первым входом устройства, входной регистр 3, весо вого коэффициента, информационный вход которого является ь.орым вход устройства. Выходы входного регистр 1 чисел и входного регистра 3 весового коэффициента соединены соот ветственно с первым и вторым входа множительного блока 4, выход которого подключен к информационному входу первого регистра 5 слагаемых Выход регистра 5 слагаемых соедине информационным входом второго регистра 6 слагаемых. Выход регистра слагаемых подключен к первому инфо мационному входу сумматора 7, к вт рому информационному входу которог подключен выход коммутатора 8, информационные входы регистров 9т12 результатов объединены между собой и соединены с выходом сумматора 7. Выходы регистров 9fl2 результатов объединены между собой и являются выходом всего устройства, кроме того, выходы регистров 9412 результатов соединены с первым информационным входом коммутатора 8, вуо-а рой информационный вход которого соединен с выходом входного регистра 2 чисел. Выходы блока 13 управления подключены к управляющим входам всех регистров, сумматора 7 и коммутатора 8. Арифметическое устройство для быстрого преобразования Фурье, обеспечивающее равномерную выдачу результатов, содержат дополнительно четыре выходных регистра 14т17, информационные входы которых объединены между собой и подключены к выходу сумматора 7, а выходы выходных регистров 14т17, также объединенные между собой, являются выходом 18 всего устройства. Входы управления приемом и выдачей информации выходных регистров 14-:-17 соединены с соответствующими выходами блока 13 управления. Сумматор 7 представляет собой сумматор- вычитатель , который имеет вход управления выполняемой операцией. Непосредственное объединение выходов регистров результатов допустимо, если в качестве этих регистров использовать регистры с тремя состояниями на выходе. Блок 13 управления фиг. 3 содержит генератор 19 синхроимпульсов, выход которого подключен к счетному входу трехразрядного счетчика 20 тактов. Первый (младший) и второй выходы счетчика 20 соединены с соответствующими входами дешифратора 21, кроме того, первый, второй и третий выходы счетчика 20 подключены к соответствующим входам микропрограммного блока 22 памяти. Второй и четвертый выходы дешифратора 21 соединены с двумя входами элемента ИЛИ 23, выход которого является выходом 24 блока 13-управления. Первый, второй, третий и четвертый выходы дешифратора 21 являются. . соответственно выходами 25-28 блока 13 управления, а первый и второй выхода блока 22 памяти являются выходами 29 и 30. Выход 2 5 подключен к синхровходу приема и к входу управления выдачей информации регистра 11, выход 26 соединен с. синхровходами приема регистров 1 и 12 и с входом управления выдачей информации регистра 12, выход 27 подключен к синхровходу приема и к входу управления выдачей регистpa 9,выход 28 соединен с синхровх дами приема регистров 2 и 10 и с входом управления выдачей информа ции регистра 10, выход 29 подключ к управляющему входу сумматора 7, выход 20 - к управляющему входу к мутатора 8. При введении четырех выходных регистроЬ 14г17 в блоке 13 управл ния блок 22 памяти содержит на шесть выходов больше, причем выхо блока памяти соединен с синхровхо приема регистра 14 и с входом упр ления выдачей регистра 17, выход соединен с синхровходом приема ре гистра 16 и с входом управления выдачей регистра 14, выход 33 под ключен к синхровходу приема регистра 15,выход 3.4 подключен к вхо управления выдачей регистра 15, выход 35 соединен с входом управления выдачей регистра 16, а выход 36 - с синхровходом приема I регистра 17. На фиг.5 приняты следующие усл ные обозначения: i-j- i-й-такт, j-й-палутакт} с - результат на выходе сумматора 7; БПФ - момент выдачи результатов преобразования с указанием какой, именно результат выдает ся; Рг1 2- входные регистры чисел 1 и РгЗ - регистр весового коэффициента 3; Рг5 - первый регистр слагаемых 5 Ргб - второй регистр слагаемых 6 Pr9tl2 - регистры результатов 9г12 МО - результат на выходе множите ного блока 4; Рг14-г17 - выходные регистры 14г17 Устройство выполняет базовую оп рацию алгоритма быстрого преобразо ния Фурье по основанию 2 A; B;tC;W; AI,, B,-C.VJ ReA; ReB; + ReC,ReW-I C;. ImA;--l B,+ (eCi-i,.ReW ReA;t, ReBrReC;-ReW t C. .r4B;-ReC;.,.ReW, где Bj,-C; - исходные отсчеты; A;,A;, , - преобразованные отсч W - весовой коэффициент, s-iT-, w.eJ ,j 4Tj Ы - количество отсчетов исходном массиве; s - действительная часть ч и ел а; Itn - мнимая часть числа. Paccмqfpим работу устройства при выполнении базовой операции. Считаем, что прием информации в регистры осуществляется в момент прихода заднего фронта синхроимпульса. . В конце первого такта по сигналу с выхода 25 блока 13 управления во входной регистр 1 чисел принимается действительная часть ReC; исходного отсчета С;, во входной регистр 3 весового коэффициента по сигналу с выхода 24 - действительная,часть ReW весового коэффициента W . Во втором такте выполняется умножение в множительном блоке 4 и произведение Re С; -Raw по сигналу с выхода 24 принимается в регистр 5. По этому же сигналу в регистр 3 принимается мнимая часть 01 W весового коэффициента W-, а по сигналу с выхода 28 в регистр 2 чисел принимается действительная часть Re В исходного отсчета В;. В третьем такте выполняется умножение и произведение ReС|Л,W по сигналу с выхода 24 принимается в регистр 5; по этому же сигналу в регистр 6 принимается произведение Rec .Re W .и в регистр 3 - мнимая часть 3n,W весового коэффициента W , во входной регистр 1 чисел по сигналу с выхода 26 принимается мнимая часть исходного отсчета С;. В четвертом такте в множительном блоке 4 выполняете умножение и произведение 3mC-1rn no сигналу с выхода 24 принимается в регистр 5 слагаемых, по этому же сигналу в регистр б принимается произведение Ret; .W , а во входной регистр 3 - действительная часть ReW весового коэффициента W . По сигналу с выхода 28 во входной регистр 2 принимается мнимая часть 3т S, исходного отсчета В,-. Коммутатор 8 по сигналу с выхода 30 подключает к входу сумматора 7 выход входного регистра 2 чисел. Сумматор 7 по сигналам с выхода 29 выполняет операцию сложения в первой половине четвертого такта, а операцию вычитания во второй половине. Соответственно Кев;+(ес--Rew по сигналу с выхода 27 -принимается в регистр 9 в середине четвертого такта, а разность ReB,-ReCReW ° сигналу с выхода 28 в конце четвертого такт.а принимается в регистр 10. В пятом такте в множительном блоке 4 выполня.етгся умножение и произведение l|T|C;-Rewno сигналу с выхода 24 принимается в регистр 5, произвеение ReW по этому сигналу принимается в регистр 6, а во входной

регистр 3 - действительная часть RP.. Во входной регистр 1 по сигналу с выхода.26 принимается действительная часть ReC, следующего исходного отсчета С, . Коммутатор 8 по сигналу с выхода 30 подключает

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

половине. В середине пятого такта суммаI Sj ReC, по сигналу с выхода 25 принимается врегистр 11, а в конце пятого такта разность 1 8;-RsC . по сигналу с выхода 26 принимается в регистр 12. В шестом такте в множительном блоке 4 выполняется умножение и произведени€ ReC по сигналу с выхода 24 принимается в регистр 5, в регистр б по этому же сигналу принимается произведение ReW;, а в регистр 3 - мнимая часть весового коэффициента . Во входной регистр 2 по сигналу с выхода 28 принимается действительная часть ЙеВ исходного отсчета Bj, .. Коммутатор 8 по сигналу с выхода 30 подключает к входу сумматора 7 объединенный выход регистров 9fl2 результатов. Сумматор 7 по сигналам с выхода 29 выполняет операцию вычитания в первой половине шестого такта и операцию сложения - во второй. В первой половине шестого такта по сигналу с выхода 27 из регистра 9 выдается сумма ReB; + ReC; и в середине такта по этому же сигналу (по заднему фронту) в регистр 9 принимается разность ReAi Яеб;;- ReC;-ReVj-I C -l W . Во второй половине шеетого такта по сигналу с выхода 28 из регистра.10 выдается разность ReVi/ и в конце такта по этому же сигналу в регистр 10 принимается сумма ReA;, ReB;-ReC;ReW+

В седьмом такте в множительном блоке 4 выполняется умножение и произведение ReC;,I«, сигналу с вы хода 24 принимается в регистр 5, в регистр б по этому же сигналу . принимается произведение Rec -ReW, а во входной регистр 3 - мнимая част весового коэффициента W Во входной регистр 1 по сигналу с выхода 26 принимается мнимая часть исходного отсчета С, . Коммутатор 8 по сигналу с выхода 30 подключает к входу сумматор 7 объединенный выход регистров 94-12 результатов. Сумматор 7 по сигналам с- выхода 29 выполняет операцию сложения и операцию вычитания соответственно в первой и второй половинах седьмого такта. В первой половине седьмого такта по сигналу с выхода 25 из регистра 11 выдается сумма ReC I,v и в середине такта по этому же сигналу в регистр 11 принимается сумма I ft;l«B;t Rec;. UC-ReWV Во второй половине седьмого такта п сигналу с выхода 26 из регистра 12 выдается разностьГ В; - ReC; tn,W и в конце такта по этому же сигналу в регистр 12 принимается разность |1«1 лм тВ;-ReC;-l C;-ReVKV

В ВОСЬМОМ такте в множительном блоке 4 выполняется умножение и произведение In, по сигналу с выхода 24 прийимается в регистр 5, в регистр 6 по этому же сигналу принимается произведение г а в регистр 3 - действительная чпс.ть Revy весового коэффициента . во входной регистр 2 по сигналу с выхода 28 принимается мнимая часть 1 9,ч, исходного отсчета Ъ . Коммутатор 8 по сигналу с выхода 30 подключает к входу су1лматора 7 выход входного регистра 2 чисел. Сумматор 7 выполнет операции сложения и вычитания в первой и второй половинах такта соответственно. В первой половине восьмого такта из регистра 9 на выход устройства выдается действительная часть Не А; преобразованного А, по сигналу с выхода 27 и по это же сигналу (по заднему фронту) в регистр 9 принимается сумма Re 8; , + fReC,- . Во второй половине восьмого такта из регистра 10 на шлход устройства по сигналу с выхода 28 выдается действительная часть Re Д;., и по этому же сигналу врегистр 10 принимается разност ReB;,-ReCi,,

В первой половине десятого такта по сигналу с выхода 25 из регистра 11 на выход устройства выдается мнимая часть In, А; преобразованного отсчета Л ; и по этому же сигналу в регистр 11 принимается сумма ,, 4 ReC,,- UW . Во второй половине девятого такта по сигналу с выхода 26 из регистра 12 на выход устройства выдается мнимая часть 1„ А;,, преобразованного отсчета А и по этому же сигналу в .регистр 12 принимается разность ,,-ReCi, . Работа остапыных элементов устройства аналогична описанной для пятого такта.

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

При введении четырех выходных регистров 14717 работа устройства отличается только в тактах 6-9, относящихся к записи преобразованных отсчетов и выдаче их на выход устройства. А именно, в середине шестого такта действительная часть Re А;

преобразованного отсчета А,- принимается не в регистр 9,а в регистр 14,соответственно Re А i ., /lyriA; flmAUi принимаются в регистры 15-17. Тогда выдачу преобразованных отсчетов можно выполнять независимо от промежуточных вычислений, причем равномерно, т.е. по одному результату за один такт. Например, в седьмом тактена выход устройства выдается ReA t в восьмом -Re А г в девятом -1т Л в десятом - + 1 а середине десятого такта в регистр 14 принимается ReA и далее .ReA,4, / т ,Гп,л;,э соответственно в десятом и одиннадца тЪм тЪктах в регистры 15-17, а в

иг. i

одиннадцатом такте можно уже -выдавать двенадцатом Re А,, и т.д.

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

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

двухвходовой. Кроме того, известное устройство имеет шесть входов, тогда как предлагаемое устройство только два, что существенно уменьшает число внешних связей и позволяет

работать с линейно организованной ; памятью.

20

Фиг. г.

2it

23

г

S

2 27

J Ъ0

.J/

-Г ±W

S tjff