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

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

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

Введення

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

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

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

$c_1(x)=xc(x)mod(x^n-1)$, користуючись тим, що $x^n\equiv 1mod(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 _{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)$, що неможливо.

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

$\bar{m}G=(m_0,m_1,\dots ,m_{k-1})\left[\begin{array}{c}g(x)\\ xg(x)\\ \dots \\ x^{k-1}g(x)\end{array}\right]=m(x)g(x)$, де $G$ є породжуючою матрицею, $m(x)$ — інформаційним поліномом.

Матрицю $G$ можна записати в символьній формі: $G=\left[\begin{array}{cccccccc}{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{array}\right]$

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

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

$H=\left[\begin{array}{cccccc}1& x& x^2& \dots & x^{n-2}& x^{n-1}\end{array}\right]modg(x)$

Тоді:

$\bar{c}{H}^T=\sum _{i=0}^{n-1}{c}_i{x}^i=0modg(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)=0modg(x)$, слід

$s(x)=-x^{r}m(x)modg(x)$

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

Приклади

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

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

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

$G=\left[\begin{array}{ccccccc}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{array}\right]$,

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

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

$H=\left[\begin{array}{ccccccc}1& 0& 0& 1& 0& 1& 1\\ 0& 1& 0& 1& 1& 1& 0\\ 0& 0& 1& 0& 1& 1& 1\end{array}\right]$,

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

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

Легко переконатися, що $G{H}^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)$.

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

Див. також

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

Посилання

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