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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения -.упрощение устройства. Цель достигается за счет реализации операций модульного сложения и вычитания при помощи одного преобразователя 20 кода числа в дополнительный код по модулю путем введения третьего элемента ИЛИ 27, пятого 24 и шестого 22 элементов И, первого 23 и второго 28 элементов НЕ, преобразователя 20 кода числа в дополнительный код по модулю , шифратора 29 в устройство, содержащее дешифратор 2, первую и вторую группы элементов И 3,4, кольцевой регистр 17 сдвига , элементы И Т2, 13, 15, 16, группу 8 элементов ИЛИК приемный регистр 9, схему 10 сравненияГсчетчик 11, дешифратор 18, группы 7 и 21 элементов И. 1 табл. ,1 ил.

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

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

РЕСПУБЛИК (5ц5 G 06 F 7/72

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕН

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. (21) 4921634/24 (22) 26.03.91 (46) 07.06.93. Бюл. М 21 (72) В.А.Краснобаев, В.П.Ирхин, Н.И.Можаев и М.Н;Кукушкин (56) Авторское свидетельство СССР

ЬЬ 1247868. кл. 6 06 Г 7/72, 1985.

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

N. 1257643, кл. 6 06 F 7/72, 1984. (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ (57) Изобретение относится к автоматике и . вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения — уп,, . Ы,, 1820379 А1 рощение устройства. Цель достигается за счет реализации операций модульного сложения и вычитания при помощи одного преобразователя 20 кода числа в дополнительный код по модулю путем введения третьего элемента ИЛИ 27, пятого 24 и шестого 22 элементов И, первого 23 и второго 28 элементов НЕ, преобразователя

20 кода числа в дополнительный код по модулю, шифратора 29 в устройство, содержащее дешифратор 2, первую и вторую группы элементов И3,4, кольцевой регистр17сдвига, элементы И 12, 13, 15, 16, группу 8 элементов ИЛИ, приемный регистр 9, схему 10 сравнения, счетчик 11, дешифратор 18, группы 7 и 21 элементов И. 1 табл.,1 ил.

18203Т9

Изобретение относится к автоматике и устройства, 15 — четвертый элемент И, 16— вычислительной технике и может быть ис- третий элемент И, 17 — кольцевой регистр пользовано в вычислительных машинах и сдвига,18-второйдешифратор,19-второй устройствах, функционирующих в системе элемент ИЛИ, 20 — преобразователь кода остаточных классов, числа в дополнительный код по модулю, Цель изобретения — упрощение устрой- 21 — четвертая группа элементов И, 22— ства. шестой элемент И, 23 — первый элемент НЕ, Сущность изобретения состоит s упро- 24 — пятый элемент И, 25 — вход операции щении устройства за счет исключения из вычитания устройства, 26- вход операции схемы трех сумматоров по модулю m, шести 10 сложения устройства, 27 — третий элемент групп элементов. И, группы элементов ИЛИ, ИЛИ, 28 — второй элемент НЕ, 29 — шифразлемента ИЛИ, умножителя частоты и их тор, 30- выход устройства, 31 — вход управлогических связей при сохранении всех ления устройства. функциональных и технических возможно- Первый информационный вход 1 устстей устройства путем введения двух инвер- 15 ройства подключен к входу первого дешифторов, двух элементов И, одного элемента ратора 2, выходы которого подключены к

ИЛИ, шифратора. Обозначим через 9+= В- .первым входам соответствующих злеменположительный сдвиг на В разрезов содер- тов И 3 первой группы. Выходы элементов жимого КСР. Рассмотрим связь проводимой И 4 второй группы соединены с соответствумодульной операции расположения второго . 20 ющими входами первого элемента ИЛИ 5, а операнда (В), минимальное количество первые входы элементов И 4 второй группы сдвигов КСР, необходимое для получения соединены с соответствующими выходами результата, и направление сдвига. Получен- кольцевого регистра 17 сдвига. Второй инные результаты представлены в таблице, формационный вход 6 устройства соединен

Эта таблица может быть реализована 25 с первыми входами элементов. И третьей при помощи только одного преобразовате- . группы 7. Выходы элементов ИЛИ группы 8 ля кода числа в дополнительный код по мо- соединены с информационными входами дулю. Дальнейшее упрощение устройства приемного регистра 9, выходы которого совозможно уменьшением количества выхода единены с первыми информационными sxoдешифратора операнда В вдвое, т.е. пред- 30 дами схемы 10 сравнения. Вторые ставлять в унитарном коде только информационные входы последней соедиm — 2 нены с выходами суммирующего счетчика

2 11, вход которого соединен с выходом втбранда В реализовать с помощью.инвертора. рого элемента И 13. Выход схемы 10 сравПоложительный эффект от внедрения 35 нениясоединенспервымивходамипервого изобретениясостоитвупрощенииустройст- 12 и второго 13 элементов И, с вторыми ва: уменьшении количества оборудования и входами элементов И 4 второй группы. Такупрощении количества логических связей товый вход 14 устройства соединен с вторымежду элементами устройства; повышении ми входами первого 12 и второго. 13 эффективности использования оборудова- 40 элементовИ, Первыйвходтретьегозлемено ния. Данное обстоятельство позволяет та И 16 соединен с первым входом четверуменьшитьстоимостьоперациимодульного того элемента И 15. выходы третьего 16 и сложения и вычитания, а.также уменьшить четвертого 15 элементов И соединены сооТ стоимость всего устройства. ветственно с входами сдвига вправо содерТехническое преимущество изобрете- 45 жимого кольцевого регистра 17 сдвига и с нйя состоит в упрощении устройства; что входом сдвига влево содержимого кольцеповышает надежность устройства сложения soro регистра 17 сдвига. Выходы элементов и вычитания по модулю m. И 3 первой группы соединены с третьими

На чертеже представлена структурная входами соответствующих элементов И 4 схеМа устроиства. где 1 — первыи информа- 50 второй гру и од О второй группы. Выходы (О... } второго ционный вход устройства, 2 — первый де- " 2 шифратор, 3 — первая группа элементов И, дешифратора 18 подключены к входам вто4 — вторая группа элементов И, 5 — элемент рого элемента ИЛИ 19. Второй информациИЛИ. 6 — второй информационный вход ус- онный вход 6 устройства подключен к входу тройствэ, 7 — третья группа элементов И, 55 второго дешифратора 18 и к входу преобра8 — группа элементов ИЛИ, 9 — приемный зователя 20. кода числа в дополнительный регистр. 10 — схема сравнения, 11 — сумми- код по модуле, выход которого подключен к рующий счетчик, 12 — первый элемент И, первым входам элементов И четвертой груп13 — второй элемент И, 14 — тактовый вход пы 21. Выход второго элемента ИЛИ 19 соединен с первым входом шестого элемента

1820379

И 22, вторыми входами элементов И третьей группы 7 и с входом первого элемента НЕ

23, выход которого соединен с первым входом пятого элемента И 24 и вторыми входами элементов И четвертой группы 21.

Вторые входы пятого 24 и шестого 22 элементов И являются соответственно входами ,операций вычитания 25 и сложения 26 устройства, а выходы пятого 24 и шестого 22 элементов И соединены с первым и вторым входами третьего элемента ИЛИ 27, выход которого соединен с втдрым входом третьего элемента И 16 и входом второго элемента

НЕ 28, выход которого соединен с вторым входом четвертого элемента И 15. Выходы элементов И третьей 7 и четвертой 21 групп соединены с соответствующими входами элементов ИЛИ группы 8. Выход первого элемента И 12 соединен с первым входом четвертого элемента И 15, выход nepaoro элемента ИЛИ 5 соединен с входом шифратора 29, выход которого является выходом

30 устройства. Вторые входы элементов И

3 первой группы соединены с входом 31 управления устройства.

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

Преобразователь 20 кода числа в дополнительный код по модулю инвертирует по модулю m (m — модуль устройства) входного операнда В. В момент поразрядного совпадения состояний соответственно приемного регистра 9 и суммирующего счетчика 11 схема поразрядного сравнения вырабатывает сигнал совпадения. Количество двоичных разрядов кольцевого регистра 17 равно количеству возможных остатков по исходному модулю m.

Пусть необходимо определить (А—

В) mod т (присутствует сигнал входа 25 операции вычитания). Исходное состояние устройства; нулевое состояние регистров 9, 17 и суммирующего счетчика 11. Операнд А перед началом работы по сигналу с входа 31 управления записывается в унитарном коде в кольцевой регистр 17 сдвига в виде единицы в соответствующий разряд, Через нулевой информационный вход 1 поступает первый операнд А, а через второй информационный вход 6 в двоичном коде поступает второй операнд В. Преобразователь 20 кода числа в дополнительный код по модулю преобразует число В в m — В. Первый дешифратор 2 преобразует операнд А из двоичного кода в унитарный и соответствующий сигнал поступает на определенный элемент И

3 первой группы. Операнд В поступает на первые входы элементов И третьей группы

7, а на первые входы элементов И четвертой группы 21 поступает операнд а-В. Второй дешифратор 18 преобразует второй операнд В из двоичного кода в унитарный. если

0 В 2, т.е. количество выходов с <

5 второго дешифратора 18 равно — . Пусть

fTl

0 В 2, тогда с выхода второго элемента ИЛИ 19 поступает сигнал на вход

10 шестого элемента И 22 и на вторые входы элементов И третьей группы 7, обеспечивая прохождение второго операнда В и двоичном коде через элементы ИЛИ группы 8 в приемный регистр 9. На выходе третьего

15 элемента ИЛИ 27 сигнала нет и, следовательно, на вход четвертого элемента И 15 поступает сигнал. С тактового входа 14 на входы открытых элементов И 12 и 13 поступают импульсы. С выхода элемента И 12

20 через открытый четвертый элемент И 15 на вход сдвига вправо содержимого кольцевого регистра 17 поступает последовательность из В импульсов. В момент совпадения состояния суммирующего счетчика 11 и п ри25 емного регистра 9 схема 10 сравнения выдает сигнал, который закрывает элементы И

12, 13 и открывает соответствующий эле-. мент И 3 первой группы и элемент И 4 второй группы, через который состояние

30 регистра 17 (установившееся после сдвига на Q+= В) через первый элемент ИЛИ 5 поступает в унитарном коде (результат операции) и далее через шифратор 29 (в двоичном коде} на выход 30 устройства. При

35 m — В m — 1 выходной сигнал первого

2 элемента НЕ 23 поступает на вход элемента

И 24, а также на вторые входы элементов И четвертой группы 21. С выхода преобразо40 вателя 20 кода числа в дополнительный код по модулю значение m  через группу 8 элементов ИЛИ поступает в приемный регистр 9. Сигнал с выхода элемента И 24 через элемент ИЛИ 27 открывает элемент И

45 16, а с. выхода элемента И 12 на вход сдвига влево содержимого регистра 17 поступает последовательность из m — В импульсов, сдвигая íà Q= (m — В) разрядов единицу s содержимом регистра 17, после чего пол50 ученный результат через вторую группу элементов И 4, элемент ИЛИ 5 и шифратор 29 поступает на выход 30 устройства.

Если необходимо определить результат операции {А+ В} mod m (присутствует сигнал

55 входа 26 операции сложения), то в этом случае работа устройства аналогична определению результата операции модульного сложения при изменении направления сдвига кольцевого регистра 17 сдвига на

1820379 противоположное для данного второго операнда В.

Рассмотрим примеры конкретного выполнения операции для m "5. В этом случае исходное состояние кольцевого 5 регистра 17 сдвига можно схематично представить в виде

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

Посигналус входа31управления врегистре 15

17 установлено состояние

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

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

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

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

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

55 третьего элемента И соединен с первым входом четвертого элемента И, выходы третьего и четвертого элементов И соединены соответственно с входами сдвига вправо содержимого кольцевого регистра сдвига и с входом сдвига влево содержимого кольце-.

Так как — » В»5-1, то сигнал с выхода

5 . 2 элемента ИЛИ 27 открывает элемент-И 16.

В приемном регистре 9 будет записано 5—

4 = 1 в двоичном коде. Следовательно, происходит сдвиг на один разряд регистра 17 в отрицательном направлении(И=-1). Состояние регистра 17 будет

0 — 0 — 0 — 1 — О. о

Это соответствует унитарному коду числа

3. (2 — 4) mod 5=3mod 5.

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

m — 2 как 0 » В» —,тооткрываетсяэлемент

И 16. В приемном регистре 9 будет записано число 1 в двоичном коде. Следовательно, происходит сдвиг на один разряд. регистра

17 в отрицательном направлении. Исходное состояние регистра 17 будет как и в первом примере, а конечное

С :. ... :.. 3

Это соответствует унитарному коду числа

3 (А+ В) mod в=(2+1) mod 5=5

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

НЕ, двух элементов И, одного элемента

ИЛИ.

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

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

1820379

Составитель 8.. Ирхин

Техред М.Моргентал Корректор Л. Пилипенко

Редактор С. Кулакова

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

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

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

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

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

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

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

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