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