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

4, I

t

-А

,ЛfУVef JPlAfa°ч V P A fr. Of с,JJ, Ш, ft fff

I f f I Р Н IV

л

t

-А

fr. ft fff

I Р Н IV

л

,7,

с S

(Л

4 4 4ib.

Ч

4

q7

ФШ

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

Цель Изобретения - расширение области применения устройства за счет увеличения числа модулей.

На фиг, 1 изображена функциональная схема предлагаемого устройства; на фиг. 2 - схема блока свертки, J Устройство содержит сумматоры ,. 1,1-1.6,объединенные в группы 2.1- 2,5, элементы 2И-ИЛИ 3.1-3.4, допол нительные сумматоры .4,1-4.8 и блок 3 свертки.. Блок 5 свертки содержит вхо ды 6 и выходы 7, сумматоры 8.1-8.4, элемент 9, элемент НЕ 10, эле менты 2И-ИЛИ 11 и элементы И 12.1- 12.4.

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

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

АО.+ А,f.

+ А 2- 2

(1)

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

г Ад-А +А -А5+ 7 . (3-)

Выражение (3) позволяет свернуть многоразрядные числа до шести эазряд- , кого вычета по модулю 13,-Для отыскания остатка г (наименьшего вычета) необходима дополнительная свертка, так как вычет г имеет семь разрядов, а вычет г - четыре разряда для модуля m - 1101. Можно разбить г на две группы чр1сел, содержащие, например, четыре и два разряда. Коэф- фициент при 2 по табл, 1 равен 3, Поэтому

г г + ЗС,

тз

(4)

где GO и С - четыре младших и три

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

Изобретение относится к вычислительной технике и может быть ис- : пользовано для формирования остатка числа по модулю 13 без выполнения операции деления. Цель изобретения - расширение области применения за счет увеличиния числа модулей. Устройство содержит сумматоры 1.1-1.6, объединенные в группы 2.1-2.5, элементы 2И-ИЛИ 3.1-3.4, дополнительные сумматоры 4.1-4.8, блок 5 свертки. 1 з.п. . ф-лы, 2 ил., 2 табл.

-г г

4 оп

mod m,

где АО, А., и А - группа .последова- 30

тельных цифр с.

одинаковым коли- где г - дополнение г до модуля

чеством разрядов.га, то

. Остаток от деления числа А(п) па

f,

.

модуль П1 равен

R A(n) АО + S,A , -1Ф. S2.A.+

е;

(2)

40

где S, 2

S 1-.,2

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

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

Как видно из табл. 1, значения вычетов периодичны, причем для S ± 1 это период равен q:.6. Отсюда выраже-г г

4 оп

mod m,

(5)

йоп

о5р

f,

. (6)

где г

об р

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

0- m - (г + Гд5р)|г + г„5р П1,(7)

Для модуля 13 .

Таким образом, получение остатка связано с суммированием 1 частей А, разрядностью q 6 числа Л(п), причем все нечетные .слагаегчые Р. отрица-. тельные. При обработке сумм, определяемых выражением (3), единица переполнения q-разрядной сетки слагаемых А одинакового знака эквивалентна единице младшего разряда тех же слагаемых, но с противоположным знаком. Это обстоятельство позволяет синтези- ровать прямоугольную матрицу без увеличения разрядной сетки сумматоров по мере Накопления результата с диагональной цепью распространения сигнала переноса сумматоров. В целях

исключения операции вычитания используется дополнение по модулю чисел Ферма ( - 10 j) отрицательных слагаемьк А.- и всех результатов, получаемых на выходах сумматоров каждой группы. Компенсация rf производится в сумматорах 4 путем добавления двойки (в частности, в сумматорах 4.1 и 4.5).

В элементах 2И-ИЛИ 3 и сумматорах 4 производится переход от семиразрядного вычета г к 4-разрядному. Переходная схема синтезирована по табл. 2 истинности, в которой выход сумматора 1.5 обозначен В, выход сумматора 1.6 обозначен В, выход переноса сумматора 1.6 обозначен Б 2, а выходы элементов 3.1-3.4 обозначены соответственно Со-С, ,

Здесь GO-C 3 это результат умно- жения БВ, В и В на три. По табл. 2 составим уравнения и минимизируем их:

С„

,;

с;

В, В,;

BiBe

- В,

в, в.

Сумматоры 4 служат для получения наименьшего вычета. В них не производится компенсация поправки, равная с ifo 10. Прибавление двойки распределено на сумматоры 4.1 и 4.5, путем прибавления в каждом из этих сумматоров по единице. При возник- сигнала переноса в сумматоре 4.4 (пятого разряда) происходит суммирование этого сигнала, умноженного на три, с четырьмя разрядами сумматоров 4.1-4.4 в сумматорах 4.5-4.8. При этом на выходах сумматоров 4.5- 4.8 и соответственно на входах 6 блока 5 свертки согласно (4J. образуется 4-ра1зрядный вычет,- .- , В блоке 5 свертки вычет г преобразуется в наименьший положительный вычет. Для этого в сумматорах 8 вычет ,г .складывается с 0010. Если при этом возникает перенос (что соответствует случаю, когда выполняется неравенство и г 15), то наименьший остаток снимается с выходов сумматоров 8 через элемент 2И-ИЛИ 11. Если сигнала переноса на сумматоре 8.4 не возникает, остаток

подается на выход схемы, минуя сумматоры 8, с выходов сумматоров 4,5-4.8 из-за наличия сигнала 1 на выходе инвертора. Исключение составляет случай, когда г . m 13,о 1101. Для получения г О служат элемент И-НЕ 9 и элементы И 12. При г. на входе элемента И-НЕ 9 установятся все 1, а на выходе образуетея О. Этот сигнал закрывает все элементы И 12 и на выходах 7 образуется код 0000 независимо от состояния сумматоров 8, Во всех остальных случаях элементы И-НЕ 9 и И 12 не пре- пятетиуют прохождению данных на выходы 6. Кроме того, такое подключение элементов И-НЕ 9 и И 12 запрещает возникновение возбуждения в сумматорах 8 при г т. - .

Приме р. А 1100010001101101001 00001111101И. При этом 10111); -А,000111; А2 010010; -Aj 011011} А СЮ0100; Aj. 11

30

35

40

45

50

55

5 14А4774 6

Проверка. Деление промежуточно устройства, прямые результата г на модуль 13:

слагаемого сумматор . (i 2, 3, , 1 - (1+2)-й группой ин дов устройства, выхо

1100111 01101

поправка за вертирования

счет ин-А,

На йыходах сумматоров.4. 5-4,8 образуется код 1110, При этом.на выходе элемента И-НЕ 9 устанавливается 1, которая разрешает прохождение кода через элементы И 12, При сложении в сумматорах 8 чисел 1110+0010 образуется переполнение, т,е. единица приплюсовывается в сумматоре 8,1 а на выход 7 результат поступает через элемент 2И-ИЛИ 11 с выходов сумматоров 8, а не с выходов суммаг торов 4,5-4,8,

Таким образом, функциональные возможности предлагаемого устройства (по сравнению с устройством-прототипом) расширены за счет использования его матричной структуры с диагональн{)й Цепью распространения сигнала .переноса для формирования остатков по , модулю чис ел Ферма и по модулю 13. при дрбав лении переходной схемы свертки (логические элементы и сумматоры) и введения блока свертки.

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

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

инверсные входы второго слагаемого и входы переноса сумматорЪв первой группы являются первой, второй и третьей группами информационного входов

устройства, прямые

входы первого

слагаемого сумматоров (i-й. группы . (i 2, 3, , 1 - 2) являются (1+2)-й группой информационных вхо- дов устройства, выходы сумм сумматоров j

Я-й (и 1, 2, :, 1 - 2) группы , соединены с инверсными входами второго слагаемого одноименных сумма- торов Ck+1)-и группы, : выход пере- носа i-ro ( 2,, q-1) сумматора не-й группы соединен с инверсным входом переноса (1+1)-го сумматора (k + )-й группы, выход

5 переноса последнего сумматора k-й группы соединён с прямым входом

пер.вого сумматора (k+1)- группы, выход переноса каждого сумматора последней группы,, кроме последнего

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

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

g первые входы элементов И второго эле- мен.та 2И-ИЛИ, инверсные первые входы элементов И третьего элемента 2И-ИЛИ к первый инверсный вход первого и первый прямой вход второго элементов

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

0 выходу суммы последнего сумматора последней группы, третий прямой вход первого и второй инверсный вход второго элемента И первого элемента 2И-ИЛИ, третий инверсный вход пер55 вого элемента И второго элемента 2И- ИЛИ и последние прямые входы первых элементов И третьего и четвертого элементов 2И-ИЛИ объединены и под- : ключены к выходу переноса последнего

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

2, Устройство по п. 1, отличющееся тем, что блок свертки содержит сумматоры, элементы 2И-РШИ, элементы Ии элемент И-НЕ, выход ко

21 2

2 48 5

11 9 5 10

пЗ.4 о5 п °

6 12 11 712

О 1 1 1

О О

1

1

о 1 о 1 о 1 о

торого соединен с первыми входами первого-четвертого элементов И, выходы сумм сумматоров подключены к первым входам первых элемейтов И соответствующих элементов 2И-ИЛИ, выход переноса каждого из первых трех сумматоров соединен с входом переноса следующего сумматора, выход переноса четвертого сумматора соединен с вторыми входами первых элементов И эле- . ментов 2И-ИЛИ, входом переноса сумматора и входом элемента НЕ, выход ко торого соединен с первыми входами вторых элементов И элементов 2И-ИЛЙ, входы первого слагаемого сумматоров i подключены к источнику код 0010, первый прямой вход, второй инверсньп, третий и четвертьш прямые входы элемента И-НЕ объединены соответственно с входом второго слагаемого одноименного сумматора и вторым входом второго элемента И одноименного элемента 2И-ИЛИ и является соответствующим входом блока свертки, выходы элементов И ЯВЛЯЮТСЯ соответствующими выходами блока свертки.

Т а б л и ц а 1

2 2 2 2

5 10 722

83612 11

.На блица 2

о о 1 о 1 о 1 ....

о 1 1 о о 1

о о

о 1

о 1 о о

4

1 о

Фиг. г