Устройство для умножения комплексных чисел в модулярной системе счисления

 

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

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

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

РЕСПУБЛИК

y!) g G 06 F 7/72

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР! (21 ) 421 231 8/24-24 (22) !6.03 ° 87 (46) 23.08.90. Бюл. ¹ 31 (71) Научно-исследовательский институт. прикладных физических проблем им. А.Н, Севченко (72) Л.Н, Василевич, А.А. Коляда и М.Ю. Селянинов (53) 68! 3 (088.8) (56) Авторское свидетельство СССР № 1510097, кл. G 06 F 7/72, 1987 °

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

¹ 1280625, кл. G 06 F 7/72, 1985, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ КОМПЛЕКСНЫХ ЧИСЕЛ В МОДУЛЯРНОЙ СИСТЕМЕ

СЧИСЛЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано в процессе быстрого преобразования Фурье, функционирующих как в модулярных, так и в позиционных системах счисления, для умножения комплексных чисел на поворачивающие

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

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

„„SU„15875 3 А1 множители, а также для получения последних. Целью изобретения является расширение области применения за счет получения произведения в позиционном коде ° Для того в устройство содержащее блок формирования дополнительного кода по модулям системы счисления, блоки групп мультиплексоров, входные регистры, элемент задержки, группу блоков памяти для хранения констант, блоки вычисления интервального индекса числа блок суммирования вычетов по вспомогательному модулю, сумматор по вспомогательному модулю, первый вспомогательный регистр и группу вспомогательных регистров, введены группа блоков суммирования вычетов по модулю р, две группы сумматоров по модулю р, счетчик по вспомогательному модулю, две группы счетчиков по модулю р, второй вспомогательный регистр, триггер и блок формирования переносов с соответствующими связями, 2 ил.

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

3.1-3.k устройства, где k — число основных модулей системы счисления, вход 4 номера константы устройства, 1587503

4 ния переносов, вторую группу счетчиков 26.1-26,п по модулю р, группу выходов 27.1-27.п устройства.

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

Блок 11.i памяти для хранения (i .= 1.2,...,k) обладает емкостью

2 ), м; + o) L E, разрядностью (I log>m t+ ng1ogzpL) бит. В ячейку блока ll.i памяти с адресом х; +

+ 23Е, у. + 2 3 О4 L 1 записы1.

20 вается набор констант

К; (х;,у;, 1)7, >c (o) /х11 1 K / где R; (х;,у;,1)

iPk;

m. ° w" + /у;м „,/ш;и

m, (i) (n) (х,, у,, 1)...,, R; (х;, х;, 1) х;,у 6 0,1

1 {0,1,...

W u W и

i /k; (2) R (х, у, l) (I W + Т W/m > (ol ) I и р (3) 40 ш,m ...,m „й (4)

45 если х„аш, x— к ш(если x „m о если у„(ш„ о

mк>2mо+ k — 2, m >k — 1; к-1

11 < Г ш е

° a у<> mo1 х;,у и l

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

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

55 вый, второй и третий адресные входы блока

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

23, вторую группу сумматоров 24.124.п по модулю р, блок 25 формировацифры, р-го представления числа

/хЛ - /В " ХЛЬ=Й W11

R „ (x„,yI„ 1),..., R „ (х„,у„,1) цифры р-ro представления числа

1 п я — ° (I ° W + I W).

mo

) ...ш; -l j, 1), целые числа из диапазона D модулярной системы счисления, определяющие соответственно действительную и мнимую часть 1-й из используемых в устройстве комплексных констант; основания модулярной системы счисления, являющиеся попарно прос-. тыми числами; вспомогательный модуль выбираемый из условий

5 !58 вляет сложение за Т = ) log ) (тактов г наборов из (k-l ), вычетов по модулю р (р = 2, ly — натуральное число, p ) mo) с формированием числа переполнений, а блок 15.п суммирования вычетов осуществляет сложение за Т тактов наборов из (k-1) по модулю р без формирования числа переполнений.

Структурно блоки 15.1 †)5.п суммирова— ния вычетов аналогичны блоку 14 суммирования вычетов. Сумматоры 16 и 17,1 †)7.п являются сумматорами с формированием суммы и признака переполнения. Сумматор 24.i (i = 1,2, ...,n-1) второй группы является сумматором по модулю р с формированием суммы признака переполнения и признака равенства суммы вычету (р-1) условия распространения переноса, Блок 25 формирования переносов служит для формирования по значениям признаков переполения (условиям возникновения переноса) и признаков равенства суммы вычету (р-1) (условиям распространения переноса) реальных признаков в разряде р;го ко— да числа.

Рассмотрим, как работает устройство для умножения комплексных чисел в модулярнои системе счисления. По сигналу,.подаваемому в каждом четном такте работы устройства с входа 1 на управляющие входы первого и второго блоков 6 и 9 групп мультиплексоров и вход разрешения элемента 10 задержки, модулирующий код (0 <,..., I

gK) действительной части комплексного числа А через информационные входы второй группы блока 6 поступает в первый входной регистр 7, а модуИ I лярный код (oC,.....g ) мнимой части

II к

А числа А через вторую группу информационных входов блока 9 поступает во второй входной регистр 8; в эле-. мент 10 задержки через вход 4 устройства передается номер 1 комплексной константы W = И /Il + j W /)) (где И = т ))„,) и после этого начинается первый такт операции умножения комплексных чисел А и W.

1

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

А (i = 1,2,...,k) с i-ro выхода

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

7503 о блока 11 i (igk) памяти для хранения и /( констант; i-я цифра о(. числа А с

i-го выхода регистра 8 подается на

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

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

15 (/ — x,"/,..., /- 0K"/ ) числа (-А ), который с выхода блока 5 через первую группу информационных входов блока 6 поступает на входной регистр

7, В регистре 8 посредством блока 9

20 формируется модулярный код (о

I . у ° ° ° у

К„) числа А; из блока памяти ) l.i считывается набор констант

V; (;, oC, 1) = (R; (g, Ы, 1)...,, Ы"1oC ;,о/, 1) (формулы 1 и 2). При этом первая компонента данного набора R (Ы;,и(;,1) с первого выхода блока 11.i памяти передается на i-й вход блока 14 суммирования вычетов по вспомогательному модулю, а j-я компонента набора (>-1), Л

R; (Ы.,Ы;,1) (j = 2,3,...,n + 1) поступает на i-й вход блока )5. j 1 суммирования вычетов по модулю р (i = 1,2,...,k-l), а блоки 12 и 13 начнут вычисление по модулю тп интерI

K вальных индексов I(A ) и I(A ) чисел ! tI

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

gp результате из блока 1!.k памяти считывается набор констант к(1 (A ), I(A ),1) = (R„(I(A ), I(A ),1),...,R „(I(A ), I(A ),1)) (формулы 3 и 4), которьп запоминается в первом вспомогательном регистре 18. Параллельно с этим в ходе

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

Q Е (М;, oL,", I ) J m

R, (Ì,,ñ(,, I)) ШО; -1 а блок 15.j (j = 1,2,...,n)., суммируя по модулю р набор соответствую щих входных вычетов, на своих выходах формирует величины

Х-1

Ri 1%Ri (о1,а(,I)/р

1 "! (т! !1

О„ = —,7 R,. (о ;,()C,,I) (j и).

1=1

На (Т + 2)-м такте работы устройства величина Q выхода блока 14 пе" о редается в счетчик 19 через его информационный вход, а величина О, (i = 1,2,...,n-1)выхода блока 15.i передается в счетчик 20.i первой группы. Кроме того, величина Rp c выхода блока 14 подается на первый вход сумматора 16 по модулю mp, на второй вход которого с первого выхода первого вспомогательного регистра 18 поступает величина

R„ (I(A ), I(A ),1).

На выходах сумматора 16 будут формированы величины.! (Rp + R (I(A )т I(A ) 1) о

mo

При этом старший бит П величины !

R0 пересылается в триггер 21, а величина Q поступает на счетный вход счетчика 19, в котором после коррекции содержимого будет сформирована величина (о1 — (QR (Ы;,() ;,1) +

0 тп, + R„(I(A ), представляющая собой число переполнений, произошедших при сложении по модулю т(т набора соответствующих вычетов. Одновременно с этим .величина

R (j = 1,2,...,n) с выхода блока 15 j суммирования вычетов по модулю р поступает на первый вход сумматора 17. j по модулю р, первой группы, на второй вход которого с (j+1)-ro выхода первого вспомогательного регистра 18

5 (1 л л подается величина К (I(А ), I(А ),1).

На выходах сумматора 17.j формируются соответственно величины

1 (1) Л Л

+ Rx(I(R ), I(A ),1)/р

I (a) л л

Rg+ Rq(I(A, I(A ),1)

1 P (j ф п), !!

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

i 1 к 1t) 25 Q+ = — (,Е.К (<,Ì,1) +

1=1 фт Л ((+ R „(1(А );I(A ),1)) г

На (Т+3)-м такте работы содержи30

1 мое Ц,) счетчика 19 поступает на первый вход сумматора 24.1 второй груп-! пы, а содержимое Q4 счетчика 20,t первой группы поступает на первый вход сумматора 24.t+1 второй группы.

35 На второй вход сумматора 24.j второй группы (j = 1,2,...,n) подается ! содержимое R вспомогательного ре-. .! гистра 22.j группы, Сумматора 24. j складывая по модулю р вычеты Q !

j-1

40 и R, находит неточное значение л((. 1„

Ь j-й цифры р-го кода мнимой части

J искомого произведения, а также формирует признак переполнения П и признак равенства суммы Ь вычету

" (P-1)Н, )(т

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

Н1,...,П,H„ запоминаются во втором вспомогательном регистре 23.

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

9 )58 переноса f„в (i + 1)-й разряд р-го

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

Величина |., = По с первого выхода регистра 23 и величины |,..., о л с выходов блока 25 поступают соответственно на счетные входы счетчиков

26.1-26.п второй группы. После коррекции содержимого счетчика 26.j (j = 1,2,...,п)в .нем будет получена

j-я цифра Ь р-ro позиционного кода

If мнимой части искомого произведения, при этом р-й код Ь,,...,Ь „ снимается с выходов 27.1-27.п устройства, В ходе тактов с второго по (Т+5)-й описанные действия выполняются для !! модулярных кодов (/-Ы,/ — <(тп) числа (А ) и (М „,..., )

I числа А, сформированных на первом такте работы устройства соответственно в регистрах 7 и 8, В результате по окончании (T+5)-ro такта в счетчиках 26,1-26.п второй группы будут

I / получены цифры Ь |,...,b> р-го кода действительной части искомого произведения, которые снимаются с выходов 27,1-27.п устройства, и на этом операция умножения комплексных чисел

А и W с формированием результата в позиционном р-м коде заканчивается, Благодаря конвейерной структуре предлагаемого устройства для умножения комплексных чисел в модулярной системе счисления, начиная с третьего такта, в нем может быть начато выполнение новой операции. Таким образом, при работе в конвейерном режиме пропускания способность устройства составляет одно комплексное умножение за два такта.

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

Устройство для умножения комплексных чисел в модулярной системе счисления, содержащее первый и второй входные регистры, первый и второй блоки групп мультиплексоров, первый и второй блоки вычисления интервального индекса числа, блок формирова— ния дополнительного кода по модулям системы счисления, элемент задержки, группу блоков памяти для хранения констант, блок суммирования вычетов по вспомогательному модулю, первый вспомогательный регистр, группу вспомогательных регистров и сумматор по вспомогательному модулю, при7503 10

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

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

20

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

j-ro сумматора по модулю р второй группы подключен к выходу j-го вспомогательного регистра группы, выход суммы j-го сумматора по модулю р второй группы соединен с информационным входом j-го счетчика по модулю р второй группы, выход которого явля= ется соответствующим выходом группы устройства, выход триггера, выход признака переполнения и выход признака равенства суммы вычета (р-1)

i-ro сумматора по модулю р второй группы соединены соответственно с входами группы второго вспомогательного регистра, выходы группы которого подключены к соответствующим входам блока формирования переносов пер/ вый выход группы второго вспомогательного регистра соединен со счетным входом первого счетчика по модулю р второй группы, i-й выход блока формирова ния переносов подключен к счетному входу (i+1)-го счетчика по модулю р второй группы, 1

1587503

1587503

7.1

Составитель А. Клюев

Редактор Н. Яцола Текред M.Äèäüï Корректор С., Черни

Заказ 2420 Тираж 564 Подписное

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

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

Производственно-издательский комбинат "Патент", г, Ужгоро:g, ул. Гагарина, 101