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

 

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

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

РЕСПУБЛИК

„„Я!.! „„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 динены с вторыми входами .соответственно первого, второго, третьего и четвертого элементов И,выходы которых являются группой выходов устройства .

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

 

Похожие патенты:

Изобретение относится к вычислительной технике и может быть использовано в процессорах быстродействующих ЦВМ

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

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

Изобретение относится к вычис;- лительной технике

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

Изобретение относится к вычислительной технике

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

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

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

Изобретение относится к области передачи информации и предназначено для измерения значения отношения сигнал-шум на входе декодера

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

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

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

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

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