3.8.12. Построение кода с заданной корректирующей способностью

Существует несложная процедура построения кода с заданной корректирующей способностью. Она состоит в следующем:

1. По заданному размеру информационной составляющей кодового слова длиной k определяется количество m дополнительных (избыточных) разрядов, обеспечивающее обнаружение и исправление 1-кратных ошибок. Сделать это можно при помощи формулы (3.1) границы Хэмминга. Длина кодовых слов получающегося кода будет равной n=k+m. Строится систематический (n,k) код.

2. Рассматривая кодовые слова построенного (n,k)-кода как новую информационную последовательность длиной k₁=n, повторяем п.1.

В результате получаем новый (n₁,k₁)-код, способный также способный исправлять однократные ошибки.

Повторяя t раз п.п. 1 и 2 можно построить составной код, исправляющий t-кратные ошибки.

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

Такой код, однако, оказывается неоптимальным с точки зрения числа дополнительных разрядов. Разработаны другие способы получения кодов с заданной корректирующей способностью, которые используют минимальное необходимое количество число дополнительных разрядов. К ним, в частности относятся широко известные среди лиц, занимающихся помехоустойчивым кодированием, коды Боуза-Чоудхури.

3.8.13. Матричное описание циклических кодов

Циклические коды можно, как и любые линейные коды, описывать с помощью матриц.

Вспомним, что KC(X) = g_m(X)*И(Х) .

Вспомним также на примере порядок умножения полиномов:

g_m(X) = 1 0 1 0 1 1

И (Х) = 1 0 1 1

1 0 1 0 1 1 * 1

1 0 1 0 1 1 * 1

1 0 1 0 1 1 * 0

1 0 1 0 1 1 * 1

1 0 0 1 0 0 1 0 1

Это соответствует описанному выше упрощенному способу умножения матриц:

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

Согласно второму способу кодирования, позволяющего получить систематический код, кодовое слово находится по формуле:

.

Образующая матрица ||ОМ|| в этом случае должна состоять из 2 частей – единичной матрицы ||I|| и матрицы дополнительных разрядов ||МДР||: ||OM|| = || I МДР || .

Результат кодирования при помощи матриц будет совпадать с результатом кодирования при помощи полиномов в том случае, если строки матрицы дополнительных разрядов образовать по следующей формуле:

.

Далее по МДР легко построить ТПМ, найти опознаватели и пользоваться описанными выше для линейных кодов процедурами кодирования-декодирования.

3.8.14. Выбор образующего полинома

Ясно, что полиномы кодовых слов КС(Х) должны делиться на образующий полином g(X) без остатка. Циклические коды относятся к классу линейных. Это означает, что для этих кодов существует m линейно-независимых кодовых слов и с их помощью путем суммирования в разных комбинациях можно получить все остальные разрешенные кодовые слова данного кода. Для того, чтобы все они делились на образующий полином без остатка, достаточно чтобы без остатка на него делились только m линейно независимых кодовых слов. Эти линейно-независимые кодовые слова можно получить путем m-кратного циклического сдвига вправо или влево на 1 позицию любого из разрешенных кодовых слов.

Напомним, что сдвигу влево соответствует умножение кодового слова на Х с вычитанием, если в результате умножения получается полином порядка n, из результата полинома Хⁿ+1. В формульном виде вышесказанное может быть отображено следующим образом:

g_i(X) = g(X)Хⁱ – B(Xⁿ+1),

где коэффициент В=1, если степень g(X)*Xⁱ < n

и В=0, если степень g(X)*Xⁱ n.

Частное g_i(X)/ g(X) не имеет остатка, если полином (Xⁿ+1) без остатка делится на образующий полином g(X) (очевидно, первое слагаемое делится на g(X) без остатка).

Таким образом, образующий полином g_m(X) циклического линейного кода должен делить полином Хⁿ+1 без остатка.

Это свойство обеспечивает отсутствие остатка при делении разрешенных кодовых слов на образующий полином. Таких слов 2^k. Всего же различных кодовых слов, которые могут быть получены на выходе канала связи 2ⁿ. Среди них 2^m − 1 запрещенных, т.е. полученных в результате искажения разрешенных кодовых слов помехой. Ошибка обнаруживается, если остаток от их деления на образующий полином не равен нулю. Образующий полином имеет порядок m. Максимально возможное количество ненулевых остатков равно 2m − 1. Такое количество остатков могут дать только так называемые неприводимые полиномы, т.е. полиномы, которые не делятся без остатка ни на какие другие полиномы, кроме 1 и себя самого. Таблица неприводимых полиномов от 1 до 9 порядков приведена в приложении 1.