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

1 Изобретение относится к вычислительной технике и может быть исполь зовано при построении устройства, реализуюп1их алгоритм быстрого преобразования Фурье (ВПФ). Известно устройство, выполняющее операции с комплексными числами. Уст ройство содержит регистры действител ной и мнимой частей сомножителей, фо мирователи поразрядных произведений комбинационно-накапливающие суммато ры, блок перевода в дополнительный код lj „ Однако это устройство требует большого объема оборудования. Наиболее близким к изобретению по технической сущности является уст ройство для быстрого преобразования Фурье, содержащее четыре входных регистра чисел и два входных регистра весового коэффициента, входы которых являются входами устройства множительный блок, сумматор, коммутатор слагаемых, коммутатор сомножителей, два регистра слагаемых, чет ре регистра произведений и блок упра ления, первый вход которого соедине с управляющим входом коммутатора слагаемых, второй - с управляющим входом коммутатора сомножителей, выходы регистров весового коэффициента соединены с первыми двумя информационными входами коммутатора сомножителей, выходы которого соединены с входами множительного блока, вьгсоды которого соединены-с вxoдa И регистров произведений, выходы которых соединены с первыми четырьмя информационными входами коммутатора слагаем1)1х, другие четыре инфорамционных входа которого соединены с выходами входных регистров- чисел, вы ходы коммутатора слагаемых соединены с входами сумматора, выход которого соединен с выходом устройства не входами регистров слагаемых, выходы которых соединены с третьим и четвертым информационными входами регистра сомножителей Н. . Недостатком известного устройства являются большие затраты оборудования . Кроме того, к недостаткам можно отнести наличие множества входов, что требует распараллеливания памяти, а это, в свою очередь, приводит к увеличению внешних связей и усложнению адресации либо к необходимости го 36 установки распределителя данных на входе устройства. Целью изобретения является уменьшение аппаратурных затрат и числа внешних связей. Поставленная цель достигается тем, что в устройство для быстрого преобразования Фурье, содержащее входной регистр чисел, входной регистр весового коэффициента, информационные входы которых являются входами устройства, множительный блок, регистр слагаемых, сумматор, четыре,, регистра результатов и блок управления, введен элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, а блок управления состоит из генератора синхроимпульсов, четырехразрядного счетчика тактов, элемента И, элемента НЕ и микропрограммного блока памяти, при этом выход цифровых разрядов регистра весового коэффициента соединен с цифровыми разрядами первого входа множительного блока, выход знакового разряда регистра весового коэффициента соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен со знаковьи: разрядом первого входа множительного блока, второй вход которого соединен с выходом входного регистра чисел, выход множительного блока соединен с информационным входом регистра слагаемых, инверсный выход которого соединен с первым информационным входом сумматора, выход которого соединен с информационнь ми входами четырех -регистров результатов, выходы которых объединены и подключены к выходу устройства и к второму информационному входу сумматора, выход генератора синхроимпульсов блока управления соединен со счетным входом счетчика тактов, выходы разрядов которого соединены с адресными входами блока памяти, выход первого разряда счетчика тактов соединен с входом приема регистров слагаемых, выход второго эазряда счетчика тактов соединен с входом элемента НЕ, выход которого оединен с первым входом элемента И, ыход которого соединен с входом уста новки в О счетчика тактов, выходы ретьего и четвертого разрядов котоого соединены с вторым и третьим ходами элемента И, выходы первой руппы блока памяти соединены с сответствующими входами приема входнорегистра чисел, входного регистра весового коэффициента, регистра слагаемых и регистров результатов, выходы второй группы блока памяти со динены с входами вьщачи регистров результатов соответственно, выход третьей группы блока памяти соединен с входом установки в О входного регистра весового коэффициента и с вторым входом элемента ИСКПЮЧАШЩЕ ИЛИ, выходы четвертой группы блока памяти соединены с входами управляющими сумматора. На фиг. 1 представлена структурная схема устройства для быстрого преобразования Фурьер на фиг. 2 структурная схема блока управления; на фиг. 3 - временная диаграмма,иллюстрирующая работу устройств а, на фиг. 4 - блок-схема алгоритма функционирования блока управления. Устройство для быстрого преобразования Фурье содержит входной регистр 1 чисел, вход которого является первым входом устройства, а вы ход подключен к первому входу множи тельного блока 2, к цифровым разряд второго входа множительного блока 2 подключены выходы цифровых разрядов и входного регистра 3 весового коэф фицента, вход которого является вто рым входом устройства. При этом вы ход знакового разряда регистра 3 весового коэффициента подключен к первому входу элемента ИСКЛЮЧАЩЕЕ ИЛИ 4, выход которого соединен с входом знакового разряда второго вх да- множительного блока 2. Выход мно жительного блока 2 соединен с инфор мационным входом регистра 5 слагаемых, выход которого подключен к первому информационному входу сумматора 6. Выход сумматора 6 соединен с информационным входами четырех регистров 7-10 результатов, выходы которых объединены и подключен к второму входу сумматора 6 и к вых ду яеего устройства. Выходы блока 11 управления соединены с управляющими входами всех регистров (1,3,5, 7f10), сумматора бис вторым входрм элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 4. Сумматор 6 представляет собой су матор с расширенными функциональным возможностями.Требуется,чтобы он выполнял следующие три операции: еложение, вычитание и пропуск одного ,из операндов без изменений. Непосредственное объединение выходов регистров допустимо, если в качестве этих регистров использовать регистры с тремя состояниями на выходе. Блок 11 управления может быть реализован, например, как показано на фиг. 2. Он содержит генератор 12 синхроимпульсов, счетчик 13 тактов, блок 14 памяти, элемент И 15, элемент НЕ 16, причем зыход генератора 12 подключен к счетчному входу четырехразрядного счетчика 13 тактов, выходы соединены с соответствующими входами микропрограммного блока 14 памяти. Кроме того, выход первого (младшего) разряда счетчика 13 тактов является выходом 17 блока управления и соединен с входом приема регистра 5 слагаемых, выход второго разряда счетчика 13 тактов соединен с входом элемента НЕ 16, выход которого соединен с первым входом элемента И 15. Выходы третьего и четвертого разрядов счетчика 13 тактов соединены соответственно с вторым и третьим входами элемента И 15, выход которого соединен с входом установки в О счетчика 13 тактов. Выходы блока 14 памяти являются выходами 18т-30 блока 11 управления, причем выход 18 соединен с синхровходом приема регистра 1 чисел, выход 19 соединен с синхровходом приема регистра 3 весового коэффициента, выходы 20723 подключены к синхровходам приема регистров 7-10 результатов соответственно, а выходы 24-727 - соответственно к входам управления выдачей информации тех же регистров 77-10. Вькоды 28 и 29 соединены с входами управления, вьтолняемой операцией сумматора 6, выход 30 подключен к второму входу элемента ИСКПЮЧАЩЕЕ ИЛИ 4, и к входу установки в О регистра 3 весового коэффициента. На фиг. 4а и 46 приняты следующие условные обозначения:, i-j - i-й такт, j-й - полутакт{ С - результат на выходе сумматора 6, БПФ - момент вьщачи результатов преобразования с указанием, какой именно результат выдается; Рг1 - входной регистр 1 чисел; РгЗ - входной регистр 3 весового коэффициента; Рг5 - регистр 5 слагаемых; Рг77Рг10 - регистры 7-710 результатов, МО - результат на выходе множительного блока. 5 Устройство выполняет базовую опер цию алгоритма быстрого преобразовани Фзфье по основанию 2 А; 8,С,-W ;, ., 6,-C-. 8eA; Re8,+l eC-ReW -l,C;. tmftrIvnB; ReC,-I W4i C;-ReW PieA-,-Re8-ReC;-ReWni C;-I W; n.H imBrReC... где B, C - исходные отсчеты, A-, - преобразованные отсчеты;W - ве СОВОЙ коэффициент, W e ,- j т N - количество отсчетов в исходном массиве; Re ... - действительная часть числа-, мнимая часть числа Рассмотрим работу устройства при выполнении базовой операции. Будем считать, что прием информации в регистры осуществляется в момент прихода заднего фронта, синхроимпульса. Устройство работает с дополнитель ными кодами чисел. Из внешней памяти весовые коэффициенты W прступают проинвертированными, т.е. (W4-1))o Информация на первый вход сумматора снимается с инверсных выходов регистра 5 слагаемых. На третий вход самого младшего разряда сумматора 6 (вход переноса) постоянно заведен сигнал, соответствующий наличию пере носа, т.е. 1. В конце первого такта по сигналу с выхода 18 блока 11 управления во входной регистр 1 чисел принимается действительная часть ReC j исходного отсчета С, во входной регистр 3 весового коэффициента по сигналу с выхода 19 .принимается действительна.я часть ReW весового коэффициента W Во втором такте выполняется,умножение в множительном блоке 2 и по си налу с выхода 17. в конце такта прои ведение ReC ReW принимается в регистр 5. По сигналу с выхода 19 в 3 принимается мнимая часть весового коэффициента W . В третьем такте в множительном блоке 2 выполняется; умножение и про изведение ReC . 1,у1 Wпо сигналу с выхода 17 принимается в регистр 5 слагаемых. Сумматор 6 по сигналам с выходов 28 и 29 выполняет пропуск .первого операнда и в регистр 7 по сигналу с выхода 20 принимается про 36 изведение ReC.;-ReW. Во входной регистр 1 чисел по сигналу с. выхода 18 принимается действительная часть ReBi исходного отсчета В. В четвертом такте в множительном блоке 2 выполняется умножение действительной части ReBj исходного отсчета В| на единицу и без изменений по сигналу с выхода 17 принимается в регистр 5. Умножение на единицу выполняется по сигналу с выхода 30, который устанавливает в О содержимое регистра 3, а значение знакового разряда инвертирует,То есть в качестве множителя подается число 1.00...О, при умножении на которое произведение равно множимому. Сумматор 6 по сигналам с выходов 28 и 29 выполняет пропуск первого операнда и в регистр 8 результатов по сигналу с выхода 21 принимается произведение ReC., Во входной регистр 1 по сигналу с выхода 18 принимается мнимая часть 1 исходного отсчеВ пятом такте в множительном блоке 2 выполняется умножение I гл B-i единицу и по сигналу с выхода 1 7 1„,В, принимается в регистр 5. Во входной регистр 1 по сигналу с выхода 18 принимается мнимая часть I С, исходного отсчета С . В регистр 3 весового коэффициента по сигналу с вьгхрда 19 принимается мнимая часть 1 V весового коэффициента У. По сигналу с выхода 24 из регистра .7 въщается произведение ReCjReW. Кроме того, в первой половине пятого такта сумматор 6 выполняет операцию вычитания и в середине такта по сигналу с выхода 22 в регистр 9 принимается разность ReBj-ReC. ReW Во второй половине пятого такта сумматора 6 по сигналам с выходов 28 и 29 выполняет операцию сложения и в конце такта по сигналу с выхода 20 сумма ReB j-1-ReC;. ReW принимается в регистр 7. В шестом такте в множительном блоке 2 выполняется умножение и произведение по сигналу с выхода 17 принимается в регистр 5, во входной регистр 3 весового коэффициента по сигналу с выхода 19 принимается действительная,часть ReW весового коэффициента W. Из регистра 8 по сигналу с выхода ,25 вьщается произведение ReCj-l W. Кроме того. в первой половине шестого такта сумматор 6 по сигналам с выходов 28 и 29 -выполняет операцию вычитания и в середине такта в регистр 10 по сигналу с выхода 23 принимается разность . . Во второй половине такта сумматор 6 выполняет операцию сложения и в конце такта по сигналу с выхода 21 в регист р 8 принимается сумма 1 В- -ReCi . В седьмом такте в множительном блоке 2 выполняется умножение и по сигналу с выхода 17 в регистр 5 принимается произведение . ReW входной регистр 1 принимается действительная часть ReC исходного отсчета ., во входной регистр 3 принимается действительная-часть ReW BecoBoro коэффициента i Кром того, в первой половине с.е.дъмого такта по сигналу с выхода 24 вьщаетс содержимое регистра 7 ReB- + ReC-ReW Сумматор 6 по сигналам с выходов 28 и 29 выполняет операцию вычитания и в регистр 7 в середине такта по сигналу с выхода 20 принимается действительная часть ReAj ReB- . Re . I-W . Bo второй половине седьмого такта по сигналу с выхода 26.из регистра 9 выдается ReBj-ReC -. I-eW , сумматор 6 выполняет операцию сложения и в конце такта по сигналу с выхода 22 в регистр 9 принимается действительная .часть ReA:;, ReBj -ReC х у ReW% . В восьмом такте в множительном блоке. 2 выполняется .умножение и произведение ReC . по сигналу с выхода 17 принимается регистр 5, во входной регистр 3 по сигналу с выхода 19 принимается мнимая ча:сть ImW весового коэффициента W Кроме того в первой половине восьм го такта из регистра 10 по сигналу с выхода 27 выдается 1„В- ReC; сумматор 6 по сигналам с выходов 28 и 29 выполняет операцию вычитания и в сере дине такта по сигналу с выхода 23 в регистр 10 принимается мнимая,час 1«,А;,, ,-ReC;.y-.T- ,ReW второй половине восьмого такта из 68 регистра 8 по сигналу с выхода 25 выдается ReC,. , сумматор 6 выполняет операцию сложения и по сигналу с выхода 21 в регистр 8 принимается мнимая часть 1..А; IB- ReC,-- .-ReW . В девятом такте в множительном блоке 2 выполняется умножение и произведение ReC. сиг налу с выхода 17 принимается в регистр 5. слагаемых, сумматор 6 по сигналам с выходов 28 и 29 выполняет пропуск nepBqro операнда, произведение ReC;,ReW по сигналу с выхода 20 принимается в регистр 7. Во входной регистр 1 принимается действительная часть исходного отсчета В,. . Кроме того, в первой половине девятого такта из регистра 7 на выход yctройства по сигналу с выхода 24 выдается ReAj. Во второй половине девятого такта по сигналу с выхода 25 на выход устройства выдается мнимая часть 3„А;. В десятом такте в множительном блоке 2 выполняется умножение действительной части единицу и по сигналу с выхода 17 ,-принимается в регистр 5, во входной регистр 1 по сигналу с выхода 18 принимается мнимая часть 1 8; исходного отсчета В . Кроме того, в первой половине десятого такта по сигналу с выхода 26 из регистра 9 на выход устройства выдается действительная часть ReA, а во второй половине десятого такта на выход устройства по сигналу с выхода 27 выдается мнимая часть гп i + 1. Далее работа всего устройства аналогична. Таким образом, по сравнению с известным устройством предлагаемое устройство при той же производительности имеет на пять регистров и два сумматора меньше. Кроме того, известное устройство имеет шесть входов, тогда как предлагаемое устройство только два, что существенно уменьшает число внешних связей и позволяет работать с линейно организованной памятью.

г I n I П r1

8 36fSS M.9 I / 7/7 Вы;(од

1М±У

С Рг5-Ргв ,, PгЭ lmW

Prg MO PeCi-ReW

3-1бПФ -Рг7 ВеЛ21-2

С Рр5

Pr8 Z

pp5 MO ReCL-lmWt

фигЛа

БП1|15«Рг9 Не Azi-i

БПСР РгШ 1тА21., РгВ С

НеВ1 Рг1 1тВ1

С Рр5- Рр7

+ Pp7 Рг7 С

2

Pp5 MO ImBt Im Wt Ci

.

C PP5-Pr8 Rp 10 С

С Рг5+Рг8

2

Pp5 MO lmCt-ImW

i

I

® . Фиг. ff

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