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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскмкСоциалистическихРеспублик и 947860 В,(61) Дополнительное к авт. свид-ву (22) Заявлено 29.04. 80(21)2935889/18-24 с присоединением заявки М 2935888/18-24 РЦМ.К т. С 06 Г 7/72 Государственный комитет СССР по делам изобретений и открытийОпубликовано 300782. Бюллетень Ю 28 Дата опубликования описания 30.07,82(71) Заявите Институт математик Каза 4) УСТРОИСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛ 10 5 15 муй 5 Устройствс относится к вычислительной технике, а именно. представляет собой устройство для умноженияпо модулю кватернионов, бикватернионов, целых рациональных и комплексных чисел.Известно устройство для умножениясодержащее регистры множимого и множителя, формирователи поправок множимого и множителя, блоки модульногоумножения, блоки деления множимогои множителя, формирователи преобразованного множимого и множителя,регистр памяти, сумматор и соответствующие связи ,11,Однако данное устройство работает только с целыми рациональными числами.Наиболее близким к предлагаемо является специализированное арифметическое устройство для операци с комплексными числами, содержащее регистры реальных и мнимых частей сомножителей, соединенные с формирователями поразрядных произведений и комбинационно-накапливающие сумматоры реальной и мнимой частей произведения, а также блок управления переводом информации в дополнительный код, информационные выходы первого регистра реальной частимножимого соединены с первьыи входами первого и четвертого формирователей поразрядных произведений,информационные выходы первого регистра мнимой части множимого соединены с первыми входами второго итретьего формирователей поразрядныхпроизведений, информационные выходывторого регистра реальной части множителя соединены со вторыми входами первого и второго Формирователейпоразрядных произведений, информационные выходы второго регистра мнимойчасти множителя соединены со вторымивходами третьего и четвертого формирователей поразрядных произведений,знаковые выходы всех регистров сомножителей соединены со входами блока управления переводом информациив дополнительный код,выход которого соединен с третьими входами всехФормирователей поразрядных произведений, выходы соединенных попарнопервого - третьего и второго -четвертого Формирователей поразрядныхпроизведений подключены ко входамкомбинационно-накапливающих сумматоров соответственно реальной и мнимойчастей произведения 23.947860 Недостатком известного устройстваявляется отсутствие возможности выполнять умно)кение кватернионов ибикватернионон.Цель изобретения - расширениефункциональных возможностей устройства за счет выполнения операции умножения над целыми рациональными, атакже кнатернионами и бикватернионами.Поставленная цель достигается тем,0что устройство для умножения по модулю, содержащее четыре входных регистра, четыре блока умножения, два сумматора, выходы которых являются соответственно первым и вторым выходами 15устройства, входы входных регистровявляются соответственно первым,вторым, третьим й четвертым входамиустройства, выход первого нходногорегистра подключен к первым входам 20первого и четвертого блоков умножения, выход второго входного регистраподключен к первым входам второго итретьего блоков умножения, выходыпервого и третьего блоков умножения 75подключены к первым входам соотнетственно первого и второго сумматоров,содержит пятый, ш .стой, седьмой ивосьмой входные р:гистры, входы которых являются соответственно пятым, 30шестым, седьмым и восьмым входамиустройства, третий и четвертый сумматоры, выходы которых являются соответственно третьим и четвертымвыходами устройства, а первые, 35входы подключены к выходам соответственно пятого и седьмого блоков умножения, вторые входы сумматоровподключены к выходам соответственновторого, четвертого, шестого и восьмого блоков умножения, первые входы пятого и седьмого, шестого и восьмого блоков умножения попарно объединены и подключены к выходам соответственно третьего и четвертоговходных регистров, вторые входы первого и восьмого, четвертого и шестого, третьего и пятого, второго иседьмого блоков умножения попарнообъединены и подключены к выходам соответственно пятого, шестого, 50седьмого и восьмого входных регистров. где (х)с 1 - вычет целого числа х помодулю с 1 в кольце целых 55Рациональных чисел;сумма квадратов коэффициентов при мнимых единицах 1, 3, )с кватернионар (здесь р= -1 р).60 В случае же бикватернионов суммаквадратов коэффициентов лежит в некотором кольце комплексных чисели имеет вид П+чш, где Ф 2 может принимать значения 1,0 или -1, тогда 65 я есть норма суммы кнадратон коэфНа фиг.1 представлена блок-схема предлагаемого устройства; на фиг.2 то е; на фиг.З - схема блока управления.Схема (фиг.1). содержит первый, второй, третий, четвертый, пятый, шестой, седьмой и восьмой блоки 1-8 умножения; первый, второй, третий и четвертый сумматоры 9-12; печеный, второй, третий, четвертый, пятый, шестой, седьмой, восьмой входные регистры 13-20. Такое выполнение устройства позноляет осуществлять параллельноеумножение двух пар целых рациональных чисел, а также кватернионов илибикватернионон, заданных комплекснымивычетами по ассоциированному основа"нию.Устройство работает следующимобразом,Умножение двух пар целых рациональных чисел.При этом сомножители первого произведения заносятся на входные регистры 13 и 17. В блоке 1 умноженияформируется произведение, котороепоступает на первый вход первого сумматора 9 и Фиксируется на нем. Сомножители второго произведения заносятсяна входные регистры 15 и 19. В блоке5 умножения Формируется произведение, которое поступает на первыйвход третьего сумматора 11 и фиксируется на нем.Умножение кватернионов и бикватернионов.На входы 17-20 подаются коды соответстненно реальных и мнимых частейВеЫ, Лщс, ВеЫ", Зщос"вычетов К, кфмножимого А по модулям Р, Р", а на нходы 21-24 подаются коды реальных имнимых частей Ве , Зщ , Ве, Эщвычетов , Рмножителя В по модулямР и Р. На выходах блоков 1-8 умножения образуются соответственнопроизнедения (Вес Ве/1),(-Лщо Зщф,дщо/ Кейф Веос, Зщ(Ь, Ве сКеф (-Лщ а"Зщ),ВеФ. Зщ ища(Ве)Ь.После сложения полученных произведений на выходах сумматоров 9-12получаются реальные и мнимые частиВеу, ,)щ; Веуф ,3 щувычетов д).произведения С=АВ сомножителей А иВ согласно Формулам у=(,Рей Кер-дмйзюр),+ Э"= (КЕЬ.КЕ-Зе ( Ъ )с+ф ЬеЭеРфт ЭвсРКе)р,10 35 40 45 50 55 60 65 фициентов в этом кольце, равнаяОф-чфи.Рассмотрим, например, умножениекватеряиона А=1+701-103-1 наВ= -2+401+93+1. Пусть в качествемодуля взяты кватернионы р =1+Э+ЗМ,Р=1-Э-ЗК,Тогда кватернионы А и В имеютсоответственно вычеты-1-31, З=(1+3+3)с)(-141-213+4)с)+(-1-31)Получим, например, вычеты произведения АВ по основаниям р и р.Здесь=-1-31,к=3,=-1,/Ф+31,с 1 = 1 +1 +3 =11.На выходах блоков 1-8 умноженияполучатся соответственно произведения КРс(.ЙЯ(=(-1)(-1) =1; -Эмс 1 ЭмР=-ЭыкЭм =о о=о;984.3 Эти ф= Ъ 3 =9-2. (рлод И)Эс(" 1 еР =о (.-) =о. После сложения получим соответственноВела=1+(-2)=-1Эв= -2+0= вЕе=2+0 = 2Эпф= -2+О = -2,т.е. проиэнедение АВ=(1+701-103-)с)к(-2+401+93+)с)= -2711-1011-813+1033)симеет вычеты -1-21, 2-21, по основаниям р =1+3+31 и р =1-1-31,Цель изобретения может быть такжедостигнута за счет несколько иногосхемного,решения теми же средствами,Можно попарно объединить блоки 1-8умножения. При этом получится четыреблока умножения с более сложной внут-.ренней структурой. Для организацииих использования вводится блок управления, который с помощью управляющихсигналов производит в блоках умножения такую коммутацию информационных входов, которая обеспечивает ихиспользование для операций над различными числовыми конструкциями. Одновременно сумматоры 9-12 иэ комбинационных превращаются в накапливающие, Это приводит к уменьшениюаппаратных затрат за счет замедлениятемпа работы устройства. Оно из однотактного становится двухтактным,15 20 25 30 Блок-схема устройства, представленная на фиг.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, с выходов которых результаты парных проиэведе. ний могут быть направлены на дальнейшую обработку.Умножение кватернионов или бикватернионон А и В, представленных своими комплекснозначными вычетами сМР К и , 1 Гпо правым ицеалам 1, 1 ф, порожденным парой ассоциированных оснонаний р(, р. Для каждой пары оснований р и рсправедлива Формула преобразования вычетов множимого)Огде (х)Ч - вычет целого числа х помодулю Ч в кольце целыхрациональных чисел;Ч - сумма квадратов коэффициентов при мнимых единицах 1, 3, )с кватернионар (здесь р =1 р 1),МВ случае же бикватернионов суммакйадратов коэффициентов лежит в некотором кольце комплексных чисел иимеет вид П+чШс И=-1,0,1, тогдаЧ есть норма суммы квадратов коэффициентов в этом кольце, равнаяг аНа входных регистрах 1-4 хранятся вычеты ВесС, Эщд Вед Зщс 4 ф 25множимых, на входных регистрах 5-8вычеты Ве, Рщ, Ве, Эпфмножителя.По второму управляющему входу19 на блок 12 управления задаетсявторой режим, при котором в момент 30на 1,4,8 и 11 выхода блока управления появляются сигналы, поступающие на первые управляющие входы соответствующих блоков 9-12 умножения.На выходах блоков умножения образуются модульные произведения (ВеВе) Ч,(Эщ Ве Ч, (-щфЭщ ) Ч, (ВеЭщ 5 Ч,которые поступают на входы соответствующих сумматоров 13-16. В моментвремени 1. на втором, пятом, девятом щи двенадцатом выходах блока управления появляются сигналы, поступающиена вторые управляющие входы соответ.ствующих блокОв 9-12 умноженияНаих выходах получаются модульные , 45произведения (-З 1 ЫЭщфЧ, (Ведзщ)Ч(ВеЪе) с 1, (ЭщсфВе) Ч, после сложения которых с первыми произведениями на сумматорах 13-16 получаются, в соответствии с формулами (1),реальные и мнимые части вычетовпроизведения кватернионон или бикватернионов по паре ассоциированныхоснований,Умножение двух пар комплексныхчисел А, В и А, В, представленныхвычетами аС,иск+ рпо нещественному Основанию Ч.По третьему управляющему входу 20на блок 17 управления задается третий режим, при котором в момент ср 60на первом, пятом, девятом и одиннадцатом выходах блока управленияпоявляются сигналы, поступающие насоответствующие управляющие входысоответствующих блоков 9-12 умноже- Ь 5 ния, на выходах которых получаютсяпроизведения (ВесВе)Ч, (ВерОщ/ЦЧ,(ВеКВеЯЧ, (ВеЫЭщ 5 Ч, поступающие,на входы сумматоров 13-16,В момент времени 1 на третьем,шестом, десятом и тринадцатом выходах блока управления появляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умножения. Произведения (ЗЫЭщ) Ч, (ЗпМВе Ч,(-ЭщЛщ) Ч, (Зщс 1 ФВеФ) Ч поступаютс выходов блоков 9-12 умножения навходы сумматорон 13-16, после сложения на которых получаются реальные и мнимые части вычетов произведений АВ и АВпо вещественномумодулю Ч, н соответствии с известной формулой умножения комплексныхчисел(а+Ь 1)(с+с 11) =(ас-Ьс 1)+(ас 1+Ьс) 1, (2)Умножение двух пар комплексныхчисел, представленных вещественнымивычетами по паре сопряженных комплексных оснований р, р с нормойЧ, удовлетворяющих условиям теоремыГаусса об изоморфизме или умножениечетырех пар вещественных чисел,В этом случае комплексные числаА, Аг, Ц, Вг представлены вещественными вычетами х, (регистр 1), х(регистр 6), у (регистр 7),ун (регистр 8), либо указанные вычетыпредставляют четыре пары вещестненных чисел.Произведение А В имеет вычеты(х, У )Ч (хгУг)Ч по основаниЯм Ри р, а произведение А В в (х у )Ч,(х 4 у 4)Ч по тем же осйойаниям. Этиже вычеты имеют произведения вещественных чисел х у, хгуг. хзузх 4 уПо четвертому управляющему входу21 на блок 17 управления задаетсячетвертый режим, при котором на первом, седьмом, девятом и четырнадцатом выходах блока управления поянляются сигналы, поступающие на соответствующие управляющие входы соответствующих блоков 9-12 умножения,на выходах которых получаются требуемые вычеты произведений (х у )Ч,(хгУг) Ч г (хзУз ) Чю (х 4 У 4) ЧБлок упранления работает следующим образом.При подаче сигнала на первый вход(блока, сигнал проходит через элементы ИЛИ 38, 39, 40 и 42 на вторыевходы элементов И 22, 25, 30 и 34 ина вход генератора 45 импульсов, напервом и втором выходах которого нмоменты 1 р и ,появляются по одномуимпульсу. В резулЬтате на первом,четвертом, восьмом и одиннадцатом выходах Олока появляются сигналы.При подаче сигналов на второй, третий и четвертый входы блока упранлеДо 947860 Формула изобретения 9ния также каждый раз включается генератор 45 импульсов, выдающий на своих первом и втором выходах в мо-. ментыи йу по одному импульсу, ко торые, прсходя через соответствующие элементы К 22-37, появляются на 5 соответствующих выходах блока уп равления,Таким образом, введение в состав устройства четырех входных регистров, двух сумматоров, четырех блоков 10 умножения и соответствующих связей позволяет расширить воэможности устройства. Устройство для умножения по модулю, содержащее четыре входных регистра, четыре блока умножения, два сумматора, выходы которых являются соответственно первым и вторым выходами устройства, входы входных регистров являются соответственно первым, вторым, третьим и четвертым входами устройства, выход первого входного регистра подключен к первым входам первого и четвертого блоков умножения, выход второго входного регистра подключен к первью входам второго и третьего блоков умножения, выходы первого и третьего блоков умножения подключены к первым входам соответственно первого и второго сумматоров, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных З 5 11возможностей за.,счет выполнения операции умножения над целыми рациональными. числами, а также кватернионамии бикватернионами, оно содержит пятый,шестой, седьмойи восьмой входныерегистры, входы которых являются соответственно пятым, шестым, седьмыми восьмым входами устройства, третийи четвертый сумматоры, выходы которых являются соответственно третьими четвертым выходами устройства, апервые входы подключены к выходамсоответственно пятого и седьмого блоков умножения, вторые входы сумматоров подключены к выходам соответственно второго, четвертого, щестогои восьмого блоков умножения, первыевходы пятого и седьмого, шестого ивосьмого блоков умножения, попарнообъединены и подключены к выходамсоответственно третьего и четвертого входных регистров, вторые входыпервого.и восьмого, четвертого ишестого, третьего и пятого, второгои седьмого блоков умножения попарнообъединены и подключены к выходамсоответственно пятого, шестого,седьмого и восьмого входных регистров,Источники информации,принятые во внимание при экспертизе 1. Авторское, свидетельство СССР 9 579617 кл, 6 Об Р 7/52 1977,2. Авторское свидетельство СССР 9 399859, кл. 0 06 Р 7/38, 1974 (про" тотип).