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

 

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

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

РЕСПУБЛИК (19) (11) (51) 4 G 06 F 15/332

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (ОПИСАНИЕ ИЗОБРЕТЕНИЯ /"

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ Дфъ р. „-, (21) 3766249/24-24 (22) 03.07.84 (46) 15.02.86. Бюл. ¹ 6 (71) Киевский ордена Ленина политехнический институт им.50-летия Великой

Октябрьской социалистической революции (72) Ю.Н.Виноградов, Ю.С.Каневский, И.П.Краснощеков, Н.Е.Куц, В.И.Лозинский и Б.А.Некрасов (53) 681.32(088.8) (56) Авторское свидетельство СССР № 467356, кл. G 06 F 15/332, 1974.

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

¹ 999061, кл. G 06 F 15/332, 1982. (54)(57) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО

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

Ф.

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

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

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

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

Фурье; на фиг. 2 — пример реализации блока управления.

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

33-40 являются управляющими входами записи, а управляющие входы 41-48— управляющими входами считывания блоков регистров 25 и 26.

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

45 постоянного запоминающего устройства 52, выходы разрядов, счетчика импульсов 51 соединены с адресными входами постоянного запоминающего устройства 52, выход 0-ro разряда счетчика импульсов 51 является входом управления 13, выход 1-ro разряда счетчика импульсов 51 является входом управления 14, первый выход постоянного запоминающего устройства 52 является управляющим входом

16, второй выход является управляющим входом 17, третий и четвертый выходы являются управляющими входами

27 и 28, пятый и шестой выходы— управляющими входами 29 и 30, седьмой и восьмой — управляющими входами

31 и 32, с девятого по шестнадцатый— управляющими входами записи 33-40, с семнадцатого по двадцать четвертый — управляющими входами считывания

41-48, управляющий вход арифметического устройства является входом управления режимом работы блока управления 49.

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

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

Re a (i), 3m а (1, R e а (+ 11, 3 m а (1м ) еа(н2), Зт а(м2), Rea(ia), Jm a (i+a), период синхроимпульсов с выхода генератора импульсов 50 Т, и его скважность E = †. Период То равен такту

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

1211750 4 упрощения описания работы обозначим, что режиму "Пропуск операндов" соответствует.код 100!, по режиму Вычитание" — код "01", режиму "Суммирование — код "10", режиму "Считывание" из блоков регистров 25, 26— код -"1" на входе управления считыва" кием, режиму записи — код "1" на входе управления записью, приему в регистры 19 и 20 по первому входу

1 соответствует 4 "0", а приему по второму входу — код "1" на входе управления. В исходном положении счетчик импульсов 51 находится в нулевом состоянии, исходный операнд

Реа(!) записан в регистры 3 и 4; в регистры 7 и 8 записаны соответственно весовые коэффициенты Re W

3!!! М!, так как на управляющих входах

15 и 16 сумматора 9 могут присутствовать только два значения управления 00, 01, а на управляющих входах 17 и 18 сумматора 10 — только коды "00" и "10", то на управляющие входы 15 и 18 можно подать постоянный нулевой уровень.

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

В исходном положении счетчик импульсов 51 находится в состоянии

"000000". Операнды Rеа, (i),Re W, 0 э 3 э

ЛщМ записаны соответственно в ре4 гистры 3, 4, 7 и 8, в умножителях

5 и 6 начинается процесс вычисления произведений Re a, (i ) Re Vr, Re а (! )"

«Jm Ф . соответственно.

В первом такте (состояние счетчика импульсов 51 — "000001") в умножителях 5 и 6 продолжают вычис" ляться значения Re a (; ) Re w,Rea (! )"

J J

«Д!!! W. которые затем проходят через сумматоры 9 и 10 на входы регистров

11 и 12 соответственно. На управляющих входах сумматоров 9 и 10 присутствует. код "00".

Во втором такте (состояние счетчика импульсов 51 — "000010") отрицательным перепадом с выхода нулевого (младшего) разряда счетчика импульсов 51 выполняется прием входных операндов 3m o (!) в регистры 3 и 4, Re W . — в регистр 7,3уп1Ю ° — в регистр 8.

Положительным перепадом с выхода

1-го разряда счетчика импульсов 51 выполняется прием Re а (i ). Re W u

3,)

Ееа (i) 1«пW соответственно в регист1 ры 11 и 12. В умножителях 5 и 6 на5

20.поступают на вход регистров 19 и 20

I чинают вычисляться произведения а а;() 3 w,,Лтa;(;) Rew ; .

В третьем такте (состояние счетчика импульсов 51 — "000011") вычисленные в умножителях 5 и 6 произведениямиm а; (! ) Зпа,!ма (! ) Rew ; поступают на первый вход сумматоров

9 и 10 соответственно, на вторых входах сумматоров 9 и 10 присутствуют значения Re а ° (! ) R е Ф, Re а (i )"

«3тМ . В Сумматоре 9 вычисляется

J действительная часть комплексного, произведения Re А; (1)=йеа (i) ReW — .

-3!!а; (i) ° 3тл W; (на управляющих входах 15 и 16 код 01), а в сумматоре

10 — мнимая часть комплексного произведения 3m А (i ) =Реа ° (i) 1«т!Ф.+

+3mа; (i).Rew,. (на управляющих входах

17 и 18 код 10) . Re А; (i) и 3m AJ(i) соответственно.

В четвертом такте (состояние счетчика импульсов 51 - "000100") отрицательным перепадом с выхода

0-го разряда счетчика импульсов 51 выполняется прием R е а (! +1), it!

Jt!!A (!+1),3!«!Ъ . соответственно в .1 регистры 3, 4, 7 и 8, и в умножителях 5 и 6 вычисляются произведения

Rp4; (i+1) Re w".,Яе А 1, i +1)3mW"во втором полутакте этого такта операнды Re А (i ) и 3!t!4 (i) отрицательным перепадом, который поступает на управляющий вход 31 из постоянного запоминающего устройства 52, принимаются в регистры 19 и 20 соответственно, на управляющем входе 32 присутствует код 10 и,.пройдя через сумматоры 23 и 24 (на управляющих входах 27-30 код 00), поступает на вход блока регистров 25 и 26 соответственно.

В пятом такте (состояние счетчика импульсов 51 (000101") в умножителях 5 и 6 вычисляются произведения

ReaJ (i+1) Re W ., 1!е а (i+1) Jtt!W " ъ 1 4 которые затем проходят через сумматоры 9 и 10 (на управляющих входах

15-18 код 00) на входы регистров 11 и 12 соответственно ° Во втором полутакте этого такта значения Re A ° (i)

4 иЗ!«! А (i) записываются, например, в регйстры 25.1 и 26.1 соответственно, на управляющем входе 33 код 1.

В шестом такте (состояние счетчика импульсов 51 — "000110") выпал няется приемЗ!и а ° (!+1),3п! w . t!

Re W . соответственно в регистры

3, 4, 7 и 8, в умножителях 5 и 6

1211750 . вычисляются произведения3та (»+1)

"3m W ;, 3Ф a; (» +1) Re W; пеложительным перепадом с выхода 1-го разряда счетчика импульсов 51 выполня"

5 ется прием Rea; (i+1) Re@I,Reà. (i+1)

»»»

"3rnYl в регистры 11 и 12 соответственно; во втором полутакте ReA (i) и3м A (i) записываются в регистры

25.3 и 26.3 соответственно, на уп-: 10 равляющем входе 35 код 1.

В седьмом такте (состояние счетчика импульсов 51 — "000111" в умножителях 5 и 6 вычисляются произведения а (»+1) д пW",Jm а; (»+1) 15

ReW". которые затем поступают. на первые входы сумматоров 9 и 10, на .вторых входах сумматоров 9 и 10 присутствуют значения Rea (i +1)r

»»1

"Re W ", еа (»+1) )»»»щ ;» . В сумма- 20 торе 9 вычисляются Re 4 (+1)

= Reа- (i+1) Re YV ." — corno (»+1) (на

1 3 3 управляющих входах 15 и 16 код 01); в сумматоре 10 — Rea; (i+1) 3»» а" +

+3m aj (» +1) ° Rp W ;" (на управляющих 25 входах 17 и 18 код 01) . Re Д (i+1) и

1, DrnA (i+1) поступают на вход регистров 19 и 20 соответственно. Во вто,ром полутакте этого такта операнды йе А () и Л»», А (») записанные ранее 3О

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

В восьмом такте (состояние счетчика импульсов 51 — "001000") выполняется прием Веа; (» +2),Re W -"

»»2

Ъ .»»»Ф . соответственно в регистры

1.

3, 4, 7 и 8, в умножителях 5 и 6 вычисляются произведения 1е a, (+2)x

"ReW .",.Reа (i+2) 3m 4" во вто- 40 ром полутакте операнды Re А (i) и

3rnAj(i), присутствующие на входе блоков регистров 25 и 26, записыва. ются в регистры 25.4 и 26.4 соответственно, на управляющем входе 36 код 1. Отрицательным перепадом, поступающим из постоянного запоминающего устройства 52 на управляющий вход 31, выполняется прием КеА. (i) и

3m Я (») соответственно в регистры

19 и 20, на управляющий вход 32 поступает код О. Операнды Re A (i+1) и 3»»»А;(i +1) проходят через сумматоры

23 и 24 (на управляющих входах 27-30 код 00) и поступают на вход блоков М регистров 25 и 26.

Из приведенного описания видно, что в каждом 4 k -ом такте во втором полутакте выполняется прием результатов комплексного умножения Re 4 (i +k), мА (»+1) по первому входу в регистры 19 и 20 соответственно. Поэтому в дальнейшем описании работы арифметического устройства порядок вычисления комплексных произведений рассматриваться не будет.

В девятом такте (состояние счетчика импульсов 51 — "001001") в первом полутакте выполняется считывание е A»(i) и 3m A (i) соответственно из регистров 25.1 и 26.1 (на управляющем входе 41 код 1) и в сумматорах 23 и 24 вычисляются Re 4 (») +

КеА (i+1),3m А; (i) + 3rnAj (i+1) (на управляющих входах 27 и 28 код 10, на управляющих входах 29 и 30 код

10); во втором полутакте в регистры 25.1 и 26.1 записываются значения

Re A (i )+ ReА; (i+1), 3»»» А (» )+3mß(i+1) соответственно (на управляющем входе

33 код 1). (В десятом такте (состояние счетчика импульсов 51 — "001010") в первом полутакте выполняется считывание из регистров 25.3 и 26.3 (на управляющем входе 43 код 1) и вычисление в сумматорах 23 и 24 выражений

Ке А ° (» ) — Re А (» +1),Дщ А (i )-3rnAj(i ) (на управляющих входах 27 и 28 код

01, на управляющих входах 29 и 30— ,О1); на втором полутакте выполняется запись этих значений в регистры

25.3 и 26.3 (на управляющем входе

36 код 1) .

В одиннадцатом такте (состояние

,.счетчика импульсов 51 — "001011") выполняется в первом полутакте прием в регистр 1.9 значения 3в4 (»+1) по второму входу, прием в регистр 20 значения йе А (i+1) по второму входу, для этого на управляющий вход 31 поступает отрицательный перепад с выхода постоянного запоминающего устройства 52, а на управляющий вход

32 — единичное значение, кроме этого, в первом полутакте выполняется считывание из регистров 25.2 и 26.2 операндов Re Д (r) и 3m Я.(»), вычисление выражений Re Я (i)-3mA (i+1) на

3 4 сумматоре 23 (на управляющих входах

27 и 28 код 01) и выражения 5т Д (» ) +

Rehj (»+1) на сумматоре 24 (на управляющих входах 29 и 30 код 10); во втором полутакте результаты вычислений записываются соответственно в

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

В двенадцатом такте (состояние им.пульсов 51 — "001100") в первом полутакте происходит считывание из регистров 25.4 и 26,4 соответственно операндов ReА (i) и 3mA> (i), вычисление на сумматорах 23 и 24 выражений Reд; (1) +3mA> (i+1),3mÀ; (i)—

-ReA (i+1), во втором полутакте— запись этих результатов соответственно в регистры 25.4 и 26.4 (на управляющем входе 36 — код 1), прием в регистры 19 и 20 операндов8е А> 6+2), Drn A> ii +2) соответственно.

В тринадцатом такте (состояние счетчика импульсов 51 — "001101") в первом полутакте происходит считывание из регистров 25.1 и 26.1 операндов Re Aj (i )+ ReAj (i +1) и Лгд A j (1) +

+3m A (i +1), вычисление Re А; (i ) +

+ Re А; (i +,1) + R е А (i +2) в сумматоре

23 и 3m А.(i) +3щ А (i+1) + Jm А (1+2) в сумматоре 24, во втором полутакте— запись полученных результатов в регистры 25.1 и 26.1 соответственно.

В четырнадцатом такте (состояние счетчика импульсов 51 — "001110") в первом полутакте происходит считывание из регистров 25.3 и 26.3 операндов йе А (i) — Re Aj (i+1) и Зтн А (i)

- JrnА (i+1), вычисление Re À ()

-Re А. (i+1) + Re А (i+2) в сумматоре

23 и 3 rn А (i ) — Зт А (i +1) +3m А. (i +2) в сумматоре 24, во втором полупериоде — запись полученных результатов в регистры 25.3 и 26.3 соответственно.

В пятнадцатом такте (состояние счетчика импульсов 51 — "001111") в первом полутакте происходит считывание из регистров 25.2 и 26.2 операндов 1е А (i) — Jm А (i+1) и

Д р А (i ) + Re А (i +1), вычисление йе А () -3m А1 (4+1) — Re А (i +2) в . сумматоре 23 и 3rnA; (i) + Яе Aj (i+1)

- JmA> (1+2) в сумматоре 24, во втором полутакте — запись полученных результатов в регистры 25.2 и 26.2 соответственно.

В шестнадцатом такте (состояние счетчика импульсов 51 — "010000") в первом полутакте происходит считывание из регистров 25..4 и 26.4 операндов ReA; (i) +Лап Я;(+1) иЗт Aj (1)—

-ИеА (i+1), вычисление Re A; (i) +

+Ъп А> (i+1) — Ке А (i+2) в сумматоре

23 и За А (1) - Re А (i+1) -Эт А (+2)

3 3 в сумматоре 24, во втором полутак

211750 8

45 В двадцатом такте (состояние счетчика импульсов 5.1 — 010100") вычисляются аналогичным образом пос-. ледние результаты базовой операции

Re Х (i +3) и Дт X j (1+3) и во втором

50 полутакте этого такта в регистры 19 и 20.принимаются операнды Re Aj,,(i) и

3 A;„ (i ) второй базовой операции.

Вычисление результатов Re Х „(i ), Яе X>„(i +1), Re Х;, 0+2), Re ;Ä (i +3), Зщх „(1),3 т х,, (1+1),3 х (+2), Jmx ° (i+3) выйолняется аналогично

}и описанным тактам с той лишь разницей, что для вычислений используются ре5

15 те — запись полученных результатов в регистры 25.4 и 26.4 соответственно, прием в регистры 19 и 20 соответственно Re А (i +3) и 3m A (i +3) по

1 первому входу.

В семнадцатом такте (состояние счетчика импульсов 51 — "010001") в первом полутзкте происходит считывание из регистров 25.1 и 26.1 йеА (i) + Re A>(i+1) + Re A> (+2) и

3rnA) (i) +3rnA) (i+1) +Да) А) (i+2), вычислениеReХ (1) = Re А> (i) +

+йеА (i+1) + КеА (i+2) + ReAj 0+3) э иДщ Х() =,. Дщ А (i+k) соответк=о

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

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

В девятнадцатом такте (состояние счетчика импульсов 51 — "010011") в первом полутакте выполняется прием в регистр 19 onepaapa3mAj(i+3) по второму входу и прием в регистр 20 операндайеА (+3) по второму входу, кроме того,в первом полутакте выпол,няется считывание из регистров 25.2 и 26.2 операндов Re А (i)-3m Aj (i+1)— ReAj(i+2) иЗа А; (1)+ ЙеА (i+1) — >rnA>(i4.2), вычисление результатов

Йех(;+1) = Re A (i)-3mA (i+1)

3 — Re A> (1+2) + Re 4> (i+1) 3mAj(i+3) и

ЭаХ(+1) =Зпз А (i) +- Re A> (i+1)

-Лье Aj(;+2) — Re А (1+3) соответствен" но в сумматорах 23 и 24, во втором полутакте — запись полученных результатов в. регистры 25.2 и 26.2 соответственно.

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

Для реализации вычислений двумерного дискретного преобразования

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

X(l)= Re(A (i)+A(i+1)+A(i+2)+

+А(+3)1+ 3 (А()+А(1+1)+

+ А(i +2)+ А (i+3)), (1)

x(i +1) = Re (А (i )+А(+1) -А(! +2)+

+A(i+3))+ j За(А (1)+A(i+1)—

-А (i +2) — А(1+3)j, (2)

X(i+2)= Не(А (1)-A(i+1)+ A (i+2)-А(+3Ц+ з 1А (1)-A(i+1)+

+A(i+2)-A(i +3)), (3) х (1+3) = Яе (А (i ) À(i+1)-А(1+2)+

+А(1+3)l + 1 Лш(4(1 ) -А (+1)

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

Вычисление зйачений Re А (i+k) и

ЗтА(1+ ) (k = 0 3) на данной структуре выполняется аналогично рассмотренному алгоритму, отличие

10 двух базовых операций (1) и (4) состоит в знаках арифметических операций при

4 формировании окончательных результатов

Re)c (+k),J Х (1". ) . Как видно из выражения (4) действительные части

1 конечных результатов Re Х (i + k) формируются только из действительных частей, а мнимые 3m g (i+k) — только из мнимых частей результатов комплексного произведения Re А (i + ), 20 3т А (i+k), следовательно при реализации выражений (4) связи с выхода регистра 10 на вход регистра 19 и с выхода регистра 19 на вход регистра 20 не используются.

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

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

$211750

1211750

Заказ 642/54

Тираж 673

Подписное

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

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

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

Составитель А. Баранов

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