Пирамидальная свертка по модулю три Советский патент 1984 года по МПК G06F11/10 

сл

00

со сг: Изобретение отИЪсится к цифровым вычислительным машинам, а именно к способам и устройствам для обнаружения ошибок, и может быть использовано в вычислительных устройствах для обнаружения сшибок с помощью избыточности в представлении данных и добавления специальных разрядов к ко дированной информации. Известна пирамидальная свертка по модулю три, содержащая группы элемен тов НЕ, И, ИЛИ 1. Недостатком этого устройства явля ются большие аппаратурные затраты. Наиболее близкой к предлагаемой является схема пирамидальной свертки по модулю три, содержащая иерархическую структуру на блоках сложения по модулю три. Пирамидальная свертка по модулю три содержит регистр приема с числовой -магистрали и несколько ярусов |(ступеней) логических блоков сложения. Входы регистра приема числа под ключены к разрядам контролируемого числа, а входы каждого блока сложения первой .ступени соединены с выходами каждых двух разрядов регистра числа. Входы блоков сложения последующих ступеней подключены к выходам двух блоков сложения предыдущих ступеней. Блок сложения последней ступени имеет три выхода, на каждом из которых появляется сигнал остатка по модулю три с функцией 01,10,11 2J Недостатком известной пирамидальной свертки являются большие аппаратурные затраты. Цель изобретения - сокращение объема оборудования и повышение быст родействия за счет предварительной свертки контролируемого числа по модулю более высокого порядка с последующей сверткой результата -по модулю три. Поставленная цель достигается тем что в пирамидальной свертке по модулю три, содержащей п ступеней, каждая из которых содержит сумматоры, п-я ступень свертки содержит сумматор по модулю три, информационные вы ходы которого являются выходами свер ки; ступени свертки с первой по (;П-1)-ю содержат сумматоры по модулю c,(c{, - модуль предварительной свер ки кратной 3, разрядностью № )( U+11 -ближайшее большее целое ), выходы переноса каждого сумматора т-й ступени (,nl свертки соединены со входом переноса этого сумматора, вхрды нечетных и че ных разрядов, сумматоров первой ступе ни свертки являются входами нечетных и четных разрядов контролируемого числа, входы нечетных и четных разря дов сумматоров j-и ступени (,ri-i свертки соединены соответствен- но с нечетными и четными выходами двух смежных сумматоров (-1)-й ступени свертки, входы нечетных и четных разрядов сумматора по модулю три соединены соответственно .с выходами нечетных и четных разрядов сумматора по модулю (nrl) -и ступени. На чертеже представлена схема пирамидальной свертки по модулю три при ч,15. В приведенном примере рассматривается наиболее оптимальная с практической точки зрения схема .пирамидальной свертки по модулю три при {,15, обеспечивающая наименьшие аппаратурные затраты при максимальном быстродействии. Схема N разрядной пирамидальной свертки по модулю 3 содержит 4-разрядные полные сумматоры 1-3 по модулю 15 первой, второй и (п-1)-й ступеней соответственно, 2-разрядньзй полный сумматор 4 по модулю три п-й ступени. Работа свертки по модулю три при Ч 15. На чертеже изображены, п ступеней,причем, ступени с 1-й по n-l)-ю выполняют операцию свертки по модулю 15, а (1 -я ступень - свертку полученного результата по модулю три. Яисло ступеней п определяется соотношением, где N - разрядность контролируемого числа. Устройство обеспечивает нахо)вдение остатка в два этапа. Сначала производится свертка контролируемого числа по модулю 15 с учетом весовых функций четных и нечетных разрядов, затем свертка полученного результата по модулю три. Контрольный код по модулю 15 находится суммированием двоично-шестнадцатиричных цифр по модулю 15 на 4-раз-. рядном сумматоре с циклическим переносом единицы из старшего разряда в младший, так как максимальная цифра, используемая в шестнадцатиричной системе счисления - пятнадцать. Если при сложении на 4-разрядном сумматоре по модулю 15 возникает перенос в пятый несуществующий разряд сумматора, то это эквивалентно потере числа 16, но 16 1 mod 15, поэтому потеря числа 16 компенсируется прибавлением единицы к младшему разряду сумматора. С этой целью и введена цепь цикличного переноса от старшего к младшему разряду сумматора. Поскольку конечная цель преобразования числа свертка по модулю три, то при выполнении операции сложения значений разрядов контролируемого числа по модулю 15 соблюдаются правила сложения помодулю три, т.-е. учитываются весо

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