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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения - упрощение устройства. Новым в устройстве, содержащем дешифратор 8, две группы элементов ИЛИ 9, 15, элемент ИЛИ 10, два элемента И 20, 21, две группы элементов И 13, 14 и шифратор 16, является введение трех элементов И 3, 4, 17, элемента ИЛИ 7, регистра 11 и коммутатора 12, что дало возможность исключить второй дешифратор и существенно уменьшить количество элементов И в используемом коммутаторе. Сущность изобретения состоит в преобразовании первого и второго операндов из двоичного в унитарный код при помощи одного дешифратора 8 с записью полученного результата (с учетом симметрии арифметической таблицы) в регистр 11 и последующем преобразовании состояния регистра 11 в результате операции A<SP POS="POST">.</SP>B (MODM) (A, B - операнды, M - модуль) с использованием коммутатора 12. 2 ил.

СО 03 СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5п5 G 06 F 7/49, 7/7?

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ о о . V

О (Л (Л (21) 4754343/24 (22) 31.10.89 (46) 30.07,91. Бюл, N 28 (72) О. Н. Фоменко, В,А. Краснобаев, В,П. Ирхин, В.М. Панков, В.Н. Уваров, С.И, Куцый и А.А. Журавлев (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 1126950, кл. G 06 F 7/49, 1983.

Авторское свидетельство СССР

¹ 1187161, кл. G 06 F 7/49, 1984. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения — упрощение устройства. Новым в устройстве, Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов.

Цель изобретения — упрощение устройства.

Сущность изобретения состоит в преобразовании первого и второго операнда из двоичного в унитарный код при помощи одного дешифратора с данного полученного результата (с учетом симметрии арифметической таблицы) в регистр и последующего преобразования состояния регистра в результат операции А - В (mod m) (А,  — операнды, m — модуль) с использованием коммутатора. Рассмотрим табл. 1 операции модульного умножения для m = 7... Ж 1667055 А1 содержащем дешифратор 8, две группы элементов ИЛИ 9, 15, элемент ИЛИ 10, два элемента И 20, 21, две группы элементов И

13, 14 и шифратор 16, является введение трех элементов И 3, 4, 17, элемента ИЛИ 7, регистра 11 и коммутатора 12, что дало возможность исключить второй дешифратор и существенно уменьшить количество элементов И в используемом коммутаторе.

Сущность изобретения состоит в преобразовании первого и второго операндов из двоичного в унитарный код при помощи одного дешифратора 8 с записью полученного результата (с учетом симметрии арифметической таблицы) в регистр 11 и последующем преобразовании состояния регистра 11 в результат операции А х В (mod m) (А, В— операнды, m — модуль).с использованием коммутатора 12. 2 ил.

Отметим, что ввиду симметрии табл. 1 можно изобразить на табл. 2, где в клетках над чертой указаны числа, соответствующие результату операции модульного умножения при )А = )В, а под чертой — при JA )В.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 — структурная схема коммутатора (для m = 7).

Устройство (фиг. 1) содержит вход 1 первого операнда устройства, вход 2 второго операнда устройства, третий 3 и четвертый

4 элементы И, первый 5 и второй 6 управляющие входы устройства, второй элемент

ИЛИ 7, дешифратор 8, первую группу элементов ИЛИ. первый элемент ИЛИ 10, регистр 11, коммутатор 12, первую 13 и вторую

14 группы элементов И, вторую 15 группу элементов ИЛИ, шифратор 16, пятый эле1667055

15

30

40

55 мент И 17, третий управляющий вход 18 устройства, выход 19 устройства, первый элемент И 20, второй элемент И 21, первый

22 и второй 23 триггеры, сумматор по модулю два 24.

Коммутатор 12 (фиг. 2) содержит 25l (i =

1,3) — единичные выходы разрядов регистра

11, 26! (i = 1,3) — нулевые выходы разрядов регистра 11, 27i (! =-1,6) — элементы И 28i(i =

1,6) — выходы элементов И 27).

Рассмотрим работу устройства, Перед началом работы все разряды регистра 11 установлены в нулевое состояние.

По входам 1 и 2 входные операнды в двоичном коде поступают на первые входы соответствующих элементов И 3 и И 4. На первый управляющий вход 5 устройства поступает сигнал и с выхода И 3 операнд А поступает через второй элемент ИЛИ 7 на вход дешифратора 8, с выхода которого через соответствующий элемент ИЛИ первой

9 группы поступает сигнал на один из входов регистра 11, Далее сигнал поступает на второй управляющий вход 6 устройства и операнд В аналогичным образом проходит с выхода второго элемента И и через рассмотренные элементы на один из входов регистра 11. СигHBfl, соответствующий JA ()в)

= 0 проходит через элементы И 4 (3) при подаче сигналов на управляющие входы 5 (6) и запоминается в триггерах 23/22. Затем сумматор 24 по модулю два при JA )в посылает сигнал на вторые входы элементов И первой 13 и второй 14 групп, Выходной сигнал коммутатора 12, соответствующий значению А, В (mod m), в унитарном коде поступает на первые входы

К-ro элемента И 13 группы и К вЂ” го элемента

И 14 групп (К = 1, 2,, „m - 1).

Если JA = JB, то выхоцной аналог сумматора 24 по модулю два отсутствует. Элементы И 13 открыты, а элементы И 14 группы закрыты (на второй запрещающий вход элемента И 13 группы сигнал с выхода сумматора 24 по модулю два не поступает). В этом случае сигнал с выхода К-ro элемента И 13 группы поступает на вход К вЂ” го элемента

ИЛИ 15 группы, с выхода которого сигнал поступает на вход шифратора 16, с выхода которого после подачи сигнал на третий управляющий вход 18 устройства через элемент И 17 поступает на выход 19 устройства.

Если JA < )в, то сигнал с выхода сумматора 24 по модулю два присутствует. Этот сигнал закрывает элементы И 13 группы и разрешает прохождение сигнала с выхода коммутатора 12 через элементы И 14 группы, В этом случае сигнал с выхода К-го элемента И 14 поступает на вход (m — К) — ro элемента ИЛИ 15 группы, Формула изобретения

Устройство для умножения чисел по модулю, содержащее дешифратор, первый элемент ИЛИ, две группы элементов ИЛИ, две группы элементов И„ первый и второй элементы И и шифратор, причем выходы первой группы дешифратора соединены с первыми входами соответствующих элементов ИЛИ первой группы и входами первого элемента ИЛИ, выход которого соединен с входом первого элемента И, выходы второй группы дешифратора соединены с вторыми входами соответствующих элементов ИЛИ первой группы, первые входы элементов И первой и второй групп соединены между собой, а их выходы — с первыми и вторыми входами соответствующих элементов ИЛИ второй группы, от л и ч а ю щ ее с я тем, что. с целью упрощения устройства, в него введены третий, четвертый и пятый элементы И, коммутатор, второй элемент ИЛИ, сумматор по модулю два, два триггера и регистр, причем входы первого и второго операндов устройства соединены соответственно с первыми входами третьего и четвертого элементов И, вторые входы которых соединены соответственно с первым и вторым управляющими входами устройства, а выходы — соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с входом дешифратора, выходы элементов ИЛИ первой группы соединены с соответствующими входами регистра, выходы которого соединены с соответствующими входами коммутатора, выходы которого соединены с первыми входами элементов И первой группы, вторые входы которых соединены с вторыми входами соответствующих элементов И второй группы и выходом сумматора по модулю два, первый и второй входы которого соединены соответственно с выходами первого и второго триггеров, входы которых соединены соответственно с выходами первого и второго элементов И, выход первого элемента ИЛИ соединен с первым входом второго элемента И, второй вход которого соединен с первым управляющим входом устройства, второй управляющий вход которого соединен с вторым входом первого элемента И, выходы элементов ИЛИ второй группы соединены с соответствующими входами информатора, выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с третьим управляющим входом устройства, а выход— с выходом устройства.

1667055

Таблица1

Таблица2

В/А

6

6 г

6

5

2

2

Я.

4 .2

6

2

m — 1

jq ()в)= О. если )<А(В) — —

1, если А(В) < m-1

@+1

1667055

Л Рб В Рбю 25

Составитель Е.Мурзина

Техред M.Ìîðãåíòàë Корректор О.Кравцова

Редактор О,Спесивых

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 2524 Тираж 403 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5