Устройство для умножения по модулю

Устройство для умножения по модулю

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскмк

Соцналистнческкх

Республик

947860 (61) Дополнительное к авт. свид-ву (22) Заявлено 29.04. 80(21)2935889/18-24 с присоединением заявки М 2935888/18-24

РЦ М.Кт.

G F 7/72

Государственный комитет

СССР но делам изобретений и открытий (23) Приоритет

153) УДК 681 325 (088.8) Опубликовано 300782. Бюллетень Ю 28

Дата опубликования описания 30.07.82

Инкцнн,. . 1 (72) Авторы изобретения

И Я AxyticKHA И т Пак р Н турмухамбето

Ю.А.Макеев и И.А.Рыбина

Институт математики и механики АН Казах (71) Заявитель (54 ) уСТРОИСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДуЛ10

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

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

Однако данное устройство работает только с целыми рациональными числами.

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

947860

Недостатком известного устройства является отсутствие возможности выполнять умножение кватернионов и бикнатернионон.

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

Поставленная цель достигается тем, Р что устройство для умножения по модулю, содержащее четыре входных регистра, четыре блока умножения, два сумматора, выходы которых являются соответственно первым и вторым выходами 15 устройства, входы входных регистров являются соответстненно первым, вторым, третьим и четвертым входами устройства, выход первого нходного регистра подключен к первым входам 20 первого и четвертого блоков умножения, выход второго входного регистра подключен к первым входам второго и третьего блоков умножения, выходы первого и третьего блоков умножения 75 подключены к первым входам соотнетственно первого и второго сумматоров, содержит пятый, ш .стой, седьмой и восьмой входные р =гистры, входы которых являются ссответственно пятым, 30 шестым, седьмым и восьмым входами устройства, третий и четвертый сумматоры, выходы которых являются соответственно третьим и четвертым выходами устройства, а первые 35 входы подключены к выходам соответственно пятого и седьмого блоков умножения, вторые входы сумматоров подключены к выходам соответственно второго, четвертого, шестого и нось- 40 мого блоков умножения, первые входы пятого и седьмого, шестого и восьмого блоков умножения попарно объединены и подключены к выходам соответственно третьего и четвертого входных регистров, вторые входы первого и восьмого, четвертого и шестого, третьего и пятого, второго и седьмого блоков умножения попарно объединены и подключены к выходам соответственно пятого, шестого, 50 седьмого и восьмого входных регистров. где (х) q — вычет целого числа х по модулю q в кольце целых

Рациональных чисел; сумма квадратов коэффициентов при мнимых единицах 1, 3, k кватерниона р (здесь р»= -ip).

60 В случае же бикватернионов сумма квадратов коэффициентов лежит в некотором кольце комплексных чисел и имеет вид U+ve, где Ф 2-может принимать значения 1,0 или -l, тогда

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

Схема (фиг.1)- содержит первый, второй, третий, четвертый, пятый, шестой, седьмой и восьмой блоки 1-8 умножения; первый, второй, третий и четвертый сумматоры 9-12; печеный, второй третий, четвертый, пятый, шестой, седьмой, восьмой входные регистры 13-20.

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

Устройство работает следующим образом.

Умножение двух пар целых рациональных чисел.

При этом сомножители первого произведения заносятся на входные регистры 13 и 17. В блоке 1 умножения формируется произведение, которое поступает на первый вход первого сумматора 9 и фиксируется на нем. Сомножители второго произведения заносятся на входные регистры 15 и 19. В блоке

5 умножения формируется произведение, которое поступает на первый вход третьего сумматора 11 и фиксируется на нем.

Умножение кватернионов и бикватернионов.

На входы 17-20 подаются коды соответстненно реальных и мнимых частей

R 3md ., Red", Dryads"вычетов cx са"множимого А по модулям Р, Р", а на нходы 21-24 подаются коды реальных и мнимых частей Ref, 3m p, Re)«Jm в « вычетов P, P» множителя В по модулям

P P. На выходах блоков 1-8 умно«жения образуются соответственно произ неден ия (Re d. Re P), (— Лт ос 3m@, 3m/ ReP«Reol, 3m), Re HReP«(-3m M3mP), Вес Зт » 3 »ReP.

После сложения полученных произведений на выходах сумматоров 9-12 получаются реальные и мнимые части

Rey, 3m ; Re+ .Зтпу«вычетов я-, -,).» произ веден ия С=АВ сомн ожителей А и

В согласно формулам у=(Р.е(Rep-ди 13vng«)++

+(змйkep ped. 3vp ), 1, 947860

65 фициентов в этом кольце, равная

Ф-ч и> .

Рассмотрим, например, умножение кватерйиона A=l+70i-10j-k на

В= -2+40it9j+k. Пусть в качестве модуля взяты кватернионы р =l+j+3k, р =1-3-31 .

Р

Тогда кватернионы A и В имеют соответственно вычеты -1-31, З

-1, -3+31|

Действительно, например 1+70i-10j-k=

=(1+j+3k)(-1 4i-21j+4k)+(-1-3i) °

Получим, например, вычеты произведения AB по основаниям р и р» °

Здесь M =-1-3i,ê =3, P =-1,(4 -3+3i, q = 1 +1 +3 =11.

На выходах блоков 1-8 умножения получатся соответственно произведения

Red. Re р =(-1)(-1) =1; -Эмад эмф =

= — (Ь)(3)=9 =--2 (1моd«);

3md. Ref =(-3)(-3) =9 -6.(моди ;

Р.ед-" Re@=3(- =-9 =-2(и од и);

2е (3vnp =(; 1)(p) = p;

-V «J p =о о=о, р,Е, + g и p„ = Ъ 3 = 9 — 2 (vn Od И );

3 «" е =о (- ) =О.

После сложения получим соответственно

Вела=1+(-2)=-1

3m = -2+0= вЂ

Re@=2+0 = 2

Зпф= -2+О = -2, т.е. проиэнедение AB=(1+70i-10j-k)» к(-2+40i+9j+k) = -2711†- 101i-81j+1033k имеет вычеты -1-2i, 2-2i, по основаниям р„ =1+j+3k и р„ =l-i-3k, 1Е

Цель изобретения может быть также достигнута за счет несколько иного схемного,решения теми же средствами.

Можно попарно объединить блоки 1-8 умножения. При этом получится четыре блока умножения с более сложной внут-. ренней структурой. Для организации их использования вводится блок управления, который с помощью управляющих сигналов производит в блоках умножения такую коммутацию информационных входов, которая обеспечивает их использование для операций над различными числовыми конструкциями. Одновременно сумматоры 9-12 иэ комбинационных превращаются в накапливающие. Это приводит к уменьшению аппаратных затрат за счет замедления темпа работы устройства. Оно из однотактного становится двухтактным.

Блок-схема устройства, представленная на фиг.2, содержит первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой входные регистры 1-8; первый, второй, третий и четвертый блоки 9-12 умножения) первый, второй, третий и четвертый сумматоры 13-16; блок 17 управления, управляющие входы устройства 18-21.

Схема блока управления (фиг.3) содержит первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый, десятый, одиннадцатый, двенадцатый, тринадцатый, четырнадцатый, пятнадцатый, шестнадцатый элементы И 22-37; первый, второй, третий, четвертый, пятый, шестой, седьмой,- элементы ИЛИ

38-44, генератор 45 импульсов.

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

Устройство работает следующим образом. умножение четырех пар целых рациональных чисел. При этом сомножители первого произведения заносятся на входные регистры 1 и 2, сомножители второго произведения на входные регистры 3 и 4, сомножители третьего произведения— на нходные регистры 5 и 6, сомножители четвертого произведения — на входные регистры 7 и 8. По первому управляющему входу 18 на блок 17 управления задается первый режим, при котором на 1, 4, 8 и 11 ныходах блока управления появляются сигналы, поступающие на первые управляющие входы соответствующих блоков 9-12 умножения. В результате на их выходах появляются произведения, поступающие на сумматоры 13-16, с выходов которых результаты парных проиэведе ний могут быть направлены на дальнейшую обработку.

Умножение кватернионов или бикватернионон A и В, представленных своими комплекснозначными вычетами с(М

Р и Р, 1Гпо правым идеалам 1, 1+, порожденным парой ассоциированных оснонаний р1, р . Для каждой пары оснований р и р справедлива формула преобразования вычетов множимого

947860

Ф, а(и мнржителя P, P+ в, вычеты у., я произведения АВ

+ (йЕОРЗ " i7rd-"ае p)err ;

10 где (x)q - вычет целого числа х по модулю q в кольце целых рациональных чисел;

q - сумма квадратов коэффиIIpH MHHMHx единицах 1, j k кватерниона р (здесь р — iði).

М

В случае же бикватернионов сумма квадратов коэффициентов лежит в некотором кольце комплексных чисел и имеет вид П+чШс N =-1,0,1, тогда

q есть норма суммы квадратов коэффициентов .в этом кольце, равная г

На входных регистрах 1-4 хран ятся вычеты Red., 3m+ Re + 3m < 25 множимых, на входных регистрах 5-8 вычеты Ref, 3m/, Ве х, Эпф множителя.

По второму управляющему входу

19 на блок 12 управления задается второй режим, при котором в момент 30 на 1,4,8 и 11 выхода блока управления появляются сигналы, поступающие на первые управляющие входы соответствующих блоков 9-12 умножения.

На выходах блоков умножения образу ются модульные произведения (R&Reg) g, (ЭщА11е ) )- q, (-Jmd. Згаp) q, (Real Эт ) q, которые поступают на входы соответствующих сумматоров 13-16. В момент времени tq на втором, пятом, девятом щ и двенадцатом выходах блока управления появляются сигналы, поступающие на вторые управляющие входы соответ.ствующих блокОв 9-12 умножения ° На их выходах получаются модульные, 45 произведения (-3md3 q, (Red3mpi)q (Ве R+")q, (3m Ref) q, после сложения которых с первыми произведениями на сумматорах 13-16 получаются, в соответствии с формулами (1), реальные и мнимые части вычетов произведения кватернионов или бикватернионов по паре ассоциированных оснований.

Умножение двух пар комплексных чисел А, В и A+, В, представленных вычетами aL, p иЫ+ р«по вещественному основанию q..

По третьему управляющему входу 20 на блок 17 управления задается третий режим, при котором в момент t Ь0 на первом, пятом, девятом и одиннадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умноже- Ь5 ния, на выходах которых получаются произведения (ВеаЖе )q, (R 3m/))q, (яеКнВея q, (ВеЫЭв 5 q, поступающие, на входы сумматоров 13-16.

В момент времени t на третьем, шестом, десятом и тринадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умножения. Произведения (3rnd3mP) q, (QmMReP) q, (-DmAnP) q, (Зтс ."Ве 9 q поступают с выходов блоков 9-12 умножения на входы сумматоров 13-16, после сложения на которых получаются реальные и мнимые части вычетов произведений AB и А В аппо вещественному модулю q, в соответствии с известной формулой умножения комплексных чисел (a+bi)(c+di) =(ac-bd)+(ad+bc) i, (2)

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

q, удовлетворяющих условиям теоремы

Гаусса об изоморфизме или умножение четырех пар вещественных чисел.

В этом случае комплексные числа

A, A, B, В представлены вещественными вычетами х (регистр 1), х (регистр 2), х (регистр 3), х (регистр 4), у (регистр 5), у (регистр 6), у> (регистр 7),у> (регистр 8), либо указанные вычеты представляют четыре пары вещественных чисел.

Произведение А В имеет вычеты (x„ )q, (х у )q по основаниям р и р, а произведение А  †(х у )q, (х4у4)Ч по тем же осйованиям. Эти же вычеты имеют произведения вещественных чисел х у„, х у, х у, х у

По четвертому управляющему входу

21 на блок 17 управления задается четвертый режим, при котором на первом, седьмом, девятом и четырнадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умножения, на выходах которых получаются требуемые вычеты произведений (х„ у )g, (x y ) q г (y ) q (х, у4 ) Ч °

Блок управления работает следующим образом.

При подаче сигнала на первый вход (блока, сигнал проходит через элементы ИЛИ 38, 39, 40 и 42 на вторые входы элементов И 22, 25, 30 и 34 и на вход генератора 45 импульсов, на первом и втором выходах которого в моменты 1р и t появляются по одному импульсу. В резулЬтате на первом, четвертом, восьмом и одиннадцатом выходах олока появляются сигналы.

При подаче сигналов на второй, третий и четвертый входы блока управле947860

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

9 ния также каждый раз включается ге нератор 45 импульсов, выдающий на своих первом и втором выходах в мо-менты и у по одному импульсу, ко. торые, прсходя через соответствующие элементы Y. 22-37, появляются на 5 соответствующих выходах блока уп« равления.

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

Устройство для умножения по моду" лю, содержащее четыре входных регистра, четыре блока умножения, два сумматора, выходы которых являются соответственно первым и вторым выходами устройства, входы входных регистров являются соответственно первым, вторым третьим и четвертым входами 25 устройства, выход первого входного регистра подключен к первым входам первого и четвертого блоков умножения, выход второго входного регистра подключен к первыи входам второго и третьего блоков умножения, выходы первого и третьего блоков умножения подключены к первым входам соответственно первого и второго сумматоров, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных

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

Источники информации, прийятые во внимание при экспертизе

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

9 579617 кл, G 06 P 7/52, 1977.

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

9 399859, кл. G 06 EI 7/38, 2974 (про" тотип).