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

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

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

Введення

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

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

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

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

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

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

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

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

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

Визначення: породжуючим поліномом циклічного ${\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)}$

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

Приклади

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

Як дільник ${\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}$.

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

Як породжуючий поліном ${\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]}$

Див. також

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

Посилання

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