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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ОЮ О 1) 315 ц С 06 Р 7/72 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПо ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТН ЦТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ(56) 1. АвторсР 550636, кл.2. АвторскоВ 922731, кл.Спрототип),е свидетельство 06 Р 7/52, 1977. свидетельство СС 06 Р 7/52, 1978 ервоииены иными в управляюс управой группы ы, первые вого ичены соотС 21) 3569036/18-24С 22) 29.03.83С 46) 30.05,84. Бюл. М 20С 72) В,А,Краснобаев, Е.И.БороденВ.И.Стеценко и А.Ю.СеменовС 53) 681.325 С 088.8) С 54)С 57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯЧИСЕЛ ПО МОДУЛЮ Р, содержащее двавходных регистра, два дешифратора,шесть элементов ИЛИ, два элемента И,две группы элементов И, две группы.ключей, сумматор по модулю два,коммутатор, выходной триггер, причемвход первого входного регистра соединен с входом первого операндаустройства, вход второго входногорегистра соединен с входом второгооперанда устройства, выход первого ивторого входных регистров соединенысоответственно с входами первого ивторого дешифраторов, выходы первогодешифратора соединены с соответству 1 о" щнми входами элементов ИЛИ группы, выходы которых сое соответственно с информаци дами ключей первой группы, щие входы которых соединен ляющими входами ключей вто и сшиной логической едини и вторые группы. выходов пе второго дешифраторов подклю ветственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, выходы второго дешифратора соединены с соответствующими входами элементов ИЛИ второй группы, выходы которых соединены соответственно с информационными входами ключей второй группы, выходы которых соединены соответственно с первой группой входов коммутатора, вторая группа входов . которого соединена соответственно с выходами ключей первой группы, первых выход сумматора по модулю два соединен с первым входом первого элемента И, второй выход сумматора по модулю два соединен с первым входом второго элемента И, выходы первого ивторого элементов И соединены с первыми входами соответственно пятогои шестого элементов ИЛИ, выход выходного регистра является выходом устройства, о т л и ч а ю щ е е с ятем, что, с целью упрощения устройства, в него введены третий и четвертый элементы И, причем управляющий выход коммутатора соединен с запрещающими входами третьего и четвертого элементов И, с вторыми входами первого и второго элементов И, выходы третвего и четвертого элементов И соединены с вторыми входами соответственно пятого и шестого элементов ИЛИ, информационные выходы коммутатора, шестого и пятого элементов ИЛИ соединены с соответствующими входами выходного регистра.Изобретение относится к вычислительной технике, и может быть исполь" зовано в системах и устройствах, работающих в системе остаточных классов.Известно устройство для умножения чисел по модулю Р, содержащее входные регистры, дешифраторы, ключевые элементы, коммутатор, выходной регистр, логические блоки поиска квадрата и квадрантов арифметическойтаблицы 1 . 1 О Недостаток устройства - сложностьего построения. 15Наиболее близким по техническойсущности к изобретению является устройство для умножения в системеостаточных классов, содержащее двавходных регистра, два дешифратора, 20шесть элементо ЙЛИ, два элемента И,две группы элементов И, две группыключей, сумматор по модулю два,коммутатор, выходной регистр, причемвход первого входного регистра соединен с входом первого операнда устройства, вход второго входногорегистра соединен с входом второгооперанда устройства, выход первогои второго входных регистров соединены ЗОсоответственно с входами первого ивторого дешифраторов, выходы первого,дешифратора соединены с соответству-,юпими входами элементов ИЛИ первойгруппы, выходы которых соединенысоответственно с информационнымивходами ключей первой группы, управляющие входы которых соединены суправляющими входами ключей второйгруппы и с шиной логической единицы, 4 Опервые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого,второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматорапо модулю два, выходы второго дешифратора соединены с соответствующимивходами элементов ИЛИ второй группы,выходы которых соединены соответственно с информационными входами клю-:чей второй группы, выходы которыхсоединены соответственно с первойгруппой входов коммутатора, вторая группа входов которого соединенасоответственно с выходами ключей пер 55вой группы, первый выход сумматорапо модулю два соединен с первым входом первого элемента И, второй выход сумматора по модулю два соединенс первым входом второго элемента И,выходы первого и второго элементов Исоединены с первыми входами соответственно пятого и шестого элементовИЛИ, выход выходного регистра является выходом устройства. Это устройство осуществляет операцию, умножениячисел по модулю Р в табличном кодеумножения 121 .Недостаток устройства - сложностьпостроения. Этот недостаток обусловлен тем, что входным шинам коммутатора присвоены значения в диапазонеР - 11 - в в в , а узлам коммутатора и2выходным шинам в диапазоне 1-Р(Р - модуль).Цель изобретения - упрощениеустройства,Поставленная цель достигаетсятем, что в устройство, содержащеедва входных регистра, два дешифратора,шесть элементов ИЛИ, два элемента И,две группы элементов И, две группыключей, сумматор по модулю два, коммутатор, выходной регистр, причемвход первого входного регистра соединен с входом первого операнда устройства, вход второго входного регистра соединен с входом второгооперанда устройства, выход первого ивторого входных регистров соединенысоответственно с входами первого ивторого дешифраторов, выходы первогодешифратора соединены с соответствующими входами элементов ИЛИ первойгруппы, выходы которых соединенысоответственно. с информационными входами ключей первой группы, управляющиевходы которых соединены с управляющими входами ключей второй группы и сшиной логической единицы, первые ивторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого, второго,третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два,выходы второго дешифратора соединены ссоответствующими входами элементовИЛИ второй группы, выходы которыхсоединены соответственно с информаЪционными входами ключей второй группы, выходы которыхсоединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответственно сЭ, 10951 выходами ключей первой группы, первый выход сумматора по модулю два соединен с первым входом первого элемента И, второй выход сумматора по модулю два соединен с первым входом второго элемента И, выходы первого и второго элементов И соединены с первыми входами соответственно пятого и шестого элементов ИЛИ, выход выходного регистра является выходом устрой 1 О ства, введены третий и четвертый элементы И, причем. управляющий выход коммутатора соединен с запрещаю-,. ,щими входами третьего и четвертого, элементов И, со вторыми входами 15 первого и второго элементов И, выходы третьего и четвертого элементов И соединены с вторыми входами соответственно пятого и шестого элементов ИЛИ, .инФормационные выходы ком мутатора, шестого и пятого элементов ИЛИ соединены с соответствующими входами выходного регистра.Сущность изобретения состоит в том, что элементам И в узлах комму татора присвоены значения, лежащие в диапазоне Р - 11- - в , т.е. результат21 операции а(пюй Г) коммутатора определяется в диапазоне от единицыР до в в в , При этом результат опера 2ции А В(вод. Р) определяется в коде табличного умножения (КТУ), гдеА = (1 п, а;) В = () - входные операнды устройстваР -41(1 с а с --- У ( ) - индекс КТУф ЧО 402равен 0 или 1. В предлагаемой схеме модульного умножения используются свойства симметрии арифметической таблицы АВ (вод Р) относительно45 диагоналей, вертикали и горизонтали. Это и определяет возможность реализа ции в схеме модульного умножения ,всего 0,25 части полной арифметической таблицы АВ(шой Р), т.е. достигается упрощение устройства.Структурная схема устройствапредставлена на чертеже.Устройство содержит входы 1 и 2первого и второго операндов, первый ,%5и второй входные регистры 3 и 4,первый и второй дешиФраторы 5 и 6первую и вторую группы элементов78 4ИЛИ 7 и 8, .первую и вторую группы ключей 9 и 10, коммутатор 11, шину12 логической единицы, элементы ИЛИ13-16, сумматор 17 по модулю два,элементы 18-21 И,элементы 22 и 23 ИЛИ,,выходной регистр 24, .выход 25 уст,ройства.Коммутатор 11 состоит из эле 4,ментов И. Количество входных шин вкаждой группе входов коммутатора 11равно колйчеству выходных шин иР-;1.равно , Количество элементов Иузлах коммутатора 11 равноРфВ табл. 1 приведены эна 2чения АВ (вод Р) для Р 11.В табл. 2 приведены зачения а, ; (шод Р), присвоенные соответствующим узлам коммутатора 11Р -,1(1 са)2Р Значения ( И Р )(.Р 21 представляются в виде Р-.аи оечены в табл. 2 знаком"+",Узлы коммутатора 11, которым присвоен одинаковый результат операцииа; (шод Р), объединяются общейвыходной управляющей шиной. Результат операции представлен ниже в КТУ. КТУ(0,5) Устройство работает следующим образом.Входные операнды А и В по соответ ствующим входам 1 и 2 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 3 и 4, и далее через соответствующие дешиФраторы 5 и 6, через соответствующую пару элементов ИЛИ 7 и 8 операнды 0; и 3 поступают на соответствующую пару ключей 9 и 10.Сигнал шины 12 логической единицы открывает эту пару ключей 9 и 10 и сигналы, соответствующие значениям а и Й , поступают соответственно на первый и второй входы коммутатора 11, 5 Если 0, тогда на нулевом выходе сумматора 17 по модулю два присутствует сигнал, который поступает на первые входы элементов 18 и 19 И. Если на выходной управляющей шине 10 коммутатора 11 отсутствует сигнал, то элемент 18 И открыт, и сигнал нулевого выхода сумматора 17 по модулюдва через элемент ИЛИ 22 поступает на нулевой вход выходного регистра 24.15 Если на выходной управляющей шине коммутатора 1 1 присутствует сигнал, то элемент И 19 открыт, и сигнал нулевого выхода сумматора 17 по модулю два через элемент ИЛИ 23 пос тупает на единичный вход выходного регистра 24. Когдао Ф, то сигнал единичного выхода поступает на первые входы элементов 20 и 21 И. Если на выходной управляющей шине коммутатора 11 отсутствует сигнал, то элемент 20 И открыт, и сигнал единичного выхода сумматора 17 по модулю два через элемент, ИЛИ 23 поступает на единичный вход выходного 30 регистра 24. Если на выходной управляющей шине коммутатора 11 присутствует сигнал, то элемент И 21 открыт, и сигнал единичного выхода сумматора 17 по модулю два через элемент ИЛИ 22 поступает на нулевой вход выходного регистра 24. Одновременно результат операции а;(шой Р) с выхода коммутатора 11 поступает на соответствующий вход выходного 40 регистра 24. Таким образом, в выходном регистре 24 содержится результат операции АВ (щось Р) в КТУ.П р и м е р. Выполнение операции АВ (шой Р) для Р:11. А=7, В="2. 45По входу 1 во входной регистр 3 заносится операнд А=0111, а по входу 2 во входной регистр 4 заносится операнд В=0010. С выхода дешифратора 5 значение А=7 поступает на . 50 четвертый (4-7=Р) элемент ИЛИ 7 и через элемент .ИЛИ 14 (6-10) на первый единичный вход ( а =1) сумматора 17 по модулю два. С выхода четвертого элемента ИЛИзначение а;= 455 А (1,4) поступает на четвертый ключ 9, С выхода дешифратора 6 1 значение В 2 поступает на второй элемент ИЛИ 8 .и через элемент ИЛИ 15 (1-5) на второй нулевой вход .( = О) сумматора 17 по модулю два, С выхода второго элемента ИЛИ 8 значение2 В-(0,2)1 поступает на второй ключ 10, Сигнал шины 12 логической единицы открывает четвертый 9 и второй 10 ключи и значения а = 4 и1- 2 поступают на входы коммутатора 11. С выхода коммутатора 11 значение а, 3; (тпод Р) (табл. 2) поступает на третий вход выходного регистра 24, Так как о= 1, р = 0 (с, +) = 1 (шос 2)1,то сигнал единичного выхода сумматора 17 по модулю два поступает на первые входы элементов 20 и 21 И. Сигнал выходной управляющей шины коммутатора 11 (табл. 2, где в узле а; = 4,= 2, цифра 3 со знаком "+") закрывает элемент 20 И и открывает элемент И 21. Таким образом, сигнал единичного выхода сумматора 17 по модулю два через элемент И 21, элемент ИЛИ 22 на нулевой вход выходного регистра 24, в котором и содержится результат операции в КТУ АВ (восо Р) = (0,3). Проверка (табл. 1 и 2): 7 2(вос 11)=3.Техническое преимущество изобретения по сравнению с базовым объектом состоит в упрощении устройства. Это достигается: во-первых, за счетР сокращения ( --- входовых элемен 2тов ИЛИ, за счет сокращения группы двухвходовых элементов ИЛИ, за счет уменьшения (вдвое) количества выходных шин коммутатора; во-вторых, эа счет представления результата операции а ; (шой Р) только в диапазонеР 1 - в в в , значительно упрощается2коммутация узлов в таблице коммутатора. Например, для модуля Р=11 сокращается приблизительно на 15% количество оборудования, Ожидаемый экономический эффект в результате использования предлагаемого изобретения заключается в уменьшении количества оборудования устройства, уменьшении веса и габаритов, что приводит к уменьшению стоимости устройства в целом.1095178 Соста тель Л. ЧедведеваА.Ач Корректор С. Иекма ктор 1. Кол ехр Заказ 359 Подписи Филиал ИПП "Патент", г, Ужгород, ул. Проектная, 4 1 Тираж 699ВНИИПИ Государственногпо делам изобретений 13035, Москва, Ж, Рау комитета СССРи открытий ская наб., д, 4/