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

План:

1 Способи боротьби з помилками
2 Коди виявлення та виправлення помилок
3 Автоматичний запит повторної передачі

Введення

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

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

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

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

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

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

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

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

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

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

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

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

2.1. Блокові коди

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

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

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

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

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

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

2.1.1. Лінійні коди загального вигляду

Лінійний блоковий код - такий код, що безліч його кодових слів утворює k -Мірне лінійне підпростір (назвемо його C ) В n -Мірному лінійному просторі, ізоморфне простору k -Бітних векторів.

Це означає, що операція кодування відповідає множенню вихідного k -Бітного вектора на невироджених матрицю G , Звану породжує матрицею.

Нехай $C ^ {\ perp}$ - Ортогональное підпростір по відношенню до C , А H - Матриця, що задає базис цього підпростору. Тоді для будь-якого вектора $\ Overrightarrow {v} \ in C$ справедливо:

$\ Overrightarrow {v} H ^ T = \ overrightarrow {0}.$

2.1.1.1. Мінімальна відстань і коригуюча здатність

Відстанню Хеммінга (метрикою Хемінга) між двома кодовими словами $\ Overrightarrow {u}$ і $\ Overrightarrow {v}$ називається кількість відмінних біт на відповідних позиціях:

$d_H (\ overrightarrow {u}, \; \ overrightarrow {v}) = \ sum_s {| u ^ {(s)}-v ^ {(s)} |}$ .

Мінімальна відстань Хемінга $d_ \ min = \ min_ {u \ ne v} d_H (\ overrightarrow {u}, \; \ overrightarrow {v})$ є важливою характеристикою лінійного блокового коду. Вона показує наскільки "далеко" розташовані коди один від одного. Вона визначає іншу, не менш важливу характеристику - коригувальну здатність :

$t = \ left \ lfloor \ frac {d_ \ min-1} {2} \ right \ rfloor$ .

Коригуюча здатність визначає, скільки помилок передачі коду (типу $1 \ leftrightarrow 0$ ) Можна гарантовано виправити. Тобто навколо кожного кодового слова A маємо t -Околиця A _t , Яка складається з усіх можливих варіантів передачі кодового слова A з числом помилок ( $1 \ leftrightarrow 0$ ) Не більше t . Ніякі дві околиці двох будь-яких кодових слів не перетинаються один з одним, так як відстань між кодовими словами (тобто центрами цих околиць) завжди більше двох їхніх радіусів $d_H (A, \; B) \ geqslant d_ \ min> 2t$ .

Таким чином отримавши перекручену кодову комбінацію з A _t , Декодер приймає рішення, що вихідною була кодова комбінація A , Виправляючи тим самим не більше t помилок.

Пояснимо на прикладі. Припустимо, що є два кодових слова A і B , Відстань Хемінга між ними дорівнює 3. Якщо було передано слово A , І канал вніс помилку в одному бите, вона може бути виправлена, тому що навіть в цьому випадку прийняте слово ближче до кодового слова A , Ніж до будь-якого іншого, і зокрема до B . Але якщо каналом були внесені помилки у двох бітах (в яких A відрізнялося від B ) То результат помилковою передачі A виявиться ближче до B , Ніж A , І декодер прийме рішення що передавалося слово B .

2.1.1.2. Коди Хемінга

Коди Хемінга - найпростіші лінійні коди з мінімальним відстанню 3, тобто здатні виправити одну помилку. Код Хемінга може бути представлений у такому вигляді, що синдром

$\ Overrightarrow {s} = \ overrightarrow {r} H ^ T$ , Де $\ Overrightarrow {r}$ - Прийнятий вектор, буде дорівнює номеру позиції, в якій сталася помилка. Ця властивість дозволяє зробити декодування дуже простим.

2.1.1.3. Загальний метод декодування лінійних кодів

Будь-який код (у тому числі нелінійний) можна декодувати за допомогою звичайної таблиці, де кожному значенню прийнятого слова $\ Overrightarrow {r} _i$ відповідає найбільш ймовірне передане слово $\ Overrightarrow {u} _i$ . Проте, даний метод вимагає застосування величезних таблиць вже для кодових слів порівняно невеликої довжини.

Для лінійних кодів цей метод можна істотно спростити. При цьому для кожного прийнятого вектора $\ Overrightarrow {r} _i$ обчислюється синдром $\ Overrightarrow {s} _i = \ overrightarrow {r} _i H ^ T$ . Оскільки $\ Overrightarrow {r} _i = \ overrightarrow {v} _i + \ overrightarrow {e} _i$ , Де $\ Overrightarrow {v} _i$ - Кодове слово, а $\ Overrightarrow {e} _i$ - Вектор помилки, то $\ Overrightarrow {s} _i = \ overrightarrow {e} _i H ^ T$ . Потім за допомогою таблиці по синдрому визначається вектор помилки, за допомогою якого визначається передане кодове слово. При цьому таблиця виходить набагато менше, ніж при використанні попереднього методу.

2.1.2. Лінійні циклічні коди

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

Циклічним кодом є лінійний код, що володіє наступною властивістю: якщо $\ Overrightarrow {v}$ є кодовим словом, то його циклічна перестановка також є кодовим словом.

Слова циклічного коду зручно представляти у вигляді многочленів. Наприклад, кодове слово $\ Overrightarrow {v} = (v_0, \; v_1, \; \ ldots, \; v_ {n-1})$ представляється у вигляді полінома $v (x) = v_0 + v_1 x + \ ldots + v_ {n-1} x ^ {n-1}$ . При цьому циклічний зсув кодового слова еквівалентний множенню многочлена на x по модулю x ⁿ - 1 .

Надалі, якщо не вказано інше, ми будемо вважати, що циклічний код є двійковим, тобто $v_0, \; v_1, \; \ ldots$ можуть приймати значення 0 або 1.

2.1.2.1. Породжує (генераторний) поліном

Можна показати, що всі кодові слова конкретного циклічного коду кратні певному породжує полиному g (x) . Породжує поліном є дільником x ⁿ - 1 .

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

несистематичне кодування здійснюється шляхом множення кодованого вектора на g (x) : v (x) = u (x) g (x) ;
систематичне кодування здійснюється шляхом "дописування" до кодованої слову залишку від ділення x ^{n - k} u (x) на g (x) , Тобто $v (x) = x ^ {n-k} u (x) + [x ^ {n-k} u (x) \, \ bmod \, g (x)]$ .

2.1.2.2. Коди CRC

Коди CRC ( англ. cyclic redundancy check - Циклічна надлишкова перевірка) є систематичними кодами, призначеними не для виправлення помилок, а для їх виявлення. Вони використовують спосіб систематичного кодування, викладений вище: "контрольна сума" обчислюється шляхом ділення x ^{n - k} u (x) на g (x) . З огляду на те, що виправлення помилок не потрібно, перевірка правильності передачі може проводитися точно так само.

Таким чином, вид полінома g (x) задає конкретний код CRC. Приклади найбільш популярних поліномів:

назва коду	ступінь	поліном
CRC-12	12	x ¹² + x ¹¹ + x ³ + x ² + x + 1
CRC-16	16	x ¹⁶ + x ¹⁵ + x ² + 1
CRC- CCITT	16	x ¹⁶ + x ¹² + x ⁵ + 1
CRC-32	32	x ³² + x ²⁶ + x ²³ + x ²² + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

2.1.2.3. Коди БЧХ

Коди Боуза - Чоудхурі - Хоквінгема (БЧХ) є підкласом циклічних кодів. Їх відмітна властивість - можливість побудови коду БЧХ з мінімальним відстанню не менше заданого. Це важливо, тому що, взагалі кажучи, визначення мінімального відстані коду є дуже складне завдання.

Математично полінома g (x) на множники в поле Галуа.

2.1.2.4. Коди корекції помилок Ріда - Соломона

Коди Ріда - Соломона - Недвійкова циклічні коди, що дозволяють виправляти помилки в блоках даних. Елементами кодового вектора є не біти, а групи бітів (блоки). Дуже поширені коди Ріда-Соломона, що працюють з байтами ( октетам).

Математично коди Ріда - Соломона є кодами БЧХ.

2.1.3. Переваги та недоліки блокових кодів

Хоча блокові коди, як правило, добре справляються з рідкими, але великими пачками помилок, їх ефективність при частих, але невеликих помилки (наприклад, в каналі з АБГШ), менш висока.

2.2. Свёрточные коды

Свёрточный кодер ( $k=7,\;R=1/2$ )

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

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

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

2.2.1. Переваги та недоліки сверточних кодів

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

2.3. Каскадне кодування. Ітеративний декодування

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

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

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

2.4. Мережеве кодування

2.5. Оцінка ефективності кодів

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

2.5.1. Кордон Хемінга і досконалі коди

Нехай є двійковий блоковий (N, k) код з коректує здатністю t . Тоді справедливо нерівність (зване кордоном Хемінга):

$\ Sum_ {i = 0} ^ t {n \ choose i} \ leqslant 2 ^ {n-k}.$

Коди, що задовольняють цьому кордоні з рівністю, називаються досконалими. До досконалим кодами відносяться, наприклад, коди Хеммінга. Часто застосовуються на практиці коди з великою коректує здатністю (такі, як коди Ріда - Соломона) не є досконалими.

2.5.2. Енергетичний виграш

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

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

2.6. Застосування кодів, що виправляють помилки

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

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

Коди, що виявляють помилки, застосовуються в мережевих протоколах різних рівнів.

3. Автоматичний запит повторної передачі

Системи з автоматичним запитом повторної передачі (ARQ - Automatic Repeat reQuest) засновані на технології виявлення помилок. Поширені такі методи автоматичного запиту:

3.1. Запит ARQ із зупинками (stop-and-wait ARQ)

Ідея цього методу полягає в тому, що передавач чекає від приймача підтвердження успішного прийому попереднього блоку даних перед тим як почати передачу наступного. У випадку, якщо блок даних був прийнятий з помилкою, приймач передає негативне підтвердження (negative acknowledgement, NAK), і передавач повторює передачу блоку. Даний метод підходить для напівдуплексного каналу зв'язку. Його недоліком є низька швидкість через високі накладних витрат на очікування.

3.2. Безперервний запит ARQ з поверненням (continuous ARQ with pullback)

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

3.3. Безперервний запит ARQ з вибірковим повторенням (continuous ARQ with selective repeat)

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

Література

Блейхут Р. Теорія і практика кодів, контролюючих помилки = Theory and Practice of Error Control Codes - М .: Світ, 1986. - 576 с.
Мак-Вільямс Ф. Дж., Слоен Н. Дж. А. Теорія кодів, що виправляють помилки. М.: Радіо і зв'язок, 1979.
Морелос-Сарагоса Р. Мистецтво завадостійкого кодування. Методи, алгоритми, застосування / пер. з англ. В. Б. Афанасьєва - М .: Техносфера, 2006. - 320 с. - (Світ зв'язку). - 2000 екз . - ISBN 5-94836-035-0.