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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Введение[править | править вики-текст]

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

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

Алгебраическое описание[править | править вики-текст]

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

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

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

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

Порождающий полином[править | править вики-текст]

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

Теорема 1

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

,

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

Теорема 2

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

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

Порождающая матрица[править | править вики-текст]

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

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

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

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

Проверочная матрица[править | править вики-текст]

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

Тогда:

Кодирование[править | править вики-текст]

Несистематическое[править | править вики-текст]

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

.

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

Систематическое[править | править вики-текст]

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

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

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

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

Примеры[править | править вики-текст]

Двоичный (7,4,3) код[править | править вики-текст]

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

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

,

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

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

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

,

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

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

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

Двоичный (15,7,5) БЧХ код[править | править вики-текст]

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

.

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

.

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]