Устройство для свертки по модулю g=2 @ -1

 

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

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

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

РЕСПУБЛИН

А1 (19) (И) (5g 4 С 06 F 11/10

OllHCAHHE ИЗОБРЕТЕНИЯ

Н ABTOPCKOMV СВИДЕТЕЛЬСТВУ р/ (21) 4032645/24-24 (22) 06.03.86 (46) 23.07.87. Бюл, У 27

Вг А в„ Ф в, ф

L:I

Ъ./ в, т

Вг ñ

Ю

Ai Вг i я в гг гг

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (72) С.А. Точин (53) 681.3(088.8) (56) Авторское свидетельство СССР (1i 1084799, кл. С 06 Р 11/10, 1984.

Журавлев Ю.П. и др. Надежность контроль ЭВМ.-М.: Советское радио, 1978, с. 114, рис. 3. 11. (54) УСТРОЙСТВО ДЛЯ СВЕРТКИ ПО МОДУЛЮ

q 2Ô (57) Изобретение относится к вычислительной технике и предназначено для формирования остатков чисел по модулю q=2 -1, где ш — целое число, при аппаратном контроле передачи двоичных чисел, представленных в параллельном коде, и арифметических действий над ними. Цель изобретения — повышение эффективности контроля эа счет 1325484 исключения неоднозначности результата формирования остатка по модулю q

2 -1 ° Устройство содержит N групп

1 по ш .подгрупп 2 в каждой группе одноразрядных сумматоров, два m-разрядных сумматора 3,4, входы 5 устрой° ства, выходы 6 устройства. Устройство

Изобретение относится к вычислительной технике и предназначено для формирования остатков чисел по модулю ,,М где ш - целое число, при аппаратном контроле передачи двоичных чисел, представленных в параллельном коде, и арифметических действий над ними, Цель изобретения — повышение дос- 1р товерности контроля эа счет исключения неоднозначности результата формирования остатка по модулю q--2 -I.

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

X-й группы сумматоров.

Устройство содержит N групп 1 по

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

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

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

1-й группы из групп 1 поступают зна1- 1 чения разрядов с весом 2, которые суммируются одноразрядными сумматорами 7, составляющими подгруппу 2. Вы-! Г-1 ходы A„. х-й подгруппы имеют вес 2

I Г

1 а выходы В. — вес 2 . Выходы В ш-и

j N

ФЭЪ подгруппы имеют вес 2, что.по модулю 2 — 1 соответствует 1, так как

2 = 1 >nod(2 -1) и равен весу выходов

А,. 1-й подгруппы. В i-x подгруппах 2 40 всех последующих групп 1 аналогично производится суммирование значений выходов подгрупп предыдущей группы с одинаковым для каждой i-й подгруппы весом 2 . Выходы А, подгрупп имеют формирует в качестве нулевого остатка код q для ненулевых кодов, кратных модулю q = 2 — 1. Повышение эффективности контроля достигается за счет введения второго ш-разрядного сумматора, формирующего перенос в первый ш-разрядный сумматор. 2 ил.

2 вес 2 ", а входы В1 — вес 21 . На последнем этапе после N-й группы, когда

P < 2, где P — - количество выходов i-й подгруппы N-й группы сумматоров, где

1 ь i m, 1 L I c N, суммирование производится m-разрядным сумматором

3 с учетом значения переноса, поступающего с сумматора 4, что и обеспечивает суммирование по модулю q =

2 -1.

На выходах ш-разрядного сумматора

3, являющихся выходами 6 устройства, формируется окончательное значение м кода остатка r по модулю q = 2—

При этом при поступлении на входы 5 устройства нулевого и-разрядного кода формируется нупевой код остатка (r =

= 0), а при поступлении любого ненулевого и-разрядного кода формируется код остатка r таким образом, что

1 (r (q. Причем для ненулевого кода, кратного модулю q, однозначно формируется значение остатка r равное модулю о (r = q). Выполнение условия

r q для ненулевых кодов обусловлено тем, что при суммирования значений разрядов и-разрядного кода одноразрядными сумматорами подгрупп любое сочетание единиц в коде приводит к появлению хотя бы одной единицы на выходах А . или В. при 1 < i «4 m, Э, 3

1 I причем для всех I при 1 6Т с N, т.е. и и и на. выходах А; или В . А на выходах оконечного m-разрядного сумматора 3 нулевой результат при этом был бы . возможен только при переполнении сумматора, но в этом случае происходит добавление единицы переноса, поступающей из сумматора 4.

Предлагаемое устройство в отличие от известного однозначно формирует в качестве нулевого остатка код для ненулевых кодов, кратных модулю

3Т

q = 2 -1, что позволяет повысить

3 132 эффективность контроля. Кроме того, для нулевых кодов формируется нулевой код остатка, что также может быть использовано для повышения эффектив ности контроля.

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

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

q = 2 -1, содержащее N групп одноразрядных сумматоров из ш подгрупп в

311 и каждой группе (-) p — где n - раэ2 2m рядность сворачиваемого числа, и первый ш-разрядный сумматор, причем груп° n- i+ па иэ К = — — — — — входов -й нод1 m группы (1 4 i «(m) первой группы одноразрядных сумматоров является группой входов устройства для подключения к выходам сворачиваемого числа с весом 2, ш выходов суммы первого mразрядного сумматора являются выходами устройства, каждая i-я подгруппа

I-й группы одноразрядных. сумматоров (1 са I «(N) содержит К;/3 (округлять

J до целого в меньшую сторону) одноразрядных сумматоров, где К, " количестМ во входов i-й подгруппы одноразрядных сумматоров Е-й группы, входы первой подгруппы одноразрядных сумматоров

Q-й группы (2 «((Q (М) подключены к выходам сумм одноразрядных сумматоров первой подгруппы (Q-1)-й группы, к (К -К /3) разрядам входного кода первой подгруппы (Q-1)-g группы (КЯ-4/ !

/3) — округлять до целого в меньшую сторону) и к выходам переносов одноразрядных сумматоров m-й подгруппы

5484

4 (Q-1)-й группы, входы ) -й подгруппы одноразрядных сумматоров (2 < С1а m)

Q-й группы подключены к выходам сумм одноразрядных сумматоров -й под5 съ 4 группы (Q-1)-й группы . к (К

0-4

Ф

К /3) разрядам входного кода 1 -й

3 подгруппы одноразрядных сумматоров (Q-1)-й группы (К 4 /3 округлять до

1 целого в меньшую сторону) и к выходам переносов одноразрядных сумматоров (3 -1) -й подгруппы (Q-1) -й груп ч пы (причем N таково, что количество выходов одноразрядных сумматоров i-й подгруппы N-й группы равно двум), выход суммы одноразрядного сумматора первой подгруппы и выход переноса од- (норазрядного сумматора ш-й подгруппы

N-й группы соединены с первыми разряд дами соответственно первого и второго слагаемых первого m-разрядного сумматора, 1-е разряды первого и второго слагаемых первого m-разрядного сумматора соединены соответственно с вы25 ходом суммы сумматора 1 -й подгруппы

N-й группы и выходом переноса одноразрядного сумматора ()-1)-й подгруппы И-й группы, о т л и ч а ю щ ее с я тем, что, с целью новьппения

30 достоверности контроля, в устройство введен второй ш-разрядный сумматор, входы первого и второго слагаемых которого соединены соответственно с (входами первого и второго слагаемых первого ш-разрядного сумматора, вход переноса которого соединен с выходом переброса второго m-разрядного сумматора, вход переноса которого подключен к шине нулевого потенциала.

1325484

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

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

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

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

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

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

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