РОЗДІЛ 17. КОРЕКТУЮЧІ КОДИ

17.1. ОСНОВНІ ПАРАМЕТРИ КОРЕКТУЮЧИХ КОДІВ

Одним із засобів підвищення якості передавання повідомлень дискрет­ними каналами зв'язку із завадами є застосування коректуючих кодів, які дають змогу виявляти та виправляти помилки, що виникають через завади в каналі. Скільки ж помилок може виявити та виправити код? За теоремою Шеннона (див. § 18.2) у разі продуктивності джерела , яка менша за пропу­скну здатність каналу , існують коди, що забезпечують безпомил­кове передавання повідомлень. Однак вони дуже складні й поки ще навіть не знайдені, тому запропоновані та використовуються коди, що виявляють і виправляють не всі, а лише частину помилок.

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

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

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

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

незбіжні в трьох розрядах (позначені пунктиром). І тому хеммінгова віддаль . Математично хеммінгова віддаль підраховується як кількість одиниць

у сумі за модулем два (mod 2) цих двох кодових комбінацій. Нагадаємо правило додавання за модулем два: ; ; ; ( - знак додавання за mod 2).

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

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

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

. (19.1)

17.2. ПРИНЦИПИ ПОБУДОВИ КОРЕКТУЮЧИХ КОДІВ

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

Прийнята кодова комбінація може в будь-якому символі відрізнятися від переданої комбінації а,- внаслідок помилок, що виникають на виході дискретного каналу зв'язку, тому кожний з її символів позначено "шляпкою". У декодері в разі надлишкового кодування з'являється можливість виявлення та виправлення помилок. Для реалізації цієї можливості, як зазначено вище (див. § 19.1), усі кодові комбінації корек­туючого коду розподіляються на дозволені та заборонені. У кодері формую­ться тільки дозволені кодові комбінації. Перехід їх у заборонені через поми­лки в каналі є необхідною умовою для виявлення та виправлення помилок, тому головна задача побудови будь-якого коректуючого коду - розподіл усіх кодових комбінацій на дозволених і заборонених так, щоб забезпечити необхідну коректуючу здатність коду. В цілому це досить скла­дна задача, що розв'язується різними методами залежно від вимог до деко­дера (потрібно виявляти чи виправляти помилки).

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

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

. (19.3)

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

Декодування з виправленням помилок. У кодах із виправленням по­милок пред'являються більш жорсткі вимоги до кодової віддалі між дозволе­ними кодовими комбінаціями. Виправлення помилок можливе також тільки в тому випадку, коли передана дозволена кодова комбінація через помилки переходить у заборонену. Рішення про те, яка кодова комбінація передава­лась, приймається в декодері на основі порівняння прийнятої забороненої кодової комбінації з усіма дозволеними. Прийнята заборонена кодова комбінація ототожнюється з тією дозволеною, до якої вона більш за все подібна, тобто з тією, від якої вона відрізняється меншим числом символів. За цим правилом, для виправлення помилок кратністю заборонена кодова комбінація, набута через помилки, має залишатись ближчою до переданої справжньої дозволеної, ніж до будь-якої іншої дозволеної кодової комбінації. Наведене вище правило виконується за такої умови

. (19.4)

Співвідношення (19.3) та (19.4) є основними для визначення коректуючої здатності коду, оскільки вони дають змогу при заданій кодовій віддалі знайти кратність помилок, що виявляються та виправляються у декодері. Наприклад, якщо "сусідні" дозволені кодові комбінації мають кодову віддаль , то в разі помилок кратності чотири і менше будь-яка дозволена кодова комбінація не може перейти в іншу дозволену, і наявність помилок легко виявити. Виправлятись будуть тільки одно- і двократні помилки, тому що вже при трьох помилках набута заборонена кодова комбінація буде ближче до іншої дозволеної. Сказа­не ілюструється рис. 19.2.

Умовно віддаль між трьома до­зволеними кодовими комбінаціями b₁, b₂, b₃ показана прямими лініями, на яких через інтервал від­кладені заборонені кодові комбіна­ції, що відрізняються в 1 - 4 симво­лах від дозволених. Штрихами обведена зона, що оточує кожну дозволену кодову комбінацію b_i. Радіус зони вибрано таким, що дорівнює , і до цієї зони попадають такі заборонені кодові комбінації, які знаходяться ближче до дозволеної в центрі цієї зони, ніж до дозволеної комбінації в іншій зоні. Під час декодування кодові комбінації, що знаходяться в будь-якій зоні, ототожнюються з дозволеною кодовою комбінацією цієї зони. Трикратна помилка, наприклад у b₁, переводить її в зону комбінації b₂ (на рис. 19.2 цей перехід показаний стрілкою), і під час декодування буде прийняте рішення, що передавалась комбінація Ь₂ (помилки не виправлені).

Отже, задача утворення коду з необхідною коректуючою здатністю зво­диться до задачі формування в кодері дозволених кодових комбінацій із необхідною кодовою віддаллю .

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

; (19.5)

, (19.6)

де - число сполучень із по . Для верхня і нижня межі зливаються, і визначене за формулами (19.5) чи (19.6) значення є точним.

Розрахунками на ЕОМ встановлено, що формула (19.6), яку називають межею Варшамова-Гільберта, дає дещо завищені, але дуже близькі до точних значення. У табл. 19.1 наведені дані розрахунків за формулою (19.6) для числа інформаційних символів у кодовій комбінації і кодовій віддалі . Із таблиці випливають дуже важливі для практичної побудови коректуючих кодів висновки:

1) при зростанні кодової віддалі і, відповідно, коректуючої здатності ко­ду різко підвищується кількість перевірних символів, значно зменшується відносна швидкість коду (на один інформаційний символ потрібно два-п'ять перевірних);

2) для утворення доброго коректуючого коду (виправляє дві і більше по­милок) при відносній швидкості його кодова комбінація повинна мати кілька десятків інформаційних символів (див. приклад 19.3).

Поиск по сайту: