Основні параметри корегуючих кодів

Завадостійке кодування. Циклічні коди

Теорія інформації та кодування

Вступ

Лекція № 4.5 − “ Завадостійке кодування. Циклічні коди ”. В лекції будуть розглянуті наступні учбові питання:

1. Основні параметри корегуючих кодів. 3

2. Циклічні коди. 7

3. Властивості циклічних кодів. 14

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

Значність (довжина) коду показує загальну кількість символів у базовому кодовому слові n та їх розподіл між інформаційними m і надлишковими символами k так, що n = m + k.

Надмірність корегуючого коду може бути абсолютною і відносною. Під абсолютною надмірністю розуміють число додаткових розрядів, що вводяться
k = n - m.

Відносною надмірністю корегуючого коду називають величину

.

Звідси можна визначити наступну характеристику – відносну швидкість коду:

.

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

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

,

оскільки в послідовності з n символів тільки m інформаційних.

Якщо число спотворень, яке потрібне знайти або виправити, є значним, необхідно мати код з великим числом перевірочних символів. Швидкість передачі інформації при цьому буде зменшена, оскільки з’являється часова затримка інформації. Вона тим більше, чим складніше кодування.

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

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

Кодова відстань може бути різною. Так, в первинному натуральному безнадмірному коді ця відстань для різних комбінацій може розрізнятися від одиниці до n, тобто може бути рівною значності коду.

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

У безнадмірному коді всі комбінації є дозволеними, = 1. Достатньо тільки спотворитися одному символу, і буде помилка в повідомленні.

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

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

Спотворення можна не тільки знаходити, але і виправляти.

У загальному випадку кратність спотворень, що виправляються, пов’язана з кодовою відстанню співвідношенням

= 2+1.

Для орієнтовного визначення необхідної надмірності коду можна скористатися уже відомою нам верхньою граничною оцінкою для k = n - m, що, як уже було показано, визначається із виразу:

k = n – m ≥ ,

де – поєднання з n елементів по t (число можливих помилок кратності t на довжині n -розрядної комбінації).

Якщо, наприклад, n = 7, =1, то

.

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

Важливими показниками коду є ймовірність виявлення Р_в і невиявлення Р_нв спотворень, під якими розуміють відношення числа спотворень, що знаходяться (що не знаходяться), до числа всіх можливих спотворень. Спотворення не виявляються, коли передана кодова комбінація перетвориться в іншу дозволену. Число всіх дозволених комбінацій при m інформаційних розрядах дорівнює 2 ^m.

Із цієї множини одна комбінація є вірною, тобто при передачі якої-небудь кодової комбінації можливе число випадків невиявлення спотворень буде рівним

N _нв = 2 ^m –1. (1)

Оскільки число всіх можливих варіантів спотворень дорівнює 2 ⁿ, де n - кількість розрядів в кодовій комбінації, той вираз для визначення величини Р_нв матиме вигляд:

Р_нв = (2 ^m - 1)/2 ⁿ = 1/(2 ^n−m) - 1/2 ^{n =} 1/2 ^k - 1/2 ⁿ,

де k = (n - m) - число надлишкових розрядів. З урахуванням того, що, як правило, n >> k, то величиною 1/2 ⁿ можна знехтувати і вважати Р_нв ≈ 1/2 ^k.

Оскільки число всіх заборонених кодових комбінацій дорівнює 2 ⁿ - 2 ^m, то ймовірність Р_в може бути визначеною з виразу:

Р_в = (2 ^{n - m}) / 2 ⁿ = 1 - 1/2 ^k = 1 - Р_нв.

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

Р_пп = Р_в Р_бр (t),

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

k_пор ≈ 0,4 (m + k_пор).

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

Дата добавления: 2014-01-04