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

113

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

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

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

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

Блок синхронизации (фиг.З) содержит генератор 16, счетчик )7, узел постоянной памяти 18, дешифратор 19, элемент И 20.

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

С,- . А,- -h Б,

D; - (А,.- В.) - W ReC,- ReA, ReB

ImCj imB

ReD; - (ReA;- Re3f) ReW +

-I- (ImA;- ImB) Im-W

ImD, « -(ReA - ReB,) ImW

+ (ImA, - ImB;) - ReW ,

де A;, B- S ,исходные отсчеты ( ний и нижний операнды графа базовой операции быстрого преобразования Фурье);

преобразованные отсчеты (верхний и нижний операнды графа базовой опе7120

5

0

5

0

5

0

5

0

IL

N

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

Re Tm

ReW cos

4(2VN} i -действительная (косинусная ) часть тригономет- ри еского коэффициента, . ,I,...,N/2; InW sin

() ij -мнимая (синусная часть тригонометрического коэффициента, ,1,,.., N/2.

Рассмотрим работу устройства при выполнении баэовой операции быстрого преобразования Фурье. Будем считать что прием в регистры осуществляется по передним фронтам полутактовых импульсов, а счетчик работает по задним фронтам полутактовых импульсов. На фиг.2 показаны выполняемые операции сумматором-вычитателем и коммутаторами и принимаемая информация в регистры, а на фиг.4 - команды, поступающие на управляющие входы элемен-. тов устройства с выходов блока 11 синхронизации. Первые два такта полезная информация на выход I3 устройства .не подается, но в дальнейшем в середине каждого такта при непрерывном поступлении данных на входы устройства на выходе 13 появляются соответствующие результаты, которые мо- записаны во внешнюю память по -передним фронтам вторых полутактовых импульсов в каждом такте. Цикл работы устройства составляет четыре такта. Такт работы -устройства есть такт работы умножителя.

В первом такте коммутатора 8 по команде с пятого выхода блока 11 синхронизации подключает вход 14 устройства к входу регистров 9 и 10 и по команде с второго выхода блока 11 синхронизации в регистры I и 9 соответственно записываются ReA- и ReB- ; по команде с третьего выхода блока 1 синхронизации коммутатор 2 подключа- 5 ет выход регистра 1 к первому входу сумматора-вычитателя 3; по команде с восьмого выхода блока II синхронизации разрешается выдача ReBt из регистра 9 на второй вход сумматоравычитателя 3, который в первой половине такта работает в режиме вычитания, а во второй половине - в режиме сложения по команде с шестого вы хода блока 11 синхронизации. Во второй половине такта на выходе суммато ра-вьгчитателя 3 формируется разность ReA.-ReB;.

Во втором такте в регистр 4 по команде с четвертого выхода блока 11 синхронизации записьгаается ReB., в регистр 6 по команде с первого выхода блока 11 синхронизации записывается ReW . Блок 5 умножения формирует на своем выходе произведение (ReA-- ReB.)-ReW , во второй половине такта в регистр 10 по команде с седьмого выхода блока 1I синхронизации записьшается ImB. .

В третьем такте по команде с первого выхода блока 11 синхронизации произведение (ReA.- ReB O ReW записьшается в регистр 7, ImW - в регистр 6. Блок 5 умножения форми-- рует на своем выходе произведение (ReA,- - Re В Л - ImW , сумматор-вычита- тель 3 по команде с шестого выхода блока 11 синхронизации в первой половине такта работает в режиме сложения, а во второй половине - в режиме вычитания. В первой половине такта на выходе 13 устройства формируется результат ReC. ReA.+ ReB-.Во второй половине такта выход регистра 7 подключается через коммутатор 8 по команде с пятого выхода блока 1J синхронизации к информационным входам регистров 9 и 10, и по команде с второго выхода блока 11 синхрони-. зации произведение (ReA-- ReB)-ReW переписывается в регистр 9, а ImA. с входа 12 устройства - в регистр 1. По команде с девятого выхода блока 1I синхронизации с выхода регистра 10 1тВ{ поступает на второй вход сумматора-вычитателя 3 и на его выходе формируется разность (IniA- - ImB-). В четвертом такте разность (IraA ImBj) по команде с четвертого выхода блока 11 синхронизации за- писывается в регистр 4, по команде с первого выхода блока 11 синхронизации произведение (ReA - ReB..)-IroW записывается в регистр 7, а ImB - в регистр 6. Блок 5 умножения формирует на своем -выходе произведение (1тпА - - ImB.) ImW . Сумматор-вычита- тель 3 по команде с шестого выхода

27120

блока 11 синхронизации работает в режиме сложения и на выходе I 3 устройства в первой .половине такта формируется результат ImC, ImB., во второй половине такта произведение (ReAj - ReB.)-ImW переписывается в регистр 10 по команде с седьмого выхода блока П синхронизации. В пятом такте по команде с первого выхода блока 1I синхронизации произве10

дение (ImA; - ImB) ImW записывается в регистр 7, а ReW - в регистр 6. Блок 5 умножения формирует на сво-- ем вьрсоде произведение (ImAj - ImBj )х «ReW, по команде с третьего выхода блока 11 синхронизации в первой поло- вине такта коммутатор 2 подключает к первому входу сумматора-вычитателя 3 выход регистра 7, а во второй половине такта - выход регистра 1. Сумматор-вычитатель 3 в первой половине такта работает в режиме сложения, а во второй половине такта - в режиме вычитания. На второй вход сумматора-вычитателя 3 по команде с восьмого выхода блока 11 синхронизации разрешается вьща- ча информации с выхода регистра 9 и в первой половине такта на выходе 13 устройства формируется результат ReD- (ReA,- - ReB,-)

+ (ImA,- - ImB.) -ImW . - Bo второй половине такта по команде с второго выхода блока 1J синхронизации в регистр 1 записывается

ReA

0

5

1 + 1

в регистр 9 - ReB;+, операн1+

дов следукяцей (1--1)-й базовой операции. На выходе сумматора-вычитателя

3 формируется разность (ReA.

ReB,.,, ).

1 + 1

В тестом такте по команде с первого выхода блока 11 синхронизации произведение (ItnA; - ImB .) ReW записывается в регистр 7, а - в регистр 6, на второй вход су1«матора-вычитателя 3 по команде с девятого выхода блока 1I синхронизации разрешается выдача информации с выхода регистра 10, по команде с четвертого выхода блока 1I синхронизации разность (ReAi+, - ReB ) записывается в регистр 4, Блок 5 шо- жения формирует на своем выходе произведение (ReA-, - ReB,)-ReW . По команде с шестого выхода блока I1 синхронизации сумматор-вычитатель 3 работает в первой половине такта в режиме вычитания, а во второй поло5 13

вине Такта - режиме сложения, в первой половине такта выход регистра 7 через коммутатор 2 по команде с третьего выхода блока П синхрони™ зации подключается к первому входу сумматора-вычитателя 3, и на выходе

13устройства формируется результат

ImD, - (ReA, - ReB-)-IraW

+ (ImA. - ImB) -ReW .

Bo второй половине такта по комак ,де с пятого выхода блока П синхронизации коммутатор 8 подключает вход

14устройства к информационньгм входам регистров 9 и 0 и по команде с второго выхода блока I1 синхронизации

в регистр 10 записывается IraB. , В седьмом такте устройство работает аналогично третьему такту и в первой половине такта на выходе I3 устрой- ства формируется результат ReC + Далее устройство работает аналогичным образом и вьща- ет результаты выполнения очередной базовой операции за четыре такта с интервалом в один такт в последовательности ImCj , eDj; , |pd)|,, , ReC.j , ImCi, eD ; ,

ImD

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

Арифметическое устройство для быстрого преобразования Фурье, содержащее первый и второй кo мyтaтopы первый и второй регистры, сумматор™ вычитатель, регистр множимого, регистр множителя, регистр пронзв€ де- ния, блок умножения, блок синхронизации и входной регистр, выход кото- рого подклкпен к первому информационному входу первого коммутатораs вьжод которого.подключён к первому входу сумматора-вычитателя, выход

с

5 0

20 6

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

фиг. 2

Изобретение относится к автоматике и вычислительной технике и предназначено для использования в составе специализированных процессоров быстрого преобразования Фурье. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входят входной регистр 1, коммутатор 2, сумматор-вычитатель 3, регистр множимого 4, блок умножения 5, регистр множителя 6, регистр произведения 7, коммутатор 8, регистры 9, 10, блок синхронизации П, вход 12 первого операнда, информационный выход 13, вход 14 второго операнда, вход 15 задания коэффициента и соответствующие связи между узлами устройства. 4 ил. ь ND

.l

ffu/x.Z

Stffjf. -4

. 7

SMX. 3 . 5 Вых. 6 ewx. 8 .S

фиг.:5