5.3. Общие свойства циклических кодов

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

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

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

Наоборот, пусть шшейный циклический код задается как некоторое множество многочленов по модулю Тогда код содержит все циклические сдвиги произвольного кодового многочлена Так как сумма кодовых слов линейного кода принадлежит коду, то код содержит все кратные многочлена по модулю Используя алгоритм Евклида, н. о. д. многочленов и можно записать по модулю как кратное многочлена Следовательно, линейный циклический код содержит н. о. д. каждого кодового многочлена и многочлена Обозначим через кодовый многочлен наименьшей степени. Тогда делит и любой кодовый многочлен.

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

Многочленная запись оказывается также полезной при задании проверочной матрицы Например, если а — корень многочлена и

то строки матрицы можно задавать многочленами где

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

Многочлен обладает тем свойством, что Так как каждый кодовый многочлен

кратен то он удовлетворяет сравнению Более того, каждый кодовый многочлен удовлетворяет сравнению для любого

Так как сумма проверочных соотношений опять задает проверочное соотношение и так как является проверочным многочленом при любом то любой многочлен, кратный многочлену по модулю опять задает проверочный многочлен. Всего имеется многочленов степени кратных многочлену Если бы код удовлетворял более чем проверочным соотношениям, то можно было бы найти более чем независимых проверочных соотношений, и тогда код должен был бы содержать больше чем проверочных позиций, что ведет к противоречию. Это приводит нас к следующему утверждению:

5.31. Теорема. Кодовыми многочленами линейного циклического кода с блоковой длиной являются все многочлены, кратные одному порождающему (код) многочлену Множество проверочных многочленов этого кода состоит всех многочленов, кратных проверочному многочлену

Например, проверочный многочлен исправляющего одиночные ошибки кода с и порождающим многочленом равен Проверки, выписанные на предыдущей странице, очевидно, имеют вид

Другой пример дает исправляющий две ошибки циклический код с блоковой длиной и порождающим многочленом . Для него Строки обычной проверочной матрицы, задаваемой уравнением (5.21), очевидно, имеют вид

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

Рис. 5.8. Кодер для циклического кода, основанный на проверочном многочлене.

Особенно простое множество образуют многочлены Им соответствуют проверки для Так как то это эквивалентно равенствам

Эти уравнения могут быть реализованы с помощью кодера такого же вида, как и на рис. 5.8, для

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

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

Ясно, что в таком методе кодирования используется регистр, имеющий всего ячеек. При кодер типа рис. 5.8 предпочтительнее кодера, изображенного на рис. 5.7.