Арифметическое устройство в системе остаточных классов

 

Союз СоветскикСоциалистическик

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву— (22) Заявлено 09. 0 1 . 81 (2 ) 3271232/18-24 с присоединением заявки №вЂ”

G 06 F 7/72

Гвсуддрставвльм квинтет

СССР во делам лэебретеллй и втарытнй (23) Приоритет

Опубликовано23. 02. 83. Бюллетень № 7

Дата опубликования описания 23.02.83 (53) УДК 681. 325..5(088.8) (72) Авторы изобретения

Н.ф. Сидоренко, А.Д. Дубовых, и В.А. Краснобаев (71 ) За я вител ь (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО В СИСТЕМЕ

ОСТАТОЧНЫХ КЛАССОВ

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

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

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

2 координат базовых квадратов, вход которого подключен к первому информационному входу устройства, управляющий вход - к входу вида операции устройства, блок кодирования, блоки перекодирования, блок координатно-узловых трансформаторов и дешифратор групп, тождественных .базовых квадратов, входы которого соединены соответственно с выходом блока определения координат базовых квадратов, с вторым информационным входом устройства, с первыми выходами первого и второго блоков перекодирования, с управляющими входами устройства, выход - через последовательно соединенные первый блок ключей, блок кодирования и блок усилителей подключен к выходу устройства; выходы первого и второго дешифраторов соединены соответственно со входами первбго и второго блоков перекодирования, вторые выходы которых подключены соответственно ко входу второго блока ключей и входу блока формирователей, ин3 9990 формационный вход второго блока ключей соединен с первым информационным входом устройства, управляющие входыс управляющими входами устройства; выход блока ключей через первый блок элементов ИЛИ соединен с первым входом блока координатно-узловых трансформаторов, второй вход которого подключен к выходу блока формирователей, выход через второй блок элементов ИЛИ 10 соединен с входом блока кодирования; информационный вход блока формирователей соединен со вторым информационным входом устройства, управляющие входы которого подключены к управляю- 15 щим входам блока формирователей (2 ).

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

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

Поставленная цель достигается тем, что арифметическое устройство в системе остаточных классов, содержащее дешифраторы, входы которых являются первым и вторым информационными вхо- 2S дами устройства, соответственно, riepвую и вторую и третью группы ключей, первую и вторую группы элементов ИЛИ, блок умножения по модулю, выходной ре-гистр, выход которого является инфор- ЗЕ мационным выходом устройства, первые входы ключей первой группы объединены и являются управляющим входом нумножение" устройства, содержит первый и второй блоки вычитания по модулю, третью группу ключей, третью группу элементов ИЛИ, сумматор по модулю . два, шестнадцать элементов ИЛИ, четыре группы элементов И, четыре элемента И, причем i-e u j-e выходы дешифраторов (i=1, 2, ..., (Р1,-1)/2; (р„,+1)/2, Д,-1; 1<†номер основания системы ) подключены ко входам соответственно первого, второго, третьего и четвертого элементов ИЛИ, i-й и

IS (Р1 - i)-й выходы дешифраторов подключены ко входам i-го элемента ИЛИ соответственно первой и второй групп, первые входы элементов И первой группы объединены и являются управляющим входом "Сложение" устройства, вторые входы первого и третьего, второго и четвертого элементов И первой группы попарно объединены и подключены к выходам соответственно первого и второ го элементов ИЛИ, выходы первого и четвертого, второго и третьего элементов И первой группы подключены ко входам соответственно третьего и четвер50 4 того элементов ИЛИ, выходы которых подключены соответственно к первому и второму входам .сумматора по модулю два, первые входы первого и второго элементов И подключены соответственно к выходам третьего и четвертого элементов ИЛИ, а вторые входы объединены между собой и с выходом шестого элемента ИЛИ и подключены к третьему входу сумматора по модулю два, четвертый вход которого подключен к выходу ! пятого элемента ИЛИ, выходы первого и второго элементов И подключены к входам седьмого элемента ИЛИ, первые входы первого и третьего, второго и четвертого элементов И второй группы попарно объединены и подключены к единичному и нулевому выходам соответственно сумматора по модулю два, первые входы ключей второй и третьей групп соответственно объединены и подключены к выходам третьего и четвертого элементов И, первые входы которых подключены соответственно к единичному и нулевому выходам сумматора llo модулю два, а вторые входы объединены и подключены к выходу восьмого элемента

ИЛИ, первый вход которого является входом "вычитание" устройства, выходы ключей первой; второй и третьей групп подключены ко входам соответственно блока умножения, первого и второго блоков вычитания по модулю, вторые входы i-x ключей первой, второй и третьей групп ключей объединены и подключены к выходам соответствующих элементов ИЛИ соответственно первой и второй групп, i-e выходы блока умножения первого и второго блоков вы- читания по модулю подключены ко входам соответственно девятого и десятого элементов ИЛИ, à j-е выходы подключены к входам одиннадцатого и соответственно двенадцатого элементов

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

ИЛИ, i-е и (P -i)-е выходы блока умножения, первого и второго блоков вы читания по модулю подключены ко вхоS ., 999 дам i-х элементов ИЛИ третьей группы, выходы которых подключены к соответ.ствующим i-м входам выходного регист.ра, первые выходы первого и второго, третьего и .четвертого элементов И четвертой группы попарно объединены и подключены к выходам соответственно тринадцатого и четырнадцатого элементов ИЛИ, а вторые входы объединены между собой и со вторым входом 10 восьмого элемента ИЛИ и подключены ко входу "Сложение" устройства, выходы первого и четвертого, второго и третьего элементов И третьей группы подключены соответственно ко входам 1$ пятнадц атого. и шестнадцатого элементов ИЛИ, выходы которых подключены к ((Р1 +1)/2+1)-му и к ((Р1 +1)/2+2)-му входам выходного регистра.

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

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

Это и определяет воэможность реа.,лизации в схеме табличного умножения

0,25 части табл. 1. 30

В табл. 2 определены номера квадрантов арифметических таблиц коммутаторов .

-Для модульного умножения используется II квадрант таб l. Числовые И значения, соответствующие входным значениям, представляются табл. 3.

Алгоритм получения результата операции определяется следующим соотношением:, если два числа х и у заданы по основанию Р1, в коде табличного умножения х1,=(р, х1 ), y<=(g, у ), то для того, чтобы получить произведение х у„, (вод Р1,) в коде табличного, умножения и инвертировать его индекс 1$ у в случае, если . отлично от у, где Рк-

О, если 0

lfx . к+

1, если 2

В табл. 4 приведена операция мо- дульного умножения, вычитания и сло:жения, которая выполняется в коде табличного умножения.

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

Это определяет воэможность реализации в схеме табличного сложения и вычитания по модулю Р1 по 0,5 части соответствующих таблиц.

При сопоставлении таблиц сложения и вычитания очевидно соотношение: (х+у)+ ((Р,1,-х)-у)=Р „ или х+у=Р - ((Р -х)-у). Из этого выражения следует, что для получения результата опера ции модульного сложения достаточно знать результат операции модульного вычитания, т.е. возникает возможность эффективно использовать код табличного умножения для реализации модульных операций сложения и вычитания.

Порядок выполнения операции модуль. ного сложения следующий:

1. Уменьшаемое Х инвертируется по модулю Р, т.е. получим Рк-х, а вычитаемое у оставляем без изменений.

2. С помощью блоков модульного вы" читания по входным операндам (Р1 -х) и у, определяется результат операции модульного вычитания ((Р1,-х)-у1 (mod Р ).

3. Результат операции модульного вычитания инвертируется по модулю Р1

lv» - ((Р»-x)-y)3=x+y.

Таким образом, изобретение будет содержать три блока: один для определения результата операции модульного умножения и два для определения результата операции модульного вычитания.

Для модульного вычитания при =

Х у используется ll квадрант табл. 6.

Этот же квадрант используется для определения результата модульного сло" жения при у„ . Числовые выходные значения в соответствии со значениями входных шин второго блока -вычитания по модулю представлены в табл. 7.

Для у =13„=0 результат операции модульного вычитания непосредственно определяется значениями выходных шин, а для р =у-„=1 (для модульного- сложения у„ =О, у =1) значения, определяе3 мые выходными шинами, инвертируются по модулю Рь.

В качестве таблицы второго блока вычитания по модулю, реализующего операцию модульного вычитания для х ф „, используется j квадрант табл. 6.

Этот же блок используется для определения рвэультата модульного сложения

7 999050 8 при 1г„ = у ). Числовые выходные значения вход одного из элементов ИЛИ 1> и 12. в соответствии со значениями входных В зависимости от результата операции шин третьего блока вычитания по моду- сумматора 26 по модулю два открываетлю представлены в табл. 8. ся один из элементов И 23 второй групДля у 1, у =0 результат операции. и пы. Через элементы ИЛИ 15 или 16 и . модульного вычитания (для модульного один из элементов И четвертой группы сложения р =О, ц=О) непосредственно 25 сигнал поступает на ((Р +1) /2+1) -й определяется значениями выходных шин или ((P<+1)/2+2/-й входы выходного реблока, а для р =О, у> =1 (для модуль- гистра 37. Таким образом,. в выходном ного сложения у„ =1, у .=1) результат 10 регистре 37 содержится операнд в коде операции инвертируется по модулю Р>. табличного умножения1 определяющий реВ изобретении блок умножения по зультат операции модульного умножения. модулю, первый и второй блоки вычита- Второй режим — определение резульния по модулю могут быть выполнены .в тата операции модульного вычитания виде постоянных запоминающих уст- " 1з (х-у) (mod P ) (управляющий сигнал 1 ройств. Это обеспечит максимальное п рисутствует на шине "Вы чита ние". быстродействие устройства. Уменьшаемое Х и вычитаемое у постуНа чертеже представлена блок-схем пают на дешифраторы 1 и 2. Если 1)) х устройства. то на нулевом выходе сумматора

Устройство содержит дешифраторы 1 10 по модулю два присутствует сигнал, и 2, элементы ИЛИ 3-18 с первого по и сигналы входных операндов через шестнадцатый, первую 19, вторую 20 и третью группу ключей 29 поступают сотретью 21 группы элементов ИЛИ, пер- ответственно íà GlloK 32. Выходной сивую 22, вторую 23, третью 24 и чет- гнал блока 32 поступает на вход одновертую 25 группы элементов И, сумма- И го из элементов ИЛИ 12 или 14 и через тор 26 по модулю два; первую 27, вто- один из элементов ИЛИ 15, 11 и элерую 28 и третью 29 группы ключей, мент И четвертой .группы 25 поступает блок 30 умножения по модулю; первый, на вход одного из элементов ИЛИ 17 и второй и третий блоки памяти таблиц . 18 и далее на соответствующий вход операций, первый 31 и второй 32 бло- зр выходного регистра 37. ки вычитания по модулю, первый 33, второй 34, третий 35 и четвертый 36 Если ух Фуу, то на единичном выхоэлементы И, выходной регистр 37. де сумматора по модулю два 26. Сигнал

Работу устройства удобно рассмат- проходит через блок 31 и далее на соривать в трех режимах работы. ответствующие входы выходного регистПервый режим - определение резуль- ра 37 тата модульного умножения xy(mod P ) Третий режим — определение резуль(управляющий сигнал присутствует на- тата операции модульного сложения шине "Умножение" (X+y) (mod Р ) (управляющий сигнал

Первый Х и второй у операнды, де- поступает на шину "Сложение)!). .Этот шифраторы 1 и 2, элементы .ИЛИ первой сигнал поступает на второй вход две19 и второй 20 групп и ключи 27 пер- надцатого элемента ИЛИ 10, и таким вой .группы, которые открываются сиг- образом, работа блоков 31 и 32 аналоналом "Умножение", поступают на вхо- гична второму режиму. С помощью сигды блока 30 умножения по модулю . нала "Сложение" инвертируется значеОдновременно выходные сигналы регист- :ние индекса кода табличного умножеР1-1 ния у< первого операнда (уменьшаемо("ь го) Х и инеертируется индекс кода

2 ! Риь" 1 табличного умноиения т результата .Ь и -4j группы выходов дЕ- операции модульного вычитания

50 аифратороа 1 и 2, через элементы ИЛИ ь(р» X) Y) ыьр)! ((р)ь ") у))

3-8, через элементы И 22 первой группы поступают на нулевой или единичный Таки + образом, введение в состав входы сумматора 26 по модулю два, устройства элементов И, ИЛИ, групп

Выходной сигнал блока 30 через опре- - элементов И и ИЛИ, ключей, блоков паИ, деленный элемент ИЛИ третьей группы мяти таблиц операции, сумматора по

21 поступает на соответствующую вход" модулю два и соответствующих связей ную шину выходного регистра 37. Одно- позволяет уменьшить обьем оборудовавременно этот сигнал поступает на ния.

999050 у 1 2 3 4 5 6 7 8 9 10

6 7 8 9 1О

2 4 б 8 10 1 3 5 7 9

2 5 8

3 6 8 !

7 10

4 8 1 5 9 2 6 1О 3 7

5 10 4 9

6 1 7 2 8

9 5 1 8 4

7 3 10 6

8 5 2 10 7 I 10 8

9 7. 5 3

10 9 8 7 6 5 4 3 2

Таблица2

II I

I 1 I 1Ч

Таблица 3

2 3 4 5

1 10 1

1 5 9

Таблица 4

Код табличного умножения

Цифра

Индекс

Цифра

8 2

3 9

2 9 2 . 4 6 8 10

3 8 3 6 9 1 4

5 6 5 10 4 9 3

Таблица 1

7 1 6

4 l0 5

9 6 3

6 4 .2

999050 12

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

Код,табличного умножения

Индекс

Цифра

Цифра

1! 11

1 1111

1 2 3 4 5 6 7 8 -9 10

8 9 10

5 6 7 8

9 !О

О 1 2

2 3

3 4

1 2 3 4 5

2 3 4 5 6

7 8 9 .10 О

8 9 10 О 1

3 4

4 5

5 6 7

6 7 8

О 2

9 10

1 2

1 О

2 10

10

8

10

2 3 4 5 6 7

3 4 5 6 7 8 9 !О 0

4 5 6 7 8 9 10 0 1

6 7 8 9 10 О

7 8 9 10 О 1

0 1

1О 0

9 10

8 9

7 8

6 7

5 6

4 5

999050

14

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

13

% (1

10

1 2

» » «t»в

7 8

6 .. 7 8

10. 1 2

О. 1

10

Таблица 7.

10

10

Таблица 8 и

ЪЯ

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

Арифметическое устройство в систе.ме остаточных классов, содержащее де". шифраторы, входы которых являются

1первым и вторым информационными вхо5$ дами устройства соответственно, первую, вторую и третью группы ключей, первую и вторую группы элементов ИЛИ, 6 7

5 6

4, 5

3 - 4

1 10 О

2 910

3 8 9

5 6 7 блок умножения по модулю, выходной регистр, выход которого является. ин;формационным выходом устройства, первые входы ключей первой группы объединены и являются управляющим входом

"Умножение" устройства, о т л и ч аю щ е е с я тем, что, с целью уменьшения объема оборудования, оно содержит первый и второй блоки вычитания

15 999050

16 групп подключены ко входам соответственно блока умножения, первого и второго блоков вычитания по модулю, вторые входы -х ключей первой, второй и третьей групп ключей объединены и подключены к выходам соответствующих элементов ИЛИ соответственно первой и второй групп, i-e выходы блока умножения первого и второго блоков вычитания по модулю подключены ко входам соответственно девятого и десятого элементов ИЛИ, à j e выходы подключены ко входам одиннадцатого и со ответственно двенадцатого элементов

ИЛИ, первые входы элементов И третьей группы объединены и подключены к выходу седьмого элемента ИЛИ, вторые входы первого и второго, третьего и по модулю, третью группу ключей, третью группу элементов ИЛИ, сумматор по модулю два, шестнадцать элементов .ИЛИ, четыре группы элементов И, четыре элемента И, причем i-e u j-e выхо- 5 ды дешифратаров (i=1 2, ... (Р -1)/2;

)=(Р +1)/2, ..., Р1 -1; k - номер основания системы) подключены ко входам соответственно первого, второго, третьего и четвертого элементов ИЛИ, 1О

i-й и (Р1,"i)-й выходы дешифраторов подключены ко входам i ãî элемента

ИЛИ. соответственно первой и второй групп, первые входы элементов И первой группы объединены и являются уп- 1$ равляющим входом "Сложение" устройства, вторые входы первого и третьего, второго и четвертого элементов И первой группы попарно объединены и подключены к выходам соответственно пер- 20 вого и второго элементов ИЛИ, выходы первого и четвертого второго и третьего элементов И первой группы подключены ко входам соответственно третьего и четвертого элементов ИЛИ, выхо- 2з ды которых подключены соответственно к первому и второму входам сумматора по модулю два, первые входы первого и второго элементов И подключены соответственно к выходам третьего и Зр четвертого элементов ИЛИ, а вторые входы объединены между собой и с выходом шестого элемента ИЛИ и подключены к третьему входу сумматора по модулю два, четвертый вход которого подключен к выходу пятого элемента

ИЛИ, выходы первого и второго элементов И подключены ко входам седьмого элемента ИЛИ, первые входы первого и третьего, второго и четвертого элементов И второй группы попарно объединены и подключены к единичному и нулевому выходам соответственно сумматора по модулю два, первые входы ключей второй и третьей групп соответственно объединены и подключены. к выходам третьего и четвертого элементов И, первые входы которых подключены соответственно к единичному и нулевому выходам сумматора по модулю два, а вторые входы объединены и подключены к выходу восьмого элемента ,ИЛИ, первый вход которого является входом "Вычитание" устройства, выходы ключей первой, второй и третьей четвертого элементов И второй и третьей групп попарно объединены и подключены к выходам соответственно девятого и одиннадцатого, десятого и двенадцатого элементов ИЛИ; выходы элементов И второй и третьей групп подключены к соответствующим входам тринадцатого и четырнадцатого элементов ИЛИ, i-e и (Р1 -i)-e выходы блока умножения первого и второго блоков вычитания по модулю подключены ко входам i-x элементов ИЛИ третьей группы, выходы которых подключены к соответствующим

i-м входам выходного регистра, первые входы первого и второго, третьего и четвертого элементов И четвертой группы попарно объединены и подключены к выходам соответственно тринадцатого и четырнадцатого элементов ИЛИ, а а вторые входы объединены между собой и со вторым входом восьмого элемента

ИЛИ и подключены ко входу "Сложение" устроиства, выходы первого и четвертого, второго и третьего элементов И третьей группы подключены соответственно ко входам пятнадцатого и шестнадцатого элементов ИЛИ, выходы которых подключены к ((Р +1)/2+1)-му и к ((Р1+1)/2+2),-му входам выходного регистра °

Источники информации, принятые во внимание при экспертизе

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

N 419891, кл. G 06 F 7/72, 1974.

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

N 549805, кл..С 06 F 7/72, 1977 (прототип).