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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советсиин

Социаяистическик

Республик ((ц 3003086 (61) Дополнительное к авт. свив-ву(51)h4. Кл. (22) Заявлено 09.02.81 (21) 3287557/18-24 с присоелинением заявки ¹ 32505 "9/18-24

G ОЬ F 7/49

Гасударственный каюнтет

СССР (23)Приоритет (53) УДК 681.325 (088,8) Опубликовано 28.02.83. Бюллетень № 8 по делам нзнбрстеннй н нтнрытий

Дата опубликования описания -28 .02 .83

В. А. Краснобаев и А. В; ф)колер...

1,7

Ф (72) Авторы изобретения (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ

Изобретение относится к вычислительной технике.

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

ИЛИ и соответствующие связи (1 J.

Недостаток устройства - большой to объем оборудования.

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

Второй групп ж;>Вщ@х подключены соответствующим взводам.элементов

ИЛИ первой и второй групп, выходы которых подключены к соответству-. ющим входам ключей соответственно первой и второй групп, первые и вторые группы выходов первого и второго дешифраторов подключены со- . ответственно к входам первого и второго, третьего и четвертого элементов ИЛИ, а также и коммутаторов (пу1оц Р; Р - модуль), сумматор по модулю P две группы элементов И, причем соответствующие входы первой ( группы входов коммутаторов объеди" нены и подключены к выходам соот" ветствующих ключей первой группы, со. ответствующие входы второй группы входов коммутаторов объединены и подключены к выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы вы001086 4

3 1 ходного регистра, вторая группа вХодов которого подключена к группе выходов сумматора по модулю Р1 первая группа входов которого подключена соответственно к выходам ключей первой группы, информационные входы которых являются входами ко;да константы Р, а управляющие входы объединены и подключены . к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены к выходам соответственно первого и второго элементов ИЛИ, а вторые входы - к выходам соответственно третьего и чет1вертого элементов ИЛИ, первые входы соответствующих элементов И второй и третьей групп объединены и подключены к соответствующим входам выходного регистра, вторые входы элементов И второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, вторая группа входов сумматора по модулю P подключена к выходам соответствующих элементов

И второй группы, группа выходов элементов И третьей группы является выходом устройства f2 ).

Недостаток устройства - большой объем оборудования..

Цель изобретения - уменьшение объема оборудования.

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

ИЛИ, первый и второй элементы И, сумматор по модулю Р, причем первый и второй входные регистры подключены выходами к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим входам элементов ИЛИ пер вой и второй групп, выходы которых подключены к соответствующим информационным входам ключей соответственно первой и второй групп, управляющие входы которых объединены и являются управляющим входом нумножение" устройства, первые и вторые груп пы выходов первого и второго дешифраторов подключены соответственно к входам первого и второго, третьего и четвертого элементов ИЛИ, одноименные входы первой группы входов Моммутато-. ров объединены и подключены к выходам соответствующих ключей первой. группы, одноименные входы второй группы входов коммутаторов объединены и . подключены к выходам соответствующих ключей второй группы, первые выходы коммутаторов подключены к соответствующим входам выходного регистра, первые входы элементов И первой, второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, вторые входы элементов И первой группы явля— ются вхсдами кода константы Р, а выходы подключены к соответству)ющим входам первой группы сумматора по модулю Р, вторые входы элемен— тов И второй и третьей групп попарно объединены и подключены к соответствующим выходам выходно.-о регистра, выходы элементов И второй группы подключены к соответствующим входам второй группы сумматора по модулю P

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

Основная идея изобретения состоит в том, что результат операции модульного умножения представляется в коде табличного умножения. Это позволяет сократить объем оборудования за счет уменьшения количества коммутаторов (уменьшения количества схем совпадения И таблиц коммутаторов 1 а также за счет исключения из устройства сумматора по модулю Р, так как

086 . 4

Двоичные входные регистры 1 служат. фиксации входных операндов, пред" ставленных двоичным кодом.

Дешифраторы 2 преобразуют двоич,ный код в унитарный, Количество выходных шин дешифратора 2 равно р-1.

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

2 определяет возможность реализации в схеме умножения только 0,25 части табл. 1.

В табл. 1 показана реализация выполнения операции модульного умножения для P=11, где Р- модуль .таблицы.

Т а б л и ц а l

1 2 3 4 5 6 7 8 9 10

1 3 5 7 9

7 10 2 5 8

2 6 10 3 7

8 2 7 I 6

3 9 4 10 5

9 5

10 6 2

7 7 3

8 8 5

2 10 7

Алгоритм получений результата операции модульного умножения определяется так: если два числа А и В заданы по основанию P в коде табличного умножения А=(с,,а), В=(ф, p ), ц то для того, чтобы .получить произведение этих чисел по модулю Р, достаточно получить произведение а f3 (mid P) в коде табличного умножения и инвертировать его индекс Я в случае если

t 50 . Q отлично ото"В,где:

Р-1

О, если О а< -. - - -1

P g

1 если -----< ас P

1 Я

1001 инвертирование по модулю P результата операции, представленного в коде табличного умножения, осуществляется путем инвертирования индекса результата Я, S

На чертеже представлена блок-схема устройства, - Устройство содержит первый и второй входные регистры 1, дешифраторы 2, первую и вторую группы элементов ИЛИ 3 и 4, первую и вторую группы ключей 5 и 6, группу, коммутаторов

7, выходной регистр 8, первую, вторую и третью группы элементов И 9-11, первый, второй, третий, четвертый и пятый элементы ИЛИ l2-$6, первый и второй элементы И 17 и 18, сумматор

19 по модулю Р, сумматор 20 по модулю два, шестой элемент ИЛИ 21, третью группу элементов ИЛИ 22.

2 2 4 6 8 10

3 3 6 9 1

4 4 .8 1 5 9

5 5 10 4 9,3

6 6 l 7 2 8

9 9 . 7 5 3 1

10 10 9 8 7 . 6

4 1 9 6 3

10 8 6 4 Я

5 4 3 2

;р, если ®„/ 1 если $> g.

Основная идея изобретения состоит в том, что узлам коммутаторов присваиваются значения в диапазоне

У-1

1--У---. Это позволяет сократить объ2.. ем оборудования за счет уменьшения количества коммутаторов (уменьшения количества схем совйадения И таблиц коммутаторов)

В качестве примера рассмотрим метод построения таблиц коммутаторов для P=ll. В прототипе реализуется

0,25 части таблицы 1 (см. табл.2).

1001086

8 аб ли ца2

Т

3 1

4 5

10+

6+

1 2

2 4

3 6+

4 8+

9+

9+

5 10+

Таблица4 (1 j

ЯЧ

2 3 4 5

1+ 1+ 1+

1+

1+ 1

5 1

Таблица5

1 1 (5+ 3+ 1+

2+ 1 4

1 5 2+

4 2+ 3

2 4

3 5+

5 1+

2 1

3 1

55

1+ о!

Табли ца6

1 1

1 1+

4 1

1 1 а(1 j г

В узлах, обозначенных знаком (+), результат операции лежит в диапазоне 15

Р В предлагаемом .устройстве значения результата операции, лежащих в диар а1 паэоне -- -----Р-1, инвертируется по модулю Р, т.е. в изобретении реа-, зв лиэуется табл. 3. 1 1 "1

1 1 3 4 5

Если в прототипе необходимо и

1л- коммутаторов, где 2

Н-1р И (для Р=11: п1-"4, и =3) .

Таким образом, в предлагаемом изобретении, например, для Р=11, количество коммутаторов .равно и =3.

Таблицы этих коммутаторов реализуют ответы по каждому иэ и разрядов результата операции модульного умножения. Выпишем такую таблицу для первого (младшего) разряда результата, отметив те квадраты, в которых результат имеет единицу по младшему разряду, и оставив пустыми квадраты с нулевыми значениями младшего разряда результата (табл. 4). Построим аналогичным образом таблицы единичных значений для второго (табл. 5) и третьего старшего разрядов ре зультата (табл. 6).

2 3 4 5

> а 1 г 3 4

В квадратах табл. 4-6, отмеченных знаком (+), указаны те значения разрядов результата операции, который инвертируется по модулю P.

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

В начале работы все разряды регистра 8 устанавливаются в нулевое

10010 состояние. Входные операнды А и В, представленные в двоичном коде, посту пают в входные регистры I. Через соответствующие дешифраторы,2 эти операнды в унитарном коде поступают на определенные соответствующие элементы ИЛИ групп 3 и 4., Управляющий сигнал открывает ключи 5 и 6 групп.

Операнды А и В одновременно поступают на соответствующие входы всех ком-10 мутаторов 7, В тех коммутаторах 7, где определены значения, разряды ре зультата для данных операндов (единица в узлах таблиц),на первых выходных шинах, подключенных к соответст- 1S вующему разряду регистра 8, присутствует сигнал „ Этот сигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние. Одновременно сигналы с выходов дешиф- 20 раторов 3 поступают на два из четырех элементов ИЛИ 12-15.

Пустьф = ф . Если сигнал второй выходной шины коммутаторов 7 отсутствует, что сигнал нулевой в-..ходной рЗ шины сумматора 20 не проходит через закрытый элемент И 18. Операнд регистра 8 (результат операции) че- . рез открытые элементы И 11, элементы ИЛИ 21 поступает на выход устройства, Если сигнал второй выходной шины коммутаторов 7 присутствует, то сигнал нуле.-ой выходной шины сумматора 20 через открытый элемент

И 17, элементы ИЛИ 15 открывает weменты И первой и второй грыппы 9 и 10 и закрывает элемент третьей группы

11. Операнд регистра 8 через открытые элементы И 10 второй группы поступает на второй вход сумматора 19, на первый вход которого через открытые элементы И 9 первой группы поступает значение модуля P в двоичном ко. де.. Инвертированный по модулю Р, ре-зультат операции регистра 8 с выхода сумматора 19,-через элементы ИЛИ 21 поступает на выход устроиства.

Пустьф 4g . Если сигнал второй выходной шины коммутаторов 7 отсутствует, то сигнал единичного выхода

° 50 сумматора 20 через открытый элемент

И 17 через пять!й элемент ИЛИ 16 открывает элементы И .первой и второй групп 9 и 10 и закрывает элемент третьей группы l i . Таким образом, инвертированное по модулю P значение,результата регистра S с выхода сумматора 19 через элементы ИЛИ 21 поступает на выход устройства. Если

86 10 сигнал второи выходной шины коммутаторов 7 присутствует, то элемент

И 17 закрыт..Значение результата опе рации с выхода регистра 8 через открытые элементы И 11, элементы ИПИ 21. поступает на выход Т8 устройства.

Таким образом, введение в состав предлагаемого устройства сумматора по -модулю два элемента ИПИ, группы элементов вЂ И и соответствующих связей приводит к уменьшению объема оборудования коммутаторов и устройств в целом.

Формула . изобретения

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

Р, причем первый и второй входные. регистры подключены выходами к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим вхо" дам элементов ИЛИ первой и второй групп< выходы которых подключены к соответствующим информационным входам ключей соответственно первой и второй групп, управляющие входы которых объединены и являются управляющим входом "Умножение" устройства, первые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого и stoporo, третьего и четвертого элементов ИПИ, одноименные входы первой группы входов коммутаторов объединены и подключены к выходам соответ ствующих ключей первой группы, одноименные входы:второй группы входов коммутаторов объединены и подключены к выходам.. соответствующих ключей второй группы, -первые выходы коммутаторов подключены к соответствующим входам выходного регистра, первые входы элементов И первой, второй, третьей групп объединены и подключены к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, вторые входы элементов И

11 1001086 12

riepeoA группы являются входами кода тьей группы выХоды первого, втоконстанты P а выходы подключены к рого, третьего и четвертого элеменсоответствующим входам первой группы тов ИЛИ подключены к соответствуюсумматора по модулю Р, вторые входы щим входам сумматора по модулю два, элементов И второй и третьей групп Ю единичный и нулевой выходы которого попарно объединены и подключены к подключены к первым входам соответсоответствующим выходам выходного ре. ственно первого и второго элементов гистра, выходы элементов И второй И, вторые входы которых объединегруппы подключены к соответствующим ны и подключены к выходу шестого входам второй группы сумматора по ® элемента ИЛИ, входы которого подмодулю P,:î т л и ч а ю щ е е с я ключены к вторым выходам соответтем, что, с целью сокращения объема ствующих коммутаторов группы. оборудования, оно содержит сумматор Источники информации, по модулю два, шестой элемент ИЛИ, принятые во внимание при экспертизе третью группу элементов ИЛИ, выходы 1$ 1. Авторское свидетельство СССР которых являются. выходом устройства, по заявке У 2675156/18-24, первые входы подключены к соответ- кл. G 06 F 7/49, 1979 ° ствующим выходам сумматора по модулю . 2. Авторское свидетельство СССР

Р, вторые входы подключены к выхо- . по заявке Ю 2916541/18-24 дам соответствующих элементов И тре- 2в кл. G 06 F 7/72, 1980 (прототип).

1001086.

ВНИИПИ Заказ 1396/55

Тираж 704 Подписное

Филиал ППП "Патент", г.Ужгород,ул.Проектная,4