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

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

ВведениеПравить

Пусть $\stackrel{¯<!--\; ¯\; -->}{y}=(y_0,y_1,\dots <!--\; \dots \; -->,y_{n-<!--\; -\; -->1})\in <!--\; \in \; -->L^n$${\overline {y}}=(y_{0},y_{1},\dots ,y_{n-1})\in L^{n}$  — слово длины n над алфавитом из элементов конечного поля $L=GF(q)$$L=GF(q)$  и $y(x)=y_0+y_{1}x+y_2{x}^2+\cdots <!--\; \cdots \; -->+y_{n-<!--\; -\; -->1}{x}^{n-<!--\; -\; -->1}$$y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\dots +y_{n-1}x^{n-1}$  — полином, соответствующий этому слову, от формальной переменной $x$$x$ . Видно, что это соответствие является изоморфизмом линейных пространств. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации $\stackrel{¯<!--\; ¯\; -->}{y}=m_1\stackrel{¯<!--\; ¯\; -->}{y_1}+m_2\stackrel{¯<!--\; ¯\; -->}{y_2}$${\overline {y}}=m_{1}{\overline {y_{1}}}+m_{2}{\overline {y_{2}}}$  пары слов $\stackrel{¯<!--\; ¯\; -->}{y_1}=(y_{1,0},\dots <!--\; \dots \; -->,y_{1,n-<!--\; -\; -->1})$${\overline {y_{1}}}=(y_{1,0},\dots ,y_{1,n-1})$  и $\stackrel{¯<!--\; ¯\; -->}{y_2}=(y_{2,0},\dots <!--\; \dots \; -->,y_{2,n-<!--\; -\; -->1})$${\overline {y_{2}}}=(y_{2,0},\dots ,y_{2,n-1})$ , равен линейной комбинации полиномов этих слов $y(x)=\underset{k=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(m_1{y}_{1k}+m_2{y}_{2k})x^k=m_1\stackrel{¯<!--\; ¯\; -->}{y_1}(x)+m_2\stackrel{¯<!--\; ¯\; -->}{y_2}(x)$${y}(x)=\sum _{k=0}^{n-1}(m_{1}y_{1k}+m_{2}y_{2k})x^{k}=m_{1}{\overline {y_{1}}}(x)+m_{2}{\overline {y_{2}}}(x)$ .

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

Алгебраическое описаниеПравить

Если $\stackrel{\to <!--\; \to \; -->}{c_1}$$\overrightarrow {c_{1}}$  — кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова $\stackrel{\to <!--\; \to \; -->}{c}$$\overrightarrow {c}$ , то соответствующий ему полином $c_1(x)$$c_{1}(x)$  получается из предыдущего умножением на x:

$c_1(x)=xc(x)\mathrm{mod}(x^n-<!--\; -\; -->1)$$c_{1}(x)=xc(x)\mod (x^{n}-1)$ , пользуясь тем, что $x^n\equiv <!--\; \equiv \; -->1\mathrm{mod}(x^n-<!--\; -\; -->1).$$x^{n}\equiv 1\mod (x^{n}-1).$ 

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

$c_j(x)=x^{j}c(x)\mathrm{mod}(x^n-<!--\; -\; -->1),$$c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),$ 

$c_{-<!--\; -\; -->j}(x)x^j=c(x)\mathrm{mod}(x^n-<!--\; -\; -->1).$$c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).$ 

Если $m(x)$$m(x)$  — произвольный полином над полем $GF(q)$$GF(q)$ , и $c(x)$$c(x)$  — кодовое слово циклического $(n,k)$$(n,k)$  кода, то $m(x)c(x)\mathrm{mod}(x^n-<!--\; -\; -->1)$$m(x)c(x)\mod (x^{n}-1)$  — тоже кодовое слово этого кода.

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

Определение

Порождающим полиномом циклического $(n,k)$$(n,k)$  кода $C$$C$  называется такой ненулевой полином $g(x)=\underset{i=0}{\overset{r}{\sum <!--\; \sum \; -->}}{g}_i{x}^i$$g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}$  из $C$$C$ , степень которого наименьшая, и коэффициент при старшей степени $g_r=1$$g_{r}=1$ .

Теорема 1

Если $C$$C$  — циклический $(n,k)$$(n,k)$  код, и $g(x)$$g(x)$  — его порождающий полином, то степень $g(x)$$g(x)$  равна $r=n-<!--\; -\; -->k$$r=n-k$ , и каждое кодовое слово может быть единственным образом представлено в виде

$c(x)=m(x)g(x),$$c(x)=m(x)g(x),$ 

где степень $m(x)$$m(x)$  меньше или равна $k-<!--\; -\; -->1$$k-1$ .

Теорема 2

$g(x)$$g(x)$  — порождающий полином циклического $(n,k)$$(n,k)$  кода — является делителем двучлена $x^n-<!--\; -\; -->1$$x^{n}-1$ .

Следствия

Таким образом, в качестве порождающего полинома можно выбирать любой полином делитель $x^n-<!--\; -\; -->1$$x^{n}-1$ . Степень выбранного полинома будет определять количество проверочных символов $r$$r$ , число информационных символов $k=n-<!--\; -\; -->r$$k=n-r$ .

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

Полиномы $g(x),xg(x),x^{2}g(x),\dots <!--\; \dots \; -->,x^{k-<!--\; -\; -->1}g(x)$$g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)$  линейно независимы, иначе $m(x)g(x)=0$$m(x)g(x)=0$  при ненулевом $m(x)$$m(x)$ , что невозможно.

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

$\stackrel{¯<!--\; ¯\; -->}{m}G=(m_0,m_1,\dots <!--\; \dots \; -->,m_{k-<!--\; -\; -->1})\left[\begin{array}{c}g(x)\\ xg(x)\\ \dots <!--\; \dots \; -->\\ x^{k-<!--\; -\; -->1}g(x)\end{array}\right]=m(x)g(x),$${\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),$ 

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

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

$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}}.$ 

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

Для каждого кодового слова циклического кода справедливо $c(x)=0\mathrm{mod}g(x)$$c(x)=0\mod g(x)$ . Поэтому проверочную матрицу можно записать как

$H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).$ 

Тогда

$\stackrel{¯<!--\; ¯\; -->}{c}{H}^T=\underset{i=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{c}_i{x}^i=0\mathrm{mod}g(x).$${\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).$ 

КодированиеПравить

НесистематическоеПравить

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

$c(x)=m(x)g(x).$$c(x)=m(x)g(x).$ 

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

СистематическоеПравить

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

$c(x)=[s(x)m(x)].$$c(x)=[s(x)\;m(x)].$ 

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

$c(x)=x^{r}m(x)+s(x),r=n-<!--\; -\; -->k.$$c(x)=x^{r}m(x)+s(x),\quad r=n-k.$ 

Тогда из условия $c(x)=x^{r}m(x)+s(x)=0\mathrm{mod}g(x)$$c(x)=x^{r}m(x)+s(x)=0\mod g(x)$  следует

$s(x)=-<!--\; -\; -->x^{r}m(x)\mathrm{mod}g(x).$$s(x)=-x^{r}m(x)\mod g(x).$ 

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

ПримерыПравить

Двоичный (7,4,3) кодПравить

В качестве делителя $x^7-<!--\; -\; -->1$$x^{7}-1$  выберем порождающий полином третьей степени $g(x)=x^3+x+1$$g(x)=x^{3}+x+1$ , тогда полученный код будет иметь длину $n=7$$n=7$ , число проверочных символов (степень порождающего полинома) $r=3$$r = 3$ , число информационных символов $k=4$$k = 4$ , минимальное расстояние $d=3$$d=3$ .

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

$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}},$ 

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

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

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

$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}},$ 

где i-й столбец, начиная с 1-го, представляет собой остаток от деления $x^{i-<!--\; -\; -->1}$$x^{i-1}$  на полином $g(x)$$g(x)$ , записанный по возрастанию степеней, начиная сверху.

Так, например, 4-й столбец получается $h_4(x)=x^3\mathrm{mod}g(x)=x+1$$h_{4}(x)=x^{3}\mod g(x)=x+1$ , или в векторной записи $[110]$$[110]$ .

Легко убедиться, что $G{H}^T=0$$GH^{T}=0$ .

Двоичный (15,7,5) БЧХ кодПравить

В качестве порождающего полинома $g(x)$$g(x)$  можно выбрать произведение двух делителей $x^{15}-<!--\; -\; -->1$$x^{15}-1$ :

$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.$$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.$ 

Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома $m(x)$$m(x)$  со степенью $k-<!--\; -\; -->1$$k-1$  таким образом:

$c(x)=m(x)g(x).$$c(x)=m(x)g(x).$ 

Например, информационному слову $\stackrel{¯<!--\; ¯\; -->}{m}=[1000111]$${\overline {m}}=[1000111]$  соответствует полином $m(x)=x^6+x^5+x^4+1$$m(x)=x^{6}+x^{5}+x^{4}+1$ , тогда кодовое слово $c(x)=(x^6+x^5+x^4+1)(x^8+x^7+x^6+x^4+1)=x^{14}+x^{12}+x^9+x^7+x^5+1$$c(x)=(x^{6}+x^{5}+x^{4}+1)(x^{8}+x^{7}+x^{6}+x^{4}+1)=x^{14}+x^{12}+x^{9}+x^{7}+x^{5}+1$ , или в векторном виде $\stackrel{¯<!--\; ¯\; -->}{c}=[100001010100101]$${\overline {c}}=[100001010100101]$ .

См. такжеПравить

• Обнаружение и исправление ошибок
• Линейный код
• БЧХ код
• Конечное поле
• Многочлен над конечным полем
• Код Рида — Соломона
• Код Хэмминга

СсылкиПравить

• Механизмы контроля целостности данных.