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

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


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_1x + y_2x ^ 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_1y_ {1k} + m_2y_ {2k}) x ^ k = m_1 \ overline {y_1} (x) + m_2 \ overline {y_2} (x)

Це дозволяє розглядати безліч слів довжини n над кінцевим полем як лінійний простір поліномів зі ступенем не вище n-1 над полем \ Mathbb {GF} (q)


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

Якщо \ 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 ^ jc (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) теж кодове слово цього коду.


2.1. Породжує поліном

Визначення породжує поліномом циклічного (N, k) коду C називається такий ненульовий поліном g (x) = \ sum \ limits_ {i = 0} ^ {r} g_ix ^ 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 .


2.2. Породжує матриця

Поліноми g (x), xg (x), x ^ 2g (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}


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

Для кожного кодового слова циклічного коду справедливо 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_ix ^ i = 0 \ mod g (x)

3. Кодування

3.1. Несистематичне

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

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

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

3.2. Систематичне

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

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

c (x) = x ^ rm (x) + s (x), r = n-k

Тоді з умови c (x) = x ^ rm (x) + s (x) = 0 \ mod g (x) , Слід

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

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


4. Приклади

4.1. Двійковий (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 , Або у векторній записи [1 1 0] .

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


4.2. Двійковий (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]