Лекція 6 циклічні коди

Мета – вивчення методів побудови циклічних кодів, алгоритм кодування, представлення комбінацій циклічних кодів у вигляді двійкових поліномів, операції над двійковими поліномами.

В лекції розглянуті наступні питання:

1. Основні властивості циклічних кодів і способи їх математичного опису.

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

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

1. Основні властивості циклічного коду й способи побудови

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

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

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

(1)

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

Так, наприклад, двійкове семи розрядне число 1010101 може бути записане у вигляді полінома

(2)

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

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

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

.

Однак в останньому виразі треба замінити на 1 і перемістити цей член на останню позицію.

Отже нова комбінація буде

.

Наприклад, циклічне зрушення кодової комбінації 1010101 може бути отриманий шляхом множення полінома (2) на х

.

Замінивши на 1, одержимо поліном

.

Відповідної кодової комбінації 0101011.

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

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

(3),

де -коефіцієнти, що приймають значення 1 при й значення 0 при .

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

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

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

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