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

.Крас ИЯ ЧИ атике и ыть исинах и истеме ГОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССМ 1095178, кл, 6 06 Р 7/72, 1983.Авторское свидетельство СССМ 951296, кл. 6 06 Р 7/49, 1980,(54) УСТРОЙСТВО ДЛЯ УМНОЖЕСЕЛ ПО МОДУЛЮ(57)Изобретение относится к автовычислительной технике и можетпользовано в вычислительных маустройствах, функционирующих в остаточных классов, Цель изобретения - упрощение устройства. Устройство содержит дешифраторы 1 и 2, группы элементов ИЛИ 3, 4 и 17, блоки 5 и 6 элементов И, элементы ИЛИ 7 и 8, коммутатор 9, шифратор 10, блок 11 инвертирования, вычитатель 12 по модулю, группы элементов И 13 и 15, сумматор 14 по модулю два и элемент НЕ 16 с соответствующими связями, Сущность изобретения заключается в построении коммутатора 9 путем соответствующего наложения частичных прямых и инверсных таблиц по какдому разряду результата операции с последующим инвертированием по тому разряду результата, где была использована частичная инверсная таблица. 2 ил 2 табл.10 15 20 Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов.Целью изобретения является упрощение устройства.На фиг, 1 представлена схема устройства для умножения чисел по модулю; на фиг, 2 - схема коммутатора (для значения модуля, равного одиннадцати).Устройство (фиг. 1) содержит первый и второй дешифраторы 1 и 2, первую и вторую группы элементов ИЛИ 3 и 4, первый и второй блоки 5 и 6 элементов И, первый и второй элементы ИЛИ 7 и 8, коммутатор 9, шифратор 10, блок 11 инвертирования, вычитатель 12 по модулю, вторую группу элементов И 13, сумматор 14 по модулю два, первую группу элементов И 15, элемент НЕ 16, третью группу элементов ИЛИ 17 и выход 18 устройства.Коммутатор 9 (фиг. 2) содержит матрицу элементов И 19, группу информационных входов 201 - 205, группу управляющих вхо- ДОВ 211 - 215 И Группу ВЫХОДОВ 221 - 2220,Сущность изобретения заключается в построении коммутатора 9 путем соответствующего наложения частичных прямых и инверсных таблиц по каждому разряду результата, где была использована частичная инверсная таблица,Устройство работает следующим образом,Первый и второй сомножители поступают на соответствующие дешифраторы 1 и 2, с выходов которых операнды в унитарном коде поступают на соответствующие элементы ИЛИ 3 и 4 первой и второй групп, Сигнал по входу запуска открывает блоки 5 и 6 элементов И, и операнды одновременно поступают на входы коммутатора 9, на выходе которого, подключенном к входу шифратора 10, появляется сигнал, преобразуемый шифратором 10 в двоичный код. Таким образом, на выходе шифратора 10 присутствует промежуточный результат(т,е. без инверсии того разряда, где была применена частичная инверсная таблица соответствующего разряда результата) операции модульного умножения в двоичном коде. Это значение поступает через блок 11 инвертирования на входы соответствующих элементов И 15 первой группы, Результат операции также поступает на вход вычитаемого вычитателя 12 по модулю, на вход уменьшаемого которого поступает значение модуля в двоичном коде, С выхода вычитателя 12 на входы соответствующих элементов И 13 второй группы поступает инвертированное по модулю значение результата операции. Сигналы с выходов дешифраторов 1 и 2 поступают на входы элементов ИЛИ 7 и 8, а с них на суммзтор 14 по модулю два, Выходной сигнал с сумматора 14 по модулю два присутствует, если Уа Уф (Я и ф - операнды), Далее этот сигнал поступает на другие входы элементов И 15 первой группы, Таким образом, сигнал с сумматора 14 осуществляет подачу на входы элементов ИЛИ 17 группы результата операции модульного умножения в двоичном коде либо его инвертированного по модулю значения, Этот результат с выходов элементов ИЛИ 17 группы поступает на выход 18 устройства. Пусть уа )р;, В этом случае сигнал с выхода сумматора 14 поступает на входы элементов И 13 второй группы, пропуская на выход 18 инвертированное по модулю значение,При уа =уф сигнал с выхода элемента Н Е 16 поступает на входы элементов И 15 первой группы, на выход 18 поступает неинвертированное по модулю значение результата умножения в двоичном коде.Рассмотрим пример конкретного выполнения операции модульного умножения для гп = 11. В этом случае количество элементов ИЛИ в шифраторе 10 равно четырем, Пронумеруем их слева направо от трех до нуля, Используем инвертированную таблицу по второму разряду результата операции. В этом случае блок 11 инвертирования состоит из одного элемента НЕ. Выходы остальных элементов ИЛИ шифратора 10 подключены прямо к входам соответствующих разрядов входа вычитаемого вычитателя 12 по модулю. Составим табл, 1, в элементе которой над чертой находится значение результата операции, а под чертой - номера элементов ИЛИ шифратора 10, на входы которых поступает сигнал с соответствующего элемента И коммутатора 9,Табл, 1 составлена с учетом свойств симметрии арифметической таблицы относительно вертикали и горизонтали, прохогп - 1 п 1 +1 дящей между числами иЧертой сверху обозначены номера элемента ИЛИ шифратора 10, выход которого поступает на элемент НЕ блока 11 ин вертирования.Обозначим элементы ИЛИ шифратора 10 как 10 з, 102, 101 и 100, Составим табл. 2, в которой отражены связи выходов 22 ькоммутатора 9 с входами соответствующих элементов ИЛИ шифратора (10 з, 102, 101 и 10 о), В табл. 2 через И обозначены номера входовкаждого элемента ИЛИ. а через- элементы ИЛИ, Иначе говоря, на выходах элементов ИЛИ шифратора 10 отображается двоичное представление промежуточного результата операции согласно табл, 1 (без инвертирования второго разряда).Пусть необходимо определить результат операции модульного умножения для а =3,% =4.На первый вход устройства поступает число а, = 3, на второй Р; = 4, В этом случае на входы сумматора 14 по модулю два сигналы не поступают и с выхода элемента НЕ 16 сигнал поступает на входы элементов И 15 первой группы. При данных операндах, исходя из табл. 1 и 2, образуется сигнал на выходе нулевого и второго элементов ИЛИ шифратора 10 (сигнал на выходе 22 ц, фиг. 2), но на выходе второго элемента ИЛИ стоит элемент НЕ в блоке 11 инвертирования, поэтому число 1 в двоичном представлении поступает на выход 18 устройства через открытый элемент И 15 первой группы и соответствующий элемент ИЛИ 17 группы.Проверка: 3 4 (вой 11) = 1,Формула изобретения Устройство для умножения чисел по модулю, содержащее первый и второй дешифраторы, с первой по третью группы элементов ИЛИ, первый и второй блоки элементов И, первый и второй элементы ИЛИ, коммутатор, шифратор, вычитатель по модулю, первую и вторую группы элементов И, сумматор по модулю два и элемент НЕ, причем входы первого и второго сомножителей устройства соединены соответственно с входами первого и второго дешифраторов, К-й и (щ - К)-й выходы первого дешифраторав - 1(К = 1 - ( - 2 - -), п 1 - значение модуля) соединены соответственно с первым и вторым входами К-го элемента ИЛИ первой группы, выходы элементов ИЛИ первой группы соединены с входами соответствующих разрядов первого входа первого блока элементов И, К-й и (т - К)-й выходы второго .дешифратора соединены соответственно спервым и вторым входами К-го элемента ИЛИ второй группы, выходы элементов ИЛИ 5 второй группы соединены с входами соответствующих разрядов первого входа второго блока элементов И, второй вход которого соединен с вторым входом первого блока элементов И и входом запуска устройства, 10 выходы разрядов первого и второго блоков.элементов И соединены соответственно с группами управляющих и информационных входов коммутатора, группа выходов которого соединена с группой входов шифратора, 15 выходы элементов И первой группы соединеныс первыми входами соответствующих элементов ИЛИ третьей группы, выходы которых являются выходами разрядов выхода устройства, (гп - К)-й выход первого дешифратора со единен с К-м входом первого элемента ИЛИ,выход которого соединен с первым входом сумматора по модулю два, второй вход которого соединен с выходом второго элемента ИЛИ, К-й вход которого соединен с а - К)м 25 выходом второго дешифратора, выход сумматора по модулю два соединен с входом элемента НЕ и первыми входами элементов И второй группы, отл ич а ю щееся тем,что, с целью упрощения устройства, оно содержит 30 блок инвертирования, причем выход шифратора соединен с входом блока инвертирования, выходы разрядов выхода которого соединены с первыми входами соответствующих элементов И первой группы и входами 35 разрядов входа вычитаемого вычитателя помодулю, выходы разрядов выхода которого соединены с вторыми входами соответствующих элемейтов И второй группы, выходы которых соединены с вторыми входами 40 соответствующих элементов ИЛИ третьейгруппы, выход элемента НЕ соединен с вторыми входами элементов И первой группы, вход задания модуля устройства соединен с входом уменьшаемого вычитателя по модулю.45Таблица 1Кор В Гирня зводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 аказ 3988 Тираж 565 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/5