Коди, що виправляють помилки

Ви́явлення помилок в техніці зв'язку — дія, спрямована на контроль цілісності даних при запису / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) — процедура відновлення інформації після читання її з пристрою зберігання або каналу зв'язку.

Для виявлення помилок використовують коди виявлення помилок, для виправлення — коригувальні коди (коди, що виправляють помилки, коди з корекцією помилок, завадостійкі коди).

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

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

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

Способи боротьби з помилками

У процесі зберігання даних і передачі інформації з мереж зв'язку неминуче виникають помилки. Контроль цілісності даних і виправлення помилок — важливі завдання на багатьох рівнях роботи з інформацією (зокрема, фізичному, канальному, транспортному рівнях мережевої моделі OSI).

У системах зв'язку можливі кілька стратегій боротьби з помилками:

• Виявлення помилок у блоках даних і автоматичний запит повторної передачі пошкоджених блоків — цей підхід застосовується, в основному, на канальному і транспортному рівнях;
• Виявлення помилок у блоках даних і відкидання пошкоджених блоків — такий підхід іноді застосовується в системах потокового мультимедіа, де важлива затримка передачі і немає часу на повторну передачу;
• Виправлення помилок (англ. forward error correction) застосовується на фізичному рівні.

Коди виявлення та виправлення помилок

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

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

З кодами, які виправляють помилки, тісно пов'язані коди виявлення помилок. На відміну від перших, останні можуть тільки встановити факт наявності помилки в переданих даних, але не виправити її.

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

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

Блокові коди

Докладніше: Блоковий код

Нехай кодована інформація поділяється на фрагменти довжиною k біт, які перетворюються в кодові слова довжиною n біт, де n > k. Тоді відповідний блоковий код зазвичай позначають (n, k). При цьому число R = k/n називається швидкістю коду.

Якщо вихідні k біт код залишає незмінними, і додає n — k перевірочних, такий код називається систематичним, інакше несистематичним.

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

• Здатність виправляти якомога більше число помилок,
• Якомога менша надмірність,
• Простота кодування і декодування.

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

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

Згорткові коди

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

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

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

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

Примітки

1. Архів оригіналу за 31 травня 2017. Процитовано 12 квітня 2013.
2. Блейхут, Ричард (1986). Теория и практика кодов, контролирующих ошибки (рос.). Москва: "МИР". с. 16—17.

Посилання