Устройство для умножения чисел по модулю @ Советский патент 1984 года по МПК G06F7/72 

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

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

Недостаток устройства - сложность его построения.

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

Недостаток устройства - сложность построения. Этот недостаток обусловлен тем, что входным шинам коммутатора присвоены значения в диапазоне

Р - 1 1 - , а узлам коммутатора и

2

выходным шинам в диапазоне 1-Р-1 (Р - модуль:) .

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

Поставленная цель достигается тем, что в устройство, содержащее два входных регистра, два дешифратора шесть элементов ИЛИ, два элемента И, две группы элементов И, две группы ключей, сумматор по модулю два, коммутатор, выходной регистр, причем вход первого входного регистра соединен с входом первого операнда устройства, вход второго входного регистра соединен с входом второго операнда устройства, выход первого и второго входных регистров соединены соответственно с входами первого и второго дешифраторов, выходы первого дешифратора соединены с соответствующими входами элементов ИЛИ первой группы, выходы которых соединены соответственно с информационными входами ключей первой группы, управляющи входы которых соединены с управлякнцими входами ключей второй группы и с шиной логической единицы, первые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых Подключены к соответствующим входам сумматора по модулю два,выходы второго дешифратора соединены с соответствующими входами элементов ИЛИ второй группы, выходы которых соединены соответственно с информа-. ционными входами ключей второй группы, выходы которыхсоединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответстветпю с выходами ключей первой группы, первый выход сумматора по модулю два соединен с первым входом первого элемента И, второй выход сумматора модулю два соединен с первым входом втрррго элемента И, выходы первого и второго элементов И соединены с первыми входами соответственно пятог и шестого элементов ИЛИ, выход выхо ного регистра является вьисодом устрой ства, введены третий и четвертый элементы И, причем.управляющий выход коммутатора соединен с запрещав |Щими входами третьего и четвертого . элементов И, со вторьми входами первого и второго элементов И, выхо третьего и четвертого элементов И соединены с вторыми входами соответственно пятого и шестого элементов ИЛИ, .информационные выходы коммутатора, шестого и пятого элементов ИЛИ соединены с соответствующим входами выходного регистра. Сущность изобретения состоит в том, что элементам Ив узлах коммутатора присвоены значения, лежащие в диапазоне Р - 11- -, т.е. результа {операции a;f3;(mod Г) коммутатора определяется в диапазоне от единицы до . При этом результат оперйции A-B(mod. Р) определяется в коде табличного умножения (КТУ), где А ()fc,, а;), В (g, р ) входные операнды устройства Р - 1 .(1 a.i-, )fa(yp индекс КТУ равен О или 1. В предлагаемой схеме модульного умножения используются свойства симметрии арифметической таблицы АВ (mod Р) относительно диагоналей, вертикали и горизонтали Это и определяет возможность реализ ции в схеме модульного умножения . всегй 0,25 части полной арифметичес 1КОЙ таблицы AB(mod Р), т.е. достига ется упрощение устройства. Структурная схема устройства представлена на чертеже. . Устройство содержит входы 1 и 2 первого и второго опера ндов, первый и второй входные регистры 3 и 4, первый и второй дешифраторы 5 и 6 j первую и вторую группы элементов ШШ 7 и 8, .первую и второго группы ключей 9 и 10, коммутатор 11, шину 12 логической единицы, элементы ИЛИ 13-16, сумматор 17 по модулю два, элементы 18-21 И,элементы 22 и 23 ИЛИ, .выходной регистр 24, выход 25 уст.ройства. Коммутатор 11 состоит из элементов И. Количество входных шин в каждой группе входов коммутатора 11 равно количеству выходных шин и . равно 2 Количество элементов И в узлах коммутатора 11 равно VP- if I -- / . В табл. 1 приведены зна г чения АВг (mod Р) для . В табл. 2 приведены зачения а 0, (niod Р), присвоенные соответствукщим узлам коммутатора 11 (,S. 6-- ). М 2 Р - 1 Значения а. р. (mod Р-)Р-1 представляются в виде Р-га (nrod Р) и отмечены в табл. 2 знаком +. Узлы коммутатора 11, которым присвоен одинаковый результат операции a-|j(mod Р), объединяются общей выходной управляющей щиной. Результат операции представлен ниже в КТУ.. Устройство работает следующим образом. Входные операнды А и В по соответствующим входам 1 и 2 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 3 и 4, и далее череё соответствзшэдие дешифраторы 5 и 6. через соответствующую пару элементов ИЛИ 7 и 8 операнды О; и поступают на соответствующую пару ключей 9 и 10. Сигнал шины 12 логической единицы открывает эту пару ключей 9 и 10 и сигналы, соответствующие значениям б, поступают соответственно н первый и второй входы коммутатора 1 Если У о Jf л тогда на нулевом выхо сумматора 17 по модулю два присутствует сигнал, который поступает на первые входы элементов 18 и 19 И. ЕСЛИ на выходной управляющей шине коммутатора 11 отсутствует сигнал, элемент 18 И открыт, и сигнал нулевого выхода сумматора 17 по модулю два через элемент ИЛИ 22 поступает на нулевой вход выходного регистра Если на выходной управляющей шине коммутатора 11 присутствует сигнал то элемент И 19 открыт, и сигнал нулевого выхода сумматора 17 по модулю два через элемент ИЛИ 23 пос тупает на единичный вход выходного регистра 24. Когда сигнал единичного выхода поступает на первые входы элементов 20 и 21И Если на выходной управляющей шине коммутатора 11 отсутствует сигнал, то элемент 20 И открыт, и сигнал единичного выхода сумматора 17 по модулю два через элемент ИЛИ 23 поступает на единичный вход выходно регистра 24. Если на выходной управ ляющей шине коммутатора 11 присутствует сигнал, то элемент И 21 открыт, и сигнал единичного выхода сумматора 17 по модулю два через элемент ИЛИ 22 поступает на нулевой вход выходного регистра 24. Одновре менно результат операции с выхода коммутатора 11 поступает на соответствующий вход выходного регистра 24. Таким образом, в выход ном регистре 24 содержится результа операции АВ (mod Р) в КТУ. Пример. Выполнение.операции АВ (mod Р) для . , . По входу 1 во входной регистр 3 заносится операнд , а по входу 2 во входной регистр 4 заноси ся операнд . С выхода дешифра тора 5 значение поступает на четвертый () элемент ИЛИ 7 и через элемент .ШШ 14 (6-10) на перв единичный вход ( )fо 1) сумматора 17 по модулю Два. С выхода четвертого элемента ИЛИ 7 значение а 4 A(t,4) поступает на четвертый ключ 9. С выхода дешифратора 6 значение поступает на второй .элемент ИЛИ 8 и-через элемент ИЛИ 15 (1-5) на второй нулевой вход (уа 0) сумматора 17 по модулю два. С выхода второго элемента ИЛИ 8 значение А- 2 в(0,2) поступает на второй ключ 10. Сигнал шины 12 логической единицы открывает четвертый 9 и второй 10 ключи и значения aj 4 и . 2 поступают на входы коммутатора 11. С выхода коммутатора 11 значение а и; (mod Р) (табл. 2) поступает на третий вход выходного регистра 24. Так как f (ct ) 1 (mod 2) ,то сигнал единичного выхода сумматора 17 по модулю два поступает на первые входы элементов 20 и 21 И. Сигнал выходной управляющей шины коммутатора 11 (табл. 2, где в узле а( 4,А; 2, цифра 3 со знаком ч-) закрывает элемент 20 И и открывает элемент И 21. Таким образом, сигнал единичного . выхода сумматора 17 по модулю два через элемент И 21, элемент ИЛИ 22 на нулевой вход выходного регистра 24, в котором и содержится результат операции в КТУ АВ (mod Р) (0,3). Проверка (табл. 1 и 2): 72(mod 11) 3. Техническое преимущество изобретения по сравнению с базовым объектом состоит в упрощении устройства. Это достигается: во-первых, за счет Р.- 1 сокращения ( - входовых элементов ШШ, за счет сокращения группы двухвходовых элементов ИЛИ, за счет уменьшения (вдвое) количества выходных шин коммутатора; во-вторых за счет представления результата операции а Д (mod Р) только в диапазоне . Р - 1 1 - ---, значительно упрощается . 2 коммутация узлов в таблице коммутатора. Например, для модуля сокращается приблизительно на 15% количество оборудования. Ожидаемый экономический эффект в результате использования предлагаемого изобретения заключается в уменьшений количества оборудования устройства, уменьшении веса и габаритов, что приводит к уменьшению стоимости устройства в целом.

Таблица 1

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ Р, содержащее два входных регистра, два дешифратора, шесть элементов ИЛИ, два элемента И, две группы элементов И, две группы ключей, сумматор по модулю два, коммутатор, выходной триггер, причем вход первого входного регистра соединен с входом первого операнда устройства, вход второго входного регистра соединен с входом второго операнда устройства, выход первого и второго входных регистров соединены соответственно с входами первого и второго дешифраторов, выходы первого дешифратора соединены с соответствуй)щими входами элементов ИЛИ первой группы, выходы которых соединены соответственно с информационными вхо.дами ключей первой группы, управляющие входы которых соединены с управляющими входами ключей второй группы и с шиной логической единицы, первые и вторые группы, выходов первого и BTOpcfro дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, выходы второго дешифратора соединены с соответствующими входами элементов ИЛИ второй группы, выходы которых соединены соответственно с информационными входами ключей второй группы, выходы котЬрых соединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответственно с выходами ключей первой группы, первых выход сумматора по модулю два i (Л соединен с первым входом первого элемента И, второй выход сумматора по модулю два соединен с первым вхо- . дом второго элемента И, выходы первогЪ и второго элементов И соединены с перQ вьгми входами соответственно пятого С и шестого элементов ИЛИ, выход вы кодного регистра является выходом устройства, о т л и чающееся СО СП, :тем, что, с целью упрощения устройства, в него введены третий и четвертый элементы И, причем управляющий выход кх)Ш1утатора соединен с запрещающими м входами третьего и четвертого эле00 ментов И, с вторыми входами первого и второго элементов И, выходы третьего и четвертого элементов И соединены с вторыми входами соответственно пятого и шестого элементов ИЛИ, информационные выходы коммутатора, шестого и пятого элементов ИЛИ соединены с соответствующими входами выходного регистра.

2

1

2 3 4 5 6 7 8 9 10

4

6

8

10

1

3

5

7

9

1

1 2 3 4 5

2 3

4 5

4

7

6

9

8

5

10

10

8

3

5

9

1

7 5 3 1

4

10

7

2

8

1

6

9

10

2

5

7

8

3

9

2

7

6

8

3

4

9

2

10

5

2

6

9

4

5

8

1

4

7

6

10

9

1

3

3

8

1

6

10

4

2

6

7

4

5

2

1

3

Таблица 2

4

5 И3

3+

5+ 2+ 1 4

4

1

2+

5

3

2+