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

Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).

ВведениеПравить

Пусть   — слово длины n над алфавитом из элементов конечного поля   и   — полином, соответствующий этому слову, от формальной переменной  . Видно, что это соответствие является изоморфизмом линейных пространств. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации   пары слов   и  , равен линейной комбинации полиномов этих слов  .

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n − 1 над полем  .

Алгебраическое описаниеПравить

Если   — кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова  , то соответствующий ему полином   получается из предыдущего умножением на x:

 , пользуясь тем, что  

Сдвиг вправо и влево соответственно на   разрядов:

 
 

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

Порождающий полиномПравить

Определение

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

Теорема 1

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

 

где степень   меньше или равна  .

Теорема 2

  — порождающий полином циклического   кода — является делителем двучлена  .

Следствия

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

Порождающая матрицаПравить

Полиномы   линейно независимы, иначе   при ненулевом  , что невозможно.

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

 

где   является порождающей матрицей,   — информационным полиномом.

Матрицу   можно записать в символьной форме:

 

Проверочная матрицаПравить

Для каждого кодового слова циклического кода справедливо  . Поэтому проверочную матрицу можно записать как

 

Тогда

 

КодированиеПравить

НесистематическоеПравить

При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий:

 

Оно может быть реализовано при помощи перемножения полиномов.

СистематическоеПравить

При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного:

 

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

 

Тогда из условия   следует

 

Это уравнение и задаёт правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров (МЛФ).

ПримерыПравить

Двоичный (7,4,3) кодПравить

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

Порождающая матрица кода:

 

где первая строка представляет собой запись полинома   коэффициентами по возрастанию степени.

Остальные строки — циклические сдвиги первой строки.

Проверочная матрица:

 

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

Так, например, 4-й столбец получается  , или в векторной записи  .

Легко убедиться, что  .

Двоичный (15,7,5) БЧХ кодПравить

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

 

Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома   со степенью   таким образом:

 

Например, информационному слову   соответствует полином  , тогда кодовое слово  , или в векторном виде  .

См. такжеПравить

СсылкиПравить