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

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

Назва кодів пішла від їх властивості, яка полягає в тому, що кожна кодова комбінація може бути отримана шляхом циклічної перестановки символів комбінації, що належить до цього ж коду. Це значить, що якщо, наприклад, комбінація а⁰а¹a²...а^п-1 є дозволеною комбінацією циклічного коду, то комбінація а^п-1a⁰a¹a²...a^n-2 також належить цьому кодові.

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

, (5.5)

де a_i – цифри даної системи числення (у двійковій системі 0 і 1).

Найбільший степінь х з ненульовим коефіцієнтом а називається степенем полінома.

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

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

V (х) = = а0 + а1х + а2х2 + ... ап-1х п-1,

то нова комбінація за рахунок циклічного зсуву буде

х · V (х) == а₀x + а₁x² + а₂x³+ ... + a_n-2x^n-1+ a_n-1xⁿ.

Однак в останньому члені необхідно замінити хn на 1. Отже, нова комбінація буде

.

Відповідно до визначення циклічного коду для побудови породжувальної матриці P_{n, k} досить вибрати тільки одну вихідну п-розрядну комбінацію V_i(х). Циклічним зсувом можна одержати (п - 1) різних комбінацій, із котрих будь-які k комбінацій можуть бути взяті як вихідні. Підсумовуючи рядки породжувальної матриці у всіх можливих комбінаціях, можна одержати інші кодові комбінації. Можна показати, що кодові комбінації, одержані з деякої комбінації V_i (х) циклічним зсувом, задовольняють умови, запропоновані до сукупності вихідних комбінацій.

Циклічний зсув комбінації з одиницею в старшому n-му розряді тотожний множенню відповідного многочлена на х з одночасним відніманням від результату многочлена (хⁿ- 1) або (хⁿ + 1), тому що операції здійснюються за модулем два. Отже, якщо як вихідний взяти деякий поліном Р(х), то процес одержання базових поліномів можна подати в такому вигляді:

де C₂, C₃, ..., С_n – коефіцієнти, що приймають значення 1 при Р(х)·х^iі (хⁿ-1) і значення 0 при Р(х)·хⁱ< (хⁿ-1).

При такому способі побудови базових поліномів поліном Р(х) називають утворюючим.

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

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

Таким чином утворюючий поліном Р(х) повинен задовольняти вимогу – він повинен бути дільником двочлена (хⁿ+1). Вибір Р(х) однозначно визначає циклічний код і його коригувальні властивості.

Циклічний (п, А)-код може бути отриманий шляхом множення простого А-значного коду, вираженого у вигляді полінома степеня (k - 1), на деякий утворюючий поліном Р(х) степеня (n - k).

Можлива й інша процедура одержання циклічного коду. Для цього кодова комбінація простого k-значного коду G(х) збільшується на одночлен х^n-k, а потім ділиться на утворюючий поліном Р(х) степеня (п-k). У результаті множення G(х) на х^n-k степінь кожного одночлена, що входить у G(х), підвищиться на (п - k). При діленні добутку х^n-kG(х) на утворюючий поліном Р(х) утвориться частка Q(х) такого ж степеня, як і G(х).

Результат множення і ділення можна подати в такому вигляді:

,

де R(х) – залишок від ділення х^n-kG(х) на Р(х).

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

Таким чином, кодова комбінація циклічного (п, k)-коду може бути отримана двома способами:

1) шляхом множення простої кодової комбінації степеня (k - 1) на одночлен x^n-k і додавання до цього добутку залишку, отриманого від ділення отриманого добутку на утворюючий поліном Р(х) степеня (п - k),

2) шляхом множення простої кодової комбінації степеня (k - 1) на утворюючий поліном Р(х) степеня (п – k).

Згідно з першим способом кодування перших k символів отриманої кодової комбінації збігаються з відповідними символами вихідної простої кодової комбінації.

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

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

Матричне подання циклічних кодів

Для формування рядків породжувальної матриці за першим способом утворення циклічного коду беруть комбінації простого k-розрядного коду G(х), що містять одиницю в одному розряді. Ці комбінації збільшуються на х^n-k, визначається залишок R(х) від ділення отриманого добутку х^n-kG(х) на утворюючий поліном і записується відповідний рядок матриці у вигляді суми добутку х^n-kG(х) і залишку R(х). При цьому породжувальна матриця Р_n,k подається двома підматрицями – інформаційною U_k і додатковою Н_р:

.

Інформаційна підматриця U_k, являє собою квадратну одиничну матрицю з кількістю рядків і стовпців, рівною k. Додаткова підматриця Н_р містить р = п - k стовпців і k рядків і утворена залишками R(х).

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

При другому способі утворення циклічного коду породжувальна матриця P_n,k формується шляхом множення утворюючого полінома Р(х) степеня  = n - k на одночлен x^k-1 наступних k-1 зсувів отриманої комбінації.

Вибір утворюючого полінома

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

Як уже відзначалося раніше, степінь утворюючого полінома повинен дорівнювати числу перевірних розрядів .

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

Найбільше число залишків, що дорівнює 2r-1 (крім нульового), може забезпечити тільки многочлен порядка степеня , що не ділиться ні на який інший многочлен.

Відомо, що двочлен типу (хⁿ + 1) = (х^2z-1 + 1), у розкладанні якого як співмножник повинен входити утворюючий многочлен, має ту властивість, що він є спільним кратним для усіх без винятку незвідних поліномів степеня n і розкладається на множники з усіх незвідних поліномів степеня 2, які діляться без залишку на число z.

Найпростішим циклічним кодом є код, що забезпечує виявлення однократних помилок. Вектору однократної помилки відповідає одночлен xⁱ, степінь котрого i може приймати значення від 1 до п. Для того щоб могла бути виявлена помилка, одночлен xⁱ не повинен ділитися на утворюючий поліном Р(х). Серед незвідних многочленів, що входять у розкладання двочлена хⁿ + 1, є багаточлен найменшого степеня х + 1. Таким чином утворюючим поліномом даного коду є двочлен Р(х) = х + 1. Залишок від ділення будь-якого многочлена на х + 1 може приймати тільки два значення: 0 і 1. Отже, при будь-якому числі інформаційних розрядів необхідний тільки один перевірний розряд. Значення символу цього розряду забезпечує парність числа одиниць у кодовій комбінації.

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

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

.

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

(5.6)

і загальну довжину п кодової комбінації.

Оскільки утворюючий многочлен Р(х) повинен входити як співмножник в розкладання двочлена (хⁿ + 1) = (х^2z-1 + 1), то використовуючи відзначені раніше властивості цього двочлена, а також умову (5.6), можна вибрати утворюючий поліном.

Однак не всякий мнгочлен степеня , що входить у розкладання двочлена хⁿ + 1, може бути використаний як утворюючий поліном. Необхідно, щоб для кожної із п однократних помилок забезпечувався свій, відмінний від інших, залишок від розподілу прийнятої кодової комбінації на утворюючий поліном. Це буде мати місце за умови, якщо обраний незвідний многочлен степеня , будучи дільником двочлена хⁿ + 1, не входить у розкладання ніякого іншого двочлена х^і + 1, степінь якого і< п.

Утворюючі поліноми кодів, які здатні виправляти помилки будь-якої кратності, можна визначати, користуючись таким правилом Хеммінга.

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

2. Розглядаючи отриманий (n, k)-код і некоректуючий n-розрядний код визначають додаткові розряди для забезпечення виправлення однієї помилки в цьому коді і знаходять відповідний утворюючий поліном.

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

Закодувати просту інформаційну групу G(х) = 1011 циклічним кодом, що забезпечує виявлення дворазових або усунення однократних помилок.

Розв’язання. За заданою кількістю інформаційних символів k = 4

визначаємо значність коду. Користуючись співвідношенням (5.6) і табл. 5.1, отримаємо n = 3,2.

Для побудови циклічного коду необхідно вибрати утворюючий поліном Р(х) степеня  = n – k = 3, що повинен входити як співмножник, а для розкладання двочлена хⁿ + 1= х^2z-1 - 1. В нашому випадку цей двочлен має вигляд х⁷+1. Складові його співмножники повинні бути незвідними поліномами, степені яких є дільниками числа z = 3. Отже, співмножниками двочлена х⁷+ 1 повинні бути незвідні поліноми першого і третього степенів. Користуючись таблицями незвідних поліномів отримаємо

.

Вибираємо як утворюючий поліном співмножник

.

Кодування здійснюємо першим способом. Для цього вихідну кодову комбінацію G(х) множимо на x^n-k=x³

.

Визначаємо залишок R(х) від розподілу х^n-k G(х) на утворюючий багаточлен Р(х):

Залишок R(x) = х².

Отже, поліном F(х) циклічного коду буде мати вигляд

.

Отримане повідомлення циклічним кодом Р*(х) = х⁶+ х⁴ + х³ + х². Перевірити декодуванням наявність помилок у прийнятій комбінації, якщо утворюючий поліном Р(х) == х³ + х² +1.

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

.

Залишок від розподілу R(х) = 0. Отже, комбінація прийнята без перекручувань.

Отримана комбінація P*(х) = х⁶ + х⁴ + х² + 1, закодована циклічним кодом. Утворюючий поліном Р(х) = х3 + х2 + 1. Перевірити наявність помилок у кодовій комбінації.

Розв’язання. Ділимо поліном отриманої комбінації на утворюючий поліном

.

залишок – R(х) = х^2№ 0. Отже, комбінація прийнята з помилками.

Побудувати породжувальну матрицю циклічного коду при n = 7;
k = 4. Утворюючий поліном Р(х) = х² + х + 1.

Розв’язання. Оскільки k = 4, інформаційна підматриця має вигляд

.

Для одержання першого рядка додаткової підматриці множимо перший рядок інформаційної підматриці на x³. Ділимо на утворюючий поліном, тобто виконуємо операції . Залишок від цих операцій 011 складає перший рядок додаткової підматриці. Аналогічно визначаємо інші рядки додаткової підматриці. Додаткова підматриця має вигляд:

.

Остаточно одержимо таку породжувальну матрицю:

.

Для побудови породжувальної матриці другим способом перший рядок матриці одержуємо шляхом множення утворюючого полінома на
x^k-1: Р(х)·x^k-1=1011·1000 = 1011000. Наступні рядки матриці отримаємо шляхом циклічного зміщення отриманої комбінації. Таким чином породжувальна матриця

.

5.5.3 Рекурентні коди

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

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

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

Довжина, що виправляється рекурентним кодом пачки помилок l залежить від кроку додавання t і визначається з умови

.

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

.

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

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

Позначаючи послідовність інформаційних символів через a₀a₁a₂...a_2ta_2t+1..., отримаємо таку послідовність перевірних символів для ланцюгового коду: b₀=a₀+a_t; b₁=a₁+a_t+1; .. b_t=a_t+a_2t; b_t+1=a_t+1+a_2t+1... У загальному потоці символів ланцюгового коду між кожними двома інформаційними символами міститься один перевірний

a₀b₀a₁b₁a₂b₂...a_tb_ta_t+1b_t+1...a_2tb_2ta_2t+1b_2t+1...

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

На прийомі інформаційні і перевірні символи розділяються і реєструються незалежно один від одного. З прийнятої послідовності інформаційних символів формуються контрольні символи так само, як формувалися перевірні символи при передачі. Після затримки на величину (3t + 1) кожний сформований контрольний символ звірюється з відповідним прийнятим перевірним символом. У випадку перекручування одного з перевірних символів буде розбіжність відповідних контрольних і перевірних символів. Якщо ж перекручений один з інформаційних символів, то буде розбіжність двох контрольних і відповідних перевірних символів, у формуванні яких бере участь даний інформаційний символ.

З розглянутого принципу виправлення помилок у коді випливає, що правильне виправлення помилок можливо тільки в тому випадку, якщо два з трьох символів, охоплених перевіркою, прийняті правильно. Це виконується за умови, що при кроці додавання t, довжина пачки помилок не більше 2t і перевірні символи передаються в канал із затримкою на (3t+ 1).

Таким чином, код виявляє і виправляє пачки помилок порівняно просто, але ціною великої надмірності.