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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ,четыре группы элементов И,табличный вычислитель значений вида а . (mod Р/2)+Р/2 пять элементов ИЛИ, два элемента И и шифратор, причем входы первого и второго операндов устройства соединены соответственно с входами первого и второго входных регистров, выходы которых соединены соответственно с входам первого и второго дешифраторов, первые группы выходов которых соединены соответственно с первыми входами элементов ШШ первой и второй групп и входами первого и второго элементов ИЛИ, а вторые группы выходов - с вторыми входами элементов ИЛИ первой и второй групп и входами третьего и четвертого элементов ИЛИ соответственно, выходы первого и четвертого элементов ИЛИ соединены соответственно с первым и вторым входами первого элемента И, выход которого соединен с первым входом пятого элемента ИЛИ,второй вход которого соединен с выходом второго элемента И, первый и второй входы которого соединены соответственно с выходами второго и третьего элементов ИЛИ, выходы элементов ИЛИ первой и второй групп соединены соответственно с первыми входами элементов И первой и второй , групп, вторые входы которых соединены с входом управления устройства, а выходы - соответственно с пер (Л вой и второй группами входов табличного вычислителя значений вида (mod Р/2)+Р/2, выходы которого соединены соответственно с первыми входами элементов И третьей и четвертой групп, вторые входыкоторых соединены с выходом пятого элемента ИЛИ, а выходы - с первыми и вторыми входами элементов ИЛИ третьей группы, отличающееся ON тем, что, с целью упрощения, в него введен выходной регистр, информационные входы которого соединены с выходами элементов ИЛИ третьей группы, а выходы - с входами шифратора, выход которого соединен с выходом устройства.

СОЮЗ СОВЕТСНИХ

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

PECflVBJlHH (19) (11) (51)4G 06 F 7 49

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3742043/24-24 (22) 16.05.84 (46) 23.10.85. Бюл. 9 39 (72) О.Н. Фоменко, В.А. Краснобаев, В.Н. Уваров и В.А. Каревский (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 981990, кл. G 06 F 7/49, 1981.

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

В 1030799, кл. G 06 F 7/49, 1982. (54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

ЧИСЕЛ ПО МОДУЛЮ, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ,четыре груп- пы элементов И,табличный вычислитель значений вида a / . (mod P/2)+P/2> пять элементов ИЛИ, два элемента И и шифратор, причем входы первого и второго операндов устройства соединены соответственно с входами первого и второго входных регистров, выходы которых соединены соответственно с входами, первого и второго дешифраторов, первые группы выходов которых соединены соответственно с первыми входами элементов ИЛИ первой и второй групп и входами первого и второго элементов ИЛИ, а вторые группы выходов — с вторыми входами элементов ИЛИ первой и второй групп и входами третьего и четвертого элементов ИЛИ соответственно, выходы первого и четвертого элементов ИЛИ соединены соответственно с первым и вторым входами первого элемента И, выход которого соединен с первым входом пятого элемента ИЛИ,второй вход которого соединен с выходом второго элемента И, первый и второй входы которого соединены соответственно с выходами второго и третьего элементов ИЛИ, выходы элементов ИЛИ первой и второй групп соединены соответственно с первыми входами элементов И первой и второй, групп, вторые входы которых соединены с входом управления устройства, а выходы — соответственно с первой и второй группами входов табличного вычислителя значений вида а f3 (mod Р/2)+Р/2, выходы которого соединены соответственно с первыми входами элементов И третьей и четвертой групп, вторые входы которых соединены с выходом пятого элемента ИЛИ, а выходы — с первыми и вторыми входами элементов ИЛИ третьей группы, о т л и ч а ю щ е е с я тем, что, с целью упрощения, в него введен выходной регистр, информационные входы которого соединены с выходами элементов ИЛИ третьей группы, а выходы — с входами шифратора, выход которого соединен с выходом устройства.

1187161

6 0 6 -1 13 1

1 6

Изобретение относится к- вычислительной технике и может быть исполь. з ов ано в системах и устройствах, функционирующих в системе остаточных классов . 5

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

На чертеже представлена структурная схема устройства для умножения чисел по модулю. 10

Устройство содержит первый 1 и второй 2 входы устройства, первый 3 и второй 4 входные регистры, первый 5 и второй 6 дешифраторы, три группы элементов ИЛИ 7-9, четыре . 15 группы элементов И 10-13, вход 14 управления устройства, пять элементов ИЛИ 15-19, два элемента И 20 и 21, табличный вычислитель 22 значений вида à P (mod Р/2)+Р/2, выход- 20 ной регистр 23, шифратор 24, выход 25 устройства.

Шифратор 24 служит для преобразования операндов унитарного кода 25 в двоичный.

Табличный вычислитель 22 представляет собой двухвходовое ПЗУ.

Количество элементов И в узлах табличного вычислителя 22 равно

P-2 2 () где P — - модуль умножения.

Входные операнды устройства лежат в интервале 1 6 А, В « Р-1 таблич(/ ного вычислителя, а входные операн- 35 ды табличного вычислителя 22

Р-г

1 а Я (—.

Известно, что для операндов, представленных в искусственной форме

A = А + P/2, В = В + P/2, резуль-. тат операции модульного умножения представляется в виде (А В) = А В

/ или (А В) = А В +Р/2. В предлагаемом устройстве табличному вычислителю 22 присваиваются значения а Р (mod P/2)+Р/2, представленные в табл.1.

Такое кодирование позволяет не- 50 посредственно установить взаимно однозначное соответствие между кодами чисел в искусственной форме и кодами чисел в обычном представлении.

В табл.1 знаком (+) отмечены случаи, 55 когда (а 3) = а /3 (mod P).

B табл.2 представлены операнды в искусственной форме для P = 14.

Т а б л л ц а 1 (Р=14)1

1 13 8 9 10 11 12 13

2 12 9 11 13 8+ 10+ 12+

3 11 10 13 9+ 12+ 8 11

4 10 11 8+ 12+ 9 13 10+

5 9 12 10+ 8 13 11+ 9

6 8 13 12+ 11 10+ 9 8+

Таблица 2 (Р=14) ((((А fA а А А gA а А

1 0 1 -6 8 1 6 1

2 0 2 -5 9 1 5 2

3 0 3 -4 10 1 4 3

4 0 4 -3 11 1 3 4

5 0 5 -2 12 1 2 5

Таким образом, при реализации операции модульного умножения в предлагаемом изобретении происходит самокоррекция результата операции за счет внутренней структуры таблицы вычислителя 22 (таблица 1). Количество входных шин в каждой группе

P-2 входов вычислителя 22 равно, а выходных шин - (Р-1) .

Дешифраторы 5 и 6 имеют две группы выходов, каждая из которых включает в себя соответственно

P-2 Р+2 (1 — — ) и (— — Р-1) выходов.

2 2

Устройство для умножения по модулю работает следующим образом.

По входам 1 и 2 входные операнды А и В в двоичном коде постуI лают на соответствующие входные регистры 3 и 4, с выходов которых поступают на соответствующие дешифраторы 5 и 6. С выходов дешифраторов 5 и 6 операнды А и В в деся/

3 1 тичном коде поступают на соответстствующие элементы ИЛИ 7 и 8, с выходов которых операнды а и /3 (А =

=(gА, а ), В = (, P )) через элементы И 10 и 11 групп, которые одновременно открываются сигналом 14, поступают на входы табличного вычислителя 22. Выходной сигнал табличного вычислителя 22, соответствующий значению а P (mod Р/2)+P/2, поступает на первые входы К-го элемента И 12 группы и К-го элемента И 13 группы (К = 1,2,...,Р-1).

Если = 4 то элементы И 20 и 21 закрыты и выходной сигнал элемента ИЛИ 19 отсутствует. Элементы И 12 группы открыты, а элементы И 13 группы закрыты (на первый запрещающий вход элемента И 12 группы сигнал с выхода элемента ИЛИ 19

187161 4 не поступает). В этом случае сигнал с выхода К-го элемента И 12 группы поступает на вход К-ro элемента ИЛИ

9 группы, с выхода которого сигнал поступает на вход регистра 23 и далее поступает на шифратор 24, с выхода которого результат операции модульного умножения в двоичном коде поступает на выход 25 устрой1р ства.

I I

Если gA 4 fs,òî сигнал с выхода элемента ИЛИ 19 присутствует. Этот сигнал закрывает элементы И 12 группы и разрешает прохождению сигнала с выхода табличного вычислителя 22 через элементы И 13 группы. В этОм случае сигнал с выхода К-го элемента И 14 поступает на вход (P-К)-ro элемента ИЛИ 9 группы.

Филиал ППП Патаитг, г. Улгорол, ул.Проаатиаа,4

ВИИИПИ Заказ 6551/54 Тираж 709

Подписное