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

 

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

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

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

РЕСПУБЛИК е (5D 4 G 06 F 11/00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ .=

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

Ar Ae Ж %

А

-Ar

I 51 ф7

ФЖ7 (21) 4143421 /24-24 (22) 31. 10. 86 (46) 15. 12.88, Бюл. r 46 ,(71) Львовский политехнический институт им.Ленинского комсомола (72) Н.В.Черкасский . (53) 681.325(088.8) (56) Авторское свидетельство СССР

1Ф 139?919, кл. Г 06 Р 11/00, 1985. (54) УСТРОЙСТВО ДЛЯ ФОРИИРОВАНИЯ

ОСТАТКОВ ПО МОДУЛИ

„„SU„„1444774 A 1 (57) Изобретение относится к вычислительной технике и может быть ис" .: пользовано для формирования остатка числа по модулю 13 беэ выполнения операции деления. Цель иэобретения— расширение области применения эа счет увеличиния числа модулей. Устройство содержит сумматоры 1.1-1,6, объединенные в группы 2.1-2.5, элементы

2И-ИЛИ 3. 1-3.4, дополнительные сумматоры 4.1-4.8, блок 5 свертки. 1 з.п. ф-лы, 2 ил., 2 табл. (В

1 1444774 2 (3) шос1 ш

"дол г обр + (6) А(п)> = А, + 8,A, +

4 Я А + .. . ), (2) обр)1 обр

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

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

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

Устройство содержит сумматоры, 1, 1-1.6,обьединенные в группы 2.12,5, элементы 2И-ИЛИ 3,1-3,4, допол- 15 нительные сумматоры .4.1-4,8 и блок 5 свертки. Блок 5 свертки содержит вхо-. ды 6 и выходы 7, сумматоры 8„1-8.4, элемент И-HE 9, элемент НЕ 10, элементы 2И-ИЛИ 11 и элементы И 12.1- 20

12.4.

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

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

А=А„+A 2 +A 2 + ° . (1) Р, Р

1 2 Ф где А, А „и A< — группа последова- 30 тельных цифр с одинаковым количеством разрядов.

Остаток от деления числа А(п) на модуль m равен 35 где S (2 ),„;

1;.

S = 1,2

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

v двойки, 50

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

S. составим табл. 1 положительных и

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

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

r. =(Ао-А.+А -А 3+ 7 131 q=6.

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

Ф так как вычет г имеет семь разрядов, а вычет r — четыре разряда для модуля m = 13 — 1101, Можно разбить г на дне группы чисел, содержащие, f например, четыре и два разряда. Коэф фициент при 2 по табл, 1 равен 3, поэтому

,, (4) где C и С „ — четыре младших и три старших разряда r 1.

При использовании выражения (4) возможно получение отрицательного остатка, в связи с чем следует произвести переход к положительному остатку, Так как где д „вЂ” дополнение r до модуля ш, то где r — обратный код значения остатка r a

Для модуля 13 d = 2 о =- 0010 .

Таким образом, получение остатка

câÿçàío с суммированием 1 частей А . .1 разрядностью q =6 числа А(п), причем все нечетные слагаемые А отрица-.

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

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

С В ВВО+ВВ

110111 Aî

+ 111000 — 
010010 А g

0111

0101

1 с =ввв +вв Сг = В2ВО + В1ВОУ. зр

01110 i сумма 01101

1 10010 перенос с =ввв +вв инверси

011011.

011011 А>

100010. о»о»

1110

° 1101

000100 А, 010001 оо«оо

+ 100110 . 000011 А

001011

>оо»о . 1 10100

" 110011 или

0010

10000 .. :1

0001

1100111 з 14447 исключения операции вычитания используется дополнение по модулю чисел

Ферма (д 2, — 10 ) отрицательных слагаемых А и всех результатов по1

5 лучаемых нв выходах сумматоров каждой группы, Компенсация ог производится в сумматорах 4 путем добавления двойки (в частности, в сумматорах

4.1 и 4.5).

В элементах 2И-ИЛИ 3 и сумматорах

4 производится переход от семиразрядного вычета r ê 4-разрядному.

Переходная схема синтезирована по табл. 2 истинности-, в которой выход )5 сумматора 1.5 обозначен В, выход сумматора 1.6 обозначен Р>, выход пепеноса сумматора 1.6 обозначен Р а выходы элементов 3. 1-3,4 обозначены соответственно С -С,. 20.

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

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

2 д = 10 . Прибавление двойки " распределено на сумматоры 4.1 и 4.5, путем прибавления в каждом из этих сумматоров по единице. При возник. новении сигнала переноса в сумматоре 4р

4.4 (пятого разряда) происходит суммирование этого сигнала, умноженного-: на три, с четырьмя разрядами сумматоров 4.1-4,4 в сумматорах 4.5-4.8., При этом на выходах сумматоров 4.5- 45 4.8 и соответственно на входах 6 блока, 5 свертки согласно (4) образуется

;4-разрядный вычет,.

В блоке 5 свертки вычет r npe06- . разуется в наименьший положительный 5 .

Вычет. Для этого в сумматорах 8 вычет,г.складывается с оР= 2 = 0010 .

Если при этом Возникает перенос (что соответствует случаю, когда вы полняется неравенство m < r . 15), .55 то наименьший остаток снимается с выходов сумматоров 8 через элемент

2И-ИЛИ 11. Если сйгнала переноса на сумматоре 8.4 не возникает, остаток подается на выход схемы, минуя сумматоры 8, с выходов сумматоров 4,5-4,8 из-за наличия сигнала "1" на выходе инвертора. Исключение составляет случай, когда r .= m = 13„, = 1101 .

Для получения г 0 служат элемент

И-НЕ 9 и элементы И 12, При r = 1101 на входе элемента И-BE 9 установятся все "1", а на выходе образуетея "0". Этот сигнал закрывает все элементы И 12 и на выходах 7 образуется код 0000 независимо от состояния сумматоров 8. Во всех остальных случаях элементы И-НЕ 9 и И 12 не прес. пятствуют прохождению данных на вы- . ходы 6. Кроме того, такое подключение элементов И-НЕ 9 и И 12 запрещает возникновение возбуждения в сумматорах 8 при r = m.

Пример . А=1100010001101101001

0000111110111. При этом А 110111 j l

-А,=000111; А>=010010 -А>=011011, A -000100, А -11

5 1444774 6

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

1100111

01101

1101

11001

1101 11001

1101

+ 0010 поправка sa счет инвертирования — А

1101

0001

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

На Выходах сумматоров,4:5-4,8 образуется код 1110, При этом.на выходе элемента И-НЕ 9 устанавливается

"1", которая разрешает прохождение кода через элементы И 12. При сложении в сумматорах 8 чисел 1 110+0010 образуется переполнение, т.е, единица и;,приплюсовывается в сумматоре 8,1

:, a на выход 7 результат поступает, через элемент 2И-ИЛИ 11 с выходов сумматоров 8, а не с выходов сумма торов 4.5-4,8.

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

Цепью распространения сигнала .переноса для формирования остатков по модулю чисел Ферма.и по-модулю 13. при добавлении переходной схемы свертки (логические элементы и сумматоры) и введения блока свертки, 1. Устройство для формирования остатков ho модулю, содержащее 1 -1 группу сумматоров (1 = n/q, и -раз рядность числа, q — число .сумматоров в группе) и блок свертки, выходы которого являются выходами устройства, прямые входы первого слагаемого инверсные входы второго слагаемого и входы переноса сумматоров первой группы являются первой, второй и третье группами информационного входов и (i = 2, 3,, 1 — 2) являются (i+2) —,й группой информационных входов устройства, выходы сумм сумматоров — 1 — 2) группы соединены с инверсными входами вто" рого слагаемого одноименных сумма10 торов (К+ 1)-й группы, . выход пере» носа i-го (i=1, 2,, q-1) сумматора не-й группы соединен с инверсным входом переноса (1+1}-го сумматора (k + 1)-й группы, выход переноса последнего сумматора k-й группы соедйнен с прямым входом первого сумматора (k+1)-й группы, выход переноса каждого сумматора последней группы,; кроме последнего

20 сумматора, соединен с входом переноса последующего сумматора данной группы, о т л и ч а ю .щ е е с я тем; что, с целью расширения области применения за счет увеличения чис25 ла.модулей, число сумматоров в группе равно 6 и в. него введены элементы

2И-ИЛИ и.дополнительные сумматоры, прямые входы первых слагаемых первых четырех дополнительных сумматоров Р

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

И первого элемента 2И-ИЛИ, прямые

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

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

И первого и второго элементов 2И-ИЛИ, 4ã.âòîðoé инверсный вход второго элемента И второго элемента 2И-ИЛИ и вторые прямые входы вторых элементов

И третьего и четвертого элементов

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

Таблица Е"В °

23 24 2 2 2 28 29 2< 2и 2 2

2о 21

+1 2 4 8 5 6 12 11 9 5 10 7 2 2

9 5 10 7 1 2 4 8 3 6 12 11-12 11

2 .Ta блица с с

0

0

0

1 1

0 0

0 о

0

7 14447 сумматора .последней группы, выходы элементов 2И-ИЛИ соединены с прямыми входами вторых слагаемых соответствующих первых четырех дополнительных сумматоров, выходы сумм которых сое5 динены с прямыми входами первых слагаемых соответствующих вторых четырех дополнительных сумматоров, выходы сумм которых соединены с соответ- 10 ствующими входами блока свертки, вы ходы переноса дополнительных сумматоров, кроме четвертого, соединены с .входами переноса последующих сумматоров, выход переноса четвертого до- 15 полнительного сумматора подключен к прямым входам второго слагаемого пятого и шестого дополнительных сумматоров, прямые входы третьих слагаемых первого и пятого дополнительных 2р сумматоров подключены к источнику сигнала логической единицы, 2, Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок свертки содержит сумматоры, элементы 2И-ИЛИ, элементы Ии элемент И-HE выход которого соединен с первыми входами первого-четвертого элементов И, выходы сумм сумматоров подключены к первым входам первых элемейтов И соответствующих элементов 2И-ИЛИ, выход переноса каждого из первых трех сумматоров соединен с входом переноса следующего сумматора, выход переноса четвертого сумматора соединен с вторыми входами первых элементов И элементов 2И-ИЛИ, входом переноса сумматора и входом элемента НЕ, выход которого соединен с первыми входами вторых элементов И элементов 2И-ИЛИ, входы первого слагаемого сумматоров, подключены к источнику код а 0010, первый прямой вход, второй инверсньпi, третий и четвертый прямые входы элемента И-НЕ объединены соответственно с входом второго слагаемого одноименного сумматора и вторым входом второго элемента И одноименного элемента

2И-ИЛИ и является соответствующим входом блока свертки, выходы элементов И являются соответствующими выходами блока свертки.

1444774

Составитель О. Неплохов

Техред Л.Олийнык Корректор Л. Патай

Редактор А. Ренин

Заказ 64S2/4S

Тираж 704 Подписное

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

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

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