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

1211750 .

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

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

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

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

Арифметическое устройство содержи два блока умножения 1 и 2, каждый из которых состоит из регистра множимого 3 и 4 умножителей 5 и 6, регистров множителя 7 и 8, сумматоров 9 и 10, регистров 11 и 12, управляющий . зход 13 является синхровходом регистров 3, 4, 7 и 8, управляющий вход 14 является синхровходом регистров II и 12, управляющие входы 15 и 16 поступают на входы управления сумматором 9, управляющие входы 17 и 18 - на входы управления сумматором 10, регистры 19 и 20, микропроцессоры 21 и 22, сумматоры 23 и 24, блоки регистров 25 и 26, управляющие входы 27 и 28 являются управляющими входами сумматора 23, а управлдкнцие входы 29 и 30 являются управляющими входами сумматора 24, управлякщие входы 31 и 32 - управляющими входами регистров 19 и 20, управляющие входы 33-40 являются управляющими входами записи, а управляющие входы 41-48 - управляющими входами считывания блоков регистров 25 и 26.

Блок управления 49 содержит генератор импульсов 50, счетчик импульсо 51, выход генератора импульсов сое- динен с счетным входом счетчика импульсов 51, количество разрядов которого р 6, и адресным входом постоянного запомицадаего устройства 52, выходы разрядов .счетчика импульсов 51 соединены с адресными

входами постоянного запоминающего устройства 52, выход 0-го разряда счетчика импульсов 51 является входом управления 13, выход 1-го разряда счетчика импульсов 51 является входом управления 14, первый выход постоянного запоминакмцего устройства 52 является управляющим входом 16, второй выход является управляющим входом 17, третий и четвертый выходы являются управляющими входами 27 и 28, пятый и шестой выходы - управлякщими входами 29 и 30, седьмой и восьмой - управляющими входами 31 и 32, с девятого по шестнадцатый- управляющими входами записи 33-40, с семнадцатого по двадцать четвертый - управлякяцими входами считывания 41-48, управляющий вход арифметического устройства является входом управления режимом работы блока управления 49.

Рассмотрим работу ари||й«1етического устройства при выполнении базовой операции алгоритма быстрого преобразования Фурье по основанию 4.

Пусть исходные операнда поступают на вход устройства в следующей последовательности

Rea(i1,, Req (-t+O, 3hia(Ui., Rea(i42),3Tna(u2),Rea(i+), Jni a()

период синхроимпульсов с выхода генератора импульсов 50 Тр и его скваж

ность у

Период TO равен такту

работы-устройства тогда как для обеспечения работы устройства необходимо чтобы время записи и считывания в. блоки регистров 25 и 26 равны TO 1/2 (полутакт), период приема в регистры 3, 4, 7 и 8 равен i 2То , период приема в регистры 19 и 20 результатов умножения - 8То. С целью

3

упрощения описания работы обозначим, что режиму Пропуск операндов с,оот- ветствует од 00, по режиму Вычи- .такие - код 01, режиму Суммирование - код 10, режиму Считыва- ние из блоков регистров 25, 26 - на входе управления считыванием, режиму записи - код 1 на входе управления записью, приему в регистры 19 и 20 по первому входу соответствует 4 О, а приему по второму входу - код 1 на входе управления. В исходном положении счетчик импульсов 51 находится в нулевом состоянии, исходный операнд () записан в регистры 3 и 4; в регистры 7 и 8 записаны соответственно весовые коэффициенты Re vy , 3m W так как на управляющих входах 15 и 16 сумматора 9 могут присут- ствовать только два значения управления 00, 01, а на управляющих входах 17 и 18 сумматора 10 - только коды 00 и 10, т.о на управляющие входы 15 и 18 можно подать постоян- ный нулевой уровень.

Арифметическое устройство работает следующим образом.

В исходном положении счетчик им- пульсов 51 находится в состоянии ОООрОО. Операнды Reaj (О ,ReWj , JmWj записаны соответственно в регистры 3, 4, 7 и 8, в умножителях 5 и 6 начинается процесс вычисления произведений Re а J () ReW - ,Rea j (О «HmV/ соответственно.

Б первом такте (состояние чика импульсов 51 - 000001) в умножителях 5 и 6 продолжают вычисляться значения Re а- (O ReWj ) Jm W- , которые затем проходят через сумматоры 9 и 10 на входы регистров 11 и 12 соответственно. На управляющих входах сумматоров 9 и 10 присутствует, кад 00.

Во втором такте (состояние счетчика импульсов 51 - 000010) отрицательным перепадом с выхода нулевого (младшего) разряда счетчика им- пульсов 51 выполняется прием входных операндов Jmoj (i) в регистры 3 и 4, RewV- в регистр 7,3mW - в регистр 8 Положительным перепадом с выхода 1-го разряда счетчика импульсов 51 вьшолняется ,прием Rea (i ) Re W и Reaj (i ) JrnWj соответственно в регистры 11 и 12. В умножителях 5 и 6 на- .

5 0 5

о

0

5

0

5

750

чинают вычисляться произведения arr,ai(;)-arTiwi,Jmoii(i) ReW . .

В третьем такте (состояние счетчика импульсов 51 - 000011) вычисленные в умножителях 5 и 6 произведения 3waj (i )-3mW ,Jmaj (i ) ReWj поступают на первый вход сумматоров

9и 10 соответственно, на вторых входах сумматоров 9 и 10 присутствуют значения Re п (i)-ReWj ,Rec( (i) JmW. В Сумматоре 9 вычисляется действительная часть комплексного . произведения ReA (i)Reaj (O ReW -. - fTiOj (i ) 3m W j- (на управляющих входах 15 и 16 код 01), а в сумматоре

10- мнимая часть комплексного произведения 3т А j (О Reaj ()-3, +

+ maj (i)-ReW - (на управляющих входах 17 и 18 код 10).ReA (О иЗгчА СО поступают на вход регистров 19 и 20 соответственно.

В четвертом такте (состоя;ние счетчика импульсов 51 - 000100) отрицательным перепадом с вькода 0-го разряда счетчика импульсов 51 вьшолняется прием Rea: (i-t-1) , 3mAj(i+1) ,Jm W j соответственно в регистры 3, 4, 7 и 8, и 9 умножителях 5 и 6 вычисляются произведения RpA; (i+O Re ,ReAj (i -i-DamW - ; BO втором полутакте этого такта операнды Re А () иДтА(1) отрицательным перепадом, который поступает на управляющий вход 31 из йостоянного запоминающего устройства 52, принимаются в регистры 19 и 20 соответственно, на управляющем входе 32 .присутствует код 10 и,.пройдя через сумматоры 23 и 24 (на управляющих входах 27-30 код 00) , поступает на вход блока регистров 25 и 26 соответственно.

В пятом такте (состояние счетчика импульсов 51 (000101) в умножителях 5 и 6 вычисляются произведения Reaj(i+1)ReVi/ . , Re flj (i+1)-3n.wy , которые затем проходят через сумматоры 9 и 10 (на управляющих входах 15-18 код 00) на входы регистров 11 и 12 соответственно. Во втором полутакте этого такта значения Re А- (О и О m Аj(i) записываются, например, в регистры 25.1 и 26.1 соответственно, на управляющем входе 33 код 1. В шестом такте (состояние счетчика импульсов 51 - 000110) выпол няется приемЗта (J+1),3ni wV , соответственно в регистры 3, 4,7 и 8, в умножителях 5 и 6

ВЫЧИСЛЯЮТСЯ произведения3m О: (i+1)« DmW l ,3maj (i+i) ; положи- i тельным перепадом с выхода 1-го разряда счетчика импульсов 51 выполни j ется прием Reaj (i + 1)-ReW - . + D JmW j в регистры 11 и 12 соответственно; во втором полутакте ReAj (i) записываются в регистры 25.3 и 26.3 соответственно, на уп- 10 равляющем входе 35 код 1.

В седьмом такте (состояние счетчика импульсов 51 - 000111 в умножителях 5 и 6 вычисляются произведения tJmaj (; +1) От ,3m Oj (t+1)« 15 , которые затем поступают на первые входы сумматоров 9 и 10, на вторых входах сумматоров 9 и 10 присутствуют значения Rea: (i +1) ,Re(Xj (i+D JmW , В сумма- 20 торе 9 вычисляются ReA (;+1) Reaj- (i+1) -JmQj(i+1) (на управляющих входах 15 и 16 код 01); в сумматоре 10 - Reaj (i+1 ) Jm W , + + 3rn oij (J+1). Re w Y (на управляющих 25

входах 17 и 18 код 01).ReAj-(i+1) и

JmA:(i+1) поступают на вход регистров 19 и 20 соответственно. Во вто,ром полутакте этого такта операнды ReAj(O и 3 m (О, записанные ранее зо в регистры 19 и 20, записываются в

регистры 25.2 и 26.2 соответственно, на управляющем входе 34 код 1 .

В восьмом такте (состояние счетчика импульсов 51 - 001000) выполняется прием Re а (j+2)-, ReWy , tlmW соответственно в регистры 3, 4. 7 и 8, в умножителях 5 и 6 вычисляются произведения Re а j (|+2)

Rew / ,.Reaj (i+2)-Jm во вто- ром полутакте операнды ReAj(O и 3mAj(i), присутствующие на входе блоков регистров 25 и 26, записыва- ются в регистры 25.4 и 26.4 соответственно, на управляющем входе 36 , код .1. Отрицательным перепадом, поступающим из постоянного запоминающего устройства 52 на управляющий вход 31, выполняется прием ReA: (i) и DrnAjCi) соответственно в регистры 50 19 и 20, на управляющий вход 32 поступает код 0. Операнды ReA: (+1) иЗтА(1+1) проходят через сумматоры 23 и 24 (на управляющих входах 27-30 код 00) и поступают на вход блоков 55 регистров 25 и 26.

Из приведенного описания видно, что в каждом 4 k -ом такте во втором i

полутакте выполняется прием результатов комплексного умножения ReA:(i+k) 3niA(i+k) по первому входу в регистры 19 и 20 соответственно. Поэтому в дальнейшем описании работы арифметического устройства порядок вычисления комплексных произведений рассматриваться не будет.

В девятом такте (состояние счетчика импульсов 51 - 001001) в первом полутакте выполняется считывание ReA j(i) nCImAj(i) соответственно из регистров 25.1 и 26.1 (на управляющем входе 41 код 1) и в сумматорах 23 и 24 вычисляются ReAj(i) + ReAj (i+1),3m Aj (i) +3mAj(J+1) (на управляющих входах 27 и 28 код 10, на управляющих входах 29 и 30 код 10); во втором полутакте в регистры 25.1 и 26.1 записываются значения Re Aj(i)+ReAj(i+1), Jm Aj (i )+JmAj(i ) соответственно (на управляющем входе

33 код 1). I

В десятом такте (состояние счетчика импульсов 51 - 001010) в первом полутакте выполняется считы- .вание из регистров 25.3 и 26.3 (на управляющем входе 43 код 1) и вычисление в сумматорах 23 и 24 выра :ений ReA-(;)-ReAj(i4-1),3r) AJ (i)-3mAj( ) (на управляющих входах 27 и 28 код 01, на управляющих входах 29 и 30 - .01); на втором полутакте выполняется запись этих значений в регистры 25.3 и 26.3 (на управляющем входе 36 код 1).

В одиннадцатом такте (состояние :счетчика импульсов 51 - 001011) выполняется в первом полутакте прием в регистр 19 значения Зт А(i+1) по второму входу, прием в регистр 20 значения Re А (i+1) по второму входу, для этого на управляющий вход 31 поступает отрицательный перепад с выхода постоянного запоминающего устройства 52, а на управляющий вход 32 - единичное значение, кроме этого в первом полутакте выполняется считывание из регистров 25.2 и 26.2 операндов Re Aj(t) H3mA;(i), вычисление выражений Re A (i)-3mAj(i+1) на сумматоре 23 (на управлякмцих входах 27 и 28 код 01) и выраженияЗтАj (i) + ReAj(i+1) на сумматоре 24 (на управляющих входах 29 и 30 код 10); во втором полутакте результаты вычислений записываются соответственно в

7

регистры 25.2 и 26.2 (на управляющем входе 34 код 1).

В двенадцатом такте (состояние им .пульсов 51 - 001100) в первом полутакте происходит считывание из регистров 25.4 и 26,4 соответственно операндов Reft; (О иЗтД; (Г), вычисление на сумматорах 23 и 24 выраже- нийЯеА(1) H-3mAj (i+1),DmAj (О- -ReA-(i+1), во втором полута.кте - запись этих результатов соответственно в регистры 25.4 и 26.4 (на управляющем взводе 36 - код 1), прием в регистры 19 и 20 операндов Re Аj (i+2) 3mA(i+2) соответственно.

В тринадцатом такте (состояние счетчика импульсов 51 - 001101)в первом полутакте происходит считывание из регистров 25.1 и 26.1 операндов Re Aj (i )+ReAj (i +1) (|) + +3rnAj (i+1), вычисление Re A j (i ) + + ReAj (i+.1) + ReA (i+2) в сумматоре 23 +3tnAj(V + t) +3mAj(U2) в сумматоре 24, во втором полутакте запись полученньрс результатов в ре- гистры 25.1 и 26.1 соответственно.

В четырнадцатом такте (состояние счетчика импульсов 51 - 001110) в первом полутакте происходит считывание из регистров 25.3 и 26.3 операн- довРеА, (i)-ReAj (i+1) H3mA(i) - -Згу Aj (i+1) , вычисление Re A j (1 ) - -ReAj (i+1) +ReAj (i+2) в сумматоре 23 иЗтА(1) -DmAj(;+1) +3mAj(i+2) в сумматоре 24, во втором полупериоде - запись полученных результатов в регистры 25.3 и 26.3 соответственно.

В пятнадцатом такте (состояние счетчика импульсов 51 - 001111)

В первом полутакте происходит считывание из регистров 25.2 и 26.2 операндов Re AJ (О -3т А (i + 1) и (i) +ReAj (i+1), вычисление Re Aj ( ) -3m A j (V+1) - Re Aj ( +2) в . сумматоре 23 иЛтА;(1) +ReAj (i+1) - (1+2) в сумматоре 24, во втором полутакте - запись полученных результатов в регистры 25.2 и 26.2 соответственно.

В шестнадцатом такте (состояние счетчика импульсов 51 - 010000) в первом полутакте происходит считывание из регистров 25..4 и 26.4 операндов ReA ( i ) + 3mAj(i+1) иЗтА(1) - -ReAj (1+1) вычисление Re А j (i) + +3mAj (i+1) -ReAj (i+2) в сумматоре 23 иЗтА (i) -ReA- (j+1) -3mAj(i+2) в сумматоре 24, во втором полутак

8

0 5

о

.

0

0 5

5

те - запись полученных результатов в регистры 25.4 и 26.4 соответственно, прием в регистры 19 и 20 соответственно Re А; (i +3) иЗmA;(i+3) по первому входу.

В семнадцатом такте (состояние счетчика импульсов 51 - 010001) в первом полутакте происходит считывание из регистров 25.1 и 26.1 ReA3(i) +ReA)(;+1) +ReAj (i+2) и JmAj(i) +3mAj(i+1) +3mAj(;+2), вычиcлeниeReX (O ReA(i) + + ReA; (i+1) +ReA- (i+2) +ReAj (i+3) 3

иОтХ(О 21 0m A: (i+k) соответ- o

ственно на сумматорах 23 и 24, во втором полутакте запись полученных результатов в регистры 25.1 и 26.1.

В восемнадцатом такте (состояние счетчика импульсов 51 - 010010) аналогичным образом вычисляются значения Re X (i+t) иЗтХ.(1+1) и записываются в регистры 25.3 и 26.3 соответственно.

В девятнадцатом такте (состояние счетчика импульсов 51 - 010011) в первом полутакте выполняется прием в регистр 19 операндаЗтA;(i+3) по второму входу и прием в регистр 20 операнда Re А j ( i+3) по второму входу, кроме того,в первом полутакте выпол- .няется считывание из регистров 25.2 и 26.2 операндов Re А j (О-Згп AJ (i+1 )- -ReAj(i+2) иЗт Aj (O+fteAj (i+1) - -3mA:(i+2)., вычисление результатов Rex(i+1) ReAj (i)-3mA:(;+1) - -ReAj (i+2) +ReA (i+1) -:)mAj(i+3) и 3mX(i+1) 3mAj(i) .+ ReAi (i+1) - -3mAj(i+2) -ReAj (i+3) соответственно в сумматорах 23 и 24, во втором полутакте - запись полученных результатов в регистры 25.2 и 26.2 соответственно.

В двадцатом такте (состояние счетчика импульсов 51 - 010100) вычисляются аналогичным образом последние результаты базовой операции ReXj(i+3) иЗтХ-(+3) и во втором полутакте этого, такта в регистры 19 и 20 принимаются операнды ReAj(i) и 3mAjt,(i) второй базовой операции.

Вычисление результатов Re Xj, (i) ReXj4, (i+1),ReXi4, (i+2) , ReX j,, (i+3) ,

amXi.,(;),3mXj,, (i+1),3niXj (J+2), 3mXj,(i+3) выполняется аналогично описанным тактам с той лишь разницей, что для вычислений используются регистры 25.5-25.8; 26.5-26.8 соответственно. Считывание результатов первой базовой операции выполняется в каждом втором полутакте 21, 15, 29, 33 тактов, а считывание результатов второй базовой операции в каждом втором полутакте 37, 41, 45 и 49 тактов и т.д. Таким образом, цикл работы устройства образуют 32 такта. Прошивка запоминающего устройства 52 должна быть выполнена в соответствии с этими значениями.

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

X(;)RetA (O+A( + 1)+A(l+2) + +A(i+3)+ (i)+A(i+1) + + A(;+2).+ A(V+3)J , (1)

x(i+1) (i)+A(i+1)-A(;+2) +

+ A(i+3)l+j (i) + A(i+1)- -A(i+2)-A(;+3)J , (2)

X(+2) (i)-A(i + 1)+ A(i+2)-A(U3)+jJtn A(i)-A(i+1) + -bAG+2)-A(;+3) , (3)

)f(i+3) (;)-A(;+1)-A(i+2) + +A(;+3)-bjam A(i)-A(i+1)- -A(U2) + A(+3), (4)

211750 0

где A (, ) , A (; +1) , A (i 2) , A (i +3) - соответствующие произведения исходных данных на поворачивающие множители W

w -,

W

К,-Х;

w

0

Вычисление значений Re А (i+k) и 3mA(i+k) (, ..., 3) на данной структуре выполняется аналогично рассмотренному алгоритму, отличие двух базовых операций (1) и (4) состоит в знаках арифметических операций при

формировании окончательных результатов ReX Cij;k) ,т )( (i+k). Как видно из

выражения (4) действительные части 5 конечньк результатов ReX (t+k) формируются только из действительных частей, а мнимые 3tn X (i + k) - только из мнимых частей результатов комплексного произведения Re А (i+k), Зт А (i+k), следовательно при реализации выражений (4) связи с выхода регистра 10 на вход :регистра 19 и с выхода регистра 19 на вход регистра 20 не используются.

Следовательно, работа арифметического устройства при вычислении базовой операции алгоритма дв5псмер- ного дискретного преобразования Фурье по основанию 2 отличается от вычислений базовой операции по основанию 4 алгоритма быстрого преобразования Фурье только значениями на управляющих входах 31, 32, 27, 28,

29, 30.. :

0

5

0

f

/J

r

3/

J2

1

Г19Л

( 1 /31

33-W

g I

ф1/.1

Составитель А. Баранов Редактор Т. Парфенова Техред А.Бабинец Корректор М. Демчик

Заказ 642/54

Тираж 673

БНИШИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Подписное