Устройство для умножения комплексных чисел в модулярной системе счисления Советский патент 1990 года по МПК G06F7/72 

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

Цель изобретения - расширение области применения за счет получения произведения в позиционном коде.

На фиг.I и 2 представлена схема устройства для умножения комплексных чисел в модулярной системе счисления.

Устройство для умножения комплексных чисел в модулярной системе счисления содержит тактовый вход .1 устройства, первую группу информацион- входов 2.1-2.k устройства, вторую группу информационных входов 3.1-3.k устройства, где k - число основных модулей системы счисления, вход 4 номера константы устройства.

СП оо | сд

со

31

блок 5 формирования дополнительного кода по модулям системы счисления, первый блок 6i групп мультиплексоров, первый и второй входные регистры 7 и 8, второй блок 9 групп мультиплексоров, элемент 10 задержки, группу блоков 11.1-ll.k памяти для хранения констант, первый и второй блоки 12 и 13 вычисления интервального индекса числа, блок 14 суммирования вычетов по вспомогательному модулю, группу блоков 15.1-15.п суммирования вычетов по модулю р, сумматор 16 по вспомогательному модулю, первую груп пу сумматоров 17.1-17,п по модулю р, первьш вспомогательный регистр 18, счетчик 19 по вспомогательному моду

лю, первую группу счетчиков 20.1- . 20.П-1 по модулю р, триггер 21, груп- 20 пу вспомогательных регистров 22.1- 22.п, второй вспомогательный регистр 23, вторую группу сумматоров 24.1- 24.п по модулю р, блбк 25 Лормирова74

Блок ll.i памяти д (i 1.2,...,k) облад 2 Jfi g2 ;Cf Et)j,LCj,,i5B р (I , + ку блока ll.i памяти 2:i« V -t . у. :, вается набор констант

V;(xi,y;,l) .y;, 1)7

(oiI

где R; (x;,y-,l)

i « k;

.(0

/x;Mr;.,|m;.w + /y;M:;.,/m;W

m;

(1)

(1

R; (x;, y; , I),... R; (x;, x; , 1) ния переносов, вторую группу счетчиков 26.1-26.П по модулю р, группу выходов 27.1-27.п устройства.

Блок 5 формирования дополнительного кода по модулям системы счисления, элемент 10 задержки, блоки 12

и 13 вычисления интервального индекса числа, блоки 6.и 8 групп мультиплексоров и блок 14 суммирования вычетов по дополнительному модулю реализованы и функционируют идентично, известным.

Блок ll.i памяти для хранения (i 1.2,...,k) обладает емкостью 2 Jfi g2 ;Cf Et)j,LCj,,i5B разрядностью (I , + ) бит. В ячейку блока ll.i памяти с адресом х; + 2:i« V -t . у. :, . записы- вается набор констант

V;(xi,y;,l) (x;,y;,l),..., .y;, 1)7,

m;

(1)

Изобретение относится к вычислительной технике и может быть использовано в процессорах быстрого преобразования Фурье, функционирующих как в модулярных, так и в позиционных системах счисления, для умножения комплексных чисел на поворачивающие множители, а также для получения последних. Целью изобретения является расширение области применения за счет получения произведения в позиционном коде. Для этого в устройство, содержащее блок формирования дополнительного кода по модулям системы счисления, блоки групп мультиплексоров, входные регистры, элемент задержки, группу блоков памяти для хранения констант, блоки вычисления интервального индекса числа, блок суммирования вычетов по вспомогательному модулю, сумматор по вспомогательному модулю, первый вспомогательный регистр и группу вспомогательных регистров, введены группа блоков суммирования вычетов по модулю P, две группы сумматоров по модулю P, счетчик по вспомогательному модулю, две группы счетчиков по модулю P, второй вспомогательный регистр, триггер и блок формирования переносов с соответствующими связями. 2 ил.

цифры, p-ro представления числа Г-1. r/2xHikJsiWll.lziMljs Js W l

L o L ,

i i k;

(2)

. УК. /l W + I -w /m.j

(3)

.УК.);..., ,,у,,1) - цифры р-го представления числа

-.(l .).(4)

х, если х Шд

Хц- т, если

Уц, если у то j

УК- т, если т„;

- величины, подаваемые

соответственно на первый, второй и третий адресные входы блока ll.i памяти;

5

0

5

х-,,1...1п; -1, . If (0,1,..., L - 1,

W и W - целые числа из диапазона D модулярной системы счисления, определяющие соответственно действительную и мнимую часть 1-й из используемых в устройстве комплексных констант;m,m, .. .m - основания модулярной

системы счисления, явг ляющиеся попарно прост тыми числами; - вспомогательный модуль выбираемый из условий

m

50

k - 2, - 1;

к-1 Л ni;5 J.I J

L - максимальное число комплексных констант, на которое рассчитано устройство.

Блок 15.i(i 1,2,...,п-1) суммирования вычетов по модулю р осущест

1587503

вляет сложение за Т тактовблока ll.i () памяти для хранения

-J Z.

наборов нз (k-1), вычетов по модулю р (р 2, - натуральное число, ) с формированием числа переполнений, а блок 15.П суммирования вычетов осуществляет сложение за Т тактов наборов из (k-1) по модулю р без формирования числа переполнений.

констант; -я цифра с числа А с i-ro ;выхода регистра 8 подается на i-e входы блока 5 формирования допол нительного кода, второго блока 13 вычисления интервального индекса числа, а также на второй адресный вход блока 11,1 памяти (i k), а номер

Структурно блоки 15.1-15.П суммирова- ю 1 константы W с первого выхода эле

ния вычетов аналогичны блоку 14 .суммирования вычетов. Сумматоры 16 и 17,1-17.п являются сумматорами с формированием суммы и признака переполнения, Сумматор 24,1 (i 1,2, .,,,п-1) второй группы является сумматором по модулю р с формированием суммы признака переполнения и признака равенства суммы вычету (р-1) условия распространения переноса.

Блок 25 формирования переносов служит для формирования по значениям признаков переполения (условиям возникновения переноса) и признаков равенства Суммы вычету (р-1) (условиям распространения переноса) реальных признаков в разряде р-го кода числа.

Рассмотрим, как работает устройство для умножения комплексных чисел в модулярной системе счисления. По сигналу , .подаваемому в каждом четном такте работы устройства с входа 1 на управляющие входы первого и вто20

мента 10 задержки поступает на третьи адресные входы блоков ll,l-ll.k-,l памяти. В блоке 5 осуществляется формирование дополнительного кода

.I . /- к/щ ) числа (-А ) , который с выхода блока 5 через первую группу информационных входов блока 6 поступает на входной регистр 7. В регистре 8 посредством блока 9 формируется модулярш,1й код (.oil,.,., ol) числа А ; из блока памяти ll.i считывается набор констант

v,(.,i) R f(o.:,/; ,i),..,,

, 1).

(формуль I и 2). При этом первая компонента данного набора ,,) с первого выхода блока l,i памяти передается на i-й вход блока 14 суммирования вычетов по вспомогатель ю-. му модулю, а j-я компонента набора

(о,,,1) (J 2,3,,,,,п + 1)

25

30

J. ,. .4,iija. . ,с1 iп- // ;

на управляющие входы первого и вто- ) (J - 2,3,,,,,п + )

рого блоков 6 и 9 групп мультиплексо-35 °с Упает на i-Й вход блока 15,-j-l

г f -, -г, ..-. T3QTJ tJCr . f ..-

ров и вход разрешения элемента 10 задержки, модулирующий код (oi{, ..., () действительной части комплексного числа А через информационные входы второй группы блока 6 поступает . в первый входной регистр 7, а моду- код ( cxf, . ., ,0,) мнимой части А числа А через вторую группу информационных входов блока 9 поступает во второй входной регистр 8; в элемент 10 задержки через вход 4.устройства передается номер 1 комплексной константы W W /М + (где М m М.,) и после этого начинается первый такт операции умножения комплексных чисел А и W.

суммирования вычетов по модулю р (i 1,2,,,.,k-1), а блоки 12 и 13 начнут вычисление по модулю интер- вапьных индексов I(А) и 1(А) чисел 40 А и А соответственно. По истечении Т-го такта работы устройства на выходах блоков I2 и 13 сформируются машинные интервальные индексы, которые на (Т+1)-м подаются соответст- 45 венно на первьй и второй адресные входы блока 11.k памяти, на третий адресный вход которого в это время подается номер 1 константы W с второ - го выхода элемента 10 задержки, В 50 результате из блока I1.k памяти считывается набор констант

(

На первом такте i-я цифра о числа

/ « 1-Ч. -ч .

А (i - I,2,.,,,k) с i-ro выхода регистра 7 подается на i-й информаци- онный вход первой группы входов блока 9, i-й вход первого блока 12 вычисления интервального индекса числа, а также на первый адресный вход

блока ll.i () памяти для хранения

констант; -я цифра с числа А с i-ro ;выхода регистра 8 подается на i-e входы блока 5 формирования дополнительного кода, второго блока 13 вычисления интервального индекса числа, а также на второй адресный вход блока 11,1 памяти (i k), а номер

1 константы W с первого выхода эле

1 константы W с первого выхода эле

мента 10 задержки поступает на третьи адресные входы блоков ll,l-ll.k-,l памяти. В блоке 5 осуществляется формирование дополнительного кода

.I . /- к/щ ) числа (-А ) , который с выхода блока 5 через первую группу информационных входов блока 6 поступает на входной регистр 7. В регистре 8 посредством блока 9 формируется модулярш,1й код (.oil,.,., ol) числа А ; из блока памяти ll.i считывается набор констант

v,(.,i) R f(o.:,/; ,i),..,,

, 1).

(формуль I и 2). При этом первая компонента данного набора ,,) с первого выхода блока l,i памяти передается на i-й вход блока 14 суммирования вычетов по вспомогатель ю-. му модулю, а j-я компонента набора

(о,,,1) (J 2,3,,,,,п + 1)

п- // ;

) (J - 2,3,,,,,п + )

°с Упает на i-Й вход блока 15,-j-l

35 °с Упает на i-Й вход блока 15,-j-l

T3QTJ tJCr . f ..-

суммирования вычетов по модулю р (i 1,2,,,.,k-1), а блоки 12 и 13 начнут вычисление по модулю интер- вапьных индексов I(А) и 1(А) чисел 40 А и А соответственно. По истечении Т-го такта работы устройства на выходах блоков I2 и 13 сформируются машинные интервальные индексы, которые на (Т+1)-м подаются соответст- 45 венно на первьй и второй адресные входы блока 11.k памяти, на третий адресный вход которого в это время подается номер 1 константы W с второ го выхода элемента 10 задержки, В 50 результате из блока I1.k памяти считывается набор констант

V,(i (А-), 1(А),1) Rf,4l(A ), I(A),l),,..,(A ). I(A ),1)

(формулы 3 и 4), которьй запоминается в первом вспомогательном регистре 18. Параллельно с этим в ходе

тактов с второго по (Т+1)-й-блок 1А суммируя по модулю Год -набор входных вычетов, на своих выходах формирует величины

RO

и

х-

Z

|1Г I

R; м;,;.1)/ш, .Mi

а блок 15.j (j l,2,...,n)., суммируя по модулю р Набор соответствую- ,щих входных вычетов, на своих выходах формирует величины

RJ .D/p

Qj ;ZR(i.V;.i) (j /п).

На (т + 2)-м такте работы устройства величина Q выхода блока 14 передается в счетчик 19 через его информационный вход, а .величина О,

(i 1,2,...,п-1)выхода блока 15.1 передается в счетчик 20.1 первой группы. Кроме того, величина R с выхода блока 14 подается на первый вход сумматора 16 по модулю т, на второй вход которого с-первого выхода первого вспомогательного регистра 18 поступает величина

(A ), 1(А),1).

На выходах сумматора 16 будут формированы величины:

15875038

тупает на первый вход сумматора 17.J по модулю р, первой группы, на второй вход которого с (j+l)-ro выхода первого вспомогательного регистра 18 подается величина (А ), 1(А ) ,1). На выходах сумматора 17.J формируются соответственно величины

(J1 А I А . ) 10 + ), I(A ),l)/p

и

(1) ( к II

Rji RjslIiA l iU)i)

15

20

25

(j n) .

При этом величина R : запоминается во вспомогательном регистре 22.j группы, а величина CJ(t 1,2,..., п-1) поступает на счетный вход счетчика 20.t первой группы, в котором после коррекции содержимого формируется величина

(..,i) ч ,р

30

(О л I Ал -1

+ RyClCA ),1(А ),1))J,

На ()-м такте работы содержимое QO счетчика 19 поступает на первый вход сумматора 24.1 второй группы, а содержимое Q счетчика 20.t первой группы поступает на первьш вход сумматора 24.t+l второй группы. 35 На второй вход сумматора 24.j второй группы (j 1,2,...,п) подается

На ()-м такте работы содержимое QO счетчика 19 поступает на пер вый вход сумматора 24.1 второй груп пы, а содержимое Q счетчика 20.t первой группы поступает на первьш вход сумматора 24.t+l второй группы 35 На второй вход сумматора 24.j второ группы (j 1,2,...,п) подается

Р / /„ , содержимое R- вспомогательного ре-- I.RO к КА ),1)/т гистра 22.j группы. Сумматора 24.j, Г (о1 , ( . . л. .-, складывая по модулю о вычеты о .

ГР 4. D °VT, A I/-А л -,4-1 „ складывая по модулю р вычеты Q

Ч , 40 и RI , находит неточное значение

L ™е J bij-й цифры р-го кода мнимой чя

U J.

Djj-и цифры р-го кода мнимой части искомого произведения, а также формирует признак переполнения П; и признак равенства суммы b вычету

R

При этом старший бит П величины пересылается в триггер 21, а величина СОо поступает на счетный вход счетчика 19, в котором после коррекции содержимого будет сформирована величина

(|R V;..;.i)

(Ol А ( Л It Т

+ RVCKA ), КА),)),

(

. П., ,Н запоминаются во втором

представляющая собой число переполне-вспомогательном регистре 23.

НИИ, произошедших при сложении по На заключительном (Т+4)-м такте

модулю m набора соответствующих вы-работы устройства величины с выходов

четов. Одновременно с этим .величина

R (j l,2,...,n) с выхода блока 15.J суммирования вычетов по модулю р посрегистра 23 передаются на входы блока 25, который на i-м своем выходе (i 1,2,.,.,п-1) формирует значение

и

(1) ( к II

Rji RjslIiA l iU)i)

(j n) .

При этом величина R : запоминается во вспомогательном регистре 22.j группы, а величина CJ(t 1,2,..., п-1) поступает на счетный вход счетчика 20.t первой группы, в котором после коррекции содержимого формируется величина

(..,i) ч ,р

(О л I Ал -1

+ RyClCA ),1(А ),1))J,

На ()-м такте работы содержимое QO счетчика 19 поступает на первый вход сумматора 24.1 второй группы, а содержимое Q счетчика 20.t первой группы поступает на первьш вход сумматора 24.t+l второй группы. На второй вход сумматора 24.j второй группы (j 1,2,...,п) подается

и RI , находит неточное значение

bij-й цифры р-го кода мнимой чя

U J.

Djj-и цифры р-го кода мнимой части искомого произведения, а также формирует признак переполнения П; и признак равенства суммы b вычету

А- ь

Величины Ь,Ьц с первых выходов сумматоров 24.1-24.П второй группы передаются соответственно в счетчики по модулю р 26.1-26.п вто- рой группы через информационные нх входы,, а величина П и признаки П ,

(

. П., ,Н запоминаются во втором

вспомогательном регистре 23.

работы устройства величины с выходов

регистра 23 передаются на входы блока 25, который на i-м своем выходе (i 1,2,.,.,п-1) формирует значение

переноса , в (i +1)-й разряд р-го

кода мнимой частиискомого произведния.

Величина с, П„с первого выхода

/V

г

/ч

о

регистра 23 и величины

7---Э

с ВЫХОДОВ блока 25 поступают соотвественно на счетные входы счетчиков 26.1-26.п второй группы. После коррекции содержимого счетчика 26.j (j 1,2,..,,п)в JieM будет получена j-я цифра Ь р-го позиционного кода мнимой части искомого произведения, при этом р-й код b ,,... ,Ь снимается с выходов 27.1-27.п устройства.

В ходе тактов с второго по (Т+5)описанные действия выполняются для модулярных кодов ( l-d ll ,..., - )числа (-А) и (od,,,..., ) числа А , сформированных на первом такте работы устройства соответственно в регистрах 7 и 8. В результате по окончании (Т+5)-го такта в счетчиках 26.1-26.п второй группы будут получены цифры b,,... ,ь р-го кода действительной части искомого произведения, которые снимаются с выходов 27.1-27.п устройства, и на этом операция умножения комплексных чисел А и W с формированием результата в позиционном р-м коде заканчивается. Благодаря конвейерной структуре предлагаемого устройства для умножения комплексных чисел в модулярной системе счисления, начиная с третьего такта, в нем может быть начато вьтолнение новой операции Таким образом, при работе в конвейерном режиме пропускания способность устройства составляет одно комплексное умножение за два такта.

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

У., „„,е„„я к„„„„.кс- ,, 1 оТе™™й;ГГио : Гк°о -™

устройства соединен с информационным входом элемента задержки, первый выход которого соединен с третьим адресным входом i-ro блока памяти для 50 хранения констант группы (i 1,2 ...,k-l), k-e входы первого и второго блоков вычисления интервального индекса числа подключены к соответствующим выходам группы первого и вто- j второго входных регистров соответственно, выходы первого и второго блоков вычисления интервального индекса числа и второй выход элемента задержки соединены соответственно с перных чисел в модулярной системе счисления, содержащее первый и второй входные регистры, первьм и второй блоки групп мультиплексоров, первый и второй блоки вычисления интервального индекса числа, блок формирования дополнительного кода по модулям системы счисления, элемент задержки, группу блоков памяти для хранения констант, блок суммирования вычетов по вспомогательному модулю, первый вспомогательный регистр, группу вспомогательных регистров и сумматор по вспомогательному модулю, при8750310

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

25

30

вым, вторым и третьим адресдгыми входами k-ro блока памяти для хранения констант группы, выходы группы которого подключены к соответствующим входам группы первого и вспомогательного регистра, первый выход i-ro блока памяти для хранения констант группы соединен с i-м входом блока суммирования вычетов по вспомгательному модулю, выход суммы которого соединен с входом первого слагаемого сум сумматора по вспомогательному модулю вход второго слагаемого которого соединен с первым выходом группы первого вспомогательного регистра, отличающееся тем, что, с целью расширения области применения за счет получения произведения в позиционном коде, оно содержит группу блоков суммирования вычетов по моду лю р (р - позиционной системы счисления, п - количество цифр р-го кода числа), первую группу сумматоров по модулю р, счетчик по вспомогательному модулю, первую группу счетчиков по модулю р, триггер, второй вспомогательный регистр, вторую группу сумматоров по модулю р, блок формирования переносов и вторую группу счетчи- ков по модулю р, причем (j + 1)-й выход (J 1,2,...,п) i-ro блока памяти для хранения констант группы под подключен к i-му входу j-ro. блока еум суммирования вычетов по модулю р, группы, выход числа переполнения блока суммирования вычетов по вспомогательному модулю соединен с информаци- онным входом счетчика по вспомогательному модулю, счетный вход кото- рого соединен с выходом признака, переполнения сумматора по вспомогательному модулю, выход старшего разряда суммы которого подключен к входу триггера, выходы сум№1 j-ro блока суммирования вычетов по модулю группы соединен с входом первого, слагаемого j-ro сумматора по модулю р первой группы, вход второго слагаемо

10

-з.О 0

87503 2

го которого подключен к (j+l)-My выходу группы первого вспомогательного регистра, выход числа переполнений i-ro блока суммирования вычетов по модулю р группы соединен с информационным входом i-ro счетчика по модулю р первой группы, счетный вход которого подключен к выходу признака переполнения i-ro сумматора по модулю р первой группы, выход суммы которого соединен с входом i-ro вспомо- тательного регистра группы, выход суммы п-го сумматора по модулю р первой группы соединен с входом п-го вспомогательного регистра группы, выход счетчика по вспомогательному модулю подключен к входу первого слагаемого первого сумматора по модулю р второй группы, выход i-ro счетчика по модулю р первой группы . соединен с входом первого слагаемого (i- -l)-ro суг-шатора по модулю р второй группы, вход второго слагаемого j-ro сумматора по модулю р второй группы подключен к выходу j-ro вспомогательного регистра группы, выход суммы j-ro сумматора по модулю р второй группы соединен с информационным входом j-ro счетчика по модулю р второй группы, выход- которого являт ется соответствующим выходом группы устройства, выход триггера, выход признака переполнения и выход 25 признака равенства суммы вычета (р-1) 1-го сумматора по модулю р второй группы соединены соответственно с входами группы второго вспомогательного регистра, выходы группы которого подключены к соответствующим входам блока формирования переносов первый выход группы второго вспомогательного регистра соеди нен со счетным входом первого счетчика по модулю р вто- 45 рой группы, i -й выход блока формирова- ния переносов подключен к счетному входу (i+l)-ro счетчика по модулю р второй группы.

20

25

Фиг Л