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

ОПИСАНИЕ

ИЗОБPЕТЕНИЯ

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

242496

Союа Советских

Социалистических

Республик

Б11ь."1ИОТЕКЛ

Зависимое от авт. свидетельства №

Кл. 42m3, 7/38

Заявлено 08.V1.1967 (№ 1163025/18-24) с присоединением заявки №

Приоритет

Опубликовано 25.1V.1969. Бюллетень № 15

Дата опуоликования описания 5.IX.1969

МПК G 061

УДК 681.325.5.047(088.8) Комитет по делам иаобретеиий и открытий ори Совете Министров

СССР

Автор изобретения

В. Г. Захаров

Институт электронных управляющих машин

Заявитель

УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ОСТАТКА ОТ ЧИСЛА

ПО МОДУЛЮ

Предложенное устройство относится к области вычислительной техники.

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

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

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

На чертеже изображена блок-схема предложенного устройства.

Устройство состоит из нескольких групп сумматоров. Первая группа 1 устройства составлена из нескольких подгрупп по и одноразрядных двоичных сумматоров 2 — 7.

Вторая группа 8 устройства составлена из нескольких подгрупп по и одноразрядныхдво ичных сумматоров 9 — 11.

Предпоследняя группа 12 устройства составлена из одноразрядных двоичных сумматоров

18 — 15, Последняя группа 16 устройства составлена из одноразрядных двоичных сумматоров

17 — 19.

На вход 20 устройства подается старший разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2" — (k — целое положительное число);

1s на вход 21 — (а + 1)-й разряд )гп разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2" — ; на вход 22 — (2п — 1)-й разряд Ьг разрядного двоичного числа с разрядным весом остатка по

20 модулю 2 +1, равным 2 — ; на вход 28 — (n — 1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2г;

25 на вход 24 — (2n — 1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2 — 1, равным 2г; на вход 25 — (3n — 1) -й разряд kn разрядного двоичного числа с разрядным весом ос30 татка по модулю 2" — 1, равным 21;

242496 на вход 26 — n-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2О; на вход 27 — 2n-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2О; на вход 28 — Зп-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2О; на вход 29 — (Зп-1-1) -й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2" — ; на вход 80 — (4п+1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2" ; на вход 81 — (5п+1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1„равным 2" — на вход 82 — (4п — 1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2 — 1, равным 2г; на вход 88 — (5п — 1) -й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2г; на вход 84 — (6n — 1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2г; на вход 35 — 4n-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2о; на вход 86 — 5п-й ра: ðÿä kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 2о; на вход 87 — бп-й разряд kn разрядного двоичного числа с разрядным весом остатка го модулю 2" — 1, равным 2>.

Устройство содержит выходную шину 88 суммы сумматора 2 с присвоенным весом остатка по модулю 2" — 1, равным 2" — ; выходную шину 89 суммы сумматора 15 с присвоенным весом остатка по модулю 2" — 1, равным 2" — ; выходную шину 40 суммы сумматора 8 с присвоенным весом по модулю 2" — 1, равным 2г; выходную шину 41 суммы сумматора 6 с присвоенным весом остатка по модулю

2" — 1, равным 2 ; выходную шину 42 переноса сумматора 14 с присвоенным весом остатка по модулю 2" — 1, равным 2г; выходную шину 48 переноса сумматора 2 с присвоенным весом остатка по модулю 2" — 1, равным 2р,. выходную шину 44 суммы сумматора 4 с присвоенным весом остатка по модулю 2" — 1, равным 2О; выходную шину 45 суммы сумматора 7 с присвоенным весом остатка по модулю 2" — 1, равным 2О; выходную шину 46 переноса сумматора 8 с присвоенным весом остатка по модулю2" — 1, равным 2 ; выходную шину 47 переноса сумматора 5 с присвоенным весом остатка по модулю 2" — 1, равным 2О; выходную шину 48 переноса сумматора 6 с присвоенным весом остатка по модулю 2" — 1, равным 2 ; выходную шину 49 переноса сумматора с присвоенным весом остатка по модулю 2 — 1, равным 2г; выходную шину 50 переноса сумматора 9

10 с присвоенным весом остатка по модулю2" — 1, равным 2О; выходную шину 51 переноса сумматора 10 с присвоенным весом остатка по модулю 2" — 1, равным 2 ;

15 выходную шину 52, переноса сумматора с присвоенным весом остатка по модулю 2" — 1, равным 2г; выходную шину 58 суммы сумматора 9 с присвоенным весом остатка по модулю 2 — 1, 20 равным 2" выходную шину 54 суммы сумматора 10 с присвоенным весом остатка по модулю 2" — 1, равным 2г; выходную шину 55 суммы сумматора 11

25 с присвоенным весом остатка по модулю 2 — 1, равным 2О;

На вход 56 устройства подается ((П вЂ” 1) n+

+ 1)-й разряд kn разрядного двоичного числа с разрядным весом остатка по модулю 2" — 1, 30 равным 2 г. Устройство содержит выходную шину 57 суммы сумматора 18 с присвоенным весом остатка по модулю 2 — 1, равным

2"- . На его вход 58 подается kn — 1-й разряд

kn разрядного двоичного числа с разрядным

35 весом остатка по модулю 2" — 1, равным 2>.

Устройство имеет также выходную шину 59 суммы сумматора 14 с присвоенным весом остатка по модулю 2 — 1, равным 2г, и íà его вход 60 подается — kn-й разряд kn-го разряд40 ного двоичного числа с разрядным весом остатка по модулю 2" — 1, равным 20

Устройство содержит также выходную шину 61 суммы сумматора 15 с присвоенным весом остатка по модулю 2" — 1, равным 2о;

45 выходную шину 62 переноса сумматора 17 с присвоенным весом остатка по модулю 2" — 1, равным 2О; выходную шину 68 переноса сумматора 19 с присвоенным весом остатка по модулю 2" — 1, 30 равным 2г; выходную шину 64 переноса сумматора 18 с присвоенным весом остатка по модулю 2" — 1, равным 2 ; выходную шину 65 переноса сумматора 15

55 с присвоенным весом остатка по модулю 2" — 1, равным 2г; выходную шину бб переноса сумматора 18

r. присвоенным весом остатка по модулю 2" — 1, равным 2О; б0 выходную шину 67 переноса сумматора 14 с присвоенным весом остатка по модулю 2" — 1, равным 2 ; выходную шину 68 суммы сумматора 17 с присвоенным весом остатка по модулю 2" — I, 65 равным 2"- ;

242496

5 выходную шину б9 суммы сумматора 18 с присвоенным весом остатка по модулю 2" — 1, равным 2 ; выходную шину 70 суммы сумматора 19 с присвоенным весом остатка по модулю 2" — 1, равным 2О.

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

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

Предлагаемая схема для нахождения остатка от числа по модулю 2" — 1 на элементах

«НŠ— И» для конкретного модуля (mod 7) позволила уменьшить количество оборудования по сравнению с прототипом в два раза, Применение устройства для нахождения остатка от числа по модулю 2" — 1 наиболее целесообразно для и «)3.

При выполнении последней группы сумма5 -,оров предлагаемого устройства необходимо учитывать специфику устройств параллельных сумматоров с циклическим переносом.

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

10 устройств для нахождения остатка от числа по модулю (2" + q), где q — целое положительное число.

Предмет изобретения

Устройство для нахождения остатка от числа по модулю 2" — 1 (где n — целое положительное число), отличающееся тем, что, с целью упрощения устройства, оно содержиг

20 одноразрядные сумматоры, объединенные в группы, каждому входу и выходу которых присваиваются разрядные веса, выходы одноразрядных сумматоров каждой группы соединены со входами последующей группы сумма25 торов, а входы каждой группы сумматоров подключены к выходам предыдущей группы сумматоров и к числовым входам устройства, последняя группа сумматоров соединена по схеме с циклическим переносом, а их выходы

30 подсоединены к выходным зажимам сумм и переносов устройства.

242496

20 23 Z6 21 242722 252829 323530 333531 3437 5б 58 Е0

1

Составитель А. А. Плащин

Техред Л. К. Малова Корректор T. П. Лаврухина

Редактор П. Шлайн

Заказ 2141/9 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Центр. пр. Серова, д. 4

Типография, пр. Сапунова, 2