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

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 17. 02. 81 (2 ) 3250557/18-24с присоелинением заявки Ля 3259079/24пв делам изобретеей и отхрытнй(72) Авторы изобретения В. А. Краснобаев и А. В. Королев 71) Заявите 47 УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛПО МОДУЛЮ 1Изобретение относится к вычислитель ной технике и может быть использовано в вычислительных устройствах, работающих в системе остаточных классов.По основному авт. св. Р 922731 известно устройство для. умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а так - же сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входныЕ регистры последовательно через соответствующие первый и второй дешиФраторы, первую и вторую группы элементов ИЛИ и первый и второй ключи подключены соот 15 ветственно к первой и второй группам входов коммутатора, первые и вторые группы входов первого и второго дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управ 2ляющие входы ключей являются входами управления устройства, первая группа выходов коммутатора подключена к входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, к вторым входам которых подключена вторая группа выходов коммутатора и входов одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элемента И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и второго и четвер" того элементов И подключены соответст- " венно к нулевому и единичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам и двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятого, 3 97644 двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входами выходного регистра, выход которого является выходом устройства(1 1.Недостаток устройства - ограниченные функцйональные возможности, связанные с обработкой только положительных чисел.Цель изобретения - расширение функциональных возможностей. 1 ОПоставленная цель достигается тем, что устройство содержит две группы элементов И, четвертую группу элементов ИЛИ, шифратор, сумматор по модулю Р (Р - модуль, по которому работа; И ет устройство), второй сумматор по модулю два, причем выходы знаковых разрядов входных регистров подключены к входам второго .сумматора по модулю два, выход которого подключен к входу р знакового разряда выходного регистра, информационные выходы выходного регистра подключены к соответствующим входам шифратора, выходы которого подключены к первым входам соответствую В щих элементов И первой и второй групп, вторые входы которых соответственно объединены и подключены к первому и второму индексным выходам выходного регистра, выходы элементов И первой груп,1 ы подключены к входам первой группы суммматора по модулю Р, входы второй группы которого объединены. и подключены к входу константы Р устройства, а выходы подключены к первым вхо"дам элементов ИЛИ четвертой группы, вторые входы которых подключены к выходам соответствующих элементов И вто-. рой группы, выходы элементов ИЛЮ, четвертой группы являются информацйонным выходом устройства, выход знакового разряда выходного регистра является знаковым выходом устройства.На чертеже представлена блок-схема устройства.4Устройство содержит входные регистры 1, дешифраторы 2, первую и вторую группы элементов ИЛИ 3, первый, вто-, рой, третий и четвертый. элементы ИЛИпервый сумматор 5 по модулю два, ключи 6, коммутатор 7,шестой, седьмой восьмой, девятый и десятый эдементы ИЛИ 8, выходной регистр 9, пятый и шестой элементы ИЛИ 10, первый, второй, третий и четвертый элементы И 11, двенадцатый и тринадцатый элементы ИЛИ 12, шиФратор 13, первую и вторую группы элементов 14 и 15, суммматор 16. по модулю Р, второй сумматор 17 по 0 фмодулю два, третью группу элементов ИЛИ 18, вход 19 константы Р устройства, выход 20 устройства, знаковый выход 21 устройства.В схеме модульного умножения используется свойства симметрии арифметической таблицы относительно диагонали, вертикали и горизонтали. Это определяет возможность реализации 0,25 части арифметической таблицы коммутатора (табл. У 1, для Р=11).Т а б л и ц а 11 1 2 3 4 52 2 4 6 8 103 3 6 9 1 44 8 1 5 95 5 10 4 9 3Если два числа Х и У заданы по основанию Р в виде табличного умножения х=( 31 х), у=(я ,у ), то для того, чтобы получить произведение этих чисел по модулю Р, достаточно получить произведение ху(пад Р) в коде табличного умножения и инвертировать его индекс в случае, если "Х отлично от Ь Р;-)0 если 0",ЗХ 1 если Р+" сх Р2При реализации операции модульного умножения возможны два основных способа введения знака:- представление чисел в искусственной Форме, т. е. А =А+Р/2- введение знака в явном виде, т.е,.сопровождать число А признакомЯего знака з 1 дп А.Условимся, что, если А Ъ О, то Я А= =О, а если А О, то Я.А=1. В первом способе диапазон ГО, Р) представимых чисел А уменьшается в два раза, так Ркак числа, лежащие в интервале 0, - -1), обозначают отрицательные числа А, а в интервале 1+1), р)- положительные. Это значительно сужает функциональные возможности устройства. Кроме этого, определение знакового признака Я.А Ачисел, представленныхв искусственной форме, вызывает необходимость значительных дополнительных аппаратурных затрат.Наиболее просто реализуется второй способ - введение знака числа А в явном виде. Во-первых, конструктивно9764 5просто реализовать признак ЙА +АтАйво-вторых, диапазон представимых чисел за счет введения признака Йд увеличивается вдвое, И, наконец, при введении знака в явном виде для реалиэа ции операции модульного умножения нет необходимости применять критерий переполнения.АА А А и А+д 1,ф1 ъ 1 А-1 о как в случае сложения.Для модульного умножения признак Я.ддрезультата операции формируется сумматором по модулю два (табл. 2)Таблица 2 А 1 Я.А Я.А+Д 15 0 О 0 0 1 . 1 1 0 1 1 1 0 25 И 14 и 15 первой и второй групп. Если Зо =О, то операнд с выхода шифратора9 через открытые элементы И 15 второйгруппы, элементы ИЛИ 18 поступает навыход 20 устройства. Если у =1, тооперанд через открытые элементы И 15второй группы поступает на первые входы сумматора 16, а на вторые входысумматора 14 поступает знацение константы Р в двоичном коде. С выходасумматора 16 инвертированный по модулю Р операнд, через элементы ИЛИ 18поступает на выход 20 устройства.Таким образом, предложенное устрой Специальный кодтабличного умножения Специальный кодтабличного,умножения Число . Цифра РЗ Йц аЧисло Цифра фО-10 1 1 150 1 0 Формула изобретения У модулц а юрасеитей иных,же по Таким образом, выходной операндпредставляется в специальном кодетабличного умножения (табл, 3).1 Таблица 3 Устроиразом.По входным шинам во входные регистры 1 поступают операнды чисел в двоичном коде, а также признаки Йоперан дов. С регистров 1 операнды поступают на свои дешифраторы 2, а сигналы, соответствующие признаками д - на входы ство работает следующим об 406 сумматора 17. С выходов дешифраторов 2 операнды, в унитарном коде, через элементы ИЛИ 3, ключи 6 поступают на соответствующие входы коммутатора 7. Коммутатор 7 определяет результат операции ху(вод Р), который через элементы ИЛИ 8 поступает на соответствующий вход регистра 9, и одновремен" но поступает на пятый или шестой элемент ИЛИ 4, и далее через первый сумматор 5 по модулю два и определенный элемент И 11, элемент ИЛИ 12 на нулевой или единичный входы регистра 9, определяя индекс ", результата операции. Сигнал нулевого ( Х = 3 у ) или единичного ( Я Ф ф) выхода сумматора 5 поступает на второй вход соответствующего элемента И 11. Сумматор 17 формирует, в соответствии с табл.2, признак Й. , который поступает на знаковый разряд регистра 9. Таким образом, в выходном регистре 9 содержится результат операции модульного умножения в специальном коде табличного умноженияхУ=(Я.Х 3 Х 1 х у(пюд Р, , Операнды регистра 9:,значения от 1 до ) поступают на входы элементов ство обрабатывает по модулю как пол жительные, так и отрицательные числа и выдает результат в двоичном коде, что делает его совместимым со всеми трактами современных ЦВМ. тройство для умножения чисел по ю по авт, св. 11 922731, о т л ищ е е с я тем, цто, с целью рения функциональных воэможнос" утем перемножения как положительтак и отрицательных чисел, а таклуцения результата в двоичном79764коде, устройство содержит две группы элементов И, четвертую группу элементов ИЛИ, шифратор, сумматор по модулю Р (Р -модуль, по которому работает устройство), второй сумматор по модулю два, причем выходы знаковых разрядов входных регистров подключены к входам второго сумматора по модулю два, выход которого подключен к входу знакового разряда выходного регистра, 10 информационные выходы выходного ре" гистра подключены к соответствующим входам шифратора, выходы которого подключены к первым входам соответствующих элементов И первой и второй 3 групп, вторые входы которых соответственно объединены и подключены к первому И второму индексным выходам выходного регистра, выходы элементов И пер 40 8вой группы подключены к входам первойгруппы сумматора по модулю Р, входывторой группы которого объединены иподключены к входу константы Р устройства, а выходы подключены к первымвходам элементов ИЛИ четвертой группы, вторые входы которых подключенык выходам соответствующих элементов Ивторой группы, выходы элементов ИЛИчетвертой группы являются информационным выходом устройства, выход знакового разряда выходного регистра является знаковым выходом устройства,Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР У 922731, кл, С 06 Г 7/49, 1978