Код із кількістю одиниць у комбінації, кратною трьом

Цей код можна утворити або додаванням до кожної комбі­нації початкового коду r = 2 перевірних елементів, або змен­шенням кількості дозволених комбінацій початкового коду з накладанням додаткової умови: кількість одиниць у кожній комбінації має бути кратною трьом.

У першому випадку до початкової кодової комбінації дода­ються два перевірних розряди, які мають такі значення, що сума одиниць у кодовій комбінації стає кратною трьом. Так, якщо початкова кодова комбінація має дві або п'ять одиниць, то для здобуття ваги w = 3 або 6 кодової комбінації треба доповнити її двома перевірними елементами 10. Якщо ж у початковій ком­бінації є одна або чотири одиниці, то вона доповнюється дво­ма перевірними елементами 11. Так, комбінація 01010 почат­кового коду, закодована кодом із кількістю одиниць, кратною трьом, матиме вигляд 0101010, а 10000 → 1000011, 0110 → n011010, 101100 → 10110000, 110110 → 11011011, 0111011 → 011101110 тощо.

У другому випадку з усіх комбінацій початкового коду ви­бирають тільки ті, які мають вагу w = 3 та 6. Решту комбінацій використовувати не можна.

Код дає змогу виявити всі поодинокі помилки та деякі по­милки більшої кратності, що призводять до порушення умови w = 3 або 6, де w - кількість одиниць у кодовій комбінації. Здатність коду виявляти помилкові комбінації майже така сама, як і коду зі сталою вагою.

Надмірність коду з доповненням до необхідної кількості оди­ниць визначається виразом

 

а коду, що утворюється відбором із загальної кількості комбі­націй з відповідною кількістю одиниць (3 або 6), - виразом

 

 

Коди, що виправляють помилки

Коди, що виправляють помилки (або коректувальні коди) повинні мати мінімальну кодову відстань d_min ≥ 3. Її зростання досягається збільшенням кількості n розрядів коду або зменшенням кількості N _д дозволених кодових комбінацій, які використовуються для передачі по­відомлень, тобто підвищенням надмірності коду.

Найбільшого поширення серед двійкових коректувальних кодів дістали систематичні та несистематичні блокові коди (вони, у свою чергу, поділяються на лінійні та нелінійні), а також ре­курентні коди. З недвійкових кодів для захисту інформації від помилок застосовуються узагальнений код Хеммінга, ланцюговий та іте­ративний коди.

 

Двійкові групові коди

8.1.1 Лінійний систематичний груповий (блоковий код)

Застосувавши теорію лінійних просторів, можна дати таке визначення: лінійним систематичним груповим двійковим (n, k)- кодом називається код, у якого перевірні елементи b_j (де j = 1... r) знаходяться як суми за модулем 2 обумовлених інфор­маційних елементів а_і (де i = 1... k). У нелінійних двійкових (n, k)-кодах перевірні елементи знаходяться інакше.

Таким чином, у лінійному коді перевірні елементи визнача­ються як

(8.1)

де ∑O - знак суми за модулем 2; α_ji - коефіцієнти, значення яких дорівнюють 0 або 1.

Як випливає з (8.1), закон побудови лінійного коду визнача­ється вибором kr коефіцієнтів α_ji.

Одна з властивостей лінійних кодів полягає в тому, що сума за модулем 2 будь-яких двох дозволених кодових комбінацій також є дозволеною комбінацією цього коду.

Нехай є дві дозволені кодові комбінації лінійного коду

перевірні символи яких визначаються відповідно виразами

При додаванні за модулем 2 комбінацій V ⁽¹⁾ і V ⁽²⁾ дістанемо комбінацію V ⁽³⁾, яка також буде комбінацією цього коду:

де

тому що при додаванні за модулем 2 діють асоціативний, ко­мутативний та дистрибутивний закони. Таким чином,

де

або

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

1) кількість початкових кодових комбінацій дорівнювала k, тобто кількості інформаційних елементів первинного коду;

2) всі початкові кодові комбінації були різними;

3) нульова комбінація не входила до складу початкових;

4) всі початкові комбінації були лінійно незалежними;

5) кількість одиниць в кожній початковій комбінації була не меншою ніж d_min;

6) кодова відстань між будь-якими парами початкових ком­бінацій також була не меншою ніж d_тіп.

Підібрані за цим правилом початкові комбінації записують­ся у вигляді твірної матриці G_{(n, k)},яка містить k рядків і n стовпців:

(8.2)

Матрицю (8.2) можна подати також у вигляді двох підматриць: інформаційної Е_k та перевірної С _{(r, k)}. Першу зручно за­писати в канонічній формі як одиничну підматрицю, що має k стовпців і стільки ж рядків:

Перевірна підматриця С _{(r, k)} будується підбором r -розряд­них комбінацій з кількістю одиниць в рядку не меншою від (d_тіп - 1). При цьому необхідно враховувати, що сума за моду­лем 2 будь-яких розрядів повинна мати більш як (d_тіп - 2) оди­ниць.

Ураховуючи викладене, в межах теорії матриць можна дати таке визначення: лінійним систематичним груповим двійко­вим (n, k)- кодом називається код, у якого всі його (2 ^k - 1) ненульові комбінації можуть бути утворені як суми за модулем 2 рядків деякої матриці G _{(n, k)}, розміром k п, яка називається твірною матрицею коду.

Розглянемо приклад побудови матриці систематичного групового коду, здатного виправляти однократну помилку (v _вп = 1) при передачі 16 повідомлень (N _д =16).

Відомо, що N _д = 2^k, звідки k = 4 (N _д= 16 = 2⁴). Отже, кількість рядків твірної матриці G _{(n, k)} дорівнює 4, а кількість стовпців - довжині п коду (n = k + r, де r = 3 для v _вп = 1 і d_тіп = 2 v _вп + 1 = 3), тобто кількість стовпців підматриці G _{(r, k )}становить 3. Кількість перевірних розрядів можна ви­значити, користуючись табл. 8.1.

 

Таблиця 8.1 – Визначення перевірних розрядів

 

dтіп	k

 

Згідно з правилом побудови підматриці C _{(r, k )}кількість одиниць в ній має бути не меншою ніж d_тіп – 1 = 3 - 1 = 2. З триелементних комбінацій для підматриці C _{(r, k )}вибираємо тільки ті, в яких кількість одиниць біль­ша двох: 110, 101, 011, 111.

Через те, що як інформаційна Е_k використовується одинична підматриця, твірна матриця лінійного коду для розглядуваного прикладу, тоб­то коду, який виправляє одну помилку, остаточно має вигляд

(8.3)

Рядки в перевірній підматриці C _{(r, k )}можна міняти місцями. При цьому дістанемо кілька варіантів твірних матриць для прикладу, що розгляда­ється.

Побудуємо за допомогою поданої раніше твірної матриці всі комбіна­ції розглядуваного (7,4)-коду. Оскільки перша комбінація - нульова, дру­га - п'ята комбінації є рядками твірної матриці, решту 11 знайдемо підсу­мовуванням за модулем 2 всіх можливих комбінацій рядків твірної матри­ці. Всі 16 комбінацій (7, 4)-коду з цією матрицею матимуть такий вигляд:

1. 0000000; 9. 0110011 (3 4);

2. 1000011; 10. 0101010 (3 5);

3. 0100101; 11. 0011001 (4 5);

4. 0010110; 12. 1110000 (2 3 4);

5. 0001111; 13. 0111100 (3 4 5);

6. 1100110 (2 3); 14. 1011010 (2 4 5);

7. 1010101 (2 4); 15. 1101001 (2 3 5);

8. 1001100 (2 5); 16. 1111111 (2 3 4 5).

При побудові комбінацій лінійного коду за твірною матри­цею необхідно вміти знаходити перевірні розряди кодових ком­бінацій за інформаційними. Алгоритм утворення перевірних розрядів за допомогою твірної матриці G _{(n, k )}за відомим інфор­маційним має вигляд

Система перевірок для кожної конкретної матриці G _{(n, k)} фор­мулюється так: у першу перевірку разом із перевірним розрядом b ₁входять інформаційні розряди, що відповідають одини­цям першого стовпця підматриці C _{(r, k )};у другу - перевірний розряд b ₂та інформаційні розряди, які відповідають одиницям другого стовпця під матриці C _{(r, k )} і т. д. Кількість перевірок дорівнює кількості перевірних розрядів коду, тобто кількості стовпців під матриці C _{(r, k )}.

Система перевірок для наведеної вище твірної матриці G _{(7, 4)} має вигляд

Опираючись на твірну матрицю, можна побудувати перевір­ну матрицю Н,яка містить r рядків, п стовпців і складається з двох підматриць: D _{(k, r )}, що має k стовпців і r рядків, кожний рядок якої відповідає транспонованому стовпцю перевірних розрядів підматриці C _{(r, k )} твірної матриці G _{(n, k )}; одиничної під­матриці Е_r:

(8.4)

Ця перевірна матриця дає змогу спростити операції кодуван­ня та декодування. Позиції, зайняті одиницями в i -му рядку під­матриці D _{(k, r )},визначають ті інформаційні розряди, які мають брати участь у формуванні i -го перевірного розряду.

Кількість розрядів кодового синдрому і, як наслідок, кіль­кість перевірних елементів при виправленні однократних по­милок визначається нерівністю 2 ^r - 1 ≥ п або 2 ^r - 1 ≥ С ¹ _п. Для виправлення не тільки однократних, а й помилок більшої кра­тності необхідно виконати умову

де v _вп - кратність виправленої помилки.

Як приклад перетворимо твірну матрицю (8.3) на перевірну

(8.5)

Перевірними елементами, що визначаються за допомогою матриці, будуть Повідомлення, наприклад 0110, закодоване таким кодом, матиме вигляд 0110011, оскіль­ки

Методи виправлення помилок у систематичному груповому коді. Розрізняють два основних таких методи: за допомогою кодового синдрому та за допомогою кодів-супутників.

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

Кодові комбінації, що передаються та приймаються, запи­шемо відповідно у вигляді

З метою виявлення помилки в кодовій комбінації, що при­ймається, зробимо перевірки

(8.6)

та порівняємо ці значення зі значеннями прийнятих перевір­них елементів . У результаті порівняння дістанемо r -елементний набір (S ₁,..., S_r),що визначається як сума за модулем 2 двох r -елементних наборів:

(8.7)

Після підстановки (8.6) у (8.7) знайдемо значення кожного елемента S_j. в наборі (8.7):

(8.8)

Набір елементів (S ₁,..., S_r) називається синдромом (пізнавачем) помилок.

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

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

Значення синдрому збігаються з комбінацією результатів перевірки на парність, які визначаються перевірною матрицею Н. Так, синдром для систематичного (7,4)-коду з перевірною матрицею (8.5) визначається виразами де перевірний елемент прийнятої кодової комбінації, - і -йперевірний елемент, обчислений за інформаційними елементами на приймальному боці. Для (7,4)-коду маємо

Якщо значення підставити у вираз S_i, то дістанемо

Установимо відповідність виду синдрому з видом помилки, що виправляється, для перевірної матриці Н (табл. 8.2).

Таблиця 8.2 – Відповідність виду синдрому з видом помилки

Комбінація (вектор) помилки	Номер спотворено-го розряду	Синдром	Комбінація (вектор) помилки	Номер спотвореного розряду	Синдром

 

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

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

Розглянутий вище лінійний систематичний груповий код належить до досконалих кодів. Досконалим лінійним ко­дом називається такий оптимальний за d_тіп лінійний код, у яко­го кількість ненульових комбінацій синдрому (2 ^r - 1)дорівнює кількості всіх можливих комбінацій помилок із вагою v _впй менше, а кожна з (2 ^r - 1)груп із 2 ^k комбінаціями помилок, які утво­рюють ненульові комбінації синдрому, має тільки одну із зазна­чених комбінацій помилок. Так, лінійний (7,4)-код, який зада­ється перевірною матрицею (8,5), є досконалим лінійним кодом, тому що при d_тіп = 3 та здатності виправлення поодиноких по­милок кількість ненульових комбінацій синдрому (2³ - 1 = 7) дорівнює кількості всіх можливих комбінацій однократних помилок (див. табл. 8.2).

Використання кодів-супутників. Цей метод передбачає по­будову кодової таблиці з кодами-супутниками за таким прави­лом (табл. 8.3): в першому її рядку розташовують усі кодові комбінації V_і, для яких необхідно знайти коди-супутники; в другому рядку записують вектори, утворені підсумовуванням за модулем 2 кодових комбінацій V_і з вектором помилки е ₁, вага якого w = 1, а одиниця знаходиться в першому розряді; третій рядок є результатом підсумовування за модулем 2 кодових ком­бінацій V_і з вектором e ₂,вага якого w = 1, а одиниця розміщу­ється в другому розряді, і т. д. Так діють доти, доки не будуть підсумовані з кодовими комбінаціями V_і всі вектори е_і вагою w = 1 з одиницями в кожному з п розрядів, потім підсумовують за модулем 2 вектори е_і вагою w = 2 з послідовним перекриван­ням усіх можливих розрядів (вага векторів е_і визначає кількість помилок, що виправляються, а розрядність цих векторів відпо­відає розрядності кодової комбінації).

Таким чином, для кожної кодової комбінації V_і лінійного систематичного коду дістають свою групу кодів-супутників, розташованих у відповідному стовпці (див. табл. 8.3), які збе­рігаються в пам'яті ЕОМ. У разі приймання комбінації, що збі­гається з одним із кодів-супутників, спотворена комбінація розшифровується як початкова робоча комбінація, до якої на­лежить цей код-супутник.

 

Таблиця 8.3 – Відповідність кодової комбінації систематичного коду групі кодів-супутників

ei	Vi
V 1	V 2	V 3	…	V (2 ^k -1)
e 1 e 2 - - - e (2 ^n -1)	e 1 V 1 e 2 V 1 - - - e (2 ^n -1) V 1	e 1 V 2 e 2 V 2 - - - e (2 ^n -1) V 2	e 1 V 3 e 2 V 3 - - - e (2 ^n -1) V 3	… … - - - …	e 1 V (2 ^k -1) e 2 V (2 ^k -1) - - - e (2 ^n -1) V (2 ^k -1)

 

Недоліками розглянутого методу є велика ємність пам'яті ЕОМ і значні затрати часу на перебір комбінацій кодів-супут­ників.

Укорочені лінійні систематичні коди. Розрізняють повні та вкорочені лінійні систематичні коди. До перших належать лі­нійні (n, k)-коди, що містять 2 ^k комбінацій, а до других - лінійні (п, k, i)-коди (де і = 1... k - 1), які мають 2 ^{k -1}комбінацій. Укоро­чений лінійний систематичний код утворюють з повного коду, при цьому дістають кодову відстань d_тіп, не меншу ніж у початкового лінійного систематичного коду зі збереженням такої самої кількості перевірних елементів, тобто r = (n - і) - (k - і) = n - k.

Здобуття вкороченого лінійного систематичного коду ґрун­тується на тому, що оскільки з загальної кількості 2 ^k комбіна­цій первинного коду, які потрібно закодувати лінійним систе­матичним кодом, 2 ^{k -1} комбінацій починаються з 0, а 2 ^{k -1} - з 1, після кодування лінійного (n, k)-коду 2 ^{k -1} його комбінацій та­кож починатимуться з 0.

Ці 2 ^{k -1} комбінацій розглядатимемо як новий лінійний систе­матичний код. Тоді, через те що вони належать початковому (n, k)-коду, кодова відстань d_тіп нового коду буде не меншою, ніж початкового. Нульовий символ на початку кодової комбінації зберігається й після кодування її лінійним (n, k)-кодом, причому в утворенні перевірних елементів лінійного систематичного ко­ду участі він не бере. З урахуванням цього нульовий символ мож­на відкинути. При цьому дістанемо лінійний (n -1, k - 1)-код, тобто код, що містить п - 1 елементів, з яких k - 1 є інформацій­ними, а r - перевірними.

Укорочений лінійний систематичний код легко дістати з пов­ного лінійного (n, k)-коду, що подається у вигляді твірної матри­ці G _{(n, k )} розміром k n виду (8.2) виключенням з матриці пер­ших рядка та стовпця. В результаті дістанемо твірну матрицю G _{(n-1, k -1)} нового вкороченого лінійного систематичного коду розміром (k - 1) (n - 1), що утворює 2 ^{k -1} його комбінацій. Для здобуття перевірної матриці H _{(n-1, r )} цього коду досить виклю­чити перший стовпець із матриці H _{(n, r )} відповідного повного коду.

Так, твірну й перевірну матриці вкороченого лінійного сис­тематичного (6, 3)-коду можна дістати з відповідних матриць G _{(7, 4)} (8.3) та H _{(7, 3)} (8.5) повного коду:

(8.9)

Після вкорочення на один символ лінійного систематичного (n -1, k - 1)- коду здобудемо вкорочений (n -2, k - 1)- код і т. д.

Коди Хеммінга

Це одні з найпоширеніших систематичних кодів, які виправ­ляють помилки. До кодів Хеммінга належать коди з мінімаль­ною кодовою відстанню d_тіп = 3, що виправляють всі пооди­нокі помилки.

Формування r перевірних елементів у комбінаціях цих кодів виконують за k інформаційними елементами. Таким чином, довжина кодової комбінації n = k + r. Перевірними елементами є лінійні комбінації інформаційних елементів, тобто зважені суми інформаційних елементів з ваговими коефіцієнтами 1 та 0.

Послідовність одиниць і нулів у кодовій комбінації назива­ється ще кодовим вектором. Кодам Хеммінга притаманні влас­тивості лінійних кодів: сума (різниця) векторів лінійного коду дає вектор, який належить цьому коду; лінійні коди утворюють алгебричну групу відносно операції додавання за модулем 2; мінімальна кодова відстань між векторами групового коду дорівнює мінімальній вазі ненульових кодових векторів.

При передачі кодового вектора може бути спотворений будь-який елемент, кількість таких ситуацій . До цього слід додати ще одну ситуацію, коли помилка не виникає. Таким чином, загальна кількість 2 ^r комбінацій перевірних елементів має перевищувати кількість можливих помилкових ситуацій в коді з урахуванням відсутності помилок для правильного роз­різнення їх і визначення місць помилки:

2 ^r ≥ n + 1. (8.10)

Оскільки 2 ⁿ = 2 ^k+r = 2 ^k · 2 ^r, можна записати

2 ⁿ ≥ (n + 1) · 2 ^k, (8.11)

де 2 ⁿ - повна кількість комбінацій коду.

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

2 ⁿ - 1 = n.

Для розрахунку основних параметрів кодів Хеммінга мож­на задати кількість перевірних елементів r; тоді з останнього виразу визначається n, а кількість інформаційних елементів k = n - r. Співвідношення між r, n, k для кодів Хеммінга наведе­мо в табл. 8.4.

Таблиця 8.4 – Співвідношення r, n, k для кодів Хеммінга

k

r

n

 

Характерна особливість перевірної матриці коду з d_тіп = 3 полягає у тому, що її стовпці є різними ненульовими комбінаціями завдовжки r. Наприклад, при r = 4, п = 15 перевірна мат­риця (15, 11)-коду може мати такий вигляд:

(8.12)

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

Після переставлення стовпців, які мають одну одиницю, ма­триця (8.12) набуває вигляду

(8.13)

Згідно з матрицею (8.13) дістаємо систему перевірних рівнянь, за допомогою яких знаходимо перевірні розряди:

(8.14)

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

Так, якщо помилка виникла в сьомому інформаційному роз­ряді (спотвореним є елемент а ₇), то не виконуються перше, тре­тє та четверте співвідношення (8.14), тобто синдром дорівнює 1011 [збігається з сьомим стовпцем матриці Н (8.13)]. Таким чином, місцезнаходження стовпця матриці Н, що збігається зі знайденим синдромом, визначає місце помилки.

Обчислене значення синдрому обов'язково збігається з одним із стовпців матриці Н,тому що як стовпці вибираються всі мож­ливі r -розрядні двійкові комбінації. Р. Хеммінг запропонував розташувати стовпці перевірної матриці так, щоб номер і -го стовпця матриці Н і номер розряду кодової комбінації від­повідали двійковому поданню числа і. Тоді синдром, знайде­ний з перевірних рівнянь, буде двійковим поданням номера розряду кодової комбінації, в якій виникла помилка. Для цьо­го перевірні розряди мають знаходитися не в кінці кодової ком­бінації, а на номерах позицій, які подаються степенем двійки (2⁰, 2¹, 2², 2³,...,2 ^{r -1}), як у матриці (8.12), тому що кожний з них входить тільки до одного з перевірних рівнянь. В останньому випадку перевірні розряди розміщуються між інформацій­ними.

Синдром відповідно до перевірної матриці (8.12) визнача­ється з системи рівнянь

(8.15)

Як перевірні вибираються розряди и ₁, и ₂, и ₄та и ₈ що зустрі­чаються в системі рівнянь (8.15) по одному разу.

Наприклад, якщо необхідно закодувати повідомлення 11001010110 двійкового простого коду (k = 11) у коді Хеммінга, то потрібно визначи­ти перевірні розряди в комбінації u ₁ u ₂1 u ₄100 u ₈1010110.

З перевірної матриці (8.12) маємо

(8.16)

Обчислюючи и ₁, и ₂, и ₄та и ₈згідно з (8.16), дістаємо

Отже, комбінація коду Хеммінга для розглядуваного повідомлення матиме вигляд 111110001010110.

Тепер припустимо, що шостий елемент цієї комбінації приймається помилково, тобто одержано повідомлення 111111001010110. Обчислю­ючи синдром за допомогою системи рівнянь (8.15), знаходимо S ₁ = 0; S ₂= 1; S ₃ = 1; S ₄ = 0, тобто синдром має вигляд 0110. Якщо це двійкове число перевести в десяткове, то дістанемо 6(0 · 2³ + 1 ·2² + 1 · 2¹ + 0 · 2⁰ = 6).Таким чином, необхідно виправити шостий розряд повідомлення, що надійшло.

 

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

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

Лінійні систематичні (n, k)-коди, в яких циклічний зсув a_{n -2}, a_{n -3}, a_{n -4}, …, a ₂, a ₁, a ₀, a_{n -1} дозволеної комбінації a_{n -1}, a_{n -2}, a_{n -3}, …, a ₁, a ₀ також є дозволеною комбінацією, що належить цьому коду, називаються циклічними. Така циклічна перестановка елементів виникає після множення полінома на х. Якщо V (x) = a_{n -1} x^{n -1} + a_{n -2} x^{n -2} + … + a ₁ x + a ₀, то xV (x) = a_{n -1} xⁿ + a_{n -2} x^{n -1} +… … + + a ₁ x ² + a ₀ x. Щоб степінь полінома не перевищував n – 1, член a_{n -1} xⁿ замінюється одиницею. Тому

xV (x) = F (x) = a_{n -2} x^{n -1} + … + a ₁ x ² + a ₀ x + a_{n -1}.

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

Як твірні поліноми різних циклічних кодів можуть бути застосовані всі незвідні поліноми та добутки їх, тому що вони також є дільниками двочлена xⁿ + 1.

З урахуванням викладеного можна дати ще одне визначення двійкового циклічного коду: циклічним називається лінійний двійковий систематичний (n, k)-код, всі 2 ^k комбінацій якого подано поліномами степеня х – 1 і менше, що діляться на деякий поліном Р (х) степеня r = n – k, який є дільником двочлена xⁿ + 1. Деякі твірні поліноми наведено в табл. 8.5.

 

Таблиця 8.5 – Твірні поліноми циклічних кодів

r	Твірний поліном Р (х)	Двійковий запис полінома
	х + 1 х ^2 + х + 1 х ^3 + х + 1 х ^3 + х ^2 + 1 х ^4 + х + 1 х ^4 + х ^3 + 1 х ^4 + х ^3 + х ^2 + х + 1 х ^5 + х ^2 + 1 х ^5 + х ^3 + 1 х ^5 + х ^3 + х ^2 + х + 1 х ^5 + х ^4 + х ^2 + х + 1 х ^6 + х ^5 + х ^4 + 1 х ^8 + х ^7 + х ^6 + х ^5 + х ^2 + х ^1 + х + 1 х ^9 + х ^5 + х ^3 + 1 х ^15 + х ^14 + х ^13 + х ^12 + х ^4 + х ^3 + х ^2 + х + 1 х ^16 + х ^12 + х ^5 + 1

 

Розрізняють алгебричні та матричні методи побудови циклічного коду. Побудова дозволеної кодової комбінації (алгоритм кодування) перших зводиться ось до чого:

- подати інформаційну частину з k елементів у вигляді полінома Q (x) степеня k -1;

- помножити Q (x) на x^r що еквівалентно зсуву k -розрядної кодової комбінації на r розрядів);

- поділити поліном x^r Q (x) на вибраний твірний поліном P (x), степінь якого дорівнює r, і визначити остачу від ділення R (x), тобто

(8.17)

де С (х) – частка від ділення, яка має той самий степінь, що й поліном Q (x); R (x) – остача від ділення, яка має степінь, не більший від r – 1 [менший, ніж степінь дільника P (x)].

Зазначимо, що r розрядів остачі є r перевіреними елементами кодової комбінації, причому

(8.18)

або

(8.19)

де F (x) – комбінація циклічного коду.

З виразу (8.19) випливають два рівноцінних алгебричних методи побудови комбінацій циклічного коду:

(8.20)

(8.21)

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

(8.22)

У комбінаціях циклічних кодів, побудованих за першим і другим методами [див. вирази (8.20) і (8.21)], розташування інформаційних і перевірних елементів підпорядковується такому правилу: k старших розрядів комбінації є інформаційними, решта n – k = r розрядів – перевірними.

При використанні третього методу побудови циклічних кодів [див. вираз (8.22)] дістають комбінації неподільного циклічного коду, в яких інформаційні та перевірні елементи не відокремлені один від одного, що ускладнює процес декодування. Тому на практиці найпоширенішими є перші два алгебричні методи побудови циклічного коду.

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

Розрізняють два матричних методи побудови циклічного коду на основі твірної матриці G _ц. Перший з них ґрунтується на вже відомому виразі (8.17). Відповідний рядок твірної матриці G _ц записується у вигляді При цьому вся матриця розбивається на дві під матриці, як і в лінійному систематичному груповому коді: , де - транспонована одинична інформаційна під матриця; - перевірна під матриця з кількістю стовпців r і рядків k, що утворюється остачами від ділення R_i (x). Такий метод дає можливість дістати твірну матрицю в канонічному вигляді.

Для побудови твірної матриці (формування її рядків) беруть не довільні комбінації Q (x) двійкового простого коду, а тільки ті з них, які містять одиницю в одному розряді Q_i (x), де i = 1, 2, …, k. Ці комбінації множать на x^r і знаходять остачу від ділення Q_i (x) x^r / P (x), що дорівнює R_i (x).

Так, для циклічного (7, 4)-коду з п = 7, k = 4 і твірним поліно­мом Р (х) = = х ³ + х ² + 1, щоб побудувати твірну матрицю, виби­рають чотириелементні одиничні комбінації Q_i, двійкового про­стого коду: Q ₁(х)= 1 (0001); Q ₂(х) = х (0010); Q ₃(x) = х ²(0100); Q ₄(х) = x ³(1000). Вибрані комбінації Q_i (х)множать на x ³ (r = п – k = 7 - 4 = 3),ділять на Р (х) = х ³ + х ² + 1 і знаходять остачі:

Таким чином, твірна матриця для розглядуваного прикладу матиме вигляд

(8.23)

Твірна матриця має змогу дістати k комбінацій коду. Решту 2 ^k - k - 1 комбінацій, крім нульової, знаходять додаванням за модулем 2 рядків твірної матриці в усіх можливих сполучен­нях. Остання комбін