Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Пусть
— слово длины n над алфавитом из элементов конечного поля
и
— полином, соответствующий этому слову, от формальной переменной
. Видно, что это соответствие является изоморфизмом линейных пространств. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле.
Полином, соответствующий линейной комбинации
пары слов
и
, равен линейной комбинации полиномов этих слов
.
Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n − 1 над полем
.
Если
— кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова
, то соответствующий ему полином
получается из предыдущего умножением на x:
, пользуясь тем, что ![{\displaystyle x^{n}\equiv 1\mod (x^{n}-1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bdbf43124b6af367e8cc46763dea292f2aea13f)
Сдвиг вправо и влево соответственно на
разрядов:
![{\displaystyle c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4198f32e337553c114ddf7257d2cfcdd44a9a3b9)
![{\displaystyle c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd088eda74a759a8aa86f96d08477b2bbdb28b1f)
Если
— произвольный полином над полем
, и
— кодовое слово циклического
кода, то
— тоже кодовое слово этого кода.
- Определение
Порождающим полиномом циклического
кода
называется такой ненулевой полином
из
, степень которого наименьшая, и коэффициент при старшей степени
.
- Теорема 1
Если
— циклический
код, и
— его порождающий полином, то степень
равна
, и каждое кодовое слово может быть единственным образом представлено в виде
![{\displaystyle c(x)=m(x)g(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bae1ee6ad28f8d034c2512b220bb85a0fe4a56e2)
где степень
меньше или равна
.
- Теорема 2
— порождающий полином циклического
кода — является делителем двучлена
.
- Следствия
Таким образом, в качестве порождающего полинома можно выбирать любой полином делитель
.
Степень выбранного полинома будет определять количество проверочных символов
, число информационных символов
.
Полиномы
линейно независимы, иначе
при ненулевом
, что невозможно.
Значит кодовые слова можно записывать, как и для линейных кодов, следующим образом:
![{\displaystyle {\overline {m}}G=(m_{0},m_{1},\dots ,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\\\dots \\x^{k-1}g(x)\end{bmatrix}}=m(x)g(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aecade7c97f6c1b4c4e7f814ac7a2c8ee138f06a)
где
является порождающей матрицей,
— информационным полиномом.
Матрицу
можно записать в символьной форме:
![{\displaystyle G={\begin{bmatrix}g_{0}&g_{1}&\dots &g_{r-1}&g_{r}&0&\dots &0\\0&g_{0}&\dots &g_{r-2}&g_{r-1}&g_{r}&\dots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&\dots &0&g_{0}&g_{1}&\dots &g_{r}\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae57b9fd7374e1869943a0f45f100760d42b46ed)
Для каждого кодового слова циклического кода справедливо
.
Поэтому проверочную матрицу можно записать как
![{\displaystyle H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f6251cdccfda030bb6a7b074de05dcbb4910ae5)
Тогда
![{\displaystyle {\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4990a88605c7267b47bfe01f6687073ccd7cb43)
При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий:
![{\displaystyle c(x)=m(x)g(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac4488cc46515e4528e1dc257f57a9c0ec2eab7a)
Оно может быть реализовано при помощи перемножения полиномов.
При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного:
![{\displaystyle c(x)=[s(x)\;m(x)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdb939472559370396eeb0d99388d89dd39dadd5)
Пусть информационное слово образует старшие степени кодового слова, тогда
![{\displaystyle c(x)=x^{r}m(x)+s(x),\quad r=n-k.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3919fcffa254d2413e73e374df5a6c1fb6dbb065)
Тогда из условия
следует
![{\displaystyle s(x)=-x^{r}m(x)\mod g(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd2d8d086ae9422a2b119765b40ace143b63b612)
Это уравнение и задаёт правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров (МЛФ).
В качестве делителя
выберем порождающий полином третьей степени
, тогда полученный код будет иметь длину
, число проверочных символов (степень порождающего полинома)
, число информационных символов
, минимальное расстояние
.
Порождающая матрица кода:
![{\displaystyle G={\begin{bmatrix}1&1&0&1&0&0&0\\0&1&1&0&1&0&0\\0&0&1&1&0&1&0\\0&0&0&1&1&0&1\end{bmatrix}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a9f8103499464f8eeda852aaa3c73e1ba1cb8cf)
где первая строка представляет собой запись полинома
коэффициентами по возрастанию степени.
Остальные строки — циклические сдвиги первой строки.
Проверочная матрица:
![{\displaystyle H={\begin{bmatrix}1&0&0&1&0&1&1\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{bmatrix}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d029978f58ef3ddd87793b4355c1f82785ce487)
где i-й столбец, начиная с 1-го, представляет собой остаток от деления
на полином
, записанный по возрастанию степеней, начиная сверху.
Так, например, 4-й столбец получается
, или в векторной записи
.
Легко убедиться, что
.
В качестве порождающего полинома
можно выбрать произведение двух делителей
:
![{\displaystyle g(x)=g_{1}(x)g_{2}(x)=(x^{4}+x+1)(x^{4}+x^{3}+x^{2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/305bbb92163e6eafe028a38447d3bb37f55004d2)
Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома
со степенью
таким образом:
![{\displaystyle c(x)=m(x)g(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac4488cc46515e4528e1dc257f57a9c0ec2eab7a)
Например, информационному слову
соответствует полином
, тогда кодовое слово
, или в векторном виде
.