Циклічний код

Визначення: породжуючим поліномом циклічного ${\displaystyle (n,k)}$ коду ${\displaystyle C}$ називається такий ненульовий поліном ${\displaystyle g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}}$ з ${\displaystyle C}$, ступінь якого найменша та коефіцієнт при старшому ступені ${\displaystyle g_{r}=1}$.

Теорема 1

Якщо ${\displaystyle C}$ — циклічний ${\displaystyle (n,k)}$ код і ${\displaystyle g(x)}$ — його породжуючий поліном, тоді ступінь ${\displaystyle g(x)}$ дорівнює ${\displaystyle r=n-k}$ та кожне кодове слово може бути єдиним чином представлено у вигляді

${\displaystyle c(x)=m(x)g(x)}$,

де ступінь ${\displaystyle m(x)}$ менше або дорівнює ${\displaystyle k-1}$.

Теорема 2

${\displaystyle g(x)}$ — породжуючий поліном циклічного ${\displaystyle (n,k)}$ коду є дільником двочлена ${\displaystyle x^{n}-1}$

Наслідки: таким чином як породжуючий поліном можна вибирати будь-який поліном, дільник ${\displaystyle x^{n}-1}$. Ступінь обраного полінома визначатиме кількість перевірочних символів ${\displaystyle r}$, число інформаційних символів ${\displaystyle k=n-r}$.

Поліноми ${\displaystyle g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)}$ лінійно незалежні, інакше ${\displaystyle m(x)g(x)=0}$ при ненульовому ${\displaystyle m(x)}$, що неможливо.

Значить кодові слова можна записувати, як і для лінійних кодів, таким чином:

${\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)}$, де ${\displaystyle G}$ є породжуючою матрицею, ${\displaystyle m(x)}$ — інформаційним поліномом.

Матрицю ${\displaystyle G}$ можна записати в символьній формі: ${\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\\.&.&\dots &.&.&.&\dots &.\\0&0&\dots &0&g_{0}&g_{1}&\dots &g_{r}\end{bmatrix}}}$

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

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

Тоді:

${\displaystyle {\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x)}$

При несистематичному кодуванні кодове слово виходить у вигляді добутку інформаційного полінома на породжуючий

${\displaystyle c(x)=m(x)g(x)}$.

Воно може бути реалізовано за допомогою перемноження поліномів.

При систематичному кодуванні кодове слово формується у вигляді інформаційного подблока та перевірочного ${\displaystyle c(x)=[s(x)\;m(x)]}$

Нехай інформаційне слово утворює старші ступені кодового слова, тоді

${\displaystyle c(x)=x^{r}m(x)+s(x),r=n-k}$

Тоді з умови ${\displaystyle c(x)=x^{r}m(x)+s(x)=0\mod g(x)}$, слід

${\displaystyle s(x)=-x^{r}m(x)\mod g(x)}$

Це рівняння задає правило систематичного кодування. Воно може бути реалізовано за допомогою багатотактних лінійних фільтрів(БЛФ).

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

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

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

де перший рядок є записом полінома ${\displaystyle g(x)}$ коефіцієнтами по зростанню ступеня. Решта рядків — циклічні зрушення першого рядка.

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

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

де i-ий стовпець, починаючи з 1-го, являє собою залишок від ділення ${\displaystyle x^{i}}$ на поліном ${\displaystyle g(x)}$, записаний за зростанням ступенів, починаючи зверху.

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

Легко переконатися, що ${\displaystyle GH^{T}=0}$.

Як породжуючий поліном ${\displaystyle g(x)}$ можна вибрати добуток двох дільників ${\displaystyle x^{15}-1}$:

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

Тоді кожне кодове слово можна отримати за допомогою добутку інформаційного полінома ${\displaystyle m(x)}$ зі ступенем ${\displaystyle k-1}$ таким чином:

${\displaystyle c(x)=m(x)g(x)}$.

Наприклад, інформаційному слову ${\displaystyle {\overline {m}}=[1000111]}$ відповідає поліном ${\displaystyle m(x)=x^{6}+x^{5}+x^{4}+1}$, тоді кодове слово ${\displaystyle 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}$, або у векторному вигляді ${\displaystyle {\overline {c}}=[1000010101001010]}$