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

 

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

СОЮЗ СОВЕТСКИХ .СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„Я!.! „„14499

А1!

5!1 4 G 06 Р ! /10

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

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

4в у -ла л -лд лу -лт I ла

alta®)c!gt азю абзац 1!ааааа ) aie s (аю аа 1 а а, 1 а aaaceaarlacraiceritaaa„aia acacac а а, а, л

-лю

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

ПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4118342/24-24 (22) 12.09.86 (46) 07.01.89. Бюл. !1- 1 (71) Львовский политехнический институт им. Ленинского комсомола

{72) Н.В. Черкасский (53) 681.3{088.8) (56) Авторское свидетельство СССР

Ф 1397918; 1397919, кл. С 06 F 11/!О, 1985.

Авторское свидетельство СССР !! 1305684; 1305685, кл. G 06 F 11/10, 1985, (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ (57) Изобретение относится к вычислительной технике и может быть использовано при построении контроли-. руемых арифметических устройств.

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

1449986 iМодуль ll

+1 2 4 8 5 10 9 7 3 6 1 2 4 8

- l O 9 7 3 6 I 2 4 8 5 10 9 7 3 сумматоров 1, объединенных в (1-1) и группу 2 (1= —, где и — разрядность контролируемого слова) . Первые две

r руппы разрядов контролируемого слова соединяются соо гветственно с инверсными входами первого слагаемого и прямыми входами второго слагаемого соответствующих одноразрядных сумматоров 1 первой группы 2.1. Выход переноса каждого предыдущего одноразрядного сумматора 1 каждой группы 2 соединен с входом переноса последующего одноразрядного сумматора 1. Выходы результата одноразрядных сумма-.

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

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

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

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

4 свертки, входы 5 блока 4 свертки и группу выходов 6 устройства.

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

И 11.1-11.4.

Устройство работает следующим образом. торов 1 каждой предыдущей группы 2 соединены с инверсными входами первого слагаемого одноразрядных сумматоров 1 последующей группы 2. Прямые входы одноразрядных сумматоров 1 каждой группы 2, кроме первой, соединены с соответствующими группами разрядов контролируемого слова. Затем с помощью восьми одноразрядных сумматоров 3.1-3.8 из пятиразрядного кода образуется четырехразрядный, который с помощью блока 4 свертки преобразуется в код остатка, поступающий на выходы группы 6 устройства.

2 ил,,l табл, Пусть A(n) исходное число, заданное в следующей двоичной системе счисления

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

Остаток от деления числа А(п) на модуль m равен

Ap+S< А БтАт где S; =(2 ), S=l 2,...

6;

Коэффициенты Я! определяют сложность вычисления остатков по выражению,2). Наименьшее число вычислений при 8 =S =...=1, что имеет место для

2 ° модулей чисел Черсенна и Ферма. В обоих этих случаях количество разрядов в группах 1 равно степени р или V.

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

c5) -г=г шорш, 40

;6) значения ос45

Пример. А=

110001000110!10100)000011)110111.

Ао=) О! Ilэ,А< =01 1 1 1 ъ А =01000 е А

= 1 1 0 l О, А4 =001 1 О, -As =000 I О, A6 = I 1 .

14499

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

5 как

r =(Ао-А,+А -A»+ . )1, / . . (3)

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

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

5 разрядов, а вычет r-4 разряда для модуля 11;+ =101) . Переход от r к r

-производится на сумматорах 3. Вычет

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

;+5, поэтому

r=(r ), lI =(В,+5В, ) zi,, где В,K) — четыре младших и один старший разряд r

При использовании. выражения,4) возможно получение отрицательного остатка, Переход от отрицательного к ЗБ положительному остатку несложен. Так как где г„ „ — дополнение г до модуля ш, то где r — обратный код татка г, а в - (r+r, ) /„,„„„,7)

Для модуля 113 =4, =0)00 .

Согласно (3) исходное число разбивается на 1п/q=32 5=6,4=7 групп по

5 разрядов, причем все нечетные числа отрицательные. При вычислении суммы единица переполнения q-разрядной . сетки слагаемых А; одинакового знака эквивалентна единице младшего разряда <5 тех же слагаемых, но с противоположным знаком. Это обстоятельство позволяет применить схему в виде прямоугольной матрицы одноразрядных трех86

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

В сумматорах 3 производится переход от 5-разрядного вычета к 4-разрядному. Цля этого содержимое сумматоров последней группы 2.6 и сумматора 1.4 группы 2.5 складывается со значением сумматора 1.5 группы 2.5, умноженным на 5,0 =101 . На входах 5 образуется вычет r согласно, 4). В блоке 4 свертки получают наименьший положительный вычет. Цля получения

1 положительного r прибавляем к r дополнение E =4 в сумматорах 7. Если возникает при этом перенос (что сооТ ветствует случаю, когда выполняется неравенство m r 15), то наименьший остаток снимается с выходов сумматоров 7 через элемент И-ИЛИ 10. Если сигнала переноса на сумматоре 7.4 не возникает, тогда остаток подается на выход схемы, минуя сумматоры 7, с выходов сумматоров 3.5-3.8 из-эа наличия сигнала "1" на выходе инвертора 9. Исключение составляет случай, когда r =ш=)1,> =IOI) . Для получения

r 0 служат элементы И-HE 8 и И 11.

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

7 при r =ш.

О1000 А

01111 -A

1449986

) 01000

Инверсия

010000

0l 111

Инверсия

-А э

11010

00110 А+

-А

00010

11011

0

11!

+ +1101

100! 1

L1OI!

Проверка-. Целение А на 1011 дает остаток 1000. На выходе сумматоров

3.5-3.8 образуется код 1000. При этом на выходе элемента И-НЕ 8 устанавливается 1", которая разрешает прохождение кода через элементы И 11.

При сложении в сумматорах 7 чисел

1000+0100 переполнения не образуется, в связи с чем через элемент И-ИЛИ 10 проходит код 1000 с выходов суммато- ров 3.5-3.8. формула и зоб ре те ния

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

ro и прямые входы второго слагаемого одноразрядных сумматоров первой группы соединены с соответствующими qразрядами первой и второй групп информационных входов устройства, в

10 каждой группе одноразрядных сумматоров выход переноса i-го одноразрядного сумматора соединен с входом переноса i+1)-ro одноразрядного сумматора (16Ыц-l), выход переноса послед1r него сумматора каждой группы соединен с входом переноса первого одноразрядного сумматора последующей группы, выходы суммы одноразрядных сумматоров каждой предыдущей группы соединены с инверсными входами первого слагаемого .соответствующих одноразрядных сумматоров последующей группы, прямые входы второго слагаемого сумматоров каждой К-й группы (2 ICcl-1) соединены

25 с {К+1)-й группой из q разрядов группы информационных входов .устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения коэффициента ис; пользования оборудования за счет фор30 мирования остатков по модулю одиннад» цать, оно содержит восемь одноразрядных сумматоров, число одноразрядных сумматоров в каждой группе, кроме последней, ц=5-, блок свертки содержит элемент И-НЕ, элемент НЕ, группу элементов И-ИЛИ и четыре элемента И, причем выходы сумматоров последней группы соединены с прямыми входами первого слагаемого первого, второго и

40 третьего одноразрядныхсумматоров, инверсный вход первого слагаемого четвертого одноразрядного сумматора соединен с выходом суммы четвертого одноразрядного сумматора пред4 последней группы, выход суммы пятого одноразрядного сумматора последней группы соединен с инверсными входами вторых слагаемых первого и третьего одноразрядных сумматоров выход переноса последнего сумматора последней группы соединен с прямым входом второго слагаемого четвертого одноразрядного сумматора, выходы суммы первого, второго, третьего и четвертого одноразрядных сумматоров соединены с прямыми входами первого слагаемого пятого, шестого, седьмого и восьмого одноразрядных сумматоров соответственно, выход переноса каждо1449986

Составитель В. Гречнев

Редактор В. Цапко Техрец М.Дидык КорректорГ.Решетник

Заказ 6967/48 Тираж 704 Подписное

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

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

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

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

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

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

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