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

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

Целью изобретения является повышение быстродействия.

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

Устройство для умножения комплексных чисел в модулярной системе счис- пения (фиг.1) содержит тактовый вход I устройства, первую группу информационных входов 2.1 2К устройства, вторую группу информационных входов 3.1-3.К устройства (К - количество основных модулей системы счисления), вход 4 номера константы устройства, блок 5 формирования дополнительного кода по модулям, первый блок 6 мультиплексоров, первый и второй входные .регистры 7 и 8, второй блок 9 мультиплексоров, группу блоков 10. 1-, 10.2, ..., 10оК Памяти, первый и второй блоки 11 и 12 вычисления интервального индекса, элемент 13 задержки, группу

блоков 14.1, 14.2,..., 14К+1 суммирования вычетов, группу модульных сумматоров 15.1, 15.2,...,15 К+1, вспо- могательньш регистр 16, группу вспомогательных регистров 17.1, 17,2,... 17.КН-1, группу блоков 18.1, 18.2,... 18.К деления на константу и группу выходов 19.1, 19.2,...,19.К устройст

Блоки 11 и 12 вычисления интервального индекса (фиг.З) имеют конвей- ерную структуру и содержат элементы 20 памяти, регистры 21 и сумматоры 22 (для ).

Отдельный блок вычисления интервального индекса по входному модуляр ному коду СЫ,,...Ы) некоторого числа А из диапазона , . , . , рМ модулярной системы счислени осуществляют формирование за Т такто вычета 1(А)/1(А), интервального индекса числа А, определяемого соотношениями

КА)-О,.(«;.;); -1

ni

tiuMj -JB, m

m

при ,.,.,k-1

ji K-t

m

при

наименьший неотрицательный вычет по некоторому модулю т;

фиксированное натуральное число такое, что га, ,2р+

+k-2

и m

, р:

и -

М

tr1

П Ш; .к-1 -

М

.-1 m;

Остатки fci 2J-1 и Ы j

являются COOT -j

ветственно младшими и старшими разрядами входа элемента 20.) -памяти, по которому записывается вычет k

№.,-,+

гЛплк -J l 2 часть). В ячейку блока lO.i памяти записывается набор констант, компоненты которого определяются выражениями:

5

0

5 .

где I

Q /ЧХ. ,Y, ,1)

Гl5iM lK:iLbi; w +11,. L...j.

,...,k-1; ,...,k+1 Q ; (X,I,I)|l w +

K,

к

X

К.Э

,,,

Y - 1Ы

,

К m,

и

если если X ,р

если Y| р

если

Y.xP

1 - значения разрядов, начиная с младшего адресного входа блока 10

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

Элемент 13 задержки представляет

ГТ1

собой цепь из - регистров. ИнформаUiiOHHbUi вход первого регистра является входом элемента задержки, выходы первого и последнего регистров являются соответственно первым и вторым выходами элемента 13 задерлжи, управляющие входы всех регистров цепи объединены и подключены к тактовому вхо- ду элемента 13 задергкки. Управляюздий вход элемента 13 задержки и селекторные входы блоков групп гультиплексо- ров 6 и 9 объединены и подключены к управляющему входу 1 устройства.

Блок 1A.i суммирования вычетов (,2,...,К+1) выполняет сложение по модулю т; наборов из К-1 вычетов за Т тактов. Структурно блоки суммирования вычетов аналогичны блокам 11 и 12 вычисления интервального индекса.

Блок 18.1 деления на константу реализован на постоянном запоминаюп ем устройстве, в ячейку которого записывается вычет

А I - Т . 1)

ti Lll9- - 9

I m., ., - m-М.-„,

m

K+ 1

где i-j. и i-| - значения младших и

старших разрядов адресного входа постоянного запоминающего устройства.

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

Пусть требуется перемножить комплексное число +JA на комплексную

т, W . W константу W -- J M имеющую но

г к- I , К-1

номер 1е (0,1...,L-l.

Действительная и мнимая части искомого произведения В В +JB могут быть вычислены по следующим приближенным формулам:

в ij; rIlAV;A w)-- к..

Г l(Jd l..

;суммирования вычетов, а блоки 11 и 12 начнут вычисление по модулю т инВ

га,

тервальных индексов. По истечении Т-го такта на вьтодах блоков 11 и 12 35 сформируются соответственно вычеты 1(А ) и i(A ), которые на (Т+1)-м такте подаются на младшие разряды адресного входа блока 10.К памяти.

„ ,В то же время на старшие разряды адПо сигналу , подаваемому в о тг

ресного входа блока 10.К памяти с

Устройство для умножения комплексных чисел в модулярной системе счисления работает следующим образом.

дом четном такте работы устройства с входа 1 на селекторные входы первого и второго бликов 6 и 9 мультиплексоров и управляющий вход элемента 13 задержки, модулярный код (с/.,, . .. ,с/| ) действительной части комплексного числа А с входа 2.1, 2.2,...,2.К через информационные входы второй группы блока 6 поступает в первый входной регистр 7, модулярный код (of- j ,... , ,) мнимой части числа с входов 3,1,

3.23.К через вторую группу инфор-

мационных входов блока 9 групп мультиплексоров поступает во второй входной регистр 8, а в элемент 13 задержки через вход 4 устройства передается номер 1 комплексной константы, после этого начинается первый такт операции умножения комплексных чисел.

второго выхода элемента 13 задержки подается номер f константы. В результате из блока 10.К памяти считывается .набор констант Q(l(A ), l(A ), I), который запоминается во вспомогательном регистре 16. Параллельно с этим в ходе тактов с второго по (Т+1)-й блок 14.j, суммируя по модулю набор входных вычетов, находит величину

С ,. с.

На Т-м такте величины q и Q с выхода блока 14.1 и 1-го выхода вспомогательного регистра 16 подают- сс ся соответственпо на первый и второй входы модульного сумматора 15.1, который получает 1-ю цифру

.

50

5

O

5

0

5

0

На первом такте цифраei с i-ro выхода регистра 7 подается на i-й информационный вход первой группы блока 9, i-й вход блока 11 вычисления интервального индекса, а также на младшие разряды адресного входа блока 10.1 () памяти; цифра с j с 1-го выхода регистра 8 подается на 1-е входы блока 5 формирования дополнительного кода, блока 12 вычисления интервального индекса, а также на следующие разряды адресного входа блока 10.1 () памяти, а номер 1 константы с первого выхода элемента 13 задержки поступает на старшие разряды адресного входа блоков памяти 10.1, 10.2,...,10.К-1. В блоке 5 осуществляется формирование дополнительного кода ((-о(-Х который с выхода Ьлока 5 через первую группу информационных входов блока 6 групп мультиплексоров (ввиду ) поступает во входной регистр 7; в регистре 8 посредством блока 9 мультиплексоров формируется модулярный код (о ,. . . ,о.). Из блока 10 памяти

считывается набор констант Q (,о(, 1), j-я компонента которого с 1-го выхода блока 10.1 памяти передается в 1-й входной регистр блока 14.J

;суммирования вычетов, а блоки 11 и 12 начнут вычисление по модулю т ин

второго выхода элемента 13 задержки подается номер f константы. В результате из блока 10.К памяти считывается .набор констант Q(l(A ), l(A ), I), который запоминается во вспомогательном регистре 16. Параллельно с этим в ходе тактов с второго по (Т+1)-й блок 14.j, суммируя по модулю набор входных вычетов, находит величину

С ,. с.

На Т-м такте величины q и Q с выхода блока 14.1 и 1-го выхода вспомогательного регистра 16 подают- ся соответственпо на первый и второй входы модульного сумматора 15.1, который получает 1-ю цифру

.

модулярного кода интервального индекса I(A W ) числа; при этом . запоминается во вспомогательном регистре 17. .

На (Т+3)-м такте вычеты l . и с выходов вспомогательных регистров 17. и 17.. . поступают соответствен( ° -- к )

но на голадшие и старшие разряды входа блока 18.1 деления, который определяет i-ю цифру модулярного кода мнимой Ю части искомого произведения, при этом модулярный код мнимой части (9, ,,.., в) снимается с выходов 19.1, 19.2, , 19.К устройства.

кода по.модулям, первый и второй блоки мультиплексоров, второй входной регистр, группу блоков памяти, второй блок вычисления интервального индекса и элемент задержки, причем выход блока формирования дополнительного кода соединен с первым информационным входом первого блока мультиплексоров, второй информационный вход ко торого является первой группой инфор мационных входов устройства, выход первого блока мультиплексоров соединен с входом первого входного регистра, выход которого соединен с перВ ходе тактов с второго по (Т+4)-й 5 вым информационным входом второго описанные действия выполняются для блока мультиплексоров, второй инфорМОДУЛЯРНЫХ кодов ( |-о(Тнл , „/-о(1е)

и (о( I ,. . . ,о( ) , сформированных на первом такте соответственно в регистрах

20

7 и 8, В результате по окончании (Т+ +Л)-го такта блоки 18,1, 18.2,..,, 1В.К деления получат модулярный код (и ....,/з ) действительной части искомого произведений, который снимается с выходов 19.1, 19.2,..., 19.К уртройства, на этом операция умножения комплексных-чисел завершается.

Благодаря конвейерной структуре устройства для умножения комплексных чисел в модулярной системе счисления начиная с третьего такта в нем может быть начато выполнение новой операции.

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

25

30

мационныи вход которого является вто рой группой информационных входов устройства, выход второго блока мультиплексоров соединение входом второго :входного регистра, выход которо го соединен с входом блока форг шрова ния дополнительного кода по модулям, селекторные входы блоков мультиплексоров и тактовый вход элемента задержки объединены и подключены к так товому входу устройства, разряды адресного входа, кроме старших, j-ro блока памяти группы () соединены соответственно с разрядами j-й группы первого и второго входных ре- -гистров, выходы первого и второго в-ходных регистров, входы первого и второго входных регистров. соединены соответственно с входами первого и второго блоков вычисления интервального индекса, вход номер а константы устройства соединен с информационным входом элемента задершси, первый выход которого соединен со старшими . разрядами адресного входа j-ro блока .памяти группы, выходы первого, второ го блока вычисления интервального индекса и второй выход элемента задержки соединены соответственно с разрядами адресного входа К-го блока памяти группы, выход которого сое ди-ден с входом вспомогательного регистра, первый и второй входы i-ro модульного сумматора группы подключе ны соответственно к выходу i-ro блок суммирования вычетов группы и к i-й группе разрядов выхода вспомогательного регистра, выходы блоков деления йа константу группы являются группой выходов устройстБа, i-я группа разря дов выхода j-ro блока памяти группы соединена c- j-м входом i-ro блока суммирования вычетов группы.

З стройство для умножения комплексных чисел в модулярной системе счисления, содержащее первый входной регистр , первый блок вычисления интервального индекса, группу модульных сумматоров, вспомогательный регистр, груп пу вспомогательных регистров, группу блоков суммирования вычетов и группу блоков деления на константу, причем вход вспомогательного регистра группы соединен с выходом соответствующего модульного сумматора группы (.i 1-K+1,iK - количество ОСНОВНЫХ модулей системы счисления) выходы вспомогательных регистров группы, кроме (К+1)-го, соединены : с младшими разрядами входа соответс гвующих блоков деления на константу грушш, старшие разряды входа которых сое;ди- нены с выходом (К-1)-го .вспомогате- льного регистра- группы, о т л и ч а ю щ е е с я тем что, с целью шеиия быстродействия, оно содержит блок формирования дополнительного

6256

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

5

0

5

0 5 0 55

мационныи вход которого является второй группой информационных входов устройства, выход второго блока мультиплексоров соединение входом второго :входного регистра, выход которого соединен с входом блока форг шрова- ния дополнительного кода по модулям, селекторные входы блоков мультиплексоров и тактовый вход элемента задержки объединены и подключены к тактовому входу устройства, разряды адресного входа, кроме старших, j-ro блока памяти группы () соединены соответственно с разрядами j-й группы первого и второго входных ре- -гистров, выходы первого и второго в-ходных регистров, входы первого и второго входных регистров. соединены соответственно с входами первого и второго блоков вычисления интервального индекса, вход номер а константы устройства соединен с информационным входом элемента задершси, первый выход которого соединен со старшими . разрядами адресного входа j-ro блока .памяти группы, выходы первого, второго блока вычисления интервального индекса и второй выход элемента задержки соединены соответственно с разрядами адресного входа К-го блока памяти группы, выход которого сое- ди-ден с входом вспомогательного регистра, первый и второй входы i-ro модульного сумматора группы подключены соответственно к выходу i-ro блока суммирования вычетов группы и к i-й группе разрядов выхода вспомогатель- ного регистра, выходы блоков деления йа константу группы являются группой выходов устройстБа, i-я группа разрядов выхода j-ro блока памяти группы соединена c- j-м входом i-ro блока суммирования вычетов группы.

г

Д

К-:

Ш-1

/7

J1S.h

щ

-

/7./W

гаг

Фуз.2

Ъ

if

If

.J

Составитель С.Пономарев Редактор Н.Цалихина Техред Л.Олейник Корректор А.Обручар

----ч- и.-- ..«.Ъ.

Заказ 7067/54 Тираж 671Подписное

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

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

Производственно-полиграфическое предприятие, г.Ужгород,, ул.Проектная,4