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

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

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

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

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

Алгебраическое описание

[править | править код]

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

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

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

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

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

[править | править код]
Определение

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

Теорема 1

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

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

Теорема 2

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

Следствия

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

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

[править | править код]

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

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

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

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

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

[править | править код]

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

Тогда

Кодирование

[править | править код]

Несистематическое

[править | править код]

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

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

Систематическое

[править | править код]

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

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

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

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

Двоичный (7,4,3) код

[править | править код]

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

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

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

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

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

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

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

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

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

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

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