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

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

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

Примітка 8.1. На відміну від звичайного ділення, при формуванні та декодуванні циклічного коду операція віднімання замінюється на додавання за модулем 2. При цьому умовою можливості додавання за модулем 2 дільника (утворюючого полінома) до діленого є наявність в співставлених старших розрядах ненульового значення, а не перевищення абсолютного значення діленого над дільником чи їх рівність. Наприклад, якщо розряди діленого мають значення 1000, а в якості утворюючого використовується многочлен 1101, то операція додавання за модулем 2 цих значень в процесі ділення повинна виконуватися і залишок від її виконання буде дорівнювати 101.

Многочлени можуть бути записані у вигляді комбінації двійкового коду або математичним виразом. Для перетворення двійкового коду в математичний вираз необхідно записати цей код як суму окремих його розрядів помножених на х в ступені, що відповідає ступеню двійки для відповідного розряду. Спрощення виразу дозволяє досягти бажаного результату.

Приклад 8.1. Представити комбінацію двійкового коду 110101 у вигляді многочлена.

Розв’язок.

Згідно з наведеним правилом в результаті перетворення отримуємо:

К(х)=1х⁵+1х⁴+0х³+1х²+0х¹+1х⁰=1х⁵+1х⁴+1х²+1х⁰=х⁵+х⁴+х²+1

Циклічний код повідомлення можна отримати множенням його значення на утворюючий поліном.

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

Приклад 8.2. Сформувати методом множення поліномів циклічний код повідомлення 1101. В якості утворюючого використати поліном 1011.

Розв’язок.

_* 1 1 0 1

1 0 1 1

_ 1 1 0 1

_ 1 1 0 1

1 1 0 1 ,

1 1 1 1 1 1 1

Циклічний код повідомлення 1101, сформований методом множення поліномів, має вигляд 1111111.

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

Для формування методом ділення поліномів циклічного коду многочлена U(х) за допомогою утворюючого многочлена К(х) слід виконати наступну послідовність дій:

1. многочлен U(х) множиться на одночлен хⁿ, де n дорівнює ступеню многочлена К(х) (в прикладі 8.1 ступінь К(х) дорівнює 5). Операція множення на одночлен фактично призводить до додавання в молодші розряди двійкового коду многочлена U(х) нулів в кількості, яка дорівнює ступеню одночлена;

2. виконується ділення отриманого многочлена U(х)*хⁿ на утворючий многочлен К(х) до отримання залишку Q(х), ступінь якого менший ступеня утворюючого многочлена К(х);

3. виконується операція додавання за модулем 2 многочлену U(х)*хⁿ та залишку Q(х) (фактично на місце доданих в результаті виконання операції U(х)*хⁿ нулів записується n розрядів залишку, які і є контрольними).

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

Приклад 8.3. Сформувати методом ділення поліномів циклічний код повідомлення, представленого многочленом U(х)=х³+х²+1. В якості утворюючого використати многочлен К(х)= х³+х+1.

Розв’язок.

Ступінь n утворюючого поліному К(х)=х³+х+1 дорівнює трьом, тобто многочлен U(х) необхідно помножити на одночлен хⁿ=х³.

U(х)*х³=х³*(х³+х²+1)=х⁶+х⁵+х³

Виконаємо ділення U(х)* х³ на К(х).

х⁶+х⁵+0+х³+0+0+0 х³+х+1

х⁶+0+х⁴+х³ х³+х²+х+1

х⁵+х⁴+0+0 

х⁵+0+х³+х² частка (в формуванні коду

х⁴+х³+х²+0 участі не приймає)

х⁴+0+х²+х¹

х³+0+х+0

х³+0+х+1

1  залишок

Таким чином, закодоване повідомлення буде мати вигляд х⁶+х⁵+0+х³+0+0+1 або х⁶+х⁵+х³+1, що дорівнює двійковому значенню 1101001.

Для перевірки виконаємо формування циклічного коду в двійкових значеннях.

U(х)=х³+х²+1=1101

К(х)=х³+х+1=1011

U(х)*х³=х³*(х³+х²+1)=1101000

Виконаємо ділення U(х)* х³ на К(х).

1 1 0 1 0 0 0 1 0 1 1

1 0 1 1 1 1 1 1

1 1 0 0 

1 0 1 1 частка (в формуванні коду

1 1 1 0 участі не приймає)

1 0 1 1

1 0 1 0

1 0 1 1

1  залишок

Таким чином закодоване повідомлення буде мати вигляд 1101001.

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

Приклад 8.4. Перевірити на наявність помилки прийняте повідомлення 1001001, якщо воно закодоване циклічним кодом з використанням утворюючого полінома 1011.

Розв’язок.

Для перевірки повідомлення на наявність помилки виконаємо його ділення на утворюючий поліном.

1 0 0 1 0 0 1 1 0 1 1

1 0 1 1 1 0 1 0

1 0 0 0

1 0 1 1

1 1 1  залишок

В результаті ділення закодованого циклічним кодом повідомлення на утворюючий поліном було отримано відмінний від нуля залишок. Це свідчить про наявність помилки в прийнятому повідомленні.

Якщо в процесі перевірки встановлюється факт наявності помилки в повідомленні, закодованому циклічним кодом, який дозволяє корегувати помилки кратності S, то виправлення помилок (при цьому кількість помилок не повинна перевищувати S) виконується за наступними правилами:

1. підраховується кількість одиниць в залишку від ділення повідомлення, що декодуэться, на утворюючий поліном. Отримане число визначається як вага залишку і позначається символом W;

2. якщо W>S, то виконується циклічний зсув повідомлення вліво на 1 розряд, після чого зсунуте повідомлення повторно ділиться на утворюючий поліном;

3. виконання пунктів 1 та 2 повторюється до отримання залишку, який задовольняє вимозі WS;

4. якщо отриманий залишок задовольняє вимозі WS, він додається за модулем 2 до поточного значення повідомлення;

5. отримане в результаті виконання пункту 4 повідомлення зсувається вправо циклічним зсувом стільки разів, скільки разів виконувався зсув вправо згідно з пунктом 2.

Приклад 8.5. В результаті ділення закодованого циклічним кодом повідомлення 1001001 на утворюючий поліном 1011 було отримано залишок 111 (див. приклад 8.4). Виконати корегування помилки в отриманому повідомленні, якщо відомо, що утворюючий поліном 1011 дозволяє отримувати семирозрядний циклічний код, здатний виправляти одну помилку.

Розв’язок.

Циклічний код здатний виправляти одну помилку, тобто для нього S=1. Підрахування кількості одиниць в залишку 111 дозволяє визначити його вагу W=3. Оскільки W>S, виконуємо циклічний зсув отриманого повідомлення на один розряд вліво і ділення отриманого результату на утворюючий поліном.

0 0 1 0 0 1 1 1 0 1 1

1 0 1 1 0 0 1 0

1 0 1  залишок

В результаті ділення закодованого циклічним кодом повідомлення на утворюючий поліном було отримано залишок 101, тобто W=2. Оскільки W>S, виконуємо повторний циклічний зсув отриманого повідомлення на один розряд вліво і ділення отриманого результату на утворюючий поліном.

0 1 0 0 1 1 0 1 0 1 1

1 0 1 1 0 1 0 1

1 0 1 0

1 0 1 1

1  залишок

Отриманий залишок дорівнює 1, тобто W=1. Оскільки W=S, виконуємо додавання за модулем 2 поточного значення повідомлення з отриманим залишком.

0. 1 0 0 1 1 0

1

0 1 0 0 1 1 1

Оскільки в процесі пошуку помилки було виконано 2 циклічних зсуви повідомлення вліво, виконуємо два циклічних зсуви отриманого значення вправо. Отримуємо результат 1101001, який і є вірним циклічним кодом повідомлення (див. приклад 8.3 та приклад 8.4).

Зазначимо, що для отримання циклічного коду, який здатний виправляти S помилок, ступінь обраного утворюючого полінома К(х) повинний бути не менший необхідної кількості контрольних розрядів n_k (див. формули (5.5)-(5.8)), а кількість одиниць в утворюючому поліномі К(х) повинна бути не меншою від необхідної для корегування S помилок мінімальної кодової відстані (формула (5.2)). При цьому розрядність утворюючого поліному слід обирати мінімальною з можливих, щоб не збільшувати надлишковість повідомлень.