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

Циклічним кодом називається лінійний блоковий (n, k) – код, який характеризується властивістю циклічності, тобто зсув вліво на один крок будь-якого дозволеного кодового слова дає також дозволене кодове слово, що належить цьому ж коду і у якого, безліч кодових слів представляється сукупністю багаточленів ступеня (n – 1) і менш, що діляться на деякий багаточлен G(x) ступеня r = n – m, що є співмножником двочлена xn + 1.

Багаточлен G(x) називається таким, що породжує.

Як випливає з визначення, в циклічному коді кодові слова представляються у вигляді багаточленів

де n – довжина коду;

– коефіцієнти з поля GF(q).

Якщо код побудований над полем GF(2), то коефіцієнти приймають значення 0 або 1 і код називається двійковим.

Циклічні коди прості в реалізації і при невисокій надмірності мають хороші властивості виявлення спотворень. Циклічні коди набули дуже широке поширення як в техніці зв’язку, так і в комп’ютерних засобах зберігання інформації. У зарубіжних джерелах циклічні коди звичайно називають перевіркою циклічним надмірним кодом (CRC, Cyclic Redundancy Check).

Розглянемо даний клас кодів докладніше. Як уже згадувалося, назва циклічних кодів пов’язана з тим, що кожна кодова комбінація, одержувана шляхом циклічної перестановки символів, також належить коду. Так, наприклад, циклічні перестановки комбінації 1000101 будуть також кодовими комбінаціями 0001011, 0010110, 0101100 і т.д.

Представлення кодових комбінацій у вигляді багаточленів F(x) дозволяє встановити однозначну відповідність між ними і звести дії над комбінаціями до дії над багаточленами.

Приклад. Якщо кодове слово циклічного коду

,

то відповідний йому багаточлен

.

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

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

Ідея побудови циклічного коду (n, m) зводиться до того, що поліном Q(x), що представляє інформаційну частину кодової комбінації, потрібно перетворити в поліном F(x) стeпенi не більш (n – 1), який без залишку ділиться на поліном G(x) (багаточлен, що не приводиться) ступеня k, що породжує
k = n - m. Розглянемо послідовність операцій побудови циклічного коду.<lt>

Представляємо інформаційну частину кодової комбінації завдовжки m у вигляді полінома Q(x). Для одержання k позицій під контрольні символи умножаємо Q(x) на одночлен xk і одержуємо Q(x)∙xk.

Ділимо поліном Q(x)∙xk на поліном G(x) ступеня k, що породжує, при цьому одержуємо результат розподілу С(x) такого ж ступеня, що і Q(x). </lt>

,

де R(x) - залишок від розподілу Q(x)∙xk на G(x).

Помноживши обидві частини на G(x), одержимо

.

Поліном F(x) ділиться без залишку на G(x), тобто є дозволеною комбінацією циклічного (n, m) - коду.

Приклад циклічного коду (9, 5) з поліномом, що породжує

.

Як інформаційну частину кодової комбінації візьмемо поліном

Q(x)= = 10111.

Множення Q(x) на xk еквівалентне підвищенню ступеня багаточлена на k.
F(x)= Q(x)∙xk = .

Формування перевірочної групи здійснюється в процесі розподілу Q(x)∙xk на G(x).

x8 + x6 + x5 + x4 x4 + x +     0
x8 +     x5 + x4   x4 + x2            
  x6                                      
    x6 + x3 + x2                                
      x3 + x2                                

 

В результаті розподілу одержуємо результат С(x)= x4 + x2 = 10100 і залишок від розподілу R(x)= x3 + x2 = 1100. Для отримання дозволеної кодової комбінації залишок (перевірочна група) поміщається на місце “порожніх” розрядів Q(x)∙xk, тобто F(x)= ® 101111100.

Дана комбінація відправляється в канал зв’язку. Аналогічні операції виконуються для інших інформаційних комбінацій.

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

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

Проте, звичайно в системах зв’язку виправлення помилок при використовуванні циклічних кодів не здійснюється, а при виявленні помилок видається запит на повтор спотвореної помилками комбінації.

Для виправлення пакетів спотворень (три і більш помилки) розроблені коди Файра, Ріда-Соломона та ін. Останні можуть виправляти кілька пакетів помилок.