Задание циклических кодов с помощью корней генераторного полинома

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

Циклические коды являются подклассом в классе линейных кодов, удовлетворяющим дополнительному свойству цикличности. Линейные коды, удовлетворяющие этому свойству, – циклические, т.е. такие коды, которые вместе с каждым кодовым словом содержат также и его циклическую перестановку При таком определении для

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

Выше при описании линейных кодов было показано, что, например, проверочная матрица кода Хэмминга (7;4) есть матрица, состоящая из элементов a поля

Используя эту матрицу, кодовое слово можно определить как вектор над такой, что в расширении поля он дает (исходя из основного уравнения кодирования

нулевое произведение с или

Отсюда кодовое слово А можно представить в виде многочлена

и операция умножения АН^Т превращается в операцию вычисления многочлена А(х) в точке х=а. Условие того, что А(х) - кодовое слово, превращается в равенство А(а)=0 т.е. двоичный многочлен А(х) является кодовым словом тогда и только тогда, когда б – корень многочлена A (x). Представление многочленами кода Хэмминга (7;4) образует множество всех многочленов над полем GF(2) степени не выше шесть таких, что б из GF(2³) является корнем каждого из них. Таким образом, если A (x) – переданное кодовое слово, то символами переданного слова будут коэффициенты многочлена A (x) (для двоичного кода коэффициенты { 0,1 }). Например, при

Циклический код задается порождающим (генераторным) полиномом g(x) степени r. Например, число проверочных разрядов r = 3 в коде, задаваемом полиномом g (x) = 1+ x + x ³. Для того чтобы полином был генераторным

полиномом циклического кода, необходимо, чтобы он был делителем полинома вида xⁿ + 1, где n – длина кода. При делении полиномов действия про-

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

Для построения циклического кода необходимо знать разложение полинома xⁿ +1 на множители.

Если n =2 ^m-1, то многочлен xⁿ + 1 представляется как произведение неприводимых многочленов степени не выше m. Каждый из этих многочленов, а также их произведения могут быть использованы как порождающие полиномы циклического кода.