Циклические коды

В поисках более простой техники кодирования и декодирования был найден подкласс линейных систематических двоичных кодов, называемых циклическими и применяемых в технике связи. Название этих кодов связано с тем, что каждый вектор, получаемый из кодового циклической перестановкой его символов, также принадлежит коду. Так, например, циклические перестановки вектора 1000101 являются также кодовыми векторами 0001011, 0010110, 0101100 и т. д.

Теория циклических кодов основана на изоморфизме, пространства двоичных n-последовательностей и пространства полиномов степени не выше п —1 вида

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

Легко видеть, что между полиномами и n-последовательностями имеется изоморфизм, причем полиному соответствует n-последовательность

Любой полином g(x) степени r<n, который делит без остатка двучлен xⁿ—1, может служить порождающим полиномом циклического (n, k)-кода, где k=n —r. В этот код входят те полиномы, которые без остатка делятся на g(x). В частности, для кода (7,4) порождающим полиномом является

(1.54)

Среди циклических кодов особое значение имеет класс кодов, предложенных Боузом и Рой-Чоудхури и независимо от них Хоквингемом. Коды Боуза — Чоудхури — Хоквингема (обозначаемые сокращением БЧХ) отличаются специальным выбором порождающего полинома, вследствие чего для них существуют сравнительно просто реализуемые процедуры декодирования. Доказано, что для любой пары натуральных чисел 5 и t<2^s-2 можно построить двоичный код БЧХ с n=2^s —1 и k≥n — st, исправляющий любую конфигурацию ошибок с кратностью, меньшей или равной t.

Относительно простой является процедура мажоритарного декодирования, применимая для некоторого класса двоичных линейных, в том числе циклических кодов. Основана она на том, что в этих кодах каждый информационный символ можно несколькими способами выразить через другие символы кодовой комбинации. Если для некоторого символа эти способы проверки дают неодинаковые результаты (одни дают результат «О», а другие — «1», что может быть только в случае ошибочного приема), то окончательное решение по каждому из информационных символов принимается по мажоритарному принципу, т. е. по большинству. Мажоритарное декодирование осуществляется относительно просто, посредством регистров сдвига.

Примером кода, допускающего мажоритарное декодирование, является код, двойственный рассмотренному ранее коду Для него матрица (1.52) является образующей. Ее удобнее записать, переставив столбцы, так:

(1.55)

Символ b₁в этом коде связан с другими символами следующими соотношениями: b₁ = b₂ + b₆ = b₇ + b₅ = b₃ + b_4. Обозначим принятые после демодуляции , , , , , , .Если бы они все были приняты верно, то для переданного символа были бы верны следующие четыре равенства (проверки):

(1.56)

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

Предположим, что один из символов блока принят с ошибкой. Тогда три из проверок (1.56) дадут одно (правильное) значение b₁,а одна проверка, в которой участвует ошибочный символ, даст другое, ошибочное значение. Принимая решение по большинству получим правильное значение b₁. Если бы ошибок было три или больше, то мажоритарное решение могло бы дать ошибочный результат. При двух ошибочно принятых символах может получиться одинаковое (верное) значение для b₁во всех проверках (например, при ошибочно принятых и ) либо в двух проверках b₁ = 0, а в двух других b₁ = 1 (например, при ошибочно принятых и ). В последнем случае можно только констатировать наличие ошибок.

После принятия решения о символе b₁аналогично проверяют значения b₂и b₃. Поскольку рассматриваемый код (7, 3)—циклический, соответствующие проверки получаются из (1.56) циклической перестановкой.