2. Способи кодування і декодування циклічних кодів

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

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

Результат множення й ділення можна представити в наступному виді:

(4),

де R(x)- залишок від розподілу · G(x) на Р(х).

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

Множачи обидві частини рівності (4) на Р(х) і роблячи деякі перестановки, одержимо

(5)

У правій частині (5) знак мінус перед R(x) замінений знайомий плюс, тому що вирахування по модулі два зводиться до додавання.

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

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

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

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

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

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

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

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

.

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

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

Нехай, наприклад, необхідно побудувати виробляючу матрицю циклічного коду. Утворюючий поліном .

Інформаційна підматриця має вигляд

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

Остаточно виробляюча підматриця має вигляд

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

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

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

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

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

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

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

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

Наприклад, для коду з = 4 інформаційна підматриця буде мати вигляд

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

Таким чином, додаткова матриця має вигляд

Отже, створюється матриця

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

(1)

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

(2)

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

У таблиці наведене найбільші значення К и n для різних р.

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

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

Розглянемо як приклад спосіб вибору утворюючого полінома для побудови циклічного коду, що містить К = 4 інформаційні символи й забезпечує виправлення однократних помилок.

Відповідно до нерівності визначаємо загальну кількість символів n = 7 і кількість перевірочних символів =3.

Утворюючий поліном Р(х) повинен бути ступеня = 3 і входити як співмножник у розкладанні двочлена Тому що n = 7, то складові співмножники двочлена повинні бути не приводимими поліномами, ступені яких є дільниками числа z = 3. До чисел, на які z = 3 ділиться без залишку, ставляться 1 і 3. Отже, співмножниками двочлена повинні бути не приводимі поліноми, першого й третього ступенів.

.

Жоден зі співмножників ступеня 3 не входить у розкладання іншого двочлена ступеня n < 7. Тому кожний із цих співмножників може бути обраний як утворюючий поліном.

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

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

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

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

Однак код, побудований таким чином, є неоптимальним з погляду числа надлишкових символів. Більш придатний код Боуза – Чоудхурі, що забезпечує мінімальне число перевірочних символів при заданому k. Математична структура цього коду трохи відмінна від розглянутої раніше й характеризується більше складними пристроями для виявлення й виправлення помилок. Особливістю цього коду є те, що для будь-яких позитивних чисел z і існує циклічний код знатності з кодовою відстанню .