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

В процесі передавання каналами зв’язку чи зберігання на носіях даних інформація може бути пошкоджена

Для виявлення пошкодження інформації, а також її відновлення використовуються спеціальні методи кодування

Найпростіша схема кодування для виявлення помилок полягає у наступному:

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

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

Перевірка парності/непарності

Найпростіший алгоритм такого кодування – “перевірка парності”: для кожного переданого байту підраховується сума одиничок, і у окремому біті заноситься “0” чи “1” в залежності від того, відповідно, чи є сума парною, чи ні. Таким чином, сума бітів у байті (разом із додатковим бітом) завжди є парною (чи непарною, якщо використовується перевірка непарності).

Поблокова перевірка парності/непарності

Алгоритм CRC

Алгоритм CRC (Cyclic Redundancy Check) є одним з найпоширеніших алгоритмів контролю цілісності даних.

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

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

Для зручності розрахунку CRC операції проводяться над поліномами, за допомогою яких представляються числа.

Існують стандартизовані поліноми:

Виправлення помилок

Виправлення помилок дещо складніше за їх виявлення

Процедура виправлення помилки передбачає два послідовних процеси: виявлення помилки та визначення місця, де вона відбулася.

Код Хемінга – популярний код виправлення помилок, відноситься до блокових кодів, який дозволяє виявити та виправити помилково переданий біт в межах одного переданого блоку.

Звичайно цей код характеризується двома цілими числами, наприклад (11,7), які означають, що при передачі 7-бітного коду (у минулому стандартне для США ASCII-кодування) передається додатково 4 контрольних біти (11 – 7 = 4).

Приклад використання коду Хемінга

Приклад. Необхідно передати літеру s = 1110011.

Передача буде здійснюватись наступним чином:

(*) – місце для контрольних бітів, ціла ступінь 2 (1,2,4,8)

Контрольна сума визначається як операція XOR над кодами позицій ненульових бітів. У даному разі це 11, 10, 9, 5 та 3.

Розрахунок:

Таким чином, передаватися буде наступний код:

У даному разі контрольна сума за операцією XOR для усіх ненульових

бітів буде рівна нулю:

Приклад використання коду Хемінга (продовж.)

Тепер уявимо, що виникла помилка у біті посилки №7 (1 замість 0), розрахунок контрольної суми дасть наступний результат:

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

1112 = 710

Обмеження коду Хемінга

Код може усувати помилку лише у одному біті, якщо відбувається декілька помилок, то використання коду для виправлення неможливе.

Для збільшення діапазону виправлення помилок використовується більш складна загальна форма коду BCH (Bose-Chadhuri-hocquenghem).

Позиційна система корекції помилок

Передбачає блочний розрахунок кодів парності у декількох вимірах.

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