Виявлення та виправлення помилок під час передачі інформації

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

Серед коригувальних кодів широко використовуються циклічні коди, в ЕОМ ці коди застосовуються при послідовній передачі даних між ЕОМ та зовнішніми пристроями, а також при передачі даних каналами зв'язку. Для виправлення двох і більше помилок (d0 5) використовуються циклічні коди що дозволяють здійснювати корекцію групових помилок. Здатність коду виявляти і виправляти помилки досягається за рахунок введень надмірності кодові комбінації, т.е. е. кодовим комбінаціям з до двійкових інформаційних символів, що надходять на вхід пристрою, що кодує, відповідає на виході послідовність з n двійкових символів (такий код називається (n, k) - кодом).

Якщо N0 = 2n - загальна кількість кодових комбінацій, а N = 2k - Число дозволених, то число заборонених кодових комбінацій дорівнює:

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

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

код коригувальний лінійний хемінг

Мал. 5.3. Подання двійкових кодів за допомогою куба

Так, склавши дві комбінації

визначимо, що відстань з-поміж них d=7.

Для коду N=3 вісім кодових комбінацій розміщуються на вершинах тривимірного куба. Такий код має кодову відстань d=1, і передачі використовуються всі вісім кодових комбінацій 000,001. 111. Такий код є не на заваді стійким, він не в змозі виявити помилку.

Якщо виберемо комбінації з кодовою відстанню d=2, наприклад: 000,110,101,011, такий код дозволить виявляти одноразові помилки. Назвемо ці комбінації дозволеними, призначеними передачі інформації. Решта 001,010,100,111 - заборонені.

Більшість коригувальних кодів утворюються шляхом додавання до вихідної k – комбінації m – контрольних символів. У результаті лінію передаються n=k+m символів. У цьому коригувальні коди називаються (n,k) кодами.

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

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

Якщо необхідно виправити дві помилки, кількість різних результатів буде становити . Тоді:

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

При цьому кількість помилок, що призводить до забороненої кодової комбінації, дорівнює:

де S - кратність помилки, тобто. е. кількість спотворених символів у кодовій комбінації S = 0, 1, 2.

Cni - поєднання з n елементів по i, що обчислюється за формулою:

Для виправлення S помилок кількість комбінацій кодового слова, складеного з m перевірочних розрядів N = 2m, має бути більше можливого числа помилок (2), при цьому кількість помилок, що виявляються, в два рази більша, ніж виправляються:

де квадратні дужки позначають заокруглення до більшого цілого.

Для виправлення дворазової помилки:

Лінійні групові коди

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

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

Групові коди зручно задавати за допомогою матриць, розмірність яких визначається параметрами k і n. Число рядків рівне k, а число стовпців дорівнює n = k+m:

Коди, що породжуються цими матрицями, називаються (n, k)-кодами, а відповідні їм матриці, що породжують (утворюють, що виробляють). Породжувальна матриця G складається з інформаційної Ikk та перевірочною Rkm матриць. Вона є стислим описом лінійного коду і може бути представлена в канонічній (типовій) формі:

Як інформаційна матриця зручно використовувати одиничну матрицю, ранг якої визначається кількістю інформаційних розрядів (8).

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

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

Стовпці додаткової матриці Rkm визначають правила формування перевірок Число одиниць у кожному рядку додаткової матриці повинне задовольняти умові r1 d0-1але число одиниць визначає число суматорів по модулю 2 в шифраторі і дешифраторі, і чим їх більше, тим складніше апаратура.

Виробнича матриця коду G(7,4) може мати вигляд:

Процес кодування полягає у взаємно – однозначній відповідності k-розрядних інформаційних слів - I і n-розрядних кодових слів - з:

c=IG. (9)

Наприклад: інформаційне слово I = [1 0 1 0] відповідає наступне кодове слово:

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

Процес декодування полягає у визначенні відповідності прийнятого кодового слова, переданому інформаційному. Це здійснюється за допомогою перевірочної матриці. H(n, k).

де RmkT -транспонована перевірна матриця (змінити рядки на стовпці); Imm - Поодинока матриця.

Для (7, 4)-коду перевірна матриця має вигляд:

між G(n,k) і H(n, k) існує однозначна зв'язок, тобто. до. вони визначаються відповідно до правил перевірки, при цьому для будь-якого кодового слова повинна виконуватись рівність cHT = 0.

Рядки перевірочної матриці визначають правила формування перевірок. Для (7, 4)-коду:

p2+a1+a2a3 = S2; (13)

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

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

Код Хеммінга, як і будь-який (n, k)- код, містить до інформаційних та m = n-k надлишкових (перевірочних) біт.

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

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

1. За заданою кількістю інформаційних символів - k або інформаційних комбінацій N = 2k, використовуючи співвідношення:

n = k+m, 2n (n+1)2k і 2m n+1 (14)

обчислюють основні параметри коду n і m.

2. Визначаємо робочі та контрольні позиції кодової комбінації. Номери контрольних позицій визначаються згідно із законом 2i, де i= 1, 2, 3. тобто. вони дорівнюють 1, 2, 4, 8, 16, ... а інші позиції є робітниками.
3. Визначаємо значення контрольних розрядів (0 або 1) за допомогою багаторазових перевірок кодової комбінації на парність. Кількість перевірок дорівнює m = n-k.

У кожну перевірку включається один контрольний та певні перевірочні біти.Якщо результат перевірки дає парне число, то контрольному біту присвоюється значення -0, інакше - 1. Номери інформаційних біт, що включаються до кожної перевірки, визначаються за двійковим кодом натуральних n -чисел розрядністю - m (табл. 1, для m = 4) або за допомогою перевірочної матриці H(mn), стовпці якої представляють запис у двійковій системі всіх цілих чисел від 1 до 2k -1 перерахованих у зростаючому порядку. Для m = 3 перевірна матриця має вигляд:

Кількість розрядів m - Визначає кількість перевірок.

У першу перевірку включають коефіцієнти, що містять 1 у молодшому (першому) розряді, тобто b1, b3, b5 і т.д.

У другу перевірку включають коефіцієнти, що містять 1 у другому розряді, тобто b2, b3, b6 і т.д.

У третю перевірку - коефіцієнти які містять 1 у третьому розряді тощо.

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

Десяткові числа (номери розрядів кодової комбінації)

Двійкові числа та їх розряди

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

Приклад 1. Побудувати код Хеммінгу для передачі повідомлень у вигляді послідовності десяткових цифр, поданих у вигляді 4-розрядних двійкових слів.Показати процес кодування, декодування та виправлення одиночної помилки на прикладі інформаційного слова 0101.

1. За заданою довжиною інформаційного слова (k = 4), визначимо кількість контрольних розрядів m, використовуючи співвідношення:

при цьому n = k+m = 7, Т. е. отримали (7, 4)-код.

2. Визначаємо номери робочих та контрольних позиції кодової комбінації. Номери контрольних позицій вибираємо згідно із законом 2i.

Для розглянутої задачі (при n = 7) номери контрольних позицій дорівнюють 1, 2, 4. При цьому кодова комбінація має вигляд:

b1 b2 b3 b4 b5 b6 b7

3. Визначаємо значення контрольних розрядів (0 чи 1), використовуючи перевірочну матрицю (5).

k1 b3 b5 b7 = k1011 буде парною при k1 = 0.

k2 b3 b6 b7 = k2001 буде парною при k2 = 1.

k3 b5 b6 b7 = k3101 буде парною при k3 = 0.

Кодова комбінація, що передається: 0 1 0 0 1 0 1.

Допустимо, прийнято: 0 1 1 0 1 0 1.

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

1) k1 b3 b5 b7 = 0111 = 1.
2) k2 b3 b6 b7 = 1101 = 1.
3) k3 b5 b6 b7 = 0101 = 0.

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

Приклад 2. Побудувати код Хеммінга для передачі кодової комбінації 1 1 0 1 1 0 1 1. Показати процес виявлення та виправлення помилки у відповідному розряді кодової комбінації.

Рішення: Розглянемо алгоритм побудови коду виправлення одиночної помилки.

1. За заданою довжиною інформаційного слова (k = 8), використовуючи співвідношення, обчислимо основні параметри коду n і m.

при цьому n = k+m = 12, Т. е. отримали (12, 8) - код.

2. Визначаємо номери робочих і контрольних позицій кодової комбінації.

Для розглянутої задачі (при n = 12) номери контрольних позицій дорівнюють 1, 4, 8.

При цьому кодова комбінація має вигляд:

b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12

к1 к2 1 к3 1 0 1 к4 1 0 1 1

3. Визначаємо значення контрольних розрядів (0 або 1) шляхом багаторазових перевірок кодової комбінації на парність. Кількість перевірок дорівнює m = n-k.

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

0001 b1 Кількість розрядів m – визначає кількість перевірок
0010 b2
0011 b3 1) к1 b3 b5 b7 b9 а11 = к111111 =>
0100 b4 парна при к1=1
0101 b5 2) к2 b3 b6 b7 b10 b11= к210101 =>
0110 b6 парна при к2=1
0111 b7 3) к3 b5 b6 b7 b12 = к31011=>
1000 b8 парна при к3=1
1001 b9 4) к4 b9 b10 b11 b12 = к11011 =>
1010 b10 парна при к4=1
1011 b11
1100 b12

Передана кодова комбінація: 1 2 3 4 5 6 7 8 9 10 11 12

1 1 1 1 1 0 1 1 1 0 1 1

Припустимо, прийнято: 1 1 1 1 0 0 1 1 1 0 1 1

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

1) к1 b3 b5 b7 b9 b11 = 110111 = 1
2) к2 b3 b6 b7 b10 b11 = 110101 = 0
3) к3 b5 b6 b7 b12 = 10011 = 1
4) к4 b9 b10 b11 b12 = 11011 = 0

Виявлено помилку в розряді кодової комбінації з номером 0101, т. е. у 5-му розряді. Для виправлення помилки необхідно проінвертувати 5-й розряд кодової комбінації.

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

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

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

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

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

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

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

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

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

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

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

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

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

Блокові коди

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

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

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

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

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

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

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

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

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

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

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

Відстань Хеммінга (метрикою Хеммінгу) між двома кодовими словами і називається кількість відмінних біт на відповідних позиціях:

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

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

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

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

Коди Хеммінгу

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

, де - прийнятий вектор, буде дорівнювати номер позиції, в якій відбулася помилка. Ця властивість дозволяє зробити декодування дуже простим.

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

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

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

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

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

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

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

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

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

Можна показати, що всі кодові слова конкретного циклічного коду кратні певному що породжує поліном . Що породжує поліном є дільником.

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

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

Коди CRC

Коди CRC (англ. cyclic redundancy check - циклічна надлишкова перевірка) є систематичними кодами, призначеними задля виправлення помилок, а їх виявлення. Вони використовують спосіб систематичного кодування, викладений вище: «контрольна сума» обчислюється шляхом поділу на . Зважаючи на те, що виправлення помилок не потрібне, перевірка правильності передачі може проводитися так само.

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

Коди БЧХ

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

Математично полінома на множники у полі Галуа.

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

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

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

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

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

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

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

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

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

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

Переваги та недоліки згорткових кодів

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

також

Цифровий зв'язок
Код відповіді (Код причини завершення)
Лінійний код
Циклічний код
Код Боуза - Чоудхурі - Хоквінгема
Код Ріда - Соломона
LDPC
Згортковий код
Турбо-код

Література

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

Посилання

Перешкодостійке кодування (11 листопада 2001). - Реферат з проблеми кодування повідомлень з виправленням помилок. Архівовано з першоджерела 25 серпня 2011 року.Перевірено 25 грудня 2006 року.

Кібернетика
Теорія кодування
Виявлення та усунення помилок

Wikimedia Foundation. 2010 .

Що таке виправлення помилок під час передачі даних