Синдромне декодування

Коректуюча здатність коду - це гарантована кількість (кратність) помилок у кодовій комбінації, що виявляються або виправляються заданим кодом. Позначається кратність помилок так: код виявляє в кодовій комбінації q_B, помилок, виправляє q_вип помилок. Цілком зрозуміло, що чим більшими є кратності q_B і q_вип тим кращим є код. Отже, надлишковість коду ще не визначає повністю його коректуючих можливостей. її, згідно теореми кодування, визначає кодова віддаль коду. Кодовою віддаллю коду прийнято називати мінімальну кодову відстань у коді, тобто величину d = min d(i, j), причому і, j охоплюють всі пари дозволених комбінацій.

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

Для кодових комбінацій на вході кодера завадостійкого коду кодові віддалі між усіма парами комбінацій будуть такими:

Для кодових комбінацій на виході кодера завадостійкого коду кодові віддалі між усіма парами комбінацій будуть такими:

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

Теорема кодування для завадостійких кодів. Якщо код має d > 1, то він дозволяє виявити всі помилки з кратністю q≤d-1 і деякі помилки з кратністю q ≥ d, а також виправляти помилки з кратністю q≤(d-1)/2.

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

Кодові відстані на виході завадостійкого кодера є більшими, ніж на його вході і вони, якраз, і визначають коректуючу здатність коду. Взагалі ж, для завадостійкого коду (7.4) кодова віддаль d = 3, тобто не існує дозволених кодових комбінацій, які відрізнялися б менш ніж у трьох розрядах. Такий код згідно теореми кодування дозволяє виявляти всі помилки кратністю q < 3, тобто одно- і двократні і деякі помилки з кратністю q ≥ 3, а також виправляти помилки з кратністю 1.

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

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

При виправленні (і виявленні) помилок часто застосовують синдромне декодування. Термін "синдром" у теорії кодування визначає сукупність ознак, характерних для кожної певної конфігурації помилок. Тому під синдромом коду розуміють контрольне число s(s₁, s₂,..., s_r), що свідчить про наявність помилок і їх розташування (конфігурацію) у кодовій комбінації. Синдром записується у двійковому коді, тобто його розряди s₁, s₂,..., s приймають значення 0 або 1. Нульовий синдром вказує на те, що кодова комбінація є дозволеною, тобто виявлених помилок нема. Ненульовому синдрому відповідає певне (визначене наперед) розміщення помилок.

Наприклад, для коду (7.4) синдром буде мати 3 розряди відповідно до кількості строчок (перевірок) перевіркової матриці. Якщо в даному рядку перевірка пройшла успішно (отримано результат 0) то цей результат (0) і заноситься в відповідний розряд синдрому. Якщо результат перевірки негативний, то в даний розряд синдрому заноситься 1. В результаті після перевірки всіх рядків перевіркової матриці отримуємо кодову комбінацію синдрому, яка відповідає певному вхідному (помилковому) коду. Наприклад, при кодуванні систематичним кодом (7.4) для інформаційної комбінації 0101 (номер рівня 5) допустимою кодовою комбінацією буде 0101110. Для цієї кодової комбінації перевірка дає нульовий результат для всіх рядків, тому синдром буде мати значення 000 - комбінація безпомилкова. Комбінація ж 0101010 не проходить перевірку у першому рядку перевіркової матриці. Отже значення синдрому буде 100 і такому синдрому відповідає конфігурація помилки 0000100. Для всіх семи розрядів коду (7.4) існують відповідні коди синдромів. Тому цей код за допомогою таблиці відповідності дозволяє виправити всі однократні помилки.

Для двійкових кодів виправлення помилок провадиться єдиним способом -інверсією символів (0 замінюється на 1 і, навпаки, 1 - на 0). Тому знання синдрому є необхідною і достатньою умовою для виправлення помилок у двійкових кодах. Таким чином, синдромне декодування двійкових кодів зводиться до пошуку тим чи іншим способом синдрому, за яким потім виявляються і виправляються помилки.

Контрольні питання:

1 Що називають віддалю Хемінга?

2 Як формулюється тео­рема кодування для завадостійких кодів?

3 Що означає термін "синдром" у теорії ко­дування?

4 Визначіть віддаль Хемінга між кодовими комбінаціями 10010 і 11001.

5 Визначіть кратність помилок, що виявляються та виправляються кодом з кодовою віддалю d_min=5.

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