Устройство для свертки по модулю G=2 @ -1 Советский патент 1987 года по МПК G06F11/10 

исключения неоднозначности результата формирования остатка по модулю q 2 -1. Устройство содержит N групп 1 по m подгрупп 2 в каждой группе одноразрядных сумматоров, два т-раз рядных сумматора 3,4, входы 5 устройства, выходы 6 устройства. Устройство

1325484

формирует в качестве нулевого остатка код q для ненулевых кодов, кратных модулю q 2 - 1. Повышение эффективности контроля достигается за счет введения второго т-разрядного сумматора, формирующего перенос в первый «-разрядньй сумматор. 2 ил.

1

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

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

т . -1, где m - целое число, при

аппаратном контроле передачи двоичных чисел, представленных в параллельно коде, и арифметических действий над ними.

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

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

Устройство содержит N групп 1 по m подгрупп 2 в каждой группе одноразрядных сумматоров, два т-разрядных сумматора 3 и 4, входы 5 и выходы 6 устройства. Каждая подгруппа 2 (фиг. 2) содержит одноразрядные сум- маторы 7.

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

На входы 5 устройства поступает параллельный п-разрядньй код, причем на входы К. каждой i-й подгруппы 2 1-и группы из групп 1 поступают значения разрядов с весом 2

1-1

которые

35

суммируются одноразрядными сумматорами 7, составляклцими подгруппу 2. Выходы А. i-й подгруппы имеют вес 2 , а выходы в . - вес 2 . Выходы В т-й подгруппы имеют вес 2 , что по модулю 2 - 1 соответствует 1, так как 2 1 Жоа() и равен весу выходов А. 1-й подгруппы. В i-x подгруппах 2 о всех последующих групп 1 аналогично производится суммирование значений выходов подгрупп предьщущей группы с одинаковым для каждой i-й подгруппы весом . Выходы А подгрупп имеют

Q

5

0

5

0

5

о

вес , а входы В1 - вес 2 . На последнем этапе после N-й группы, когда Р 2, где Р - количество выходов i-й подгруппы N-й группы cy D4aтopoв, где 1 i i т, 1 i I N, суммирование производится т-разрядным сумматором 3 с учетом значения переноса, поступающего с сумматора 4, что и обеспечивает суммирование по модулю q .

На выходах т-разрядного сумматора 3, являющихся выходами 6 устройства, формируется окончательное значение кода остатка г по модулю q 2 - 1. При этом при поступлении на входы 5 устройства нулевого п-разрядного кода формируется нулевой код остатка (г 0), а при поступлении любого ненулевого п-разрядного кода формируется код остатка г таким образом, что 1 г q. Причем для ненулевого кода, кратного модулю q, однозначно формируется значение остатка г, равное модулю q (г q). Выполнение условия г q для ненулевых кодов обусловлено тем, что при суммирования значений разрядов п-разрядного кода одноразрядными сумматорами подгрупп любое сочетание единиц в коде приводит к появлению хотя бы одной единицы на выходах А. или В при 1 4 1 : т, причем для всех I при 1 1 i N, т.е. и на выходах А. или В. . А на выходах оконечного т-разрядного сумматора 3 нулевой результат при этом был бы . возможен только при переполнении сумматора, но в этом случае происходит добавление единицы переноса, поступающей из сумматора 4.

Предлагаемое устройство в отличие от известного однозначно формирует в качестве нулевого остатка код q . для ненулевых кодов, кратных модулю : q 2 -1, что позволяет повысить

31325484

эффективность контроля. Кроме того, (р-1)-й группы, входы -и подгруппы для нулевых кодов формируется нуле- одноразрядных сумматоров (2 i га) вой код остатка, что также может быть Q-й группы подключены к выходам сумм использовано для повышения эффектив- одноразрядных сумматоров -й под- ности контроля. группы (д-1)-й группы, . к () разрядам входного кода -и Формула изобретения подгруппы одноразрядных сумматоров

Устройство для свертки по модулю (Ц-О-й группы ( округлять до q 2 -1, содержащее N групп однораз- ю целого в меньшую сторону) и к выхо- рядных сумматоров из m подгрупп в дам переносов одноразрядных суммато, пров (-1)-й подгруппы (р-1)-й груп-ч

каждой группе (j) 2--, где п - раз- , количество

рядность сворачиваемого числа, и пер- выходов одноразрядных сумматоров i-й вый га-разрядный сумматор, причем груп-15 подгруппы N-й группы равно двум), вы„ п - i + 1 , , ход суммы одноразрядного сумматора па из К --- входов 1-й под- подгруппы и выход переноса одгруппы (1 i т) первой группы од- ( поразрядного сумматора т-й подгруппы поразрядных сумматоров является груп- N-й группы соединены с первыми разря- пой входов устройства для подключения 20 дами соответственно первого и второго к выходам сворачиваемого числа с ве- слагаемых первого т-разрядного сумма- сом , m выходов суммы первого т- тора, -е разряды первого и второго разрядного сумматора являются выхода- слагаемых первого т-разрядного суммами устройства, каждая i-я подгруппа тора соединены соответственно с вы- 1-й группы одноразрядных.сумматоров 25 ходом сукмы сумматора -и подгруппы (1 41 N) содержит Kf/3 (округлять N-й группы и выходом переноса одно- до целого в меньшую сторону) однораз- разрядного сумматора ( -1)-й подрядных сумматоров, где К. - количест- группы К-й группы, отличающе- во входов i-й подгруппы одноразрядных е с я тем, что, с целью повышения сумматоров 1-й группы, входы первой 30 достоверности контроля, в устройство подгруппы одноразрядных сумматоров введен второй т-разрядный сумматор, Q-й группы (2 4 Q N) подключены к входы первого и второго слагаемых ко- выходам сумм одноразрядных сумматоров торого соединены соответственно с первой подгруппы (р-1)-й группы, к (входами первого и второго слагаемых ( /3) разрядам входного кода с первого ю-разрядного сумматора, вход первой подгруппы (р-1)-й группы ( переноса которого соединен с выходом /3) - округлять до целого в меньшую переноса второго т-разрядного сумма- сторону) и к выходам переносов одно- тора, вход переноса которого подклю- разрядных сумматоров т-й подгруппы чек к шине нулевого потенциала.

Редактор В. Петраш

Составитель И.Иваныкин

Техред Л.Серцюкова Корректор В. Бутяга

Заказ 3111/45 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Фие.2

Изобретение относится к вычислительной технике и предназначено для формирования остатков чисел по модулю -1, где m - целое число, при аппаратном контроле передачи двоичных чисел, представленных в параллельном коде, и арифметических действий над ними. Цель изобретения - повьше- ние эффективности контроля за счет (Л .f. , f °m лГ i I ., , V t я Ят On-l t Ли О