Устройство для формирования остатков по модулю

 

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

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

РЕСПУБЛИК

А1 (5и4Н ОЗМ 7 18

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4138855/24-24 (22) 24.10.86 (46) 07.04.88. Бюл. № 13 (71) Львовский политехнический институт им. Ленинского комсомола (72) Н. В. Черкасский (53) 681.3 (088.8) (56) Авторское свидетельство СССР № 1084798, кл. G 06 F 11/08, 1972.

Авторское свидетельство СССР № 1305685, кл. Н 03 М 7/18, 1985. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ

80»1387201 (57) Изобретение относится к вычислительной технике и поедназначено для формирования остатков от многоразрядного числа по модулю. Целью изобретения является расширение области применения за счет формирования остатков по модулю тринадцать. Поставленная цель достигается тем, что устройство для формирования остатков по модулю, содержашее одноразрядные сумматоры 1i — 16, объединенные в группы

2i — 25, блок свертки содержит элементы 3i, 3 запрета, элемент ИЛИ 4, одноразрядные сумматоры 5i — 5s, элемент И 7 с соответствующими связями. 1 з.п. ф-лы, 2 ил., 1 табл.

1387201

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

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

На фиг. 1 представлена схема устройства для формирования остатков по модулю (от 32-разрядного числа); на фиг. 2 — схема блока свертки.

Устройство содержит одноразрядные сумматоры 1 — 1п, объединенные в группы 2 —

25, элементы 3I и 32 запрета, элемент ИЛИ 4, одноразрядные сумматоры 5 — 5, блок 6 свертки, элемент И 7, выход 8 устройства, информационный вход 9 устройства и вход

l0 константы устройства.

Блок 6 свертки содержит элемент НЕ 11, элементы И вЂ” ИЛИ 12 — 124, элементы И

13 — 134, элемент 14 запрета, одноразрядные сумматоры 15 — 154. 20 о 4 2

2 2 2

2 2 2 2 2 2

2 2 2

8 3 6

+ 1 2 4

12 11 9 5 10 7

1 2

2 4 8

3 6 12 11 нения q-й разрядной сетки слагаемых А одинакового знака эквивалентна единице младшего разряда тех же слагаемых, но с противоположным злаком. Это обстоятельст35 во позволяет применить прямоугольную матрицу одноразрядных трехвходовых сумма торов с горизонтальной цепью распространения сигнала переноса, содержащую ряд ступеней. В этой матрице не происходит

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

В сумматорах 5 и элементах 3, 4 и 7 произ50 водится переход от 6-разрядного вычета к

4-разрядному. Для этого содержимое сумматоров 1 — 14 последней группы 2: складывают в сумматорах 5 с содержимым сумматоров 1ь u Io этой же группы, умноженным на 3io= 1 l . На выходах образуется

4-разрядный наименьший вычет r согласно (4) . В блоке 6 свертки получают наименьший положительный вычет путем прибавления к r дополнения 0010>. Если при этом

Отсюда выражение для отыскания вычета можно записать как г = (Ap — А +А +А +...) 13/q = 6 (3) Выражение (3) позволяет свернуть многоразрядное число до 6-разрядного вычета по модулю тринадцать.

Для отыскания остатка г (наименьшего вычета) необходима дополнительная свертка. Выражение для остатка

r = (r )„= .С, + ЗС, )„(4) где Со, С вЂ” двух и четырехразрядные числа. Коэффициент «+3» определен по таблице при 2".

При использовании выражения (4) возможно получение отрицательного наименьшего вычета. Переход от отрицательного к положительному остатку производится следующим образом. Так как (5) — г=г modгп, где гпо — дополнение r до модуля m, то

Гдоп = Гобр + б, (б где romp. — обратный код значения остатка r, а б = m — (r+roop)/, +,о (т. (7)

Для модуля тринадцать 3 = 0010>.

Согласно (3) исходное число разбивается на I = n/q = 5,36 групп по 6 разрядов, причем все нечетные числа отрицательные.

При вычислении суммы единица перепол12 11 9 5 10 7

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

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

А = Ао + Ai2 i + А 2 g + .", (1) где Ар, А i А — группы последовательных цифр с одинаковым количеством разрядов. Остаток от деления числа А(п) на модуль m равен

К=(А(п) )m=(Ao+SiAi+S A + -. ) где S; = (2" ), $ = 1, 2,.... (2)

Коэффициенты S определяют сложность вычисления остатков по выражению (2) .

Для отыскания минимальных значений

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

1387201

Формила изобретения возникает перенос, то наименьший остаток снимается с выходов сумматоров 15 через элемент И вЂ” ИЛИ 12. Если сигнала переноса на сумматоре 154 не возникает, то остаток подается на выход, минуя сумматоры

15 с выходов сумматоров 5s — 5s из-за наличия сигнала «1» на выходе элемента НЕ 11.

Исключение составляет случай, когда г =

13io. Для получения r = 0 служат элемент 14 запрета и элементы И 13. При г =

= 1101 на выходе элемента 14 запрета образуется «О». Этот сигнал закроет все элементы И 13 и на выходе 8 образуется код

«0000» независимо от состояния сумматоров 15. Во всех остальных случаях элемент 14 запрета и элемент И 13 не препятствуют прохождению данных на выходе 8.

1. Устройство для формирования остатков по модулю, содержащее (1 — 1) групп одноразрядных сумматоров (l= и/q, где и— разрядность числа, q — число сумматоров в группах) и блок свертки, причем прямые входы первого слагаемого одноразрядных сумматоров i-й группы (i=1 — 1 — 1) соединены с входами соответствующих разрядов (i+1) -й группы информационного входа устройства, выход переноса к-ro одноразрядного сумматора i-й группы соединен с входом переноса (k+1) -го одноразрядного сумматора i-й группы (k = 1 — q — 1), выход переноса последнего одноразрядного сумматора

j-й группы соединен с входом переноса первого одноразрядного сумматора (j+1)-й группы (j= 1 — — 2), выход блока свертки является выходом устройства, отличающееся тем, что, с целью расширения области применения за счет формирования остатков по модулю тринадцать, оно содержит два элемента запрета, элемент И, элемент ИЛИ и восемь одноразрядных сумматоров, причем количество одноразрядных сумматоров в группе q = 6, причем инверсные входы второго слагаемого одноразрядных сумматоров первой группы соединены с входами соответствующих разрядов первой группы информационного входа устройства, выходы суммы одноразрядных сумматоров j-й группы соединены с инверсными входами второго слагаемого соответствующих одноразрядных сумматоров (j+1)-й группы, инверсные выходы суммы одноразрядных сумматоров с первого по четвертый последней группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров, выходы суммы которых соединены соответственно с входами первого слагаемого одноразрядных сумматоров с пятого по восьмой, выходы суммы которых соединены соответственно с входами первой группы блока свертки, входы второй группы которого соединены с входами соответствующих разрядов входа константы устройства, выход

55 переноса р-го (р= 1 — 3) одноразрядного сумматора соединен с входом переноса (р+1) -го одноразрядного сумматора, вых. . переноса четвертого одноразрядного сумматора соединен с входами второго слагаемого пятого и шестого одноразрядных сумматоров, выход переноса (р+4) -го одноразрядного сумматора соединен с входом переноса (р+5) -го одноразрядного сумматора, инверс ный выход суммы пятого одноразрядного сумматора последней группы соединен с управляющим входом первого элемента запрета, с информационным входом второго элемента запрета, с первым входом элемента И и с входом второго слагаемого первого одноразрядного сумматора, вход третьего слагаемого которого соединен с выходом переноса шестого одноразрядного сумматора последней группы, инверсный выход суммы которого соединен с информационным входом первого элемента запрета, с управляющим входом второго элемента запрета и с вторым входом элемента И, выход которого соединен с входом второго слагаемого четвертого одноразрядного сумматора, выход первого элемента запрета соединен с входом второго слагаемого третьего одноразрядного сумматора и с первым входом элемента ИЛИ, второй вход и выход которого соединены соответственно с выходом второго элемента запрета и с входом второго слагаемого второго одноразрядного сумматора.

2. Устройство по и. 1, отличающееся тем, что блок свертки содержит четыре одноразрядных сумматора, четыре элемента И, элемент запрета, четыре элемента И --ИЛИ, элемент НЕ, причем выход переноса р-го (р= 1 — 3) одноразрядного сумматора соединен с входом переноса (р+ 1)-го одноразрядного сумматора, выход переноса четвертого одноразрядного сумматора соединен с входом переноса первого одноразрядного сумматора, инверсный выход элемента запрета соединен с первыми входами элементов И с первого по четвертый, выходы которых являются выходом блока свертки, входы первой группы которого соединены соответственно с входами первых слагаемых одноразрядных сумматоров с первого по четвертый, входы вторых слагаемых которых соединены с соответствующими входами второй группы блока свертки, входы первого слагаемого одноразрядных сумматоров с первого по четвертый соединены соответственно с первым информационным, управляющим, вторым и третьим информационными входами элемента запрета, входы первого слагаемого одноразрядных сумматоров с первого по четвертый соединены с первыми входами первых групп соответствующих элементов И вЂ” ИЛИ, первые входы вторых групп которых соединены с выходами суммы соответствующих однораз1387201 рядных сумматоров, выход переноса четвер- рез элемент НŠ— с вторыми входами пертого одноразрядного сумматора соединен вых групп элементов И вЂ” ИЛИ с первого по с вторыми входами вторых групп элемен- четвертый, выходы которых соединены с втотов И вЂ” ИЛИ с первого по четвертый и че- рыми входами соответствующих элементов И. л, -,а, А, (,фд а а а а,а а g а а„а,ава„аваа „а,,ааааа,. с а а,а а, 9

1 ! !

1 !!

Составитель А. Клюев

Редактор П. Гереши Техред И. Верес Корректор М. Демчик

Заказ 232/58 Тираж 928 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4