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

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

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

m - 1 , m + 1 и

22

где m - модуль устройства. Если обозначен

индекс операнда уд (ув)

как

УА (ув)

0,еслиО А(В),еспи + А(В)т,

то для операции модульного умножения можно обойтись 1/8 полной таблицы, вычитая полученный результат таблицы 1 из модуля. При имеем. При уд ув 0 .

А В (modm)A В (modm). При уд 0, ув 1

А В (modm) т-А В1 (modm), где В1 т-В. При уд 1,ув 0

А В (modm) т-А1 В (modm), где А1 т-А.

При уд ув Г

А В (modm) A1 В1 (modm).

Аналогичным образом можно вывести подобные соотношения для операций модульного сложения и вычитания, сохраняя принятые обозначения, т.е. при уд ув О

(A+B) modm () modm; (A-B) modm (А-В) modm; при уд 0, ув 1

(А+ В) modm (A-B1) modm; (A-B) mod m (A+B1) modm; при уд 1,ув. 0

(A+B) modm m-(A -B)modm; (A-B)modm m-(A +B)modm; приуд ув 1

(A+B)(A +B )modm; (A-B)modm m A -B jmodm.

Подобное обстоятельство позволяет использовать всего две таблицы для проведения модульного сложения и вычитания, соответствующие 1/8 полной таблицы, соответственно таблицу 2 для модульного сложения и таблицу 3 для модульного вычитания, хотя при проведении одной из этих операций необходимо использовать сразу две таблицы с применением коммутатора прототипа.

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

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

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

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

На чертеже представлена структурная схема устройства, где: 1 - вход первого операнда устройства, 2 второго операн0 да устройства, 3 - первый дешифратор, 4 - второй дешифратор, 5 - первая группа элементов ИЛИ, 6 - вторая группа элементов ИЛИ, 7 - первый элемент ИЛИ, 8 - второй элемент ИЛИ, 9 - сумматор по модулю два,

5 10 - коммутатор, 11 - первый шифратор, 12 - второй шифратор, 13 - третий шифратор, 14 - первый блок элементов И, 15 - второй блок элементов И, 16 - третий блок элементов И, 17 - первая группа элементов И, 18 0 вторая группа элементов И, 19-третья группа элементов ИЛИ, 20 - первый элемент НЕ, 21 - элемент запрета, 22 - вход признака операции умножения устройства, 23 - третий элемент И, 24 - второй элемент НЕ, 25

5 - вход признака операции вычитания устройства, 26 - вход признака операции сложения устройства, 27 - пятый элемент ИЛИ, 28 - первый элемент И, 29 - второй элемент И. 30 - третий элемент ИЛИ, 31 - первый

0 блок элементов ИЛИ, 32 - четвертый блок элементов И, 33 - преобразователь кода числа в дополнительный код по модулю, 34 - пятый блок элементов И, 35 - четвертый элемент И, 36 - четвертый элемент ИЛИ, 37 5 третий элемент НЕ, 38 - второй блок элементов ИЛИ, 39 - выход устройства,

Входы первого 1 и второго 2 операндов устройства соединены соответственно с входами первого 3 и второго 4 дешифрато0 ров, младшие выходы групп первого 3 и второго 4 дешифраторов соединены соответственно с первыми входами элементов ИЛИ первой 5 и второй 6 групп, старшие выходы групп первого 3 и второго 4 дешиф5 раторов соединены соответственно с входами первого 7 и второго 8 элементов ИЛИ, выходы которых соединены соответственно с входами первого и второго слагаемых сумматора 9 по модулю два, выходы элементов

0 ИЛИ первой 5 группы соединены с соответствующими информационными входами группы коммутатора 10, выход которого соединен с входами шифраторов с первого по третий (11,12,13), выходы которых соедине5 ны с первыми входами блоков элементов И соответственно с первого по третий (14,15,16), старшие выходы групп первого 3 и второго 4 дешифраторов соединены соответственно со вторыми входами элементов ИЛИ первой 5 и второй 6 групп, выходы

которой соединены соответственно с первыми входами элементов И первой 17 и второй 18 групп, выходы которых соединены соответственно с первыми и вторыми входами элементов ИЛИ третьей 19 группы, выходы которых соединены с соответствующими управляющими входами группы коммутатора 10, вторые входы элементов И первой 17 группы соединены с выходом первого 20 элемента НЕ, вход которого соединен с вторыми входами второй 18 группы элементов И и с выходом элемента 21 запрета устройства, вход 22 признака операции умножения устройства соединен со вторым входом третьего 16 блока элементов И, с первым входом третьего 23 элемента И и с управляющим входом элемента 21 запрета, информационный вход которого соединен с выходом второго 24 элемента НЕ, а выход - со вторым входом второго 15 блока элементов И, входы признаков операций сложения 25 и вычитания 26 устройства соединены соответственно с первым и вторым входами пятого 27 элемента ИЛИ, а также соединены соответственно с первыми входами первого 28 и второго 29 элементов И, вторые входы которых соединены с инверсным и прямым выходами сумматора 9 по модулю два, а выходы с первым и вторым входами третьего 30 элемента ИЛИ, выход которого соединен с вторым входом первого 14 блока элементов И и с входом второго 25 элемента НЕ, выходы блоков элементов И с первого по третий (14.15.16) соединены с соответствующими входами первого блока 31 элементов ИЛИ, выход которого соединен с первым входом четвертого 32 блока элементов И и с входом преобразователя 33 кода числа в дополнительный код по модулю, выход которого соединен с первым входом пятого 34 блока элементов И, выход первого элемента ИЛИ соединен с первым входом четвертого 35 элемента И, второй вход которого соединен с выходом пятого 27 элемента ИЛИ. а выход - с первым входом четвертого 36 элемента ИЛИ, прямой выход сумматора 9 по модулю два соединен со вторым входом третьего 23 элемента И, выход которого соединен со вторым входом четвертого 36 элемента ИЛИ, выход которого соединен ео вторым входом пятого 34 блока элементов И, а через третий 37 элемент НЕ - со вторым аходом четвертого 32 блока элементов l/i, выходы четвертого 32 и пятого 34 блоков элементов И соединены с соответствующими входами второго 38 блока элементов ИЛИ, выход которого является выходом 39 устройства. Работу устройства удобно рассмотреть а трех режимах (1-режим модульного сложения, 2-режим модульного вычитания, 3- режим модульного умножения).

В первом режиме - определение результата модульного сложения (A-t-B)modm (управляющий сигнал присутствует на шине

25)первый А и второй В операнды поступают на соответствующие дешифраторы 3 и 4. С выхода дешифратора 3 операнд В поступает на соответствующий элемент ИЛИ 5, с

0 выхода которого - на соответствующий информационный вход коммутатора 10. Операнд В с выхода дешифратора 4 поступает на соответствующий элемент ИЛИ 6, с выхода которого через соответствующий эле5 мент И17 (сигнал на выходе элемента НЕ 20 присутствует) - на определенный элемент ИЛИ 19. С выхода ИЛИ 19 сигнал, соответствующий операнду В, поступает на один из управляющих входов коммутатора 10. Шиф0 раторы 14,16 реализуют двоичное представление результата модульных операций согласно таблиц 2,3 и 1 соответственно. Изменение операции модульного сложения на операцию модульного вычитания (измене5 ние таблицы 2 на 3) происходит в том случае, когда уд &УВ . Это производится с помощью элементов И28, И29, ИЛИЗО, НЕ24 и элемента запрета 21 при использовании управляющих сигналов 26 и 25, а также сигна0 ла с выходов (прямого и инверсного) сумматора 9 по модулю.два. Сигнал с прямого выхода соответствует случаю УА 5й УВ .Таким образом сигнал, соответствующий результату операции с выхода шифра5 тора 11 (уд ув) или шифратора 12 (уд ув) поступает через И 14 либо И 15 на соответствующий вход блока элементов ИЛИ 31. Использование преобразователя кода 33 числа в дополнительный код по мо0 дулю производится в том случае, когда уд 1 (сигналом с выхода первого 7 элемента ИЛИ с использованием элементов ИЛИ 27, И 35, ИЛИ 36). Если уд 1, то сигнал с выхода элемента ИЛИ 36 отсутствует и сигнал

5 с выхода элемента НЕ 37 открывает блок элементов И 32. Результат операций (A+B)modm через блок элементов ИЛИ 38 поступает на выход 39 устройства. При уд 1 сигнал с выхода элемента ИЛИ 36 открывает блок элементов И 34. Результат операции модульного сложения, инвертированный по модулю m устройства, через преобразователь 33 кода, блок элементов И 34 и блок элементов ИЛИ 38 поступает на

выход 39 устройства.

Во втором режиме - определение результата модульного сложения (A-B)modm (управляющий сигнал присутствует на шине

26)процессы в устройстве при изменении

0

таблиц (сложения и вычитания), а также коррекции результата операции происходят аналогичным образом при ранее описанных управляющих сигналах с точностью до номера коммутируемой таблицы (вместо таблицы сложения таблица вычитания). Отметим также, что при использовании таблицы 3 (модульного вычитания) происходит коммутация выходов элементов ИЛИ 6 при помощи элементов И 18 и элементов ИЛИ 19.

Третий режим - определение результата модульного умножения A-Bmodm (управляющий сигнал присутствует на входе 22). Операнды аналогично описанным ранее случаям поступают на входы коммутатора 10 (только переключения второго операнда здесь не происходит). Используется в данном случае шифратор 13 в паре с блоком 16 элементов И, а сигнал на включение коррекции результата при уд ув поступает с выхода элемента ИЛИ 36 через элемент И 23. При уд ув результат операции определяется непосредственно по таблице 1.

Рассмотрим примеры конкретного выполнения модульных операций при .

П р и м е р 1. Пусть необходимо определить результат операции модульного сложения для , . (уд ув 0).

В этом случае используется таблица 2, т.к. поступит сигнал с выхода И28, ИЛИ 30 на вход И 14. Присутствует сигнал на выходе элемента НЕ 20 и выходе элемента НЕ 37. Результат операции, равный, поступает на выход 39 устройства.

Пример 2. Пусть необходимо определить результат операции модульного сложения для , (уд 1, ув 0).

В этом случае и используется таблица 3, т.к. поступит сигнал с выхода элемента НЕ 24 через элемент 21 запрета на вход блока 15 элементов И. Этот сигнал поступит на входы элементов И 18, произведя коммутацию второго операнда в соответствии с таблицей 3. Присутствует сигнал на выходе элемента И 35 (уд 1), который через ИЛИ 36 поступит на вход блока 34 элементов И. Результат получится схематично следующим образом

(7 + 2)mod11 lH4-2)mod11 (11-2)mod11 9mod11

Пример 3. Пусть необходимо определить результат операции модульного сложения для , 0, ув 1).

В этом случае и используется таблица 3 аналогично предыдущему случаю, но сигнала с выхода элемента И 35 не будет (уд з 1) поэтому схематично имеем

(3+8)mod1 M3-3)mod11 0mod11

0

5

0

5

0

5

0

5

0

5

Пример 4. Пусть необходимо определить результат операции модульного сложения для , (уд ув 1).

В этом случае . и используется таблица 2 (присутствует сигнал с выхода элемента И 28). Имеем сигнал также с выхода элемента И 35 (уд 1),т.е.

(8+9)mod11 11-(3+2)mod1 Ц11-5)mod11 6mod11

Пример 5. Пусть необходимо определить результат операции модульного вычитания при , (уд 0, ув 1).

В данном случае используется таблица 2 (уд ув) и сигнал на выходе элемента И 29 присутствует, а на выходе элемента И 35 отсутствует (уд М), т.е. имеем

(3-8)mod 1 НЗ+(11 -8) mod 11 6mod 11

Пример 6. Пусть необходимо определить результат операции модульного умножения при , (уд 1, ув 0).

В данном случае используется таблица 1 (присутствует сигнал на входе блока 16 элементов И и на выходе элемента И 23, а следовательно, и блока 34 элементов И, т.е.

8 2 (mod 11) 11-(11-8) -2 mod11

(11-6)mod11 5mod11

Техническое преимущество заявляемого изобретения по сравнению с прототипом состоит в существенном уменьшении оборудования и повышении его коэффициента использования. Это достигается применением всего трех таблиц для производства всех модульных операций (сложения, вычитания и умножения) за счет использования выведенных соотношений для модульного сложения и вычитания, что существенно уменьшает требуемые переключения. Также отсутствуют сложные переключения входных операндов А и В при подсоединении к симметричному коммутатору (использующему свойства симметрии таблиц 1,3).

Достоверность достижения поставленной цели подтверждается примерами выполнения модульных операций для .

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

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

и

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

Таблица I.

Таблица 2

Таблица 3