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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения - упрощение устройства. Устройство содержит дешифраторы 1 и 2, группы элементов ИЛИ 3, 4 и 17, блоки 5 и 6 элементов И, элементы ИЛИ 7 и 8, коммутатор 9, шифратор 10, блок 11 инвертирования, вычитатель 12 по модулю, группы элементов И 13 и 15, сумматор 14 по модулю два и элемент НЕ 16 с соответствующими связями. Сущность изобретения заключается в построении коммутатора 9 путем соответствующего наложения частичных прямых и инверсных таблиц по каждому разряду результата операции с последующим инвертированием по тому разряду результата, где была использована частичная инверсная таблица. 2 ил., 2 табл.

союз сОВетских

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

РЕСПУБЛИК (я)л G 06 F 7/72

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

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

ПРИ ГКНТ СССР

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

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

18 (21) 4652304/24-24 (22) 21.02.89 (46) 23.12,90., Бюл. М 47 (72) С.А.Чарковский, Г,М.Чигасов, В.А.Краснобаев и В.П.Ирхин (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 1095178, кл, G 06 F 7/72, 1983.

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

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

3, 4 и 17, блоки 5 и 6 элементов И, элементы

ИЛИ 7 и 8, коммутатор 9, шифратор 10, блок I1 инвертирования, вычитатель 12 по модулю, группы элементов И 13 и 15, сумматор

14 по модулю два и элемент НЕ 16 с соответствующими связями, Сущность изобретения заключается в построении коммутатора

9 путем соответствующего наложения частичных прямых и инверсных таблиц по каждому разряду результата операции с последующим инвертированием по тому разряду результата, где была использована частичная инверсная таблица. 2 ил., 2 табл.

1615714

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, группу информационных входов 20> — 20, группу управляющих входов 211 — 21 и группу выходов 221 — 222o, Сущность изобретения заключается в построении коммутатора 9 путем соответствующего наложения частичных прямых и инверсных таблиц по каждому разряду результата, где была использована частичная инверсная таблица, Устройство работает следующим образом.

Первый и второй сомножители поступают на соответствующие дешифраторы 1 и 2, с выходов которых операнды в унитарном коде поступают на соответствующие элементы

ИЛИ 3 и 4 первой и второй групп, Сигнал по входу запуска открывает блоки 5 и 6 элементов И, и операнды одновременно поступают на входы коммутатора 9, на выходе которого, подключенном к входу шифратора 10, появляется сигнал, преобразуемый шифратором

10 в двоичный код. Таким образом, на выходе шифратора 10 присутствует промежуточный результат(т,е. без инверсии того разряда, где была применена частичная инверсная таблица соответствующего разряда результата) операции модульного умножения в двоичном коде. Это значение поступает через блок 11 инвертирования на входы соответствующих элементов И 15 первой группы. Результат операции также поступает на вход вычитаемого вычитателя 12 по модулю, на вход уменьшаемого которого поступает значение модуля в двоичном коде, С выхода вычитателя 12 на входы соответствующих элементов И 13 второй группы поступает инвертированное по модулю значение результата операции. Сигналы с выходов дешифраторов 1 и 2 поступают на входы элементов ИЛИ 7 и 8, а с них на суммэтор 14 по модулю два. Выходной сигнал с сумматора

14 по модулю два присутствует, если ур АрР (а и P — операнды). Далее этот сигнал поступает на другие входы элементов И 15 первой группы, Таким образом, сигнал с сумматора 14 осуществляет подачу на входы элементов ИЛИ 17 группы результата операции модульного умножения в двоичном коде либо его инвертированного по модулю значения, Этот результат с выходов элементов ИЛИ 17 группы поступает на выход 18 устройства.

Пусть gai gP;, В этом случае сигнал с выхода сумматора 14 поступает на входы элементов И 13 второй группы, пропуская на выход 18 инвертированное по модулю значение, При gc =)>P сигнал с выхода элемента Н Е 16 поступает на входы элементов И 15 первой группы, на выход 18 поступает неинвертированное по модулю значение результата умножения в двоичном коде.

Рассмотрим пример конкретного выполнения операции модульного умножения для m = 11. В этом случае количество элементов ИЛИ в шифраторе 10 равно четырем.

Пронумеруем их слева направо от трех до нуля, Используем инвертированную таблицу по второму разряду результата операции. В этом случае блок 11 инвертирования состоит из одного элемента НЕ. Выходы остальных элементов ИЛИ шифратора 10 подключены прямо к входам соответствующих разрядов входа вычитаемого вычитателя 12 по модулю. Составим табл, 1, в элементе которой над чертой находится значение результата операции, а под чертой — номера элементов ИЛИ шифратора

10, на входы которых поступает сигнал с соответствующего элемента И коммутатора 9, Табл. 1 составлена с учетом свойств симметрии арифметической таблицы относительно вертикали и горизонтали, npoxom — 1 m+1 дящей между числами 2 и

Чертой сверху обозначены номера элемента ИЛИ шифратора 10, выход которого поступает на элемент НЕ блока 11 ин вертирования.

Обозначим элементы ИЛИ шифратора

10 как 10з, 10z, 101 и 10о, Составим табл. 2, в которой отражены связи выходов 22ькоммутатора 9 с входами соответствующих weментов ИЛИ шифратора (10з, 102, 10> и 10о), В табл. 2 через N обозначены номера входов

1615714 каждого элемента ИЛИ. а через L — элементы ИЛИ. Иначе говоря, на выходах элементов ИЛИ шифратора 10 отображается двоичное представление промежуточного результата операции согласно табл, 1 (без инвертирования второго разряда).

Пусть необходимо определить результат операции модульного умножения для

ai — — 3 Pi =4.

На первый вход устройства поступает число a; = 3, на второй Р; =4. В этом случае на входы сумматора 14 по модулю два сигналы не поступают и с выхода элемента НЕ 16 сигнал поступает на входы элементов И 15 первой группы. При данных операндах, исходя из табл. 1 и 2, образуется сигнал на выходе нулевого и второго элементов

ИЛИ шифратора 10 (сигнал на выходе 22, фиг. 2), но на выходе второго элемента ИЛИ стоит элемент НЕ в блоке 11 инвертирования, поэтому число 1 в двоичном представлении поступает на выход 18 устройства через открытый элемент И t5 первой группы и соответствующий элемент ИЛИ 17 группы.

Проверка; 3 4 (mod 11) = 1, Формула изобретения

Устройство для умножения чисел по модулю, содержащее первый и второй дешифраторы, с первой по третью группы элементов ИЛИ, первый и второй блоки элементов И, первый и второй элементы ИЛИ, коммутатор, шифратор, вычитатель по модулю, первую и вторую группы элементов И, сумматор по модулю два и элемент НЕ, причем входы первого и второго сомножителей устройства соединены соответственно с входами первого и второго дешифраторов, К-й и (m — К)-й выходы первого дешифратора

m — 1 (К = 1 — (— 2 — -), m — значение модуля) соединены соответственно с первым и вторым входами К-го элемента ИЛИ первой группы, выходы элементов ИЛИ первой группы соединены с входами соответствующих разрядов первого входа первого блока элементов И, К-й и (m — К)-й выходы второго дешифратора соединены соответственно с первым и вторым входами К-го элемента

ИЛИ второй группы, выходы элементов ИЛИ

5 второй группы соединены с входами соответствующих разрядов первого входа второго блока элементов И, второй вход которого соединен с вторым входом первого блока элементов И и входом запуска устройства, 10 выходы разрядов первого и второго блоков. элементов И соединены соответственно с группами управляющих и информационных входов коммутатора, группа выходов которого соединена с группой входов шифратора, 15 выхооды элементов И первой группы соединены с первыми входами соответствующих элементов ИЛИ третьей группы, выходы которых являются выходами разрядов выхода устройства, (m — К)-й выход первого дешифратора со20 единен с К-м входом первого элемента ИЛИ, выход которого соединен с первым входом сумматора по модулю два, второй вход которого соединен с выходом второго элемента

ИЛИ, К-й вход которого соединен с (m — К)м

25 выходом второго дешифратора, выход сумматора по модулю два соединен с входом элемента НЕ и первыми входами элементов И второй группы, отл ич а ю щееся тем,что, с целью упрощения устройства, оно содержит

30 блок инвертирования, причем выход шифратора соединен с входом блока инвертирования, выходы разрядов выхода которого соединены с первыми входами соответствующих элементов И первой группы и входами

35 разрядов входа вычитаемого вычитателя IlQ модулю, выходы разрядов выхода которого соединены с вторыми входами соответствующих элемейтов И второй группы, выходы которых соединены с вторыми входами

40 соответствующих элементов ИЛИ третьей группы, выход элемента НЕ соединен с вторыми входами элементов И первой группы, вход задания модуля устройства соединен с входом уменьшаемого вычитателя по модулю.

Таблица 1

1615714

Продолжение табл.1

Таблица 2

Составитель А, Клюев

Редактор О,Юрковецкая Техред М.Моргентал Корректор В Гирняк

Заказ 3988 Тираж 565 Подписное

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

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

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