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

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

Якщо 00010111 — дійсне ключове слово, застосовуючи правий циклічний зсув, отримаємо рядок 10001011. Якщо код циклічний, то 10001011 — знову дійсне ключове слово. Загалом, застосування правого циклічного зсуву переміщує молодший значущий біт (LSB) в крайнє ліве положення, так що він стає старшим бітом (MSB); інші позиції зсуваються на 1 вправо.

Введення

Нехай ${\overline {y}}=({y_{0}},{y_{1}},\dots ,{y_{n-1}})\in \mathbb {GF} (q^{n})$ — слово довжини n над алфавітом з елементів кінцевого поля $\mathbb {GF} (q)$ та $y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\dots +y_{n-1}x^{n-1}$ — поліном, що відповідає цьому слову, від формальної змінної $x$. Видно, що ця відповідність не просто взаємно однозначна, а й ізоморфна. Оскільки «слова» складаються з літер з поля, то їх можна складати та множити (поелементно), причому результат буде в тому ж полі. Поліном, що відповідає лінійній комбінації ${\overline {y}}=m_{1}{\overline {y_{1}}}+m_{2}{\overline {y_{2}}}$ пари слів ${\overline {y_{1}}}=(y_{1,0},\dots ,y_{1,n-1})$ та ${\overline {y_{2}}}=(y_{2,0},\dots ,y_{2,n-1})$, дорівнює лінійній комбінації поліномів цих слів ${\overline {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 над полем $\mathbb {GF} (q)$.

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

Якщо ${\overrightarrow {c_{1}}}$ — кодове слово, що виходить циклічним зрушенням на один розряд вліво зі слова ${\overrightarrow {c}}$, то відповідний йому поліном $c_{1}(x)$ виходить з попереднього множенням на x:

$c_{1}(x)=xc(x)\mod (x^{n}-1)$, користуючись тим, що $x^{n}\equiv 1\mod (x^{n}-1)$,

Зрушення вправо та вліво відповідно на $j$ розрядів:

$c_{j}(x)=x^{j}c(x)\mod (x^{n}-1)$

$c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1)$

Якщо $m(x)$ — довільний поліном над полем $GF(q)$ та $c(x)$ — кодове слово циклічного $(n,k)$ коду, то $m(x)c(x)$ $\mod (x^{n}-1)$ теж кодове слово цього коду.

Породжуючий поліном

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

Теорема 1

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

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

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

Теорема 2

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

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

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

Поліноми $g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)$ лінійно незалежні, інакше $m(x)g(x)=0$ при ненульовому $m(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$ є породжуючою матрицею, $m(x)$ — інформаційним поліномом.

Матрицю $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\\.&.&\dots &.&.&.&\dots &.\\0&0&\dots &0&g_{0}&g_{1}&\dots &g_{r}\end{bmatrix}}$

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

Для кожного кодового слова циклічного коду справедливо $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)$

Тоді:

${\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)=[s(x)\;m(x)]$

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

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

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

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

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

Приклади

Бінарний (7,4,3) код

Як дільник $x^{7}-1$ виберемо породжуючий поліном третього ступеня $g(x)=x^{3}+x+1$, тоді отриманий код буде мати довжину $n=7$, число перевірочних символів (ступінь породжуючого полінома) $r=3$, число інформаційних символів $k=4$, мінімальна відстань $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)$ коефіцієнтами по зростанню ступеня. Решта рядків — циклічні зрушення першого рядка.

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

$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}$ на поліном $g(x)$, записаний за зростанням ступенів, починаючи зверху.

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

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

Бінарний (15,7,5) БЧХ-код

Як породжуючий поліном $g(x)$ можна вибрати добуток двох дільників $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$.

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

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

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

Див. також

• Виявлення і виправлення помилок
• Лінійний код
• БЧХ код
• Поле Галуа

Посилання

• Механізми контролю цілісності даних