4. Кодистійкі до перешкод

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

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

• Виявлення помилок у блоках даних і автоматичний запит повторної передачі пошкоджених блоків - цей підхід застосовується, в основному, на канальному і транспортному рівнях;

• Виявлення помилок у блоках даних і відкидання пошкоджених блоків - такий підхід іноді застосовується в системах потокового мультимедіа, де не повинно бути затримки передачі і немає часу на повторну передачу;

• Виправлення помилок (англ. forward error correction) застосовується на фізичному рівні.

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

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

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

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

R_над = (n−k )/п,

Означення 4.3. Кількість одиниць у кодовій комбінації називають вагою (w).

Приклад 4.1. Кодова комбінація 1001001 характеризується значністю n=7 і вагою w=3. ▲

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

Приклад 4.2. Визначення відстані за Хеммінгом між комбінаціями 10010010 та 11011000. Ці комбінації відрізняються в другій, п’ятій та сьомій позиції. Щоб пересвдчитись застосуємо побітове альтернативне “або”:

Отже, вага отриманої комбінації w=3, тому відстань між вихідними комбінаціями d=3. ▲

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

.

Означення 4.5. Кодом Хеммінга називається (n, k) – систематичний код, який містить надлишкові біти на позиціях 1, 2, 4, 8 .. , де<n<.

Синдром коду Хемінга обчислюється наступним чином:

.

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

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

Приклад 4.4. Закодувати двійковим кодом Хеммінга комбінацію A = 10111 двійкового простого коду та показати на прикладі виправлення будь-якої однократної помилки. Визначити надмірність коду Хеммінга.

Виконуємо кодування заданої комбінації А. При k = 5 кількість надишкових елементів r = n-k = 4 становить. Перевірні елементи знаходяться на позиціях 1, 2, 4 та 8.

Записавши кодовий вектор коду Хеммінга у вигляді u₁u₂1u₄011u₈1, визначаємо значення u₁, u₂, u₄, u₈:

П’ятий біт ми не враховуємо, тому що він рівний “0”. Кожне з чисел 1, 2, 3, 4, 6, 7, 8 та 9 розписуємо у двійковій системі :

1 = 0001, 2 = 0010, 3 = 0011, 4 = 0100, 6 = 0110, 7 =0111, 8 = 1000, 9 = 1001. При застосуванні кон’юнкції над невідомими бітами, для прикладу, результатом буде0 0 0. Запишемо бітове представлення вертикальними стовбцями:

Звідcи:

u₁ = 1; u₂ = 1; u₄ = 1; u₈ =1.

Отже комбінація коду Хеммінга матиме вигляд 111001111.

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

Нехай передане кодове слово 1101001, а прийняте слово – 1101101. Синдром, відповідний прийнятому слову, буде дорівнювати:

.

Обчислений синдром вказує на помилку в п'ятій позиції.

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

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

S₁ = u₁  u₃  u₅  u₇  u₉ = 1  1  0  0  1 = 1;

S₂ = u₂  u₃  u₆  u₇ = 1  1  1  0 = 1;

S₃ = u₄  u₅  u₆  u₇ = 0  0  1  0 = 1;

S₄ = u₈  u₉ = 1  1 = 0.

Маємо синдром 0111. Отже, спотворено елемент за номером 0111₂ = 7₁₀, тобто елемент и₇. Виправляємо його: замість помилкового елемента и₇ = 0 записуємо значення и₇ = 1 і дістаємо правильну кодову комбінацію 111001111.

Надмірність коду Хеммінга R_над = r/п = 4/9. ▲

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