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

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

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

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

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

· Виправлення помилок (англ. 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 ₂1 u ₄011 u ₈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. ▲

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

Поиск по сайту: