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

 

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

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

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

РЕСПУБЛИН (19) (11) З 151) С 06 F 15/332

ВЕГГД1 ;..1ъ.з)-..;,, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ (21) 3511922/18-24 (22) 17. 11. 82 (46) 07.07.84. Бюл. N - 25 (72) Ю.С; Каневский, С.Э. Котов, .

Н.Е. Куц, В.И. Лозинский и Б.А. Некрасов (71) Киевский ордена Ленина политехнический институт им.50-летия Великой

Октябрьской социалистической революции (53) 681 . 3 (088. 8) (56) 1. Авторское свидетельство СССР

N 399859, кл. G 06 F 7/38, 1971.

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

У 736113, кл. С 06 F 15/332, 1977 (прототип) (54) (57) УСТРОЙСТВО ДЛЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее входной регистр чисел, входной регистр весового коэффициента, информационные входы которых являются входами устройства, множительный блок, регистр слагаемых, сумматор, четыре регистра результатов и блок управления, о т л и ч а ю щ е е с я тем, что, с целью уменьшения аппаратурных затрат, в него введен элемент

ИЛИ, а блок управления состоит из генератора синхроимпульсов, счетчика тактов, элемента И, элемента HE и блока памяти, при этом выход цифровых разрядов регистра весового коэффициента соединен с цифровыми разрядами первого входа множительного блока, выход знакового разряда регистра весового коэффициента соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен со знаковым разрядом первого входа множительного блока, второй вход которого соединен с выходом входного регистра чисел, выход множительного блока соединен с информационным входом регистра слагаемых, инверсный выход которого соединен с первым информационным входом сумматора, выход которого соединен с информационными входами четырех регистров результатов, выходы ко. торых объединены и подключены к выходу устройства и к второму информационному входу сумматора, выход генератора синхроимпульсов блока управления соединен со счетным входом счетчика тактов, выходы разрядов которого соединены с адресными входами блока памяти, выход первого разряда счет- 3 чика тактов соединен с входом приема регистра слагаемых, выход второго разряда счетчика тактов соединен с входом элемента НЕ, выход которого соединен с первым входом элемента И, выход которого соединен с входом установки в "0" счетчика тактов, выходы третьего и четвертого разрядов которого соединены с вторым и третьим входами элемента И, выходы первой группы блока памяти соединены с входами приема входного регистра чисел, входного регистра весового коэффициента, регистра слагаемых и регистров результатов соответственно, выходы второй группы блока памяти соединены с входами выдачи регистров результатов соответственно, выход «ф» третьей группы блока памяти соединенс с входом установки в "0" входного регистра весового коэффициента и с вторым входом элемента ИСКЛ10ЧАЮЩЕЕ ИЛИ, выходы четвертой группы блока памяти соединены с управляющими входами сумматора.

1101836

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

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

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

Наиболее близким к изобретению по технической сущности является устройства для быстрого преобразования

Фурье, содержащее четыре входных регистра чисел и два входных реги- 20 стра весового коэффициента входы которых являются входами устройства, множительный блок, сумматор, коммутатор слагаемых, коммутатор сомножителей, два регистра слагаемых, четы2 ре регистра произведений и блок управления, первый вход которого соединен с управляющим входом коммутатора слагаемых, второй — с управляющим входом коммутатора сомножителей, выходы регистров весового коэффициента соединены с первыми двумя информационными входами коммутатора сомножителей, выходы которого соединены с входами множительного блока„ выходы которо †соединены с входами регистров произведений, выходы которых соединены с первыми четырьмя информационными входами коммутатора слагаемых, другие четыре инфарам- 40 ционных входа которого соединены с выходами входных регистров чисел, выходы коммутатора слагаемых соединены с входами сумматора, выход которого соединен с выходом устройства и с входами регистров слагаемых, выходы которых соединены с третьим и чегвертым информационными входами регистра сомножителей f2) .

5G

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

Целью изобретения является уменьшение аппаратурных затрат и числа внешних связей.

Поставленная цель достигается тем, чта в устройство для быстрого преобразования Фурье, содержащее входной регистр чисел, входной регистр весового коэффициента, информационные входы которых являются входами устройства, множительный блок, регистр слагаемых, сумматор, четыре. регистра результатов и блок управления, вв"-.— ден элемент ИСКЛ10ЧЛЮЩЕЕ IIIIH, а блок управления состоит из генератора синхраимпульсов, четырехразряднагo счетчика тактов, элемента И, элемента НЕ и микропрограммного блока памяти, при этом выход цифровых разрядов регистра весового коэффициента соединен с цифровыми разрядами первого входа множительного блока, выход знакового разряда регистра весового коэффициента соединен с первым входo>", элемента ИСКЛЮЧЛЮЩЕЕ ИЛИ, выход которого соединен со знакавьп разрядам первого входа множительного блока, второй вход которого соединен с выходам входного реги" òðà чисел, выход множительного блока соединен с информационным входом регистра слагаемых, инверсный выход которого соединен с первым информационным вхадам сумматора, выход кстарага соединен с информационными входами четырех регистров результатов, выходы которых объединены и подключены к выходу устройства и к второму информационному входу сумматора, выход генератора синхраимпульсов блока управления соединен са счетным входом счетчика тактов, выходы разрядов которого соединены с адресными входами блока памяти, выход первого разряда счетчика тактов соединен с входом приема регистров слагаемых, выход второго разряда счетчика тактов соединен с входом элемента НЕ, выход которого соединен с первым входом элемента И, выход которого соединен с входом установки в "О" счетчика тактов, выходы третьего и четвертого разрядов которого соединены с вторым и третьим входами элемента И, выходы первой группы блока памяти соединены с соответствующими входами приема входного регистра чисел, входного регистра

1101836 весового коэффициента, регистра слагаемых и регистров результатов, выходы второй группы блока памяти с оединены с входами выдачи регистров результатов соответственно, выход третьей группы блока памяти соединен с входом установки в "0" входного регистра весового коэффициента и с вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы четвертой группы 10 блока памяти соединены с входами управляющими сумматора.

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

Устройство для быстрого преобразования Фурье содержит входной регистр 1 чисел, вход которого является первым входом устройства, а вы- 5 ход подкпючен к первому входу множительного блока 2, к цифровым разрядам второго входа множительного блока 2 подключены выходы цифровых разрядов и входного регистра 3 весового коэффицента, вход которого является вторым входом устройства. При этом выход знакового разряда регистра 3 весового коэффициента подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ 4, выход которого соединен с

35 входом знакового разряда второго вхо. да-множительного блока 2. Выход множительного блока 2 соединен с информационным входом регистра 5 слага40 емых, выход которого подключен к первому информационному входу сумматора 6. Выход сумматора 6 соединен с информационным входами четырех регистров 7-10 результатов, вы45 ходы которых объединены и подключены к второму входу сумматора 6 и к выходу веего устройства. Выходы блока

11 управления соединены с управляющими входами всех регистров (1,3,5, 7-,10), сумматора 6 и с вторым вхо50 дом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 4.

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

Непосредственное объединение выходов регистров допуСтимо, если в качестве этих ре-гистров использовать регистры с тремя состояниями на выходе.

Блок 11 управления может быть реализован, например, как показано на фиг. 2. Он содержит генератор 12 синхроимпульсов, счетчик 13 тактов, блок 14 памяти, элемент И 15, элемент НЕ 16, причем зьтход генератора

12 подключен к счетчному входу четырехразрядного счетчика 13 тактов, выходы соединены с соответствующими входами микропрограммного блока 14 памяти. Кроме того, выход первого (младшего) разряда счетчика 13 тактов является выходом 17 блока управления и соединен с входом приема регистра 5 слагаемых, выход второго разряда счетчика 13 тактов соединен с входом элемента HE 16, выход которого соединен с первым входом элемента И 15. Выходы третьего и четвертого разрядов счетчика 13 тактов соединены соответственно с вторым и третьим входами элемента И 15, выход которого соединен с входом установки в "0" счетчика 13 тактов. Выходы блока 14 памяти являются выходами 18-, 30 блока 11 управления, причем выход 18 соединен с синхровходом приема регистра 1 чисел, выход 19 соединен с синхровходом приема регистра 3 весового коэффициента, выходы 20 †;23 подключены к синхровходам приема регистров 7-10 результатов соответственно, а выходы 24-:27 — соответственно к входам управления выдачей информации тех же регистров 7-. 10. Выходы

28 и 29 соединены с входами управления. выполняемой операцией сумматора 6, выход 30 подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 4, и к входу установки в "0" регистра 3 весового коэффициента.

На фиг. 4а и 4б приняты следующие условные обозначения:. i-j — i-й такт, j-й — нолутакт, С вЂ” результат на выходе сумматора 6, БПФ вЂ” момент выдачи результатов преобразования с указанием, какой именно результат выдается; Prl — входной регистр 1 чисел;

Рг3 — входной регистр 3 весового коэффициента; Pr5 — регистр 5 слагаемых;

Pr7-;Pr10 — регистры 7-;10 результатов, M0 — результат на выходе множительного блока, 1101836

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

Фурье по основанию 2

А;=8„+С; 5 ;

ReA,= Ee8„>ReC„ReW -1,„С; 1„,а ;

1 A„=I 8; ReC, 1„,%1 i 1. с;- кеФ, Яея;„=Рев„-ReC; ReW 1 с; I„W4;

1,„ ;,„=1„„8,- ЯеС, 1„,М/"-1„,С; Re9t

t0 где В;, С, — исходные отсчеты, А;, А„, — преобразованные отсчеты W — ве — 15

1 ЯЙ, совой коэффициент, W = е ";,j

N — количество отсчетов в исходном массиве; Re ... — действительная часть числа; I — мнимая часть числа.

Рассмотрим работу устроиства при

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

Устройство работает с дополнительными кодами чисел. Из внешней памяти весовые коэффициенты W поступают проинвертированными, т. е. (И" (-1))A«„

Информация на первый вход сумматора 6 снимается с инверсных выходов реги30 стра 5 слагаемых. На третий вход самого младшего разряда сумматора 6 (вход переноса) постоянно заведен сигнал, соответствующий наличию переноса, т.е. "1". 35

В конце первого такта по сигналу с выхода 18 блока 11 управления во входной регистр 1 чисел принимается действительная часть ReC исходногс отсчета С,, во входной регистр 3 40 весового коэффициента по сигналу с выхода 19,принимается действительная часть ReW весового коэффициента W .... I 1

Во втором такте выполняется умножение в множительном блоке 2 и по сиг45 налу с выхода 17, в конце такта произведение ЕеС ReW принимается в регистр 5. По сигналу с выхода 19 в регистр 3 принимается мнимая часть

J W весового коэффициента W".

Ф

В третьем такте в множительном блоке 2 выполняется умножение и произведение ReC 1„ И по сигналу с вы1 хода 17 принимается в регистр 5 слагаемых. Сумматор 6 по сигналам 55 с выходов 28 и 29 выполняет пропуск ,первого операнда и в регистр 7 по сигналу с выхода 20 принимается произведение ReC;, - ReW Во входной регистр 1 чисел по сигналу с выхода 18 принимается действительная часть ReBi исходного отсчета В

В четвертом такте в множительном блоке 2 выполняется умножение действительной части ReB исходного отсчета В1 на единицу и ReBj без изменений по сигналу с выхода 17 принимается в регистр 5. Умножение на единицу выполняется по сигналу с выхода 30, который устанавливает в "0" содержимое регистра 3, а значение знакового разряда инвертирует.То есть в качестве множителя подается число

1.00...0, при умножении на которое произведение равно множимому. Сумматор б по сигналам с выходов 28 и 29 выполняет пропуск первого операнда и в регистр 8 результатов по сигналу с выхода 21 принимается произведение

КеС„ 1 П". Во входной регистр 1 по сигналу с выхода 18 принимается мнимая часть 1 В„ исходного отсчета В„ .

В пятом такте в множительном блоке 2 выполняется умножение „„ 8„ на единицу и по сигналу с выхода 17 I Â, принимается в регистр 5. Во входной

-регистр 1 но сигналу с выхода 18 принимается мнимая часть 1 щ С„ исходного отсчета С, . В регистр 3 весового коэффициента по сигналу с вьгхода 19 принимается мнимая часть 1щ v весового коэффициента У". По сигналу с выхода 24 из регистра 7 выдается произведение ReC, ReM . Кроме того, в первой половине пятого такта сумматор 6 выполняет операцию вычитания и в середине такта по сигналу с выхода 22 в регистр 9 принимается разность ReB -ReC ReV . Во второй ! половине пятого такта сумматора 6 по сигналам с выходов 28 и 29 выполняет операцию слОжения и в конце такта по сигналу с выхода 20 сумма

ReB 1.ReC ReW принимается в регистр 7.

В шестом такте в множительном блоке ? выполняется умножение и произведение 3 С 7 Б по сигналу с выrrl 1 Р1 хода 17 принимается в регистр 5, во входной регистр 3 весового коэффициента по сигналу с выхода 19 принимается действительная, часть ReW весового коэффициента Ы". Из регистра

8 по сигналу с выхода,25 выдается произведение ReC< 1 И". Кроме того, 1101836 в первой половине шестого такта сумматор 6 по сигналам с выходов 28 и

29 выполняет операцию вычитания и в середине такта в регистр 10 по сигналу с выхода 23 принимается раз- 5 ность I В -КеС„. ? M . Во второй половине такта сумматор 6 выполняет операцию сложения и в конце такта по сигналу с выхода 21 в регистр

8 принимается сумма I В.>ReC ° I W . 1О

rll 1 1 m

B седьмом такте в множительном блоке 2 выполняется умножение и по сигналу с выхода 17 в регистр 5 принимается произведение Т С„КеУ, во входной регистр 1 принимается дей- 15 ствительная часть ВеС1 „ исходного отсчета С„ „, во входной регистр 3 принимается действительная часть

ReW весового коэффициента Б1 . Кроме

1 1 -1+ 1 того, в первой половине седьмого 20 такта по сигналу с выхода 24 выдается содержимое регистра 7 КеВ;+ВеС. ReW, 1

Сумматор 6 по сигналам с выходов 28 и 29 выполняет операцию вычитания и в регистр 7 в середине такта по сигналу с выхода 20 принимается действительная часть КеА1 = КеВ; ReC„. ReW .

-I С . I W" . Во второй половине седь1 мого такта по сигналу с выхода 26 из регистра 9 выдается ReB1-ВеС,:.еЫ", 30 сумматор 6 выполняет операцию сложения и в конце такта по сигналу с выхода 22 в регистр 9 принимается действительная .часть КеА„ „= ReB -ВеС„х

Кец 1I„C ТФЦ . В восьмом такте в 35 множительном блоке 2 выполняется,умножение и произведение КеС; ReW

Н1 (11 по сигналу с выхода 17 принимается в регистр 5, во входной регистр

3 по сигналу с выхода 19 при- 4р нимается мнимая часть I W весового коэффициента И ". Кроме того, в первой половине восьм<.го такта из регистра 10 по сигналу с выхода 27 выдается I  — РеС I„W, сумматор 45

6 по сигналам с выходов 28 и 29 выполняет операцию вычитания и в середине такта по сигналу с выхода 23 в регистр 10 принимается мнимая, часть

ImAi«Т, В„-ReC„ I 11"- ImC;, ReW, Во второй половине восьмого такта из регистра 8 по сигналу с выхода 25 вьгдается I В :ReC; I W, сумматор 6 выл\ полняет операцию сложения и по сигналу с выхода 21 в регистр 8 принимается мнимая часть 1 А = I В ReC ° ° Т W + щ 1 )i1 1 1 m

1й налу с выхода 17 принимается в регистр 5 слагаемых, сумматор 6 по сигналам с выходов 28 и 29 выполняет пропуск первого операнда, произведение

ReC;„ ReM по сигналу с выхода 20 принимается в регистр 7. Во входной регистр 1 принимается действительная часть КеВ;11 исходного отсчета В; 1

Кроме того, в первой половине девятого такта из регистра 7 на выход устройства по сигналу с выхода 24 выдается ReA, . Во второй половине девятого такта по сигналу с выхода 25 на выход устройства выдается мнимая часть 2 А;.

В десятом такте в множительном блоке 2 выполняется умножение действительной части ReB;,1на единицу и по сигналу с выхода 17 ReB„ .принимается в регистр 5, во входной регистр 1 по сигналу с выхода 18 прини. мается мнимая часть 1,„ 8;,„исходного отсчета В; 1 . Кроме того, в первой половине десятого такта по сигналу с выхода 26 из регистра 9 на выход устройства выдается действительная часть КеА;д, а во второй половине десятого такта на выход устройства по сигналу с выхода 27 выдается мнимая часть

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

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

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

1101836

1,01836

17

Фиг. Г дыр

bid О дыха

1 2 РеСс ,I

4 5 6 7 д У 10

Ред 1тд 1 Ю РеС j Ред (I 8

1101836

Ф 1 6ПФ5 Pr9=8e А, 1

С=Рг5- Pr 7

Рг7=0

1-2

5-1 C= Рг5 Рг7

Рг9=С

С=pr 5- Pr 10

P,1O= С

5-2

2-2

С=Рг5- Ргб

Rr 1О= С

1-1 ЬПФ=-Рг7= RGAЯ-g

6 — 2

З-2 Риг. Фа

Фиг. М

Редактор В. Иванова

Тираж 699 Подписное

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

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

Заказ 4769/33

Филиал ЛПП "Патент", r. Ужгород, ул. Проектная, 4

С=Рг5- Рг9

Рг9=0

Рг 1= ReCi, РгЗ=Ееыс

Рг5=1"10

С=pr5 — P 5

pr 8=С

pf 5=ImWL

Pr 5= МО=peCi. ROW"

С= Рг5

0ПФ= Рг8=1" Азв-

Рг7= С

Рг1= Re Bi

Pr 5 = М0= йЕ С Im Wi

C= Рг5

br1lp= prl0= lWA2tf

Ргб=С

Рг5 =MO=Rebi

Pr1 =I bi

С= Pr5+Prl

Рг7=С рг5=МО=ЬВс

РгЗ=Ьп Wi

Рг1=Irrr Ci

С= Рг5+Рг8

Рг8= С . P г 5 = М О = I m С i . .J rrr д 1

Pr 3 =Re

Составитель А. Федоров

Техред Т. Маточка Корректор В. Бутяга