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

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

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУБЛИК дц4 С 06 F 7/72

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

У

®сВ у.,.

OIlHGAHHE NSO5PETEHNQ„

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ Aki ti-:; „.. (21) 3938741/24-24 (22) 01.08.85 (46) 30.12.86. Бюл. М 48 (71) Научно-исследовательский институт прикладных физических проблем им. А.М.Севченко (72) А.А.Коляда (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 947860,.кл. G 06 F ?/72, 1980.

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

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

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

ÄÄSUÄÄ 1280625 А1 для умножения комплексных чисел на поворачивающие множители. Цель изобретения — повышение быстродействия устройства. Поставленная цель достигается тем, что устройство, содержащее первый входной регистр, первый блок вычисления интегрального индекса, группу модульных сумматоров, вспомогательный регистр, группу вспомогательных регистров, группу блоков суммирования вычетов и группу блоков деления на константу, содержит б, ок формирования дополчительного кода по модулю, первый и второй блоки мультиплексоров, второй входной регистр, группу блоков памяти, второй блок вы- cg числения интервального индекса и элемент задержки с соответствующими связями. 3 ил. С::

1280625! Id М вЂ” — 1 — -1- -4 при а=1 ... k-1

111 П1 к

55 при i=k к

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

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

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

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

3.1-3.К устройства (К вЂ” количество 20 основных модулей системы счисления), вход 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,..., 35

17.К+1, группу блоков 18.1, 18.2,..., 18.К деления на константу и группу выходов 19.1, 19.2,...,19.К устройства.

Блоки 11 и 1? вычисления интервального индекса (фиг.3) имеют конвей- 40 ерную структуру и содержат элементы

20 памяти, регистры 21 и сумматоры

22 (для К=7).

Отдельный блок вычисления интервального индекса по входному модуляр-45 ному коду (д,,...,Ы ) некоторого числа А из диапазона Э= -рЫ,, pN -1j модулярной системы счисления

К-1 осуществляют формирование за Т тактов вычета Х(А)=/Т(А)/г„к интервального индекса числа А, определяемого соотношениями к R (a 1);

1-. 1 где x) наименьший неотрицательный вычет по некоторому моцулю m; фиксированное натурапьное число такое, что m, >2р+

+k-2 и m > р 1 -

11, М =Птп, Ы

Остатки М, и с, .являются соответственно младшими и старшими разрядами входа элемента 20.1 памяти, по которому записывается вычет IR + 4-1 гk

+ R, (j=1 t — j, C ) — целая часть).

В ячейку блока 10.1 памяти записывается набор констант, компоненты которого опрецеляются выражениями:

q ." (Х.,у., ) = У !

ХМ, I И+1т Ы ., И

ГГ

q " (X r., Х) 1- W „Т "Ъ| < где

Х,, если Х ср

Х,-m, если Х > р к

Уу,, если Y,< р

Y -т<, если У, >,р

Х.,У и 1 — значения разрядов, начиная с младшего адресного входа блока 10 памяти;

1 ll

W u W — целые числа из диапазона

Э модулярной системы счисления, определяющие соответственно действительную и мнимую части

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

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

128062э

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

Блок 18.i деления на константу реализован на постоянном запоминающем устройстве, в ячейку которого записывается вычет 10 ). 1к 2 «1 + 1 в.=! — — — + — — — — 1 i=1 k ! .1, t — 1 Э t где 1. и «1 — значения младших и

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

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

Пусть требуется перемножить комп-!! лексное число A=A +jA на комплексную

W . W константу W= — — — -+j — — —, имеющую но-25

pM pM номер 1 E. 10,1...,L-1) .

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

Г I(A W -А W )1 в -(— — —— ((m к

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

По сигналу Г=1, подаваемому в каж-10 дом четном такте работы устройства с входа 1 на селекторные входы первого и второго блоков 6 и 9 мультиплексоров и управляющий вход элемента 13 задержки, модулярный код (с,,...,Ы ) действительной части комплексного числа А с входа 2.1, 2.2,...,2.К через информационные входы второй группы блока 6 поступает в первый входной регистр 7, модулярный код (о,,..., Ц ,Ы ) мнимой части числа с входов 3.1, к.

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

На первом такте цифра < с i-го

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

10.i (igk) памяти; цифра,(. с i-ro выхода регистра 8 подается на i-e входы блока 5 формирования дополнительного кода, блока 12 вычисления интервального индекса, а также на следующие разряды адресного входа блока 10.i (igk) памяти, а номер 1 константы с первого выхода элемента

13 задержки поступает на старшие разряды адресного входа блоков памяти

10.1, 10.2,...,10.К-1. В блоке 5 осуществляется формирование дополнительного кода (t — d.,1,...,)- „) ), который с выхода блока 5 через первую группу информационных входов блока б групп мультиплексоров (ввиду

Г=О) поступает во входной регистр 7; в регистре 8 посредством блока 9 мультиплексоров формируется модулярный код (Ы,- ° °,d. ). Из блока 10 памяти

I считывается набор констант Q,(<Ê;,Ы

1), j-я компонента которого с i-го

I выхода блока 10. i памяти передается в i-й входной регистр блока 14.j суммирования вычетов, а блоки 11 и

12 начнут вычисление по модулю г „ интервальных индексов. По истечении

Т-го такта на выходах блоков 11 и 12 сформируются соответственно вычеты

I(A ) и I(A ), которые на (Т+1)-м такте подаются на младшие разряды адресного входа блока 10.К памяти.

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

, =| ", .

На T-м такте величины g. u Q с выхода блока 14. i u i-го выхода вспомогательного регистра 16 подают-. ся соответственно на первый и второй входы модульного сумматора 15.1, который получает 1-ю цифру ч ., =,. а „ 1-, 1280б25

10

20 льтиплексорав соединен"с входом втоУстройство для умножения комплексных чисел в мадулярной системе счисления., содержащее первый входной регистр, первый блок вычисления интервального индекса, группу модульных сумматоров, вспомогательный регистр, группу вспомогательных регистров, группу блоков суммирования вычетов и группу блоков деления на константу, причем вход х-го вспомогательного регистра группы соединен с вьгходом соответствующего модульного сумматора группы (i=1-К+1, К вЂ” количество основных .модулей системы счисления), выходы вспомогательных регистров группы,. кроме (К+1)-ro, соединены с младшими разрядами входа соответствующих блоков деления на константу группы, старшие разряды входа которых соединены с выходом (K-1)-го вспомогательного регистра группы, о т л и ч а " ю щ е е с я тем, что, с целью повышения быстродействия оно содержит блок формирования дополнительного модулярного кода интервального индекса I(A W +Л W ) числа; при этом ! запоминается во вспомогательном регистре 17.

На (Т+3)-м такте вычеты 1, и 1„„ с выходов вспомогательных регистров

17. и 17 поступают соответственKÞ t но на Младшие и старшие разряды входа блока 18.i деления, который определяет -ю цифру модулярногс кода мнимой части искомого произведения, при этом

1( мадулярныи код мнимси части (P а в

P ) снимается с выходов 19.1, 19.2, 19.К устройс-,ва.

В ходе тактов с второго по (Т+4)-й описанные действия выполняются для

13 модулярных кодов (-g,"7„,,... „1-d, ) и (с,,...,3 ), сформированных на первом такте соответственно в регистрах

7 и 8. В результате по окончании (Т+

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

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

Формула изобретения кода по модулям, первый и второй блоки мультиплексоров, второй входной регистр, группу блоков памяти, второй блок вычисления интервального индекса и элемент задержки, причем выход блока формирования дополнительного кода соединен с первым информационным входам первого блока мультиплексоров, второй информационный вход которого является первой группой информационных входов устройства, выход первого блока мультиплексоров соединен с входом первого входного регистра, выход ксторога соединен с первым информационным входом второго блока мультиплексоров, второй информационный вход которого является второй группой информационных входов устройства, выход второго блока мурого входного регистра, выход которого соединен с входом блока формирования дополнительного кода па модулям, селектарные входы блоков мультиплексоров и тактовый вход элемента задержки объединены и подключены к тактовому входу устройства., разряды адресного входа, кроме старших„ j-га блока памяти группы (j=1-K-1) соединены соответственна с разрядами 1-Й группы первого и второго входных регистров, выходы первого и второго входных регистров, входы первого и второго входных регистров. соединены соответственно с входами первого и второго блоков вычисления интервального индекса, вход номера константы устройства соединен с информационным входом элемента задержки, первый вы40 ход которого соединен со старшими . разрядами адресного входа j-ro блока памяти группь, выходы первого, второго блока вычисления интервального индекса и второй выход элсмента задержки соединены соответственно с разрядами адресного входа К-ro блока памяти группы, выход которого соединен с входом вспомогательного регистра, первьгй и второй входы i-ro модульного сумматора группы подключены соотве"ственно к выходу 1 Fo блока суммирования вычетов группы и к i-й группе разрядов выхода вспомогательного регистра, выходы блоков деления йа константу группы являются группой вьгходов устройства, i-я группа разрядов выхода 1-гс блока r.:àìÿòè группы соединена с 1-м входам 1-го блока суммирования вычетов группы.

1280625

Фие. 3

Составитель С.Пономарев

Техред Л.Олейник

Корректор А,Обручар

Редактор Н.Цалихина

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

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

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

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