Тема 3 Перешкодостійке кодування

Заняття 5

Основи перешкодостійкого кодування. Оцінка перевіряючої та корегуючої здатності кодів

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

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

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

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

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

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

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

Нехай нам необхідно закодувати чотири повідомлення (імовірності надходження повідомлень вважати однаковими) для передачі по каналу з перешкодами. З формули (1.1) ми можемо визначити, що для кодування цих повідомлень в двійковому алфавіті достатньо двох розрядів коду (такий код буде безнадлишковим), а кодові комбінації, відповідно, будуть наступні: 00, 01, 10, 11. Аналіз наведених кодових комбінацій дозволяє дійти висновку, що викривлення значення будь-якого їх розряду (заміна 0 на 1 або 1 на 0) переводить одну комбінацію цього коду в іншу, тому, у випадку наявності перешкод у лініях зв’язку, стверджувати правильність прийняття коду повідомлення приймачем без додаткової інформації неможливо.

Використаємо для кодування зазначених повідомлень трьохрозрядні кодові комбінації: 000, 011, 101, 110. Ці кодові комбінації будемо визначати як дозволені, а інші можливі трьохрозрядні комбінації двійкового коду (001, 010, 100, 111) – як заборонені. Викривлення значення будь-якого одного розряду дозволених комбінацій такого коду переводить їх в заборонені. Отримання забороненої кодової комбінації свідчить про наявність помилки в повідомленні, тобто наведений код дозволяє виявити будь-які одиночні помилки.

Використаємо для кодування повідомлень кодові комбінації: 00000, 00111, 11011, 11100. Інші можливі п’ятирозрядні комбінації двійкового коду, відповідно, будуть заборонені. Викривлення значення будь-якого одного розряду дозволених комбінацій такого коду переводить їх в заборонені, але особливістю отриманої забороненої кодової комбінації є те, що вона буде менше відрізнятися від вихідної кодової ніж від інших дозволених (від вихідної – в одному розряді, а від інших – в двох або більше). Таке кодування дозволяє виправити одиночні помилки шляхом переведення забороненої комбінації в найближчу дозволену.

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

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

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

Кодовою відстанню двох кодових комбінацій називається кількість символів, в яких ці комбінації відрізняються між собою.

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

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

Приклад 5.1. Визначити мінімальну кодову відстань для коду, що складається з кодових комбінацій: 010101; 101011; 000111.

Розв’язок.

Для визначення мінімальної кодової відстані коду необхідно обчислити значення кодових відстаней, визначених попарним перебором всіх кодових комбінацій коду, тобто для пар кодових комбінацій: 010101 та 101011; 010101 та 000111; 101011 та 000111.

Обчислюємо кодову відстань для кодових комбінацій 010101 та 101011:

_010101

101011

111110

d₁=1+1+1+1+1+0=5.

Обчислюємо кодову відстань для кодових комбінацій 010101 та 000111:

_010101

000111

010010

d₂=0+1+0+0+1+0=2.

Обчислюємо кодову відстань для кодових комбінацій 101011 та 000111:

_101011

000111

101100

d₃=1+0+1+1+0+0=3.

Мінімальну кодову відстань для наведеного коду визначаємо як найменше із значень кодових відстаней d₁, d₂, d₃, тобто:

d_min = d₂ =2 .

Перевіряюча та корегуюча здатності коду пов'язані з його мінімальною кодовою відстанню d_min наступними залежностями:

- код має здатність виявляти r помилок, якщо

d_min =r+1 ; (5.1)

- код має здатність виявляти та виправляти s помилок, якщо

d_min =2s+1 ; (5.2)

- код має здатність виявляти r помилок та виправляти s помилок (rs), якщо

d_min =r+s+1 . (5.3)

Примітка 5.1. Згідно з формулами (5.2) та (5.3) може бути отримане дробове значення s. Оскільки кількість помилок в повідомленні може бути лише цілим числом, корегуюча здатність такого коду визначається найбільшим цілим значенням, меншим від розрахункового.

Примітка 5.2. У випадку, визначеному формулою (5.3), передбачається ситуація, яку можна пояснити на прикладі коду з d_min=4. За формулою (5.2) можна визначити, що такий код може виявляти одну помилку. Підстановкою значення s=1 в (5.3) отримуємо r=2. Дійсно, будь-яка одиночна помилка може бути виправлена таким кодом, а у випадку двох помилок може виникати ситуація, коли отримана заборонена комбінація буде двома розрядами відрізнятися від двох різних дозволених комбінацій (помилки в такому випадку будуть виявлені, але однозначно визначити форму вихідного повідомлення буде неможливо).

Примітка 5.3. На перший погляд між наведеними формулами може виникнути протиріччя. Так для d_min=4 за формулою (3.1) r=3, а за формулою (3.3) при s=1 отримуємо r=2. Це вказує на залежність превіряючої та корегуючої здатності коду від характеру перешкод, які можуть виникати в ході передачі повідомлення. Якщо в повідомленні може виникнути не більше двох помилок, то одна помилка може бути виправлена, а факт наявності двох помилок – зафіксовано. Якщо в повідомленні може виникнути три помилки, то здатність коду виявляти помилки буде втрачено (див формулу (3.3) при r=3), оскільки в результаті корегування помилки повідомлення, в якому перекручено три розряди, може бути відновлене невірно.

Приклад 5.2. Визначити перевіряючу та корегуючу здатність коду, наведеного в прикладі 5.1.

Розв’язок.

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

Для визначення перевіряючої здатності коду скористаємось формулою (5.1). З (5.1) отримуємо:

r = d_min –1 = 2-1 =1 .

Таким чином код може виявляти лише одну помилку.

Для визначення перевіряючої здатності коду скористаємось формулою (5.2). Отримуємо:

s = 0.5( d_min –1) = 0.5(2-1) = 0.5 ;

s < 1 .

Таким чином код не спроможний виправляти жодної помилки.

Згідно з формулами (5.1)-(5.3) можна оцінити перевіряючу та корегуючу здатність коду з відомими кодовими комбінаціями. На практиці ж часто виникає потреба розв’язання зворотної задачі - створення коду з заданими показниками перевіряючої та корегуючої здатності. Ця задача зводиться до визначення кількості додаткових (контрольних) розрядів n_к, яку необхідно додати до n_і інформаційних розрядів повідомлення для отримання рівномірного перешкодостійкого коду з довжиною кодових комбінацій n=n_і+n_к, здатного корегувати s помилок, де s визначається з формули (5.2) як:

s =(d_min –1)/2 (5.4)

Значення кількості контрольних (додаткових) розрядів , необхідної для корегування S помилок, обмежується нерівністю (ліва частина нерівності – нижня межа Хеммінга, права - верхня межа Варшамова-Гільберта):

. (5.5)

Приблизні розрахунки можна виконувати за формулою:

, (5.6)

де значення в квадратних дужках слід заокруглити (аналогічно і в формулах (5.7) та (5.8)).

Враховуючи, що загальна кількість розрядів повідомлення визначається сумою кількостей інформаційних та контрольних розрядів (n=n_i+n_k), з формул (5.5) та (5.6) можна отримати вираз для визначення необхідної кількості контрольних розрядів n_k при відомій кількості інформаційних n_i. Для d_min=3, що дає s=1 або r=2, отримуємо:

. (5.7)

Для d_min=4, (r=3) отримуємо:

. (5.8)

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

Розв’язок.

Кількість контрольних розрядів, які необхідно додати до інформаційних для забезпечення можливості виявлення помилок кратності 2 можна визначити за формулою (5.7), оскільки дві помилки виявляє код з d_min=3, для якого r=2:

.

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

n = n_i + n_k =6+3 = 9.

Виконаємо перевірку правильності розрахунків за формулою (5.6). При цьому будемо враховувати, що n = 9, та s=1 (для d_min=3 згідно з формулою (5.2)):

.