Арифметическое устройство в системе остаточных классов Советский патент 1983 года по МПК G06F7/72 

(5) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

.1

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

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

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

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

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

Поставленная цель достигается тем, что арифметическое устройство в системе остаточных классов, содержащее дешифраторы, входы которых являются первым и вторым информационными входами устройства, соответственно, первую и вторую и третью группы ключей, первую и вторую группы элементов ИЛИ, блок умножения по модулю, выходной ре-гистр, выход которого является информационным выходом устройства, первые входы ключей первой группы объединены и являются управляющим входом Умножение устройства, содержит первый и второй блоки вычитания по модулю, третью группу ключей, третью группу элементов ИЛИ, сумматор по модулю два, шестнадцать элементов ИЛИ, четыре группы элементов И, четыре элемента И, причем i-e и j-e выходы дешифраторов (, 2, ..,, (Pi(-l)/2; j (р,()/2,... 1с- номер основания системы )подключены ко входам соответственно первого, второго, третьего и четвертого элементов ИЛИ, i-й и ()-й выходы дешифраторов подключены ко входам i-ro лемента ИЛИ соответственно первой и второй групп, первые входы элементов И первой группы объединены и являются управляющим входом Сложение устройства, вторые входы первого и третьего, второго и четвертого элементов И первой группы попарно объединены и подключены к выходам соответственно первого и второго элементов ИЛИ, выходы первого и четвертого, второго и третьего элементов И первой группы подключены ко входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключены соответственно к первому и второму входам сумматора по модулю два, первые входы первого и второго элементов И подключены соответственно к выходам третьего и четвертого элементов ИЛИ, а вторые входы объединены между собой и с выходом шестого элемента ИЛИ и подключены к третьему входу сумматора по модулю два, четвертый вход которого подключен к выходу пятого элемента ИЛИ, выходы первого и второго элементов И подключены к входам седьмого элемента ИЛИ, первые входы первого и третьего, второго и четвертого элементов И второй группы попарно объединены и подключены к единичному и нулевому выходам соответственно сумматора по модулю два, первые входы ключей второй и третьей групп соответственно объединены и подключены к выходам третьего и четвертого элементов И, первые входы которых подключены соответственно к единичному и нулевому выходам сумматора по модулю два, а вторые входы объединены и подключены к выходу восьмого элемента ИЛИ, первый вход которого является входом Вычитание устройства, выходы ключей первой, второй и третьей групп подключены ко входам соответственно блока умножения, первого и второго блоков вычитания по модулю, вторые входы 1-х ключей первой, второй и третьей групп ключей объединены и подключены к выходам соответствующих элементов ИЛИ соответственно первой и второй групп, 1-е выходы блока умножения первого и второго блоков вычитания по модулю подключены ко входам соответственно девятого и десятого элементов ИЛИ, а j-e выходы подключены к входам одиннадцатого и соответственно двенадцатого элементов ИЛИ, первые входы элементов И третьей группы объединены и подключены к выходу седьмого элемента ИЛИ, вторые входы первого и второго, третьего и четвертого элементов И второй и третьей групп попарно объединены и подкж)чены к выходам соответственно девятого и одиннадцатого, десятого и двенадцатого элементов ИЛИ, выходы элементов И второй и третьей групп подключены к соответствующим входам тринадцатого и четырнадцатого элементов ИЛИ, i-e и ()-e выходы блока умножения, первого и второго блоков вычитания по модулю подключены ко Bjicoдам i-x элементов ИЛИ третьей группы выходы которых подключены к соответ.ствующим |-м входам выходного регист ра, первые выходы первого и второго, третьего и четвертого элементов И четвертой группы, попарно объединены и подключены к выходам соответственно тринадцатого и четырнадцатого эле ментов ИЛИ, а вторые входы объединены между собой и со вторым входом восьмого элемента ИЛИ и подключены ко входу Сложение устройства, выхо ды первого и четвертого, второго и третьего элементов И третьей группы подключены соответственно ко входам пятнадцатого и шестнадцатого элементов ИЛИ, выходы которых подключены к {(Р|(+1)/2+1)-му и к ({Pit+l)/2+2)-My входам выходного регистра. В схеме модульного умножения используются свойства симметрии арифме 5{(1ческой таблицы относительно диагонали, вертикали и горизонтали, тпрохо V р+1, дящих между величинами и Ji- где Р - модуль таблицы. В табл. 1 приведен пример для . Это и определяет возможность реа,лизации в схеме табличного умножения О,25 части табл. 1. В табл. 2 определены номера квадрантов арифметических таблиц коммутаторов. Для модульного умножения использУ ется II квадрант табл. 1. Числовые значения, соответствующие входным значениям, представляются табл. 3Алгоритм получения результата операции определяется следующим соотношением: еслк два числа х и у заданы по основанию Р. в коде табличного умножения х(ух, хц), y(fy, ), то для того, чтобы получить произведение (mod Р) в коде табличного умножения и инвертировать его индекс у в случае, если отлично от -у, PX-I если Pv-f-f VI, если i P-(j В табл. k приведена операция модульного умножения, вычитания и сложения, которая выполняется в коде табличного умножения. в схеме модульного сложения исполь зуется свойство симметрии арифметичес кой таблицы (табл. 5) относительно ле вой диагонали, а в схеме модульного вычитания используется свойство симметрии арифметической таблицы (табл. 6) относительно правой диагонали. Это определяет возможность реализации в схеме табличного сложения и вычитания по модулю Р по 0, соответствующих таблиц. При сопоставлении таблиц сложения и вычитания очевидно соотношение: (х+у)+ C(P-x-x), или Г()-у. Из этого выражения следует, что для получения результата операции модульного сложения достаточно знать результат операции модульного вычитания, т.е. возникает возможность эффективно использовать код табличного умножения для реализации модульных операций сложения и вычитания. Порядок выполнения операции модульного сложения следующий: 1. Уменьшаемое X инвертируется по модулю Р, т.е. получим , а вычитаемое у оставляем без изменений. 2.С помощью блоков модульного вычитания по входным операндам () и у, определяется результат операции модульного вычитания ()-yJ (mod Р-к). 3.Результат операции модульного вычитания инвертируется по модулю Р-ъ Plc-(V)-y YТаким образом, изобретение будет содержать три блока: один для определения результата операции модульного умножения и два для определения результата операции модульного вычитания. Для модульного вычитания при -jv j используется II квадрант табл. 6. Этот же квадрант используется для определения результата модульного сложения при -g-jj ffy. Числовые выходные значения в соответствии со значениями входных шин второго блока вычитания по модулю представлены в табл. 7Для -jj результат операции модульного вычитания непосредственно определяется значениями выходных шин, а дпя г у (для модульного-с ложе Тх TV значения, определяемые выходными шинами, инвертируются по модулю P.j. В качестве таблицы второго блока вычитания по модулю, реализующего операцию модульного вычитания для f ft #т, используется 1 квадрант табл. 6. Этот же блок используется для определения результата модульного сложения 79 при j у. Числовые выходные значения в соответствии со значениями входных шин третьего блока вычитания по модулю представлены в табл. 8. Для Ху 0 результат операции модульного вычитания (для модульного сложения х 0 УУ непосредственно определяется значениями выходных шин блока, а для-уу 0 ,-уу 1 (для модульного сложения Ух 1 Уу 1) результат операции инвертируется по модулю Р, В изобретении блок умножения по модулю, первый и второй блоки вычитания по модулю могут быть выполнены .в виде постоянных запоминающих устройств. Это обеспечит максимальное быстродействие устройства. На чертеже представлена блок-схема устройства. Устройство содержит дешифраторы 1 и 2, элементы ИЛИ 3-18 с первого по шестнадцатый, первую 19, вторую 20 и третью 21 группы элементов ИЛИ, первую 22, вторую 23, третью 2 и четвертую 25 группы элементов И, сумматор 26 по модулю два; первую 27, вторую 28 и третью 29 группы ключей, блок 30 умножения по модулю; первый, второй и третий блоки памяти таблиц операций, первый 31 и второй 32 блоки вычитания по модулю, первый 33, второй 3, третий 35 и четвёртый Зб элементы И, выходной регистр 37. Работу устройства удобно рассматривать в трех режимах работы. Первый режим - определение результата модульного умножения xy(mpd Р (управляющий сигнал присутствует на шине Умножение . Первый X и второй V операнды, дешифраторы 1 и 2, элементы ИЛИ первой 19 и второй 20 групп и ключи 27 первой группы, которые открываются сигналом Умножение, поступают на входы блока 30 умножения по модулю. Одновременно выходные сигналы регист / Р|,-1 ров 37 через первые и. . или ВТО/V V рые .l группы выходов дешифраторов 1 и 2, через элементы ИЛИ 3-В, через элементы И 22 первой груп пы поступают на нулевой или единичны входы сумматора 26 по модулю два. Выходной сигнал блока 30 через определенный элемент ИЛИ третьей группы 21 поступает на соответствующую вход ную шину выходного регистра 37- Одно временно этот сигнал поступает на 08 вход одного из элементов ИЛИ 1 и 12. В зависимости от результата операции сумматора 26 по модулю два открывается один из элементов И 23 второй груп пы. Через элементы ИЛИ 15 или 16 и один из элементов И четвертой группы 25 сигнал поступает на (()/2+1)-й или ((+1)/2+2/-й входы выходного peгистра 37. Таким образом, в выходном регистре 37 содержится операнд в коде табличного умножения определяющий результат операции модульного умножения. Второй режим - определение результата операции модульного вычитания (х-у) (mod Р) (управляющий сигнал присутствует на шине Вычитание. Уменьшаемое X и вычитаемое У поступают на дешифраторы 1 и 2. Если Y, jy, то на нулевом выходе сумматора п6 модулю два присутствует сигнал, и сигналы входных операндов через третью группу ключей 29 поступают соответственно на блок 32. Выходной сигнал блока 32 поступает на вход одного из элементов ИЛИ 12 или 14 и через один из элементов ИЛИ 15, 11 и элемент И четвертой .группы 25 поступает на вход одного из элементов ИЛИ 17 и 18 и далее на соответствующий вход выходного регистра 37. EcлиjpJ( -jv,, то на единичном выходе сумматора по модулю два 26. Сигнал проходит через блок 31 и далее на соответствующие входы выходного регистра 37 Третий режим - определение результата операции модульного сложения () (mod ) (управляющий сигнал поступает на шину Сложение). Этот сигнал поступает на второй вход двенадцатого элемента ИЛИ 1П, и таким образом, работа блоков 31 и 32 аналогична второму режиму. С помощью сигнала Сложение инвертируется значе:ние индекса кода табличного умножения -jr первого операнда (уменьшаемого) X, и инвертируется индекс кода табличного умножения тр результата операции модульного вычитания ()(РК-х)-у . . Такик образом, введение в состав устройства элементов И, ИЛИ, групп элементов И и ИЛИ, ключей, блоков памяти таблиц операций, сумматора по модулю два и соответствующих связей позволяет уменьшить объем оборудова ния.

1 2 3

2 1 6 8

6 8 1 k 7 10 2

if

10 1 3 5 7 9

5 6 7 8

5 8

9 10

10

8

k 8 1 5 9 2 6 10 3 7

6 1

10

9 7 5 3 1

7 3

5 10 i 9 3 8 2 7 1 6

9 8

5

2

. 7 2

10 6 2 9 5 1 8 Ц

7 6 5 i(

10

,8 3 9 i

7 i 1

to

8 6 If 2

3

9 6 3

10 5 .2 1

Т a 6 л и ца 2

il

IV III ::i::i:i: ;i; :i;i:ii: :;i:i: :ii:;: :i

10

2

9

8

i 7 6

Цифра

2

k 8 1 5 9

3 6

5

10 k 9 3

9 1 k

Таблица j

Код табличного умножения Индекс I Цифра

1

О О

110 О

29 10

389 i7 8 56 7

Та б л и ц а. 7

ft

3 2 1 О 10

3 2

1 О

8

10

10

it 3 2

9 8

7 6

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

S 7 6

7 6 5 4 3

9 8

7 6

5 1

5 ёлок умножения по модулю, выходной регистр, выход которого является, ин формационным выходом устройства, первые входы ключей первой группы объединены и являются управляющим входом Умножение устройства, о т л и ч аю щ е ее я тем, что, с целью уменьшения объема оборудования, оно содержит первый и второй блоки вычитания по модулю, третью группу ключей, третью группу элементов ИЛИ, сумматор по модулю два, шестнадцать элементов ИЛИ, четыре группы элементов И, четыре элемента И, причем 1-е и j-e выходы дешифраторов (1, 2, ... (Рц-1)/2 j ()/2, ..., В)-1; k - номер основания системы) подключены ко входам соответственно первого, второго, третьего и четвертого элементов ИЛИ, i-й и (Р-)(.-1)-й выходы дешифраторов подключены ко входам i-го элемента ИЛИ соответственно первой и второй групп, первые входы элементов И первой группы объединены и являются управляющим -входом Сложение устройства, вторые входы первого и третьего, второго и четвертого элементов И первой группы попарно объединены и подключены к выходам соответственно первого и второго элементов ИЛИ, выходы первого и четвертого второго и треть его элементов И первой группы подключены ко входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключены соответственно к первому и второму входам сумматора по модулю два, первые входы первого и второго элементов И подключены соответственно к выходам третьего и четвертого элементов ИЛИ, а вторые входы объединены между собой и с выходом шестого элемента ИЛИ и подключены к третьему входу сумматора по модулю два, четвертый вход которого подключен к выходу пятуго элемента ИЛИ, выходы первого и второго элемен тов И подключены ко входам седьмого элемента ИЛИ, первые входы первого и третьего, второго и четвертого элементов И второй группы попарно объединены и подключены к единичному и нулевому выходам соответственно сумматора по модулю два, первые входы ключей второй и третьей групп соотве ственно объединены и подк/юмены к вы ходам третьего и четвертого элементов И, первые входы которых подключе ны соответственно к единичному и нулевому выходам сумматора по модулю два| а вторые входы объединены и под ключены к выходу восьмого элемента .ИЛИ, первый вход которого является входом Вычитание устройства, выходы ключей первой, второй и третьей групп подключены ко входам соответственно блока умножения, первого и второго блоков вычитания по модулю, вторые входы |-х ключей первой, второй и третьей групп ключей объединены и подключены к выходам соответствующих элементов ИЛИ соответственно первой и второй групп, i-e выходы блока умножения первого и второго блоков вычитания по модулю подключены ко входам соответственно девятого и десятого элементов ИЛИ, а j-е выходы подключены ко входам одиннадцатого и со-« ответственно двенадцатого элементов ИЛИ, первые входы элементов И третьей группы объединены и подключены к выходу седьмого элемента ИЛИ, вторые входы первого и второго, третьего и четвертого элементов И второй и третьей групп попарно объединены и подключены к выходам соответственно девятого и одиннадцатого, десятого и двенадцатого элементов ИЛИ, выходы элементов И второй и третьей групп подключены к соответствующим входам тринадцатого и четырнадцатого элементов ИЛИ, i-e и ()-e выходы блока умножения первого и второго блоков вычитания по модулю подключены ко входам i-x элементов ИЛИ третьей группы, выходы которых подключены к соответствующим i-M входам выходного регистра, первые входы первого и второго, третьего и четвертого элементов И четвертой группы попарно объединены и подключены к выходам соответственно тринадцатого и четырнадцатого элементов ИЛИ, а вторые входы объединены между собой и со вторым входом восьмого элемента ИЛИ и подключены ко входу Сложение устройства, выходы первого и четвертого, второго и третьего элементов И третьей группы подключены cooTBetcTвенно ко входам пятнадцатого и шестнадцатого элементов ИЛИ, выходы которых подключены к (()/2+1 )-му и к (()/2+2),-му входам выходного регистра. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР (f 19891, кл. G Об F 7/72, 197. 2.Авторское свидетельство СССР № , кл. .G 06 F 7/72, 1977 (прототип) .