Устройство для формирования остатков по модулю Советский патент 1989 года по МПК G06F11/10 

1

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

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

На фиг. приведена функциональ- ная схема устройства; на фиг. 2 - функциональная схема блока свертки.

Устройство для формирования остатка по модулю (фиг.1) рассчитано на контроль 32-разрядного числа и содер жит одноразрядные с мматоры 1.1-1.5, объединенные в шесть групп 2.1-2.6, одноразрядные сумматоры 3.1-3.8, бло 4 свертки, входы 5 блока 4 свертки

и группу выходов 6 устройства.

Блок 4 свертки-: (фиг. 2) содержит одноразрядные сумматоры 7.1-7.4, элемент И-НЕ 8, элемент НЕ 9, группу 10 элементов И-ИЛИ элементы

И 11.1-1.4.

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

Пусть А(п) исходное число, заданное в следующей двоичной системе счисления

А А„-нА,. +А.2--..., (1)

где А ,А,,А2 - группы последовательных двоичных цифр с одинаковым количеством разрядов. Остаток от деления числа А(п) на

модуль го равен

(п) А,+5,А,..., (2)

где , ,2,...

Коэффициенты Sj определяют сложность вычисления остатков по выражению (2). Наименьшее число вычислений при S,S2, . . . 1 , что имеет место для модулей чисел Мерсенна и Ферма. В обоих этих случаях количество разрядов в группах 1 равно степени р или V.

Для отыскания минимальных значений S таблица положительных и отрицательных остатков от длеения последовательного разряда степени двойки на модуль 11 имеет следующий вид.

Как видно из таблицы, значения вычетов периодичны. Для этот период равен . Отсюда вьГражение для отыскания вычета можно записать как

г А,-А,,-. . . . (3)

Выражение (3) позволяет свернуть многоразрядное число до 5-разрядного вычета по модулю II.

Для отыскания остатка г (наименьшего вычета) необходима дополнительная свертка, так как вычет г имеет 5 разрядов, а вычет г-4 разряда для модуля 114 10114. Переход от г к г

ПJpoизвoдитcя на сумматорах 3. Вычет г можно разбить на две группы, каждая из которых содержит определенное число разрядов, например 2 и 3 или 1 и 4. Наиболее экономичным с точки зрения аппаратной реализации является второй вариант. Присоединение старшего разряда к младшим должно производиться с определенным коэффициентом, который определяется по таб1

лице, Так, при 2 -+5,. поэтому

коэффициент равен

rS

II ВоН-5В,п,

где Bg,R, - четыре младших и один старший разряд г .

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

.on nod™ (5)

AOCI дополнение г до модуля т, +S,(6)

г

Обр

доя -овр

- обратный код значения остатка г.

( )/h.r

Обр

|

(7)

Для модуля Il8 4,0 01005,.

Согласно (3) исходное число разбивается на l«n/q 32:5 6,4s;7 групп по 5 разрядов, причем все нечетные числа отрицательные. При вычислении суммы единица переполнения q-разрядной сетки слагаемых А- одинакового знака эквивалентна единице младшего разряда тех же слагаемых, но с противоположным знаком. Это обстоятельство позволяет применить схему в виде прямоугольной матрицы одноразрядных трех

449986

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

матрице не происходит увеличения разрядной сетки сумматоров по мере накопления результата. В целях исключения операции вычитания использовано сочетание прямых кодов частей исход10 ного числа и инвертирование отрицательных слагаемых и всех промежуточных результатов путем дополнения их по модулю. Выбранный способ инверти- . рования суммируемых чисел позволяет 15 взаимно компенсировать все отрицательные и положительные значения О .

В сумматорах 3 производится переход от 5-разрядного вычета к 4-разрядному. Для этого содержимое сумма- 20 торов последней группы 2.6 и сумматора 1 ,4 группы 2.5 складывается со значением сумматора 1.5 группы 2.5,

50

gg умноженным на 5 . Н входах 5 образуется вычет г согласно (4). В 25 блоке 4 свёртки получают наименьший положительный вычет. Для получения положительного г прибавляем к г дополнение в сумматорах 7. Если возникает при этом перенос (что соот- 30 ветствует случаю, когда вьшолняется неравенство ), то наимецьший остаток снимается с выходов сумматоров 7 через элемент И-ИЛИ 10. Если сигнала переноса на сумматоре 7.4 не возникает, тогда остаток подается на выход схемы, минуя сумматоры 7, с выходов сумматоров 3.5-3.8 из-за наличия сигнала 1 на выходе инвертора 9. Исключение составляет случай, 40 ,о 10112. Для получения г 0 служат элементы И-НЕ 8 и И 11. При на входе элемента И-НЕ В установятся все 1, а на выходе образуется О . Этот сигнал закрьюает все элементы И 11 и на выходах 6 образуется код 0000 независимо от состояния сумматоров 7. Во всех остальных случаях элементы И-НЕ В и И 11 не препятствуют прохождению данных на выходы 6 устройства. Кроме того, такое подключение элемента И-НЕ 8 и элементов И П.1-1I.4 запрещает возникновение возбуждения в сумматорах 7 при .

П р и м е р. А

, 1100010001 101 10100100001 1 1 1101 I 1 . Ав 10111, -А,01111, Aj 01000, -Л, 11010, А4 00110, -А5 00010, .

45

о 1000 01111

-А.

Инверсия

010000.

ОПП

Инверсия

11010 -А,

10100J

011101.

00010

00010 -А,

000100

Аб

ОНО - 01

10011 + UlOl

FOOO .

Проверка. Деление А на 1011 дает остаток 1000. На выходе сумматоров 3.5-3.8 образуется код 1000. При этом на выходе элемента И-НЕ 8 устанавливается , которая разрешает прохождение кода через элементы И 1I. При сложении в сумматорах 7 чисел 1000+0100 переполнения не образуется, в связи с чем через элемент И-ИЖ 10 проходит код 1000 с выходов сумматоров 3.5-3.8.

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

Устройство для формирования остатков по модулю, содержащее (1-1) группу одноразрядных сумматоров /1

где п - разрядность числа, q П

2

число одноразрядных сумматоров в

м ,

20

25

499866

группе) и блок свертки, содержащий группу одноразрядных сумматоров, причем инверсные входы первого слагаемого и прямые входы второго слагаемого одноразрядных сумматоров первой группы соединены с соответствующими q- разрядами первой и второй групп информационных входов устройства, в Q каждой группе одноразрядных сумматоров выход переноса i-ro одноразрядного сумматора соединен с входом переноса (i+l)-ro одноразрядного сумматора (l iiq-l), выход переноса послед- 15 него сумматора каждой группы соединен с входом переноса первого одноразрядного сумматора последующей группы, выходы суммы одноразрядных сумматоров каждой предыдущей группы соединены с инверсными входами первого слагаемого .соответствующих одноразрядных сумматоров последующей группы, прямые входы второго слагаемого сумматоров каящой К-й группы (2S-K61-1) соединены с (К+1)-й группой из q разрядов группы информационных входов устройства, отличающееся тем, что, с целью повышения коэффициента исг - пользования оборудования за счет фор- 30 мирования остатков по модулю одиннадл цать, оно содержит восемь одноразрядных сумматоров, число одноразрядных сумматоров в каждой группе, кроме последней, , блок свертки содержит элемент И-НЕ, элемент НЕ, группу элементов И-ИЛИ и четыре элемента И, причем выходы сумматоров последней группы соединены с прямыми входами первого слагаемого первого, второго и 40 третьего одноразрядных сумматоров, инверсный вход первого слагаемого четвертого одноразрядного сумматора соединен с выходом суммы четвертого одноразрядного сумматора пред- 45 последней группы, вькод суммы пятого одноразрядного сумматора последней группы соединен с инверсньии входами вторых слагаемых первого и третьего одноразрядных сумматоров,, выход переноса последнего сумматоре последней группы соединен с прямым входом второго слагаемого четвертого одноразрядного сумматора, выходы суммы первого, второго, третьего и четвертого одноразрядных сумматоров соединены с прямыми входами первого слагаемого пятого, шестого, седьмого и восьмого одноразрядных сумматоров соответственно, выход переноса каждо35

50

55

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

49986 8

элементов И, входы второго слагаемого первого, второго и четвертого одноразрядных сумматоров группы соединены с шиной нулевого потенциала устройства, вход второго слагаемого третьего одноразрядного сумматора группы соединен с шиной единичного потенциала устройства, выходы пере10 носа первого, второго и третьего

одноразрядных сумматоров группы соединены с входами переноса второго, третьего и четвертого одноразрядных сумматоров группы соответственно,

15 выход переноса четвертого одноразрядного сумматора группы соединен с вторыми входами всех элементов И-ИЛИ группы и входом элемента НЕ, выход которого соединен с третьими

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

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