УСТРОЙСТВО для КОДИРОВАНИЯ двоичных ЦИКЛИЧЕСКИХ кодов Советский патент 1972 года по МПК H03M13/51 

Изобретение относится к устройству кодирования для двоичного циклического кода и может найти применение в тех областях вычислительной техники и техники передачи данных, где повышение помехоустойчивости информации производится с помощью циклических кодов, порождаемых различными полиномами, в частности в больших информационных и управляющих системах. Как известно кодовый полипом /о(л;), принадлежащий циклическому коду, находится по информационному полиному f(x) как fo{x)f(x)x -{-r(x), где f(x)-остаток от деления f(x)x на порождающий пол:ипом g(x) степени г.

Применяемые схемы кодирования реализуют этот алгоритм, осуществляя деление информационного полинома, умноженного на х, на фиксированный порождаюш,ий полином. Деление осуществляется путем последовательного сложения по модулю два делителя вначале со старшими членами делимого, затем со старшими членами (начиная с первого значащего члена) получившегося остатка, и так до тех пор, пока, наконец, степень остатка не станет меньше степени делителя.

включения сумматоров определяются коэффициентами полинома g(x).

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

Недостатком существующих кодирующих устройств является то, что они осуществляют

нахождение кода, порождаемого фиксированным полиномом g(x). При этом дл кодирования информации при работе по Л каналам требуется N различных устройств кодирования. При необходимости нахождения кодов,

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

Цель изобретения - создание универсального устройства, позволяющего находить проверочные символы для двоичных циклических кодов, порождаемых любыми полиномами степени, не превыщающей числа запоминаюполинома, на который необходимо производить деление, и управления схемами «И. Порождающий полином записывается в запоминающем регистре в нормализованной форме, т. е. вместо полинома степени записывается полином g(x). При этом старший член полинома имеет степень г, а младдаие члены г-/ являются нулями. В итоге после /г сдвигов получаем остаток от деления f{x)x на g(, т. е. тот же самый результат, что и при делении f(x)xJ на g(x).

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

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

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

Запоминающий регистр J состоит из г запомипающих ячеек 0-ь (г-1), в которые из запоминающего устройства 2 поступают коэффициенты полинома g(x), где за исключением коэффициента при х . С тех запоминающих ячеек 0-н(г-1), в которых записаны «1, подаются разрешающие сигналы на соответствующие схемы «И 3 О-(г-1). Это создает цепи обратной связи, соответств-ующие полиному, порождающему код.

Сдвигающий регистр 4 состоит из г запоминающих ячеек со встроенными между ними сумматорами 5 по модулю два. На сумматор 6 поступают старший раЗ|ряд промежуточного остатка от деления и информационные символы 7. Ввод информационных символов в эту точку эквивалентен умножению их на л;. С выхода сумматора 6 сигналы поступают на схемы «И 3 и проходят только те из них, на которых имеется разрешающий сигнал с ячеек регистра 1.

На регистр 1 поступают коэффициенты полинома, лорождающие необходимый код, начиная с коэффициента при степени г-1. При этом полином представляется в нормализованном виде, т. е. если степень полинома , то он записывается умноженным на х- с тем, чтобы коэффициент при старшем члене находился на позиции г. При этом коэффициенты при младших г-/, членах будут равны 0.

ется в ячейку U при члене первой степени в ячейку Лит. д., при члене г-I степени - в ячейку / (г-I). С выходов ячеек запоминающего регистра, в которых записаны «1, подаются разрешающие сигналы на соответствующие схемы «PI, и таким образом создаются необходимые цепи обратной связи для суммирования информационных символов с порождающим полиномом.

Процесс деления состоит из последовательных сдвигов и вычитания (суммирования) по модулю 2 информационного полинома f(x), умноженного на х , и порождающего полино.ма g(x), умноженного на . Это эквивалентно делению f(x)x на g{x), т. е. тому, что выполняет обычная схема кодирования для циклического кода, порождаемого фиксированным полиномом g{x) степени /.

Коэффициенты информационного полинома 7, начиная с коэффициентов при членах старших степеней, поступают на вход сумматора 6. Тем самым они умножаются на х . На другой вход сумматора 6 поступают сигналы со старшего разряда сдвигающего регистра 4

(/--1). Последовательность сигналов с выхода сумматора 6, являющаяся частным от деления f{x}x-i на порождающий полином g{x) степепи / через схемы обратной связи «И, на которые подано разрешение с регистра порождающего полинома, поступает на соответствующие сумматоры 5. Таким о-бразом производится суаммирование содержимого сдвигающего регистра с порол дающим полиномом.

Так как результат суммирования старших разрядов делимого и делителя всегда равен О, то сумматор для этой операции не предусмотрен. После поступления К коэффициентов информационного полинома в ячейках сдвигающего регистра 4 (г-/)-н(г-1) остается остаток от деления, являющийся совокупностью проверочных символов кода.

Предмет изобретения

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