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

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

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

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

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

10 второго регистра реальной части множителя соединены со вторыми входами первого и второго формирователей поразрядных произведений, информационные выходы второго регистра мнимой

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

25 первого - третьего и второго -четвертого формирователей поразрядных произведений подключены ко входам комбинационно-накапливающих сумматоров соответственно реальной и мнимой 30 частей произведения t2.

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

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

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

На фиг.1 представлена блок-схема предлагаемого устройства; на фиг.2 то 4® нз фиг.З - схема блока управления.

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

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

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

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

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

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

На входы 17-20 подаются коды соответственно реальных и мнимых частей Real, Jmc, Reo 01П}а вычетов ol, оС множимого А по модулям Р, , а на входы 21-24 подаются коды реальных и мнимых частей Ref, 3mf,, Ref, Dm р вычетов f, р множителя В по модулям Р и Р На выходах блоков 1-8 умножения образуются соответственно произведения (Кео(-НеЭ) , (-Jmo Лт , Omo/Rep, ., Re ., (-Лт ) i3inrf Re.

После сложения полученных произведений на выходах сумматоров 9-12 получаются реальные и мнимые части Re-j, От gr, RegT Отдг вычетов iff произведения сомножителей А и В согласно формулам

7--С Reel Re р - Пип ol :,1п ib )cj, + +(о vfl rit, Re «:-с Re oL DMI fb) „ i;

.ep -Dnio( 3vrif,)cy +

(.ReaL :JKnp U iot ftep)(j,

где (x)q - вычет целого числа x по модулю q в кольце целых рациональных чисел; q - сумма квадратов коэффициентов при мнимых единицах i, j/ k кватерниона р (здесь р -ip). В случае же бикватернионов сумма квадратов коэффициентов лежит в некотором кольце комплексных чисел и имеет вид U+viw, где(/ может принимать значения 1,0 или -1, тогда q есть норма суммы квадратов коэффициентов в этом кольце, равная (V. Рассмотрим, например, умножение кватерйиона A H-70i-10j-k на В -2+40i+9j+k. Пусть в качестве модуля взяты кватернионы р l+j4-3k p l-j-3k. . Тогда кватернионы А и В имеют соответственно вычеты } -1-31, 3J }-, -3+31} Действительно, например 1+701-10j-k {l+j+3k) (-l- -4i-21j+4k) + (-l-3i) . Получим, например, вычеты произведения АВ по основаниям р и р, Здесь се -1-31,3, ,/ -3+31 q 1%1 + . На выходах блоков 1-8 умножения получатся соответственно произведенияReo{.RBp(-|)l--|)-l; -ЭгУ1о1Эм(1 -(iXi)(V)iod«)/ DHici R.)с-)-9 -fi(vMod-i-f); p..-bt-i) -95i(vnoaH-0; HeoLamp-(,-i)(o)-o; -Эгио(.:зи1 0-o-o; Mot D wi p, - г 3 - 9 - 2-C.m od и); 3yn i | e|b-o-C-)-0. После сложения получим соответственноRear- l+(-2)-l Зтз -2 + 2 3mf -2+0 -2, т.е. произведение АВ (1 + 701-10j-k) (-2+401+9j+k) -2711-1011-8Ij+103 имеет вычеты -1-21, 2-21, по основаниям Pf l + j + 3k и р 1-1-3k, Цель изобретения может быть так достигнута за счет несколько иного схемного решения теми же средствам Можно попарно объединить блоки 1-8 умножения. При зтом получится четы блока умножения с более сложной вн ренней структурой. Для организации их использования вводится блок упр ления, который с помощью управляющ сигналов производит в блоках умножения такую коммутацию информацион ных входов, которая обеспечивает и использование для операций над раз личными числовыми конструкциями. Од новременно сумматоры 9-12 из комби национных превращаются в накаплива ющие. Это приводит к уменьшению аппаратных затрат за счет замедлен темпа работы устройства. Оно из од тактного становится двухтактным. Блок-схема устройства, представленная на фиг.2, содержитпервый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой входные регистры 1-8; первый, второй, третий и четвертый блоки 9-12 умножения; первый, второй, третий и четвертый сумматоры 13-16; блок 17 управления, управляющие входы устройства 18-21. Схема блока управления (фиг.З) содержит первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый, десятый, одиннадцатый, двенадцатый, тринадцатый, четырнадцатый, пятнадцатый, шестнадцатый элементы И 22-37; первый, второй, третий, четвертый, пятый, шестой, седьмой,- элементы ИЛИ 38-44, генератор 45 импульсов. Такое выполнение устройства позволяет осуществлять параллельное умножение четырех пар целых рациональных чисел, либо двух пар комплексных чисел, представленных в соответствии с теоремой Гаусса об изоморфизме вещественными вычетами по паре сопряженных оснований, либо умножать две пары комплексных чисел, представленных остатками по вещественному основанию, либо умножать кватернионы либо бикватернионы, заданные комплексными вычетами по ассоциированному основанию. Устройство работает следующим образом. Умножение четырех пар целых рациональных чисел. При этом сомножители первого произведения заносятся на входные регистры 1 и 2, сомножители второго произведения на входные регистры 3 и 4, сомножители третьего произведения на входные регистры 5 и 6, сомножители четвертого произведения - на входные регистры 7 и 8. По первому управляющему входу 18 на блок 17 управления задается первый режим, при котором на1, 4, 8и11 выходах блока управления появляются сигналы, поступающие на первые управляющие входы соответствующих блоков 9-12 умножения. В результате на их выходах появляются произведения, поступающие на сумматоры 13-16, с выходов которых результаты парных произведе НИИ могут быть направлены на дальнейшую обработку. Умножение кватернионов или бикватернионов Л и В, представленных своими комплекснозначными вычетами ot, , правым идеалам 1,1, порожденным парой ассоциированных оснований р, р. Для каждой пары оснований р и р справедлива формула преобразования вычетов множимого (, oi И мнржителя /, в. вычеты , flT произведен и я АВ Т - (лед Re -3wa э«1 р )cj. t -«(у1о111ер 1-ИЫЭ Р)с), ) « РН + lReoL 3 np t: w Ref)«Vi, где {x)q - вычет целого числа х по модулю q в кольце целых рациональных чисел; q - сумма квадратов коэффициентов при мнимых едини цах i, j, k кватерниона , р (здесь ) . В случае зке бикватернионов сумма кйадратов коэффициентов лежит в некотором кольце комплексных чисел и имеет вид U+vo/c ,0,1, тогда q есть норма суммы квадратов коэффициентов -в этом кольце, равная На входных регистрах 1-4 хранятся вычеты Reot, Dm, Reo Jmci множимых, на входных регистрах 5-8 вычеты Rep, Зт(ь, Rep От|Ь множителя По второму управляющему входу 19 на блок 17 управления задается второй режим, при котором в момент t на 1,4,8 и 11 выхода блока управ ления появляются сигналы, поступающие на первые управляющие входы соо ветствующих блоков 9-12 умножения. На выходах блоков умножения образуются модульные произведения (Re3(.Re| pmol-Ref - q, ()q, (, которые поступают на входы соответ ствующих сумматоров 13-16. В момен времени t на втором, пятом, девято и двенадцатом выходах блока управле ния появляются сигналы, поступающи на вторые управляющие входы соотве ствующих блоков 9-12 умножения. На их выходах получаются модульные произведения (-OmciDmjl)q, (ReofOmpJq ()q, pmcJt Re)%)q, после сложения которых с первыми произведениями на сумматорах 13-16 получают ся, в соответствии с формулами (1) реальные и мнимые части вычетов произведения кватернионов или бикватернионов по паре ассоциированн оснований. Умножение двух пар комплексных А, В и А, В, представленны вычетами оС, (ь vidi, вещественн му аснованию q. По третьему управляющему входу на блок 17 управления задается тре тий режим, при котором в момент t на первом, пятом, девятом и одиннадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умноже ния, на выходах которых получаются произведения {Reo(Rep)q, ()q, (, (, поступающие, на входы сумматоров 13-16. В момент времени t на третьем, шестом, десятом и тринадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умножения. Произведения pitWJm/i)q, ()q, (-Jmo/Jmp)q, ()q поступают с выходов блоков 9-12 умножения на входы сумматоров 13-16, после сложения на которых получаются реальные и мнимые части вычетов произведений АВ и А В по вещественному модулю q, в соответствии с известной формулой умножения комплексных чисел (аН-Ы) (c+di) (ac-bd) + (ad+bc)i, (2) Умножение двух пар комплексных чисел, представленных вещественными вычетами по паре сопряженных комплексных оснований р, р с нормой q, удовлетворяющих условиям теоремы Гаусса об изоморфизме или умножение четырех пар вещественных чисел. В этом случае комплексные числа А, Aj./ В , Bg представлены вещественными вычетами х (регистр 1), х. (регистр 2), Хд (регистр 3), х (регистр 4), у (регистр 5), (регистр 6), у (регистр 7) ,у, (регистр 8), либо указанные вычеты представляют четыре пары вещественных чисел. Произведение А В имеет вычеты ()Ч () по основаниям р и р, а произведение (.j)q, (x,y)q по тем же основаниям. Эти же вычеты имеют произведения вещественных чисел х у, у, Xgy, , . По четвертому Sпpaвляющeмy вхЪду 21 на блок 17 управления задается четвертый режим, при котором на первом, седьмом, девятом и четырнадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умножения, на выходах которых получаются требуемые вычеты произведений ()q, (x,)q, (X3y3)q, (X4.y4)q. Блок управления работает следующим образом. При подаче сигнала на первый вход (блока, сигнал проходит через элементы ИЛИ 38, 39, 40 и 42 на вторые входы элементов И 22, 25, 30и34и на вход генератора 45 импульсов, на первом и втором выходах которого в моменты tp и tj появляются по одному импульсу, в результате на первом, четвертом, восьмом и одиннадцатом выходах олока появляются сигналы. При подаче сигналов на второй, третий и четвертьгй входы блока управлеНИИ также каждый раз включается генератор 45 импульсов, выдающий на своих первом и втором выходах в моменты t и tf по одному импульсу, ко торые, преходя через соответствующие элементы К 22-37, появляются на соответствукнцих выходах блока управления. Таким образом, введение в состав устройства четырех входных регистров, друх сумматоров, четырех блоков умножения и cooтвeтcтвsrющиx связей позволяет расширить возможности устройства. Формула изобретения Устройство для умножения по модулю, содержащее четыре входных регист ра, четыре блока умножения, два сумматора, выходы которых являются соответственно первым и вторым выходам устройства, входы входных регистров являются соответственно первым, вторым, третьим и четвертым входами устройства, выход первого входного регистра подключен к первым входам первого и четвертого блоков умножения, выход второго входного регистра подключен к первым входгш второго и третьего блоков умножения, выходы первого и третьего блоков умножения подключены к первым входам соответст венно первого и второго сумматоров, отличающееся тем, что, с целью расширения функционгшьных возможностей за-.счет выполнения операции умножения над целыми рациональными числами, а также кватернионами и бикватернионами, оно содержит пятый, шестой, седьмой и восьмой входные регистры, входы KOTOJMJX являются соответственно пятым, шестым, седьмым и восьмым входами устройства, третий и четвертый сумматоры, выходы которых являются соответственно третьим и че ертым выходами устройства, а первые входы подключены к выходам соответственно пятого и седьмого блоков умножения , вторые входы сумматоров подключены к выходам соответственно второго, четвертого, шестого и восьмого блоков умножения, первые входы пятого и седьмого, шестого и восьмого блоков умножения.попарно объединены и подключены к выходам соответственно третьего и четвертого входных регистров, вторые входы первого и восьмого, четвертого и шестого, третьего и пятого, второго и седьмого блоков умножения попарно объединены и подключены к выходамсоответственно пятого, шестого, седьмого и восьмого входных регистров. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 579617, кл. G 06 F 7/52, 1977. 2.Авто|к:кое свидетельство СССР 399859, кл. G 06 F 7/38, 1974 (прототип)..

Фиг. 1

0- 2fo-

гоо

190-9 180

Фиг. г