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

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

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

Цель изобретения - расширение функциональных возможностей за.счет выполнения операции сложения.

Поставленная цель достигается тем, что устройство, содерлсащее входные регистры, дешифраторы, первую группу элементов И, первый коммутатор, сумматор по модулю два, группы ключей, группы элементов ИЛИ, элементы ИЛИ, выходной регистр, при этом первый и вторрй входные регистры последовательно через соответствукнцие первый и второй дешифраторы, первую и вторую группы элементов ИЛИ, первую и вторую группы ключей подключены ко входам первого коммутатора , первые и вторые группы выходов первого и второго деамфраторов подключены соответственно ко входам первого и второго, третье О и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управляюо ие входы ключеЯ первой и второй групп соединены между собой и являются управлякадим входом устройства, нулевой и единичный выходы сумматора по модулю два соединены соответственно с первыми входами первого, третьего и второго, четвертого элементов И первой группы, выходы первого и четвертого элементов И первой группы соединены со входами пятого элемента ИЛИ, а выходы второго и третьего элементов И первой группы соединены со входами шестого элемента ИЖ, вторые входы первого и второго элементов И первой группы соединены между собой и с выходом элемента ИЛИ, вторые входы третьего и четвертого элементов И первой группы соединены между собой и с. выходом восьмого элемента ИЛИ, содержит вторую, третью, четвертую и группы элементов И, третью rpjfeny элементов ИЛИ, шесть элементов И, два элемента И-НЕ, второй коммутатор, третью группу ключей, причем первая и вторая группы выходов первого коммутатора подключены соответстйенно к первым входам элеuteHTOB И четвертой и пятой групп, выходы 1 -ых и tP-i)7bix ключей первой и второй групп (1 1,2,. ...,Р-1; Р - модуль) подключены ко входам

соответствующих ключей третьей группы, выходы которых подключены ко входам второго коммутатора, первая и вторая группы --(/2 выходов которого подключены к первым P--f/2 входам соответственно седьмого и восьмого элементам ИЛИ, выходы 1 -ых и {P-i)a элементов И четвертой группы подключены соответственно к первым .и вторым входам элементов ИЛИ третьей группы и ко вторым P-f/2 входам седьмого и восьмого элементов ИЛИ, выходы -I-bix и (Р-1)-ых элементов И пятой группы подключены соответственно к третьим и четвертым входам-элементов ИЛИ третьей группы и к третьим P-f/i входам седьмого и восьмого элементов ИЛИ,(1-2)-ые и (Р-)-ые выходы второго коммутатора подключены соответственно к пятым и шестым входам соответствующих элементов ИЛИ третьей группы, выходы которых подклчены, к первым Р входам выходного регистра, первые входы элементов И второй и третьей группы объединены и подключены соответственно к выхода пятого и шестого элементов ИЛИ, управляющие входы ключей третьей группы объединены и подключены к выходу первого элемента И, к первому входу второго элемента И, ко вторым входам первого и четвертого элементов И, соответственно, второй и третьей групп вторые входы вторых элементов И второй и третьей, и пятой групп объединены и являются Умножение устройства, вторые входы третьих элементов И второй и третьей групп и первый вход третьего элемента И объединены и подключены к вькоду четвертого элемента И; первый вход которого подключен к первому входу пятого элемента И ко второму входу первого элемента И и является входом Сложение устройства, вторые входы четвертого элемента И второй группы и первого элемента И третьей группы объединены и подключены к выходу третьего элемента И, второй вход которого объединен со вторыми входами элементов И четвертой группы и подключен к выходу пятого элемента И, второй вход которого подключен к нулевому выходу сумматора по модулю два, выходы первого, второго, четвертого элементов И второй группы и выход третьего элемента И третьей группы подключены ко входам девятого элемента ИЛИ, выход которого подключен к первому входу первого элемента И-НБ, выходы третьего элемента И второй группы и первого, второго, четвертого элементов И третьей группы подключены ко входам десятого элемента ИЛИ, выход которого подключен к первому входу второго элемента И-НЕ, выходы первого и второго элементов И-НЕ подключены соответственно к ;(1Н-1;-му и (Р+2)му входам выходного регистра, вторые

входы первого и второго элементов И-НЕ объединены и подключены к выходу второго элемента И, вход Шестого элемента И подключен к выходу четвертого элемента ИЛИ, вторые входы второго и шестого элементов И объединены и подключены к выходу второго элемента ИЛИ, выход шестого элемента И подключен KCJ второму входу четвертого элемента И.

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

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

Таблица 1

Таблица 3

2

4

5

3

3

6

5

4

4

7

5

б

5

7

8

б

6

8

9

7

7

8

10

9

10

О

9

8

10

1

9

О

1

2

10

О

О

2

1

3 Это и определяет возможность регш эации в схеме табличного сложения только 0,5 части табл.3 при условии что операция модульного сложения выполняется в специальном коде умножения. Определены номера квадрантов ариф метической таблицы: (II IV III На чертеже представлена блок-схем предлагаемого устройства. Устройство содержит входные регистры 1, дешифраторы 2, первая и третья элементов ИЛИ 3,4 и 5 первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый и десятый элементы ИЛИ 6-15, первая, вторая и третья группы ключей 16, 17 и 18, первый и второй коммутаторы 19 и 20, первая, вторая третья, четвертая и пятая группы эле ментов И 21-25, сумматор 26 по моду лю два, первый, второй, третий, четвертый, пятый и шестой элементы И 27-32, первый и второй элементы И-НЕ 33 и 34, выходной регистр 35. Первый коммутатор 19 определяет результат модульного умножения табл и операции модульного сложения для VI и ff квадрантов табл.3 (т.е. для 0Тс 1 Г|} 1) В зависимж:ти от кода операции (умножения или сложения) первый коммутатор 19 определяет результат модульного умножения или сложения, т.е. первый коммутатор совмещает выполнение дву операций. Первая и вторая группы выходов первого коммутатора 19 определяют результат модульного умножения, при чем первая группа выходов определяет значения 14- а вторая

8 9

О 1 2 3 4 5 б 7 8 9

9

10

10

О

10

1

О

0

О

1

2

1

2 3 4 5 б 7

3

4

2

3

5

4

б

7

5

8

б PV-f . Третья и четвертая группы в ходов первого коммутатора 19 определяют результат модульного сложе- ния для И и IV квадрантов табл.3, причем третья группа .выходов определяет значение Yf 12 i s чет.вертая .fp,- -1. - Величины О к Р не кодируются, так как при умножении на эти величины результат равен нулю, и в этом случае операция выполняется быстрее простым анализом операндов, при сложении с этими величинами значение второго операнда не изменяется, он и определяет результат операции, при определении результата операции со второго коммутатора ( I , III квадранты выходная шина, объединяющая элементы И, которым присвоен результат модульного сложения О и Справая диагональ табл. З; , подключается непосредственно к выходу устройства. При необходимости значения О и могут быть также включены в табл.2. Второй коммутатор 20 определяет результат модульного сложения для I и III квадрантов (табл.3 . Первая группа выходов второго коммутатора определяет значения-ffp -- /, а вторая R,4- f/2fP --f . Первый 19 и второй 20 коммутаторы (матрицы ответов; представляют набор элементов И. Количество элементов И кгивдого коммутатора равно )/ Элементы И, которым присвоен одинаковый результат операции, объединяются выходной шиной. В коммутаторах осуществляется операция в унитарном коде. Результат операции также представляется в унитарном коде. Количество выходных шин второго коммутатора 20 равно Р,-1, он определяет результат модульного

сложения для | и щ квсэдрайтов. Первая группа выходов объединяет ишны, которым .присвоен результат модульного сложения -f p ---;/, а вторая группа PI + -/ /2 т PI - (

Количество выходных шин первого коммутатора 19 равно 2-(Pj-l)f так как коммутатор 19 определяет результат модульного умножения (первая и вторая группы выходов.определяют, соответственно, . .значения .и Rf -f/2.fR,--f для умножения) и. результат модульного сложения для .11 и IV квадрантов (третья и четвертая группы выходов определяют, соответственно, значения

f - P-j-i 12 и PI --f/if PV - для сложения ;.

Таким образом, каждому элементу И коммутатора 19 присваивается два значения: результат модульного умножения и результат модульного сложения (для И и IV квадрантов).

Количество элементов первой и ; второй, и третьей групп элементов ИЛИ 3, 4 и 5 равно Pi--f/2 в каждой группе. Количество элементов И четвертой 24 и пятой 25 групп элементов И равно -1 в каждой группе.

Выход элемента ИЛИ 14 определяв ет значение Т 1 а выход элемента ИЛИ .

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

Первый режим работы - определение результата модульного умножения. На входные регистры 1 заносятся операнды и последовательно через дешифраторы 2, группы элементов ИЛИ 3 и 4 и .группы ключей 16 и 17 поступают на коммутатор 19. Ключи 16 открываются сигналом с управляющего входа устройства. Одновременно присутствует сигнал Умножение устройства. Выходной сигнал коммутатора 19 через один из элементов И 25 пятой- группы поступает на один из шести входов определенного элемента ИЛИ 5 третьей группы. С выхода этого элемента сигнал поступает на соответствующий вход выходного регистра 35. Элементы 12, 13, 21, 10, 11, 22, 23, 14, 15, 33 и 34 служат для опре 1еления индекса -J- в записи результата модульной операции. Коммутатор 20 закрыт, так как отсутствует сигнал Сложение устройства.

Второй режим работы - определение результата операции модульного сложения для И и IV квадрантов таблицы модульного сложения ( т.е. 5|, 0 и Уа . В этом случае сигнал Сложение устройства присутствует. Коммутатор 20 закрыт, так как отсутствует сигнал с единичного выхода сумматора 26 по модулю г О ) / элемент И 27 закрыт, и, следовательно, ключи 18 третьей груп

пы закрыты. Группа элементов И 25 пятой группы закрыта (отсутствие сигнала Умножение устройства. Выходной сигнал коммутатора 19 по третьей и четвертой группам выходов (по с одной из шин этих групп) через один из элементов И 24 четвертой группы, элемент ИЛИ 5 третьей группы поступает на выходной регистр 35.

Третий режим работы - определе- ние результата операции модульного .; сложения для | и Й{ квадрантов таблицы модульного сложения (т.е. для

Го 0 Гг% 1 и Гр. 0 Сигнал Сложение устройства присутствует, а сигнал Умножение устройства отсутствует. Коммутатор 20 открыт, а на выходных шинах коммутатора 19 отсутствует выходной сигнал, так как элементы И 24 и 25 четвертой и пятой групп закрыты. Ключи 18 третьей группы открыты (на выходе элемента И 27 присутствует сигнал) и коммутатор 20 определяет результат модульного сложения для I и IU квадрантов. Для -jfg 1, ff 0 значение индекса -у в записи результата модульного сложения определяется с выходов элементов ИЛИ 14 и 15. , (1 значение дг определяется инвертированием выходных сигналов элементов ИЛИ 14 и 15.

Таким образом, изобретение совмещает выполнение операций модульного умножения и Сложения в коде табличного умножения (табл.2). При этом таблица реализукяцая операцию умножения, может быть конструктивно уменьшена в четыре раза, а таблица, реализующая операцию сложения - в два раза. Если для реализации операции умножения и сложения без применения

0 специального кода умножения необходимо 2 (Р - }-элементов табл.1 и 3, то с применением кода (табл. 2) .-(В,-)/2 элементов таблиц. При применении специального кода умножения сокращается

5 также количество элементов входных, выходных регистров и дешифраторов.

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

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

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

группы выходов первого и второго дешифраторов подключены соответственно ко входам первого и второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим- входам сумматора по модулю два, управляющие входы ключей первой и второй групп соединены между собой и являются управляющим входом устройства, нулевой и единичный выходы сумматора по модулю два соединены со ответственно с первыми входами перво го, третьего и второго, четвертого элементов И первой группы, выходы пе вого и четвертого элементов И первой группы соединены со входами пятого элемента ИЛИ, а выходы второго и третьего элементов И первой группы соединены со входами шестого элемента ИЛИ, вторые входы первого и второго элементов И первой группы соеди нены между собой и с выходом седьмого элемента ИЛИ, вторые входы третье го и четвертого элементов И первой группы соединены между собой и с выходом восьмого элемента ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции сложения, оно содержит вторую, третью, четвертую и пятую группы эле ментов И, третью группу элементов ИЛИ, шесть элементов И, два элемента И-НЕ, второй коммутатор, третью группу кличей, причем первая и вторая группы выходов первого коммутатора подключены соответственно к пер вым входам элементов И четвертой и пятой групп, выходы 1-ых и ( ключей первой и второй групп (-i 1, 2,...,Р-1; Р - модуль) подключены ко :входам соответствуквдих ключей третьей группы, выходы которых подключены ко входам второго коммутатора, первая и вторая группы 0. выходов которого подключены к первым Р-у) /2. входам соответственно седьмого и восьмого элементов ИЛИ, выходы .1 -ых и (Р- -1 f-ых. элементов И четвертой группы подключены соответственно к первым и вторым входам эле ментов ИЛИ третьей группы и ко вторым Р- 4 (2. входам седьмого и вось мого элементов ИЛИ, выходы -f -ых и СР- ()-ых элементов. И пятой группы подключены соответственно к третьим и четвертым входам элементов ИЛИ третьей группы и к третьим P-l/i входам седьмого и восьмого элементов ИЛЙ,(|-2)-ые и (Р-1)-ые выходы второго коммутатора подключены соот ветственно к пятым и шестым в ходгии ответствующих элементов ИЛИ третьей группы, выходы которых подключены к первым Р входам выходного регистра, первые входы элементов И второй и третьей группы объединены и подключены с оответственно к выходам пятого и шестого элементов ИЛИ, управляющие входы ключей третьей группы объединены и подключены к выходу первого элемента И, к первому входу второго элемента И, ко BTOptJM входам первого и четвертого элементов И, соответственно, второй и третьей групп, вторые входь: вторых элементов И второй и третьей, и пятой групп объединены и являются Умножение устройства, вторые входы третьих элементов И второй и третьей групп и первый вход третьего элемента И объединены и подключены к выходу четвертого элемента И, первый вход которого подключен к первому входу пятого элемента И, ко второму входу первого элемента И и является входом Сложение устройства, вторые входы четвертого элементаИ второй группы и первого элемента И третьей группы объединены и подключены к выходу-третьего элемента И, второй вход которого объединен со вторыми входами элементов И четвертой группы и подключен к выходу пятого элемента И, второй вход которого подключен к нулевому выходу сумматора по модулю два, выходы первого, второго, четвертого элементов И второй группы и выход третьего элемента И третьей группы подключены ко входам девятого элемента ИЛИ, выход которого подключен к первому входу первого элемента И-НЕ, выходы третьего элемента И второй группы и первого, второго, четвертого элементов И третьей группы подключены ко входам десятого элемента ИЛИ, выход которого подключен к первому входу второго элемента И-НЕ, выходы первого и второго элементов И-НЕ подключены соответственно к ( Р+1j-му и { P-f 2)-му входам выходного регистра, вторые входы первого и второго элементов И-НЕ объединены и подключены к выходу второго элемента И, первый вход шестого элемента И подключен к выходу четвертого элемента ИЛИ, вторые входы второго и шестого элементов И объединены и подключены к выходу второго элемента ИЛИ, выход шесToro элемента И подключен ко второму входу четвертого элемента И. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 550636, кл. G 06 F 7/52, 1977. 2.Авторское свидетельство СССР по заявке 2675156/18-24, кл. G 06 F 7/49, 1978 (прототип)