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

 

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

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

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

РЕСПУБЛИК (st)s G 06 F 7/49, 7/72

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4768659/24 (22) 11.12.89 (46) 23;08.92. Бюл. М 31 (72) B.À.Êðàñíîáàeâ, В.П.Ирхин, И.В.Милехин и М.В.Юмашев (56) Авторское свидетельство СССР

N 1257643, кл. G 06 F 7/72, 1986.

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

М 1532923, кл. G 06 F 7/72, 1988, Авторское свидетельство СССР

N 1636844, кл; G 06 F 7/72, 1989, (54)АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ПО

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

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

Недостатком устройства являются низкие функциональные возможности.

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

Недостатком этого уст ройства являются низкие функциональные возможности,,,БЫ„„1756881 А1 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Целью изобретения является расширение области применения за счет выполнения деления. Устройство содержит два дешифратора, два шифратора, пять элементов И, три элемента ИЛИ, пять блоков элементов И, вычитатель, два блока элементов ИЛИ, приемный регистр, счетчик, схему сравнения, два элемента запрета, кольцеьой сдвигающий регистр, элемент

НЕ, матрицу элементов И. 1 ил., 4 табл.

С::

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

Недостатком данного устройства явля- О© ются низкие функциональные возможности ввиду невозможности получения результата О операции модульного деления. . Целью изобретения является расширение области применения за счет выполнения деления.

° 33k Зй

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

20

35

50 мент I)Е матрицу элементов И, первый и второй элементы ИЛИ и первый шифратор, причем первый информационный вход устройства соединен с входом первого дешиф-. ратора, второй информационный вход устройства соединен с первым входом первого блока элементов И, с входом вычитаемого вычитателя, вход уменьшаемого и выход которого соединены, соответственно. с входом задания модуля устройства и с первым входом второго блока элементов И, выход задания вычитания устройства соединен с вторым входом второго блока элементов И. выходы первого и второго блоков элементов И соединены, соответственно, с первым и вторым входами первого блока элементов ИЛИ, выход которого соединен с входом второго дешифратора, выходы приемного регистра и счетчика соединены соответственно с первым и вторым входами .схемы сравнения, выход которой соединен с управляющими входами первого и второго элементов запрета, с первым входом третьего блока элементов И, входы разрядов второго входа которого соединен ы, соответственно, с выходами (Iogzm+1}, (m— величина модуля) младших разрядов кольцевого сдвигающего регистра, входы разрешения сдвига право и влево которого соединены, соответственно с выходами первого и второго элементов И, тактовый вход устройства соединен с информационными входами первого и второго элементов запрета, выход второго элемента запрета соединен со счетным входом счетчика, первый вход первого элемента И через элемент

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

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

На чертеже представлена структурная схема устройства, Устройство содержит первый информационный вход 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.

Первый информационный вход 1 устройства соединен с первым входом первого дешифратора 2, второй информационный

1756881 вход 3 устройства соединен с первым вхо- Вход 31 ",здания деления устройства са дом первого блока 4 элементов И, с входом единебн с вторым входом 30 элемента ИЛИ. вычитаемого вычитателя 5, вход уменьшае-. с первыми входами четвертага 32 и пл ога мого и выход которого соединены соответ- 33 элементов И и с первым входом блока 25. ственно с входом 6. задания мо ля адулл 5 входы разрядов второго входа которого соустройства и с первым входом второго бло- единены соответственно с выходами разрлка 7 элементов И. выходы первого 4 и вто- дов, кроме младшего, выхода второго 34 р э ементав И соединены шифратора, входы которого соединены рого 7 блоков элементов соответственно с первым и вторым входами соответственно с нФ<6дами элементов И первого блока 8 элементов ИЛИ, выход ко- 10 матрицы 22, Младший выход дешифрата а торого соединен с входом второго дешиф- 9 соединен с вторым входом элемента И 33, ратора 9, выходы приемного регистра 10 и выход которого является выходом 35 сигнасчетчика 11 соединены соответственно с ла ошибки устройства, выход блока 26 элепервым и вторым входами схемы 12 сравне- ментов ИЛИ соединен С входам пр дом приемного д оторои соединен с управляю- 15 регистра 10, выход элемента ИЛИ 29 соедищими входами первого 13 и второго 14 нен с первым входом третьего элемента И элементов запрета, с первым входом треть- 36, выходы младших разрядов выходов перт ого шифраторов соединены его блока 15 элементов И, входы разрядов ваго 23 и второго 34 шиф ата второго входа которого соединены соответ-. соответственно с вторыми входами третьего ственнос выходами(!оа2т+1),(m — величина 20 36 и четвертого 32 элементов И, выходы модуля) младших разрядов кольцевого которых соединены "соответственно с пе - р р,,ады разреше- вым и вторым входами третьего элемента ния сдвига вправо и влево которого соеди- ИЛИ 37, выход которого. соединен с входом нены соответственно с выходами первого элемента НЕ 20.

17 и второго 18 элементов И, тактовый вход 25 Устройство работает в тр у. р " соединен с информационны- При проведении операции модульного слатов зап т ми входами первого 13 и второго 14 элемен- женил (А+ B)modm в двоичном ко е рета, выход элемента 14 запрета . 1 поступаетаперандА, на вход3 — операнд соединен со счетным вхо ом счетчйк 11 д с етчйка 11, В, который также поступает на вход вычитапервый вход первого элемента И 17 через 30 теля 5 (по модулю т) н по модулю т), на выходе которого

0 соединен с первым входом получим значение (m-В). Сигнал с входа 27 второго элемента И 18, второй вход которо- проходит через элемент И 30

ro абъе инен г в д . вторым входом первого эле- блок 4 элементов И, через который и блок 8 элемент . и открывает мента И 17 и соединен с выходом элемента злемен о ИЛИ В

13 зап ет запрета, выходтретьего блока 15элемен- 35 вход дешифратора 9. С выхода деши атоф р ц ым выходом ра 9 операнд В в унитарном коде поступает

21 устройства, выходы дешифратора 2 сое- на вторые входы элементов И столбцов матдинены соответственно с первыми входами рицы 22, на первые . элементов строк матрицы 22, выходы де- стракматрицы22 поступаетчерездешифрашифратора 9 соединены соответственно с 40 тор 2 операнд А, В зависимости от соотновторыми входами элементов И столбцов . шенил а р А В мат и ы22 вых ы матрицы, выходы элементов И матрицы шифратора 23 образуется двоичное число, твующее количеству сдвигов реги22 соединены соответственно с входами соответствующее ко первого шифратора 23, выходы разрядов, стра 16, а на выходе элеМента И 36 абразукроме младшего которого соединены соот- 45 ется сигнал, если направление сдвига ветственно с входами аз л ов и р р д ервого правае(таккаксигналнавыходеэлемента присутствует). тат сигнал поступа- входа четвертого блока 24 элементов И, вы- .ИЛИ 29 присутствует). Э ходы четвертого 24 и пятого 25 блоков эле- ет на первый вход элемента И 17; а если ментов И соединены соответственно с сигнал отсутствует, то.открывается элемент лем нт первым и вторым входами второго блока 26 50 И 18, обеспечивая левое на з е ов ИЛИ, входы 27 и 28 задания сло- га. С выхода ш ф 23 вое направление сдви. да шифратора через элемент И число сдвигов в двоичном коде жения и вычитания устройства соединены. 24 и.ИЛИ 26 числ соответственно с первым и вторым входами поступает в при м 10. С емныи регистр 10. С входа входы открытых элементов 13 и 14 первого элемента ИЛИ, выход которого 19 на входы откр соединен с вторым входом блока 24 элемен- 55 запрета поступают им, П пульсы, ри совпадечетчика и приемного ред задания сложения устройства нии состояний счетчи 11 соединен с первым входом второго 30 эле- гистра 10 схема 12 мента ИЛИ, выхо .ото ог ра схема сравнения выдает рым входом блока элементов И., выход .оторога соединен свта- сигнал, катарыйзакрывает 13 14 через который значение группы двоичных

1756881

Таблица 2 10

25

В табл, 4 отражено необходимое коли3р чество тактов сдвига для каждой пары операндов и направление сдвйга.

Таблица 4

40 — 45 Следовательно, первый 23 и второй 34

А шифраторы формируют четыре числа: "00", "01", "10"; "11". На входе элемента И 36 а объединяются выходы матрицы 22 элементов И,.которые помечены знаком "-" в табл.2, 50 а на входе элемента и 32 обьединяются выходы матрицы 22 элеметов И, которые помечены знаком "-" в табл. 4, П р и. м е р 1. А = О, В - 2. Необходимо (А + B)mod m. Первый операнд А = 0 посту55 пает на первый дешифратор 2, с входа кото.рого поступает на первый вход первых входов элементов И строк матрицы 22, Операнд В через блок 4 элементов И, блок 8 . элементов ИЛИ поступает на дешифратор 9, С выхода дешифратора 9 поступает на треразрядов (результат операции модульного сложения).поступает на выход 21 устройства.

Пусть необходимо определить результат (А — B)mod m. В этом случае сигнал с 5 входа 28 поступает на блок 7 элементов И, С выхода вычитателя 5 значение.(m — В) через открытый блок 7 элементов И, блок 8 элементов ИЛИ поступает на дешифратор 9.

Дальнейшая работа аналогична определению результата операции модульного сложения.

: Если определяется результат (А/B)mod

m, то присутствует сигнал на входе 31, который открывает блок 4 элементов И, элемент

И 32, блок 25 элементов И. В зависимости от соотношения операндов А и В на выходе шифратора 34 образуется двоичное число, соответствующее количеству сдвигов регистра 16 при модульном делении, а на выходе

И 32 образуется сигнал, если направление сдвига правое при задайной операции. В этом случае на вход приемного регистра 10 информация поступает с выходов элементов ИЛИ 34 через элементы И 25 и ИЛИ 26, а на вход элемента И 17 — с выхода ИЛИ 37.

Дальнейшая работа аналогична определению результата модульного сложения. Если

В = О, то на выходе элемента И 33 будет сигнал, свидетельствующий об ошибке при проведении операции модульного деления (деление на ноль).

Рассмотрйм примеры конкретного выполнения операции модульного сложения, вычитанйя и деления для m = 7.. 35

Исходное состояние регистра 16; 1 — 01-1-0-0-0; Первые три двоичных разряда соответствуют числу "5". Число "3" соответствует сдвигу регистра влево на один двоичный разряд, "2" — вправо на один двоичный разряд и т.д. Составйм таблицу для реализации операции модульного сложения, В табл. 1 отражены результаты операции модульно го сложения.

В табл. 2 отражено необходимое. коли чество сдвига;цля каждой пары операндов и В и напрэвление сдвига. Сдвиг соответст вует полажитбльному направлению сдвиг и отмечен 8 табл. 2 знаком "+".

Таблица 1

Составим таблицу для реализации операции модульного деления, В табл, 3 отражены результаты модульного деления, Таблица 3

1756881

10 тий вход вторых входов элементов И столб- элементы 13 и 14 запрета посгупзкп на ре цов матрицы 22. В приемном регистре 10 гистр 16 и на счетчик 11. В момент совпадебудет записано число "01" согласно таблице - ния состояния регистра 10 и счетчика 11 (в

2 (сигналом с выхода ИЛИ 29 открыт эле- счетчике 11 содержится значение "01") схемент И 36 и блок 24 элементов И). Сигйал на 5 ма 12 сравнения формирует сигнал, закрывыход элемента И 36 не поступит, а на вающий элементы 13 и 14 запрета и элемент И 18 поступйт сигнал. Импульсы открывающий блок 15 элементов И. Состоячерез открытые элементы 13 и 14 запрета ние регистра 16 будет следующее: поступают на регистр 16 и на счетчик 11. B момент совпадения состояния регистра t0 10 0 — 1 — 1 — 0 — Π— 0-1 — 0 и счетчика 11 (в счетчике 11 содержится зна.чение "01") схема 12 сравнения формирует Содержание первых трех разрядов ресигнал, закрывающий элементы 13 и 14 за- гистра 16 и есть результат операции модульпрета и открывающий блок 15 элементов И. ного деления.

Состояние регистра 16 будетследующее: 15 Техническое преимущество предлагаемого устройства в сравнении с известным

0 — 1 — 0 — 1 — 1 — 0 — 0 состоит в расширении области применения за счет выполнения деления с небольшими

Содержание трех разрядов регистра 16 затратами оборудованик через блок 15 элементов И поступает.на 20 Положительный:эффект от внедрения выход 21. Это и есть результат операцйи.: - данного изобретения состоит в расширении

Пример 2. А = О, В = 2. Необходимо функциональных возможностей (одновреопределить (А — B)mod m. менное использование его и для получения

В этом случае на первый вход первых результата операции модульного деления). входов элементов И строк матрицы 22 по- 25 Дополнительным преимуществом данного ступаетсигнал. На шестой вход вторых вхо- способа реализации операции (А/B)mod m . дов элементов И столбцов матрицы 22 является также то, что используется только также поступает сигнал (7 — 2 = 5). В прием- одна матрица 22 элементов И для всех моном регистре 10 будет записано числа " ОО". дульных операций и то,.что быстродействие

Сигнал свыхода элемента И 36 не поступит;. 30 выполнения модульной операции деления а схема 12 сравнения.в момент включения равнобыстродействйювыполнения модульустройства вырабатывает сигнал, закрйва- ных операций сложения in вычитания. ющий элементы 13 и 14 запрета и открывающий блок 15 элементов И. Сдвига не: Ф о р м у л а и з о б р е т е н и я произойдет. Срстояние регистра 16 будет 35 следующее: ду щ: Арифметическое устройство по модулю, содержащее первый и второй дешифрато1 — 0 — 1-1 — 0— — 0 — 0 — 0 . ры, с первого по пятый блоки элементов И, вычитатель, первый и второй блоки элеменСодержимоепервыхтрехдвоичных раз- 40 та ИЛИ, приемный регистр, счетчик, схему рядов регистра 16 представляет результат сравнения, первый и второй элементы заоперации модульного вычитания.. прета, кольцевой сдвигающий регистр, перП ри м е р 3, A=2, В =3. Необходимо вый и второй элементы И, элемент НЕ, определить (А/B)mod m. Первый.oneðàí@ А= матрицу элементов И, первый и второй эле2 поступает:на первый 2 дешифратор, с 45 мейты ИЛИ и первый шифратор, причем выхода которого поступает на третий вход первый информационный вход устройства первых. входов элементов И строк матрицы соединен с входом первого- дешифрато а, р д через блок 4 элементов, ЙЛЙ второй информационный вход устройства через второй 9 дешифратор поступает на соединен с первым входом первого блока четвертый вход вторых входов элементов:И 50 элементов И, входом вычитаемого вычитатестолбцов матрицы 22. Во втором 34 шиф- ля, вход уменьшаемого и выход которого раторе формируется двоичное число, соот- соединены соответственно с входом задаветствующее количеству сдвигов регистра ния модуля устройства и первым входом

16 при операции модульного деленйя (со-. второго блока элементов И, вход задания ном 10 г гласнотаблице4}. Вданномслучаевприем- 55 вычитания устройства сое ин ном регистре будет записано число "01" входом второго блока элементов И, выходы согласно таблице 4 (сигнал присутствует на первого и второго блоков элементов И соевтором входе блока 25 элементов И). Сигнал динены соответственно с первым и вторым с выхода элемента НЕ 20 поступит на вход входами первого блока элементов ИЛИ, выэлемента И 18, Импульсы через открытые ход которого соединен с.входом второгоде1756881

12 шифратора, выходы приемного регистра и счетчика соединены соответственно с первым и вторым входами схемы сравнения, выход которой соединен с управляющими входами первого и второго элементов за- 5 прета, с первым входом третьего блока элементов И, входы разрядов второго входа которого соединены соответственно с выходами (logjam+1), (m — величина модуля) младших разрядов кольцевого сдвигающего 10 регистра, входы разрешения сдвига вправо и влево которого соединены соответственно с выходами первого и второго элементов И, тактовый вход устройства соединен с информационными входами первого и второго 15 элементов запрета, выход второго элемента запрета соединен со счетным входом счетчика, первый вход первого элемента И через элемент HE соединен с первым входом вто- . рого элемента И, второй вход которого обь- 20 единен с вторым входом первого элемента

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

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

1756;l31

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

Техред ММоргентал Корректор Е,Папп

Редактор О.Хрипта

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

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

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

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