Устройство для вычитания по модулю

 

УСТРОЙСТВО ДЛЯ ВЫЧИЧ АНИЯ ПО МОДУЛР, содержащее первый и второй входные регистры, входы являютсй Ьходами операндов устройства , выходы подклю ены к входим первого и второго де11ЮфрахЬров, первую и вторую группы ключей, первую, вТорую , третью и четвертую группы элементов ИЛИ Первый и второй коммутёторы , сумматор по модулю два, Нервый второй, третий, четве1 тый и пятый элемейтЫ ИЛИ, перйый и второй «лемёмты И, причем i -и и ()-й выходы дешифраторов (,1, . ,. jP-l; Р модуль ) подключены соответственно к Первому и второму входам j-го элеМеН а ИЛИ (j 1,2 , ...., (Р-1) /2 при Р йечетной j 1,2 ,.,Р/2 при Р четном ) cdlffTBeTCTBeHHo пербой и второй групп, первая группа i-x выходов (,i,..., (Р-1)/2 при Р нечетном ,1,J..,Р/2 при Р четном) соответственно Первого и втсфого дешифратоjpoB подключена к входам соответствейно первого и второго элементов ИЛИ, выходы которых подключены соответственно к Первому и второму входам сумматора по модулю два вторая групПА -it выходов (Г (Р-1)/2+1, .. ,Р-1 при Р нечетном г гР/2+1,.. ,Р-1 при Р четном) соответственно первого и второго дешифраторов подключена Кб входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключены соответственно к третьему и четвертому входам сумме тора по модулю два, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей первой и второй групп, вг-хойы которых подключенысоответственно к первой и второй группам входов соответственно первого и второго коммутаторов ,. первые входы первого и вто рого элементов И объединены и подключены к выходу второго элемента ИЛИ, вторые входы первого и второго элементов И noдkлючeны к выходам третьего и четвертого элементов ИЛИ соответственно, выходы первого и второго элементов И подключены к входам Пятого элеМента ИЛИ, о т л ич а ю щ е е b я там, что , с целью (/ уменьшения объема оборудования, оно содержит шифратор, первую и вторую с: группы элементов И, сумматор по модулю Р , Первый вход которого является входом константы Р устройства, а второй вход подключен к выходам соответствующих элементов И перво.й группы, группа выходов сумматора X по модулю Р подключена к первым входаМ элементов ИЛИ третьей группы, вторые входы которых подключены к выходам соотвеТствуюпдах элементов И второй группы, первые входы которых объединены с первыми входами соответствукицйх элементов И первой группы и Подключены к соответствующим выходам шифратора, входами подключенного к выходам соответствующих элементов ИЛИ четвертой группы, перBfcJe и вторые входы которьЬс подключены к соответствующим выходам соответственно перйого и второго коммутаторов , вторые входы элементов И первой и второй групп объединены и подключены к выходу пятого элемента ИЛИ, выходы элементов ИЛИ третьей группы являются, выходом устройства.

СОЮЗ СОВЕТСКИХ

О N5NI

РЕСПУБЛИК

3(5D G. 06 F 7/49

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н АВтОРсиОмУ сВЙДЙтельстВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБ %ТЕНИЙ И ОТНРЫТЦЙ

Т21) 3368093/18-24 (22) 03.12.81 (46) 15.04а83. Бюл. М 14 (72) В.A. Краснобаев и И.Б. Давыдов (53) 681 .325(088 .8) (56) 1. Авторское свидетельство СССР

М 446056, кл. G 06 F 7/72, 1975.

2 Авторское свидетельство СССР по заявке Р 3213273/24, кл . 6 06 F 7/49, 1980 (протбтип) . .(54)(57) УС1РОИС1ВО ДЛЯ ВЫЧИТАНИЯ

ПО МОДУЛА%0, содержащее первый и второй входные регистры, входы которых являются вхсщами операндов устройсФва, выходы подключены к входам nepsoro и второго дейифраторов, первую и. вторую группы ключей, первую, вто- . рую, третью и четвертую группы элеМентав ИЛИ первый и второй коммутаторы, сумматор по модулю два, первый второй, третий, четвертый и пятый элементы Или, первый и второй элементы И, причем 1 -й и (Р-i-1)-й выходы дешифраторой (1 =0,1,...,Ð-1у 9 - Модуль) подключены соответственно к первому и второму входам ) -ro элеМЕНта ИЛИ () =1,2,...,(Р-1)/2 Прн Р

НечетноМ . ) =1,2,.s.,Р/2 при Р четном) сдбтветственно первой и второй групп,: первая группа t.-х выходов (%=0,l,...,(Р-1)/2 при Р нечетноМ

К=0р 1, 1 .,Р/2 при Р четном) соотвеФ - ственно первого и второго дешифратоРов подключена к входам соответствейно первого и второго элементов ЙЛЙ, выходы которых подключены соответственно к первому и второму входам сумматора по модулю два вторая группа F -х выходов (l =(Р"1)/2+1 ° ° i Р-1 при Р нечетном; г=Р/2+1,...,P-1 при

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

„„SU„„, A

l третьему и четвертому входам сумматора по модулю два, выходы элементов

ИЛИ первой И второй групп подключены к первым входам соответствующих ключей первой и второй групп, вгходы которых подключены соответственно к первой и второй группам входов соответственно первого и второго коммутаторов, первые входы первого и вто-"

Рого элементов И объединены и подключены к выходу второго элемента

ИЛИ, вторые входы первого и второго элементов И подключены к выходам третьего и четвертого элементов ИЛИ соответственно, выходы первого и второго элементов И подключены к входам пятого элемента HJIH, о т л и- В ч а ю щ е е с я тем, что, с целью уменьШЙНИя объема оборудования, оно Щ содержит шифратор, первую и вторую группы элементов Й, сумматор по мо- 4„; дулю Р, первый вход котороге является входом константы Р устройства, В а второй вход подключен к выходам соответствующих элементов И первой, группы, группа выходов сумматора по модулю Р подключена к первым входаМ элементов ИЛИ третьей группы, вторые вхсды которых подключены к выходам соответствующих элементов И второй группы, первые входы которых объединены с первымн входами соответствующих элементов N первой группы и подключены к соютветствующим выходам шифратора, входами подключенного к выходам соответствующих элеМентсв ИЛИ четвертой группы, пер вые и вторые входы которых подключены к соответствующим выходам соотВетственно первого и второго коммутаторов, вторые входы элементов И . первой и второй групп объединены и подключены к выходу пятого элемента

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

1012242

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

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

,линейку, операционную матрицу, усилители и соответствующие связи (1 3.

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

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

rry элементов ИЛИ, девять элементов

ИЛИ, восемь элементов И, второй коммутатор, причем 1 -й и (P- J-1) -й вы ходы дешифраторов (1 =0,1 2,...,P- 1 25

Р— модуль) подключены соответственно к первому и второму входам j -го элемента ИЛИ (j=1,2,...,(P-1)/2 при

Р нечетном; 1 =1,2,...,Р/2 при Р четном) соответственно первой и второй групп, первая группа В -ых выходов (1c=0,1,2,...,(P-1)/2 при Р нечетном; 4с =0,1,2,...,P/2 прн P четном) соответственно первого и второго дешифраторов подключена к входам соответственно первого н второго 35 элементов ИЛИ, выходы которых подключены соответственно к первому и второму входам сумматора по модулю два, вторая группа r-x выходов (=(Р-1)/2+1,...,P-1 при P нечетном, 40

Г=P/2+1,...,P-1 при P четном) соответственно первого и второго дешифраторов подключена к входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключе- 45

)ны соответственно к третьему и чет-, вертому входам сумматора по модулю два, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей пер- 50 вой и второй групп, вторые входы которых объединены и подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а вторые входы объединены и являются управляющим входом устройства, выходы ключей первой и второй групп подключены соответственно к первой и второй группам входов соответственно первого и второго коммутаторов подключены к соответствующим входам пятого эле1 мента ИЛИ и соответственно к первым и третьим входам j --x элементов ИЛИ .65 третьей группы, (P-j) -е выходы первого и второго коммутаторов подключе. ны к соответствующим входам шестого элемента ИЛИ и соответственно к вторым и четвертым входам -х элементов ИЛИ третьей группы, первые входы третьего и пятого, четвертого и шестого элементов И попарно объединены и подключены к выходам соответственно пятого и шестого элементов ИЛИ, вторые входы третьего, четвертого, пятого и шестого элементов И объединены и подключены к выходу седьмого элемента ИЛИ, выходы которого подключены к выходам седьмого и восьмого элементов И соответственно, первые входы которых подключены соответственно к выходам второго. и четвертого элементов ИЛИ, а вторые входы объединены и подключены к выходу

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

ИЛИ соответственнОр выходы которых подключены соответственно к первому и второму входам выходного регистра, выходы элементов ИЛИ третьей группы подключены к соответствующим Р -М входам (9 =3,4,...,(Р+1)/2+2 При Р нечетном, Р =. 3,4,...,Р/2+2 при P четном) выходного регистра, выходы ко" торого являются выходами устройст" ва (.2).

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

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

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

ИЛИ, первый и второй коммутаторы,сумматор по модулю два, первый, второйр третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И,причем 1-й и (P-j-1)-й выходы дешифраI торов (1= О, 1 ° ., Р-1; P модуль) подключены соответственно к первому и второму входам g-го элемента ИЛИ (j =1 2,..., (P-1) /2 . при P нечетном;

j =1,2,...,P/2 прн P четном) соответственно первой:и второй групп, первая группа Ф -х выходов (М= О, 1,..., ..., (Р-1)/2 при Р нечетном; tc =

-0,1,...,P/2 при P четном) соответственно первого и второго дешифраторов подключена к входам соответственно первого и второго элемента

ИЛИ, выходы которых подключены соответственно к первому и второму входам сумматора по модулю два, вторая группа r--х выходов (r=(P-1)/2+1,..., 1012242,Р-1 при P нечетномуФ Р/2+1,..., ...,Р-1 при Р четном) соответственно . первого и второго дешифраторов под.ключена к входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключены соответственно к третьему и четвертому входам сумматора . по модулю два, выхдды элементов ИЛИ первой и второй групп подключены fc первым входам соответствующих ключей:первой и второй групп, выходы которых подключены соответственно к первой и второй группам вхо.« дов соответственно первого и второго коммутаторов, первые входы первого и второго элементов И объединены и, подключены к выходу второго элемента

ИЛИ, вторые входы первого и второго элементов И подключены к выходам третьего и четвертого элемеитов ИЛИ соответственно, выходы первого и вто р0 рого элементов И подключены к. входам вующих элементов ИЛИ четвертой группы, первые и вторые входы которых подключены к соответствующим выходам 40 соответственно первого и второго комйутаторов q вторые входы элементов

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

В устройстве используется свойство симметрии арифметической таблицы от носительно диагоналей.

ПустЬ А — уменьшаемое, .В " Вйчй- ц» таемое, P - модуль и пусть необхофюмо определить (A-B) вой Р.:

Входные операнды можно представыть в виде A = (g<, а) И В = (f8,f3) ! где 3; - индекс кода табличного Ум- 55 ножения, и 1 4 à ñ (Р-1)/2. Возможные варианты модульного вычитания для соответственно l, 11, 111 и lу квадрантов таблицы модульного вычнтания имеют вид

60 (Р-a)+= (Р-(а1)ь)) иод Р; (a-P) mod Р;

d- (Р-Р) = (а р) mod Р; (p-а) -(P-(ь) = 1Р- (ca-p)Jmo8 Р.

65 пятого элемента ИЛИ, содержит шифратор, первую и вторую группы элемен-. тов И, сумматор по модулю Р, первый вход которого является входом константы Р устройства, а второй Вход подключен к выходам соответствующих элементов И первой группы, rpyhna выходов сумматора по модулю Р подключена к первым входам элементos ИЛИ третьей группы, вторые входы которых подключеиы к выходам соответствующих элементов И второй группы, первые входы которых объединены с первыми входами соответствующих элементов И .первой группы и подключены к соответ- 5 ствующим выходам шифратора, входами подключенного к выходам .сьответстИз приведенных соотношений следует, что в качестве первого и второго коммутаторов размером:(. Зв. можно использовать 1Х квадранты соответственно таблиц модульных опе- раций (А-В) mod P и (А+В) щой Р.

В качестве первого коммутатора, реализующего операцию модульного вычитания для 11 и lу квадрантов, используется табл. 1; таблица 1.

5..

10 0 :1 2 3 4

91001

8 9 10 0

7 8 9 10

2 3

1 2

О, 1

1 хо о

6,7 ;8 9

Г

ДЛЯ lу квадранта (З" =у =-1) результат операции инвертиру ется по модулю Р, В качестве второго коммутатора, реализующего операцию модульного вычитания для 1 и ill квадрантов, используется второй квадрант табл.2 (А+В) mod Р. Й а б л и ц а 2! 1. 2 3 4 5 .10 9 8 7 6

2 3 4 5 б

3 4 5 б 7

4 5 б 7 8

6 .7 8

7 .8 9

° 1 ° ° (° г

Для 1 квадранта (= l, ) =0) результат операции инвертируется по модулю Р.

На чертеже представлена структурная схема устройства.

Устройство содержит первый 1 и второй 2 входы, первый 3 и второй 4 входные регистры, первый 5 и второй

6 дешифраторы, первую 7 и вторую 8 группы элементов ИЛИ, первую 9, вторую 10, третью 11 и четвертую 12 группы ключей, первый. 13 и второй 4 .коммутаторы, первый 15, второй 16:„

1012242

10 третий 17 и четвертый 18 элементы

ИЛИ, сумматор 19 по модулю два, первый 20 и второй 21 элементы И, пятый

22 элемент ИЛИ, четвертую 23 группуэлементов ИЛИ, шифратор 24, первую

25 и вторую 26 группы элементов И, сумматор 27 па модулю Р, третью 29 группу элементов ИЛИ, вход 28 константы P выход 30 устройства.

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

На вход 1 подается уменьшаемое

А, а на вход 2 вычитаемое В в двоичном коде. Входные операнды A и В последовательно через сОответствующие дешифраторы 3 и 4, первую 7 и вторую 15

8 группы элементов ИЛИ поступают на первую 9 и вторую 10, третью 11 и четвертую 12 группы ключей. Одновременно выходные сигналы дешифраторов

5 и 6 через соответствующие элементы 10

ИЛИ 15 - 18 поступают на нулевой или единичный входы сумматора 19, Если

З;„= р, то на нулевом выходе сумматора 19 присутствует сигнал, который открывает. ключевые элементы первой

9 и второй 10 групп, и входные операнды A и В поступают на входы перьвого 13 коммутатора. Если у,„фу то на единичном выходе сумматора 19 присутствует сигнал, который откры" 30 вает ключевые элементы третьей 11 и четвертой 12 групп, и входные операнды А и В поступают на входы второго 14 коммутатора. Результат операции коммутатора 13 или коммутатора 14 через элементы ИЛИ 23 четвертой группы поступает на вход шифратора 24, с выхода которого результат в двоичном коде поступает на первые входы элементов И 25 и 26.

Элементы И 20 и 21 и элемент ИЛИ 22 формируют признакЯ=у л - ч g л инвертирования по модупю Р результата операции коммутаторов 13 и 14.

Если Я= 0 (отсутствует выходной сигнал пятого элемента ИЛИ 22), то эле" менты И 26 открыты ° Результат операции (элементы И 25 закрыты) через элементы ИЛИ 29 поступает на выход

30 устройства. Если Я = lр то выходной сигнал пятого элемента ИЛИ 22 открывает элементы И .25 и закрывает

26. Результат операции коммутаторов

13 или 14 через открытые элементы

И 25 поступает на первые входы сумматора 27 по модулю Р, на вторые входы которого по шинам 28 поступает значение константы Р в двоичном ко де, и таким образом сумматор 27 инвертирует по модулю P результат операции коммутаторов 13 или 14. Это значение через элементы ИЛИ 29 поступает на выход 30 устройства.

Таким образом, пРименение предло" женного устройства позволяет умень шить объем оборудования.

1012242 .

ВНИИПИ Заказ 2766/60 Тираж 704 Подписное

Филиал ППП "Патент", t.Óæãîðîä, ул.Проектная,4