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

 

ПИРАМИДАЛЬНАЯ СВЕРТКА ПО МОДУЛЮ ТРИ, содержащая п ступеней, каждая из которых содержит сумматоры , п-я ступень свертки содержит сумматор по модулю три, информационные выходы которого являются выходами свертки, отличающаяся тем, что, с целью сокращения объема оборудования и повышения быстродействия , ступени свертки с первой по {ь -1)-ю содержат сумматоры по мсдулю v Н 9 модуль предварительной свертки кратный 3, разрядностью q, +10( ( ближайшее большее целое ), выходы переноса каждого сумматора i-и ступени (, п ) свертки соединены со входсм переноса этого сумматора, вхсды нечетных и четных разрядов сумматоров первой ступени свертки являются входами нечетных и четных разрядов контролируемого числа, входы нечетных и четных разрядов сумматоров j-й ступени (, п -1) свертки соединены соответственно с нечетными и четными выходами двух смежных сумма- § торов {j-l)-й ступени свертки, входы нечетных и четных, разрядов суммагЛ тора по модулю три сгоединены соответственно с выходами нечетных и четных разрядов сумматора по модулю (п-1)-й ступени.

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

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

РЕСНУБЛИН

3(51) 0 06 11/10

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3442132/24-24 (22) 24.05.82 (46) 30. 07. 84. Бюл. Р 28 (72) A.Ë.Càìoéëoâ (53) 681.3(088.8) (56) 1. Селлерс Ф. Методы обнаружения и исправления ошибок в работе

ЭЦВМ. М., "Мир", 1972, с. 92, рис. 4. 27.

2. Путинцев Н.Д. Аппаратный контроль управляющих ЦВМ. М., "Сов. радио", 1966, с. 55, рис. 11. 10 (прототип). (54) (57) ПИРАМИДАЛЬНАЯ СВЕРТКА ПО

МОДУЛЮ ТРИ, содержащая и ступеней, каждая из которых содержит сумматоры, н -я ступень свертки содержит сумматор по модулю три, информационные выходы которого являются выхода" ми свертки, отличающаяся тем, что, с целью сокращения объема оборудования и повышения быстродей,„Я0„„1105896 А ствия, ступени свертки с первой по (h -11-ю содержат сумматоры по модулю % (% Ъ.9 — модуль предварительной свертки кратный 3, разрядностью ю=(Е0,(q, +1})(,ГEog (+1Ц .— ближайшее большее целое), выходы переноса каждого сумматора i -й ступени (i =1, и ) свертки соединены со входом переноса этого сумматора, входы нечетных и четных разрядов сумматоров первой ступени свертки являются входами нечетных и четных разрядов контролируемого числа, входы нечетных и четных разрядов сумматоров j-й ступени (j =2, и -1 ) свертки соединены соответственно с нечетными и четными выходами двух смежных сумма- cg

Я торов (j -1)-й ступени свертки, входы нечетных и четных, разрядов сумматора по модулю три соединены соответственно с выходами нечетных и четных разрядов сумматора по модулю (n -1 1-й ступени.

М®

1105896

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

Известна пирамидальная свертка по модулю три, содержащая группы элемен- 10 тов НЕ, И, ИЛИ (1).

Недостатком этого устройства являются большие аппаратурные затраты.

Наиболее близкой к предлагаемой является схема пирамидальной свертки 15 по модулю три, содержащая иерархическую структуру на блоках сложения по модулю три.

Пирамидальная свертка по модулю три содержит регистр приема с число- 20 вой магистрали и несколько ярусов

)(ступеней ) логических блоков сложения. Входы регистра приема числа подключены к разрядам контролируемого числа, а входы каждого блока сложения первой ступени соединены с выходами каждых двух разрядов регистра числа. Входы блоков сложения последующих ступеней подключены к выходам двух блоков сложения предыдущих 30 ступеней. Блок сложения последней ступени имеет три выхода, на каждом из которых появляется сигнал остатка по модулю три с функцией 01,10,11 (2).

Недостатком известной пирамидальной свертки являются большие аппаратурные затраты.

Цель изобретения - сокращение объема оборудования и повышение быстродействия за счет предварительной свертки контролируемого числа по мо" 40 дулю более высокого порядка с последующей сверткой результата .по модулю три.

"= г г.

N где N — разрядность контролируемого числа.

Устройство обеспечивает нахождение остатка в два этапа. Сначала производится свертка контролируемого числа по модулю 15 с учетом весовых функций четных и нечетных разрядов, затем свертка полученного результата по модулю три.

Контрольный код по модулю 15 находится суммированием двоично-шестнадцатиричных цифр по модулю 15 на 4-раз-. рядном сумматоре с циклическим переносом единицы из старшего разряда в младший, так как максимальная цифра, используемая в шестнадцатиричной системе счисления — пятнадцать. Если при сложении на 4-разрядном сумматоре по модулю 15 возникает перенос в пятый несуществующий разряд сумматора, то это эквивалентно потере числа

16, но 16 = 1тпод 15, поэтому потеря числа 16 компенсируется прибавлением единицы к младшему разряду сумматора.

С этой целью и введена цепь цикличного переноса от старшего к младшему разряду сумматора. Поскольку конечная цель преобразования числа " свертка по модулю три, то при выполнении операции сложения значений разрядов контролируемого числа по модулю 15 соблюдаются правила сложения ,по модулю три, т.е. учитываются весоПоставленная цель достигается тем, 45 что в пирамидальной свертке по модулю три, содержащей и ступеней, каждая из которых содержит сумматоры, и-я ступень свертки содержит сумматор по модулю три, информационные выходы которого являются выходами сверт ки; ступени свертки с первой по (;и -1)-ю содержат сумматоры по модулю

q,(q,> 9 - модуль предварительной свертки кратной 3, разрядностью

=(о ((, +1 )))(Р о (q +1 Ц - ближайшее большее целое ), выходы переноса кажйого сумматора i-й ступени (i =1,n) свертки соединены со входом переноса этого сумматора, входы нечетных и четных разрядов сумматоров первой ступе-60 ни свертки являются входами нечетных и четных разрядов контролируемого . числа, входы нечетных и четных разрядов сумматоров j -й ступени (j=22,п-1) свертки соединены соответствен7 но с нечетными и четными выходами двух смежных сумматоров (j -1) -й ступени свертки, входы нечетных и четных разрядов сумматора по модулю три соединены соответственно .с выходами нечетных и четных разрядов сумматора по модулю (л-.1) -й ступени.

На чертеже представлена схема пирамидальной свертки по модулю три при ф=15 °

В приведенном примере рассматривается наиболее оптимальная с практической точки зрения схема .пирамидальной свертки по модулю три при ч.=15, обеспечивающая наименьшие аппаратурные затраты при максимальном быстродействии

Схема )(разрядной пирамидальной свертки по модулю 3 содержит 4-разрядные полные сумматоры 1-3 по модулю

15 первой, второй и (и -1)-й ступеней соответственно, 2-разрядный полный сумматор 4 по модулю три и-й ступени.

Работа свертки по модулю три при с),= 15.

На чертеже изображены. в ступеней, причем, ступени с 1-й по (n"1)-ю выполняют операцию свертки по модулю 15, а ь -я ступень — свертку полученного результата по модулю три. исло ступеней и определяется соотно. ением

1105896

Заказ 5603/39

99 Подписное вые функции нечетных и четных разрядов числа 1весовые функции всех нечетных разрядов равны 1, а четных-2).

Принцип свертки по модулю 15, с . учетом весовых функций четных и нечетных разрядов, основан на попарном сложении четных и нечетных разрядов контролируемого числа, т.е. в нечетный разряд сумматоров 1 по модулю 15 заведены два нечетных разряда контролируемого числа, а в четный разряд сумматоров 1- два четных разряда числа. При сложении двух нечетных разрядов в нечетном (первом или третьем) разряде сумматора возможен результат 0,1,2., этот результат эквива-)5 лентен остатку свертки по модулю три.

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

Следовательно, в четном разряде сумматора (втором или четвертом ) сложатся значения четных разрядов контролируемого числа и переноса из нечетного разряда. При этом с учетом весовой функции слагаемых, равной 2, возможен результат 0,2,4,6. При результате 4 и 6 возникает единица переноса с весовой функцией 1, так как

4 = 1 synod 3, а 6 = 2+4=2+1 tnod 3. В этом случае единица переноса попадает в следующий нечетный разряд сумматора по модулю 15, где происходит сложение нечетных разрядов контролируемого числа. Таким образом, в сумматоре по модулю 15 обеспечивается.чеедование сложения четных и нечетных азрядов. В этом случае при сложении разрядов контролируемого числа по модулю 15 соблюдаются условия свертки по модулю три. Последняя ступень свертки 4 преобразует остаток по модулю 15 в остаток по модулю три, используя приведенный принцип сложения нечетных и четных разрядов числа.

Технико-экономическая эффективность от использования изобретения заключается в снижении объема оборудования при одновременном повышении быстродействия.

ППП "Патент", г,ужгород,ул.Проектная,4