Арифметическое устройство по модулю

 

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5!)5 G

ОПИСАНИЕ ИЗОБРЕТЕ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4900966/24 (22) 09.01.91 (46) 15.11.92. Бюл. ¹ 42 (72) В.А.Краснобаев, В.П.Ирхин, Н.И.Можаев, M,Н.Кукушкин, М.В.Квасов и И.В.Приходько (56) Авторское свидетельство СССР

N 999050, кл. G 06 F 7/72, 1981.

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

N 1571583, кл, G 06 F 7/72, 1989.

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

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

Наиболее близким по технической сущности к предлагаемому изобретению является устройство, которое позволяет реализовать умножение, сложение и вычитание по модулю в системе остаточных классов и содержит дешифраторы, группы элементов И и ИЛИ, элементы И и ИЛИ, сумматор по модулю два, элементы НЕ и Ы 1775721 А1 (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ПО

МОДУЛЮ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения — сокращение аппаратурных затрат.

Сущность изобретения состоит в исключении ряда этапов коммутации и использовании. всего трех, таблиц для реализации всех модульных операций. 1 ил„Э табл. (/3 коммутатор, Для выполнения всех операций необходимо большее количество коммутационного.оборудования, что и обусловливает основной недостаток устройства.

Недостаток прототипа — большой объем используемого оборудования, ввиду того, что для реализации всех модульных операций требуется выполнить с переключениями пять таблиц на одном коммутаторе. (Л

Цель изобретения — сокращение аппаратурных затрат. M

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

1775721

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

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

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

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

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

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

2 2 где m — модуль устройства. Если обозначен индекс операнда уд (ув) как

0, если 0

>д (») = п1 + 1 2

1, если

При yA =ye=0

А В (тоба)=А В (modm).

При yA = О, ув = 1

А В (modm} = m-А В (modm), где S = m-В.

П ри ) д = 1, > = 0

А В (modm) = m-А В (modm), гдеА =m — А.

При уд =/a =1

А В (modm) = А В (modm).

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

1775721 (А+В) modm =- (А+В) modm; (А — В) modm =

=(А — В) modm; и ри yA = 0, 1в = 1 (Р+ В) modm = (А-В ) modm; (А — В) mod m =

= (А+В ) modm; 5 при д = 1, ув,= 0 (А+В) modm = m (À -B)modm; (А-B)modm=

= m— - (A+B)modm; при уд = уц = 1 (A+B)modm=m — (А+В )modm; (А — B)modm= "0

= m — (А — В )modm.

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

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

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

Заявляемое техническое решение соответствует критерию "новизна", т,к. введенные новые признаки (две группы элементов

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

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

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

ИЛИ, 7 — первый элемент ИЛИ, 8 — второй элемент ИЛИ, 9 — сумматор по модулю два, 10 — коммутатор, 11 — первый шифратор, 12 — второй шифратор, 13 — третий шифратор, 14 — первый блок элементов И, 15 — второй блок элементов И, 16 — третий блок элементов И, 17 — первая группа элементов И, 18— вторая группа элементов И, 19 — третья группа элементов ИЛИ, 20 — первый элемент НЕ, 21 — элемент запрета, 22 — вход признака операции умножения устройства, 23 — третий элемент И, 24 — второй элемент НЕ, 25 — вход признака операции вычитания устройства. 26 — вход признака операции сложения устройства, 27 — пятый элемент ИЛИ, 28 — первый элемент И, 29 — второй элемент

И, 30 — третий элемент ИЛИ, 31 — первый блок элементов ИЛИ, 32 — четвертый блок элементов И, 33 — преобразователь кода .числа в дополнительный код по модулю, 34— . пятый блок элементов И, 35 — четвертый элемент И, 36 — четвертый элемент ИЛИ, 37— третий элемент НЕ, 38 — второй блок элементов ИЛИ, 39 — выход устройства, Входы первого 1 и второго 2 операндов устройства соединены соответственно с входами первого 3 и второго 4 дешифраторов, младшие выходы групп первого 3 и второго. 4 дешифраторов соединены соответственно с первыми входами элементов ИЛИ первой 5 и второй 6 групп, старшие выходы групп первого 3 и второго 4 дешифраторов соединены соответственно с входами первого 7 и второго 8 элементов ИЛИ, выходы которых соединены соответственно с входами первого и второго слагаемых сумматора 9 по модулю два, выходы элементов

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

ИЛИ первой 5 и второй 6 групп, выходы

1775721

10

15 выходом второго 24 элемента НЕ, а выход— со вторым входом второго 15 блока элемен- 20

55 которой соединены соответственно с первыми входами элементов И первой 17 и второй 18 групп, выходы которых соединены соответственно с первыми и вторыми входами элементов ИЛИ третьей 19 группы, выходы которых соединены с соответствующими управляющими входами группы коммутатора 10, вторые входы элементов И первой 17 группы соединены с выходом первого 20 элемента НЕ, вход которого соединен с вторыми входами второй 18 группы элементов И и с выходом элемента 21 запрета устройства, вход 22 признака операции умножения устройства соединен со вторым входом третьего 16 блока элементов И, с первым входом третьего 23 элемента И и с управляющим входом элемента 21 запрета, информационный вход которого соединен с тов И, входы признаков операций сложения

25 и вычитания 26 устройства соединены соответственно с первым и вторым входами пятого 27 элемента ИЛИ, а также соединены соответственно с первыми входами первого

28 и второго 29 элементов И, вторые входы которых соединены с инверсным и прямым выходами сумматора 9 по модулю два, а выходы с первым и вторым входами третьего 30 элемента ИЛИ, выход которого соединен с вторым входом первого 14 блока элементов И и с входом второго 25 элемента

НЕ, выходы блоков элементов И с первого по третий (14,15.16) соединены с соответствующими входами первого блока 31 элементов ИЛИ, выход которого соединен с первым входом четвертого 32 блока элементов И и с входом преобразователя ЗЗ кода числа в дополнительный код по модулю, выход которого соединен с первым входом пятого 34 блока элементов И, выход первого 7 элемента ИЛИ соединен с первым входом четвертого 35 элемента И, второй вход которого соединен с выходом пятого 27 элемента ИЛИ. а выход — с первым входом четвертого 36 элемента ИЛИ, прямой выход сумматора 9 по модулю два соединен со вторым входом третьего 23 элемента И, выход которого соединен со вторым входом четвертого 36 элемента ИЛИ, выход которого соединен со вторым входом пятого 34 блока элементов И, а через третий 37 элемент НЕ— со вторым входом четвертого 32 блока элементов И, выходы четвертого 32 и пятого 34 блоков элементов M соединены с соответствующими входами второго 38 блока элементов ИЛИ, выход которого является выходом 39 устройства, Работу устройства удобно рассмотреть а трех режимах (1-режим модульного сло30

40 жения, 2 — режим модульного вычитания, 3режим модульного умножения).

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

25) первый А и второй В операнды поступают на соответствующие дешифраторы 3 и 4.

С выхода дешифратора 3 операнд В поступает на соответствующий элемент ИЛИ 5, с выхода которого — на соответствующий информационный вход коммутатора 10. Операнд В с выхода дешифратора 4 поступает на соответствующий элемент ИЛИ 6, с выхода которого через соответствующий элемент И17 (сигнал на выходе элемента НЕ 20 присутствует) - на определенный элемент

ИЛИ 19. С выхода ИЛИ 19 сигнал, соответствующий операнду В, поступает на один из управляющих входов коммутатора 10. Шифраторы 14,16 реализуют двоичное представление результата модульных операций согласно таблиц 2,3 и 1 соответственно. Изменение операции модульного сложения на операцию модульного вычитания (изменение таблицы 2 на 3) происходит в том случае, когда уд уБ . Это производится с помощью элементов И28, И29, ИЛИЗО, НЕ24 и элемента запрета 21 при использовании управляющих сигналов 26 и 25, а также сигнала с выходов (прямого и инверсного) сумматора 9 по модулю,два, Сигнал с прямого выхода соответствует случаю уд Ф ув .Таким образом сигнал, соответствующий результату операции с выхода шифратора 11 (yA =ув) или шифратора 12 (1 А A®) поступает через И 14 либо И 15 на соответствующий вход блока элементов

ИЛИ 31. Использование преобразователя кода 33 числа в дополнительный код по модулю производится в том случае, когда уд =

1 (сигналом с выхода первого 7 элемента

ИЛИ с использованием элементов ИЛИ 27, И 35, ИЛИ 36), Если уд Ф 1, то сигнал с выхода элемента ИЛИ 36 отсутствует и сигнал с выхода элемента НЕ 37 открывает блок элементов И 32. Результат операций (A+8)modm через блок элементов ИЛИ 38 поступает на выход 39 устройства. При уд =

=1 сигнал с выхода элемента ИЛИ 36 открывает блок элементов И 34. Результат операции модульного сложения, инвертированный по модулю m устройств-, через преобразователь ЗЗ кода, блок элементов И

34 и блок элементов ИЛИ 38 поступает на выход 39 устройства.

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

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

1775721

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

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

19, Третий режим — определение результата модульного умножения A Bmodm (управляющий сигнал присутствует на входе 22), Операнды аналогично описанным ранее 15 случаям поступают на входы коммутатора

10 (только переключения второго операнда здесь не происходит), Используется в данном случае шифратор 13 в паре с блоком 16 элементов И, а сигнал на включение коррек- 20 ции результата при уд ув поступает с выхода элемента ИЛИ 36 через элемент И 23.

При уд =уa результат операции определяется непосредственно по таблице 1.

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

Пример 1. Пусть необходимо определить результат операции модульного сложения для А=З, B=4, (yA = ye .= О).

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

Результат операции, равный 7, поступает на выход 39 устройства. 35

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

В этом случае А=11-7=4 и используется таблица 3, т,к. поступит сигнал с выхода 40 элемента НЕ 24 через элемент 21 запрета на вход блока 15 элементов И. Этот сигнал поступит на входы элементов И 18, произведя коммутацию второго операнда в соответствии с таблицей 3, Присутствует сигнал на 45 выходе элемента И 35 (уд = 1), который через ИЛИ 36 поступит на вход блока 34 элементов И. Результат получится схематично следующим образом (7+2) mod11 = 11 — (4 — 2)mod11=(11 — 2)mod11= 50

= 9воб11

Пример 3. Пусть необходимо определить результат операции модульного сложения для А=З, В=8 (yA = О, ys = 1).

В этом случае В=11-8=3 и используется таблица 3 аналогично предыдущему случаю. но сигнала с выхода элемента И 35 не будет (уд 1) поэтому схематично имеем (3+8)mod11=(3 — 3)mod11=0mod11

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

B этом случае А=11 — 8=3, B=11 — 9=2 и используется таблица 2 (присутствует сигнал с выхода элемента И 28). Имеем сигнал также с выхода элемента И 35 (yA = 1),т.е, (8+9)mod11=11 — (3+2) воб11=(11-5)mod11=

= 6mod11

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

В данном случае используется таблица

2 (уд W уя) и сигнал на выходе элемента И 29 присутствует, а на выходе элемента И 35 отсутствует (уд <1), т.е, имеем (3 — 8)тоб11=(3+(11-8)) тоб11=6тоб11

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

В данном случае используется таблица

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

8 2 (mod11) =11 — ((11 — 8) . 2)mod11=

= (11-6)mod11=5mod11

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

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

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

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

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

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

ИЛИ первой и второй групп. выходы элементов ИЛИ второй группы соединены соответственно с первыми входами элементов

И первой и второй групп, выходы элементов

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

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

15 которого соединен с вторым входом первого блока элементов И и входом второго элемента Н Е, выходы элементов И блоков с первого по третий соединены с соответствующими входами элементов ИЛИ первого

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

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

ИЛИ. а выход — с первым входом четвертого

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

35 элементов И пятого блока и через третий элемент НŠ— с вторыми входами элементов

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

40 второго блока, выходы которых являются выходом устройства.

1775721

Таблица 3

Таблица 2

Составитель В.Краснобаев

Техред М.Моргентал Корректор Н.Тупица

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 4034 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5