Устройство для формирования остатков по модулю Советский патент 1988 года по МПК H03M7/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)УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ

(57) Изобретение относится к вычислительной технике и поедназначено для формирования остатков от многоразрядного числа по модулю. Целью изобретения является расширение области применения за счет формирования остатков по модулю тринадцать. Поставленная цель достигается тем, что устройство для формирования остатков по модулю, содержащее одноразрядные сумматоры 1 - 1б, объединенные в группы 2,-25, блок свертки содержит элементы 3i, 32 запрета, элемент ИЛИ 4, одноразрядные сумматоры 5i-58, элемент И 7 с соответствующими связями. 1 з.п. ф-лы, 2 ил., 1 табл.

00 00

1C

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

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

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

Устройство содержит одноразрядные сумматоры Ii - 1б, объединенные в группы 2i - 25, элементы 3i и 82 запрета, элемент ИЛИ 4, одноразрядные сумматоры 5i-Ss, блок б свертки, элемент И 7, выход 8 устройства, информационный вход 9 устройства и вход 10 константы устройства.

Блок б свертки содержит элемент НЕ 11, элементы И-ИЛИ I2i -124, элементы И 13i -134, элемент 14 запрета, одноразрядные сумматоры 15i-164.

Отсюда выражение для отыскания вычета можно записать как

г Ао-А,+А|+А2+... 13/q б (3)

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

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

Со + ЗС,„ ,(4)

где Со, GI - двух и четырехразрядные числа. Коэффициент «+3 определен по таблице при 2

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

-г гдоп mod ш, где гдогт-дополнение г до модуля ш, то

Гдоп Гобр -|- б,(6

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

б т-(г+гобр)/,+ , т. (7) Для модуля тринадцать б 00102. Согласно (3) исходное число разбивается на 1 n/q 5,36 групп по 6 разрядов, причем все нечетные числа отрицательные. При вычислении суммы единица переполУстройство работает следующим образом.

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

А АО +Ai2 , + A22 2-f ...,(1)

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

(n)m Ao-fSiAi+S2A2+ .-,

где5,- S 1,2,... .(2)

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

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

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

В сумматорах 5 и элементах 3, 4 и 7 произ- водится переход от 6-разрядного вычета к 4-разрядному. Для этого содержимое сумматоров 1| - U последней группы 25 складывают в сумматорах 5 с содержимым сумматоров Is и 1б этой же группы, умножен- г ным на . На выходах образуется 4-разрядный наименьший вычет г согласно (4). В блоке 6 свертки получают наименьший положительный вычет путем прибавления к г дополнения 00102. Если при этом

возникает перенос, то наименьший остаток снимается с выходов сумматоров 15 через элемент И-ИЛИ 12. Если сигнала переноса на сумматоре 154 не возникает, то остаток подается на выход, минуя сумматоры 15 с выходов сумматоров 55-58 из-за наличия сигнала «1 на выходе элемента НЕ 11. Исключение составляет случай, когда г 13io. Для получения г О служат элемент 14 запрета и элементы И 13. При г ПОЬ на выходе элемента 14 запрета образуется «О. Этот сигнал закроет все элементы И 13 и на выходе 8 образуется код «0000 независимо от состояния сумматоров 15. Во всех остальных случаях элемент 14 запрета и элемент И 13 не препятствуют прохождению данных на выходе 8.

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

переноса р-го () одноразрялиого сумматора соединен с входом перенося (р+1)-го одноразрядного сумматора, выхч) , переноса четвертого одноразрядного сумма тора соединен с входами второго слагаемого пятого и шестого одноразрядных сумматоров, выход переноса (р+4) -го одноразрядного сумматора соединен с входом переноса (p-f 5)-го одноразрядного сумматора, инверс

0

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

0

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

0 сумматора,

5 элемент НЕ, причем выход переноса р-го () одноразрядного сумматора соединен с входом переноса (р+1)-го одноразрядного сумматора, выход переноса четвертого одноразрядного сумматора соединен с

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

5 соответственно с входами первых слагаемых одноразрядных сумматоров с первого по четвертый, входы вторых слагаемых которых соединены с соответствующими входами второй группы блока свертки, входы первого слагаемого одноразрядных суммато0 ров с первого по четвертый соединены соответственно с первым информационным, управляющим, вторым и третьим информационными входами элемента запрета, входы первого слагаемого одноразрядных сумматоров с первого по четвертый соеди5

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

WuV i nV«°a , 4 ,Л

,Оа

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

At

,Л

-А, Л ,ОаУ ЛО 1 Г1 Л