- Циклический код
-
Для улучшения этой статьи желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Циклический код — линейный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Содержание
Введение
Пусть
слово длины n над алфавитом из элементов конечного поля
и
полином, соответствующий этому слову, от формальной переменной
. Видно, что это соответствие не просто взаимнооднозначное, но и изоморфное. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации
пары слов
и
, равен линейной комбинации полиномов этих слов
Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n-1 над полем
Алгебраическое описание
Если
кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова
, то соответствующий ему полином
получается из предыдущего умножением на x:
, пользуясь тем, что
,
Сдвиг вправо и влево соответственно на
разрядов:
Если
— произвольный полином над полем
и
— кодовое слово циклического
кода, то
тоже кодовое слово этого кода.
Порождающий полином
Определение Порождающим полиномом циклического
кода
называется такой ненулевой полином
из
, степень которого наименьшая и коэффициент при старшей степени
.
Теорема 1
Если
— циклический
код и
— его порождающий полином, тогда степень
равна
и каждое кодовое слово может быть единственным образом представлено в виде
,
где степень
меньше или равна
.
Теорема 2
— порождающий полином циклического
кода является делителем двучлена
Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель
. Степень выбранного полинома будет определять количество проверочных символов
, число информационных символов
.
Порождающая матрица
Полиномы
линейно независимы, иначе
при ненулевом
, что невозможно.
Значит кодовые слова можно записывать, как и для линейных кодов, следующим образом:
, где
является порождающей матрицей,
— информационным полиномом.
Матрицу
можно записать в символьной форме:
Проверочная матрица
Для каждого кодового слова циклического кода справедливо
. Поэтому проверочную матрицу можно записать как:
Тогда:
Кодирование
Несистематическое
При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий
.
Оно может быть реализовано при помощи перемножителей полиномов.
Систематическое
При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного
Пусть информационное слово образует старшие степени кодового слова, тогда
Тогда из условия
, следует
Это уравнение и задает правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров(МЛФ)
Примеры
Двоичный (7,4,3) код
В качестве делителя
выберем порождающий полином третьей степени
, тогда полученный код будет иметь длину
, число проверочных символов (степень порождающего полинома)
, число информационных символов
, минимальное расстояние
.
Порождающая матрица кода:
,
где первая строка представляет собой запись полинома
коэффициентами по возрастанию степени. Остальные строки — циклические сдвиги первой строки.
Проверочная матрица:,
где i-ый столбец, начиная с 1-ого, представляет собой остаток от деления
на полином
, записанный по возрастанию степеней, начиная сверху.
Так, например, 4-ий столбец получается
, или в векторной записи
.
Легко убедиться, что
.
Двоичный (15,7,5) БЧХ код
В качестве порождающего полинома
можно выбрать произведение двух делителей
:
.
Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома
со степенью
таким образом:
.
Например, информационному слову
соответствует полином
, тогда кодовое слово
, или в векторном виде
См. также
Ссылки
Категории:- Обнаружение и устранение ошибок
- Теория кодирования
Wikimedia Foundation. 2010.