Характеристики завадостійких кодів

Двійкові завадостійкі коди

Завадостійке (надмірне) кодування, що ґрунтується на розробці і використанні завадостійких (коригувальних) кодів, широко застосовується в телекомунікаційних мережах (ТКМ) і їх елементах для захисту від спотворень при зберіганні інформації чи її передачі між окремими елементами ТКМ. Воно дозволяє одержати вищі якісні показники роботи систем зв’язку. Його основне призначення − забезпечення малої імовірності спотворень переданої інформації, незважаючи на впливи завад на канали її передачі або збоїв у роботі технічних пристроїв.

Завадостійким кодом називається певна n−розрядна сукупність із символів деякого інформаційного об’єкта чи його частини (m інформаційних символів) і контрольної ознаки (k перевірочних символів), які є додатковими, надлишковими. Ці надлишкові символи непотрібні для відображення інформації, генерованої джерелом, і призначені для забезпечення виявлення, а при деяких обставинах і виправлення спотворень, які виникають в інформаційних символах під час їх циркуляції в елементах ТКМ внаслідок впливу завад або збоїв у роботі технічних пристроїв.

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

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

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

спотворення відсутні − − 1 випадок, одиночне спотворення − випадків, двократне спотворення − випадків, ……………………………………….. спотворення кратності tв випадків.

Отже, загальна кількість спотворень кратності tв і менше дорівнює звідси мінімальна необхідна кількість перевірочних розрядів для виправлення спотворень кратності tв і менше визначається з такої нерівності:

2k звідки k ≥ log2 .

Звичайне бажанням − мати такий код, який дозволяє виправити усі можливі спотворення, тобто tв = n. Тоді, використовуючи властивості коефіцієнтів бінома Ньютона:

k ≥ log2 = log2 2n = n,

k ≥ m + k,

що є неможливим.

Виходом з цієї ситуації є постановка задачі виявлення або виявлення і виправлення не будь-яких спотворень у початковому коді, а тільки всіх можливих у заданих умовах. Іншими словами відповідний завадостійкий код слід орієнтувати на реальну статистику спотворень у каналі передачі (у ЗП даного типу), коли кількість спотворених символів tв = n·Рсп, де Рсп − згадана вище імовірність спотворення біта в каналі передачі (ЗП).

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

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

До показників ефективності − найважливіших характеристик коригувальних кодів відносяться:

значність коду, або довжина базового кодового слова (БКС), яка містить інформаційні символи (m) і перевірочні, або контрольні, символи (k). Зазвичай значність коду п є сума
n = т + k;

відносна швидкість коду R, є відношенням кількості інформаційних символів в кодовій комбінації m до значності коду n: R = m/n;

надмірність коду Кнадм, є відношенням числа контрольних символів у кодовій комбінації k до значності коду n:

Кнадм = к/n = (n − m)/n = 1 − m/n = 1 − R;

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

На визначенні останніх зупинимося більш детально.

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

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

Nнв = 2m − 1.

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

Рнв = (2m - 1)/2n = 1/2n−m - 1/2n = 1/2k - 1/2n, (3.1)

де k = (n - m) - кількість надлишкових розрядів.

З урахуванням того, що, як правило, n >> k, то величиною 1/2n можна знехтувати і вважати Рнв ≈ 1/2k.

Оскільки кількість всіх заборонених кодових комбінацій дорівнює 2n - 2m, то імовірність Рв можна визначити з виразу:

Рв = (2n - 2m) / 2n = 1 - 1/2k = 1 - Рнв.

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

Рпп = Рв Рбр(t),

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

kпор ≈ 0,4 (m + kпор).

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

3.2.2. Двійкові коди з перевіркою на парність або на непарність (контроль по модулю 2)

При побудові таких кодів передана послідовність розрядів розбивається на групи — базові кодові слова (БКС). У найпростішому випадку при перевірці в кожному базовому кодовому слові розраховується контрольна ознака (контрольний біт) шляхом складання по модулю 2 всіх двійкових символів БКС. Контрольна ознака (контрольний біт) записується в кінці БКС. Під час контролю на парність, в результаті нього, кількість одиниць в БКС доводиться до парної. Так, кодова комбінація 01110 в результаті кодування перетвориться в комбінацію 011101. Перевірочна матриця коду з перевіркою на парність має вигляд Н (n, m) = ||111...1||.

Варіантом цього способу контролю цілісності є контроль на непарність, коли в кінець БКС як контрольна ознака (контрольного біта) дописується інверсне значення результату складання по модулю 2 всіх двійкових символів даного БКС. У результаті цього при контролі на непарність кількість одиниць в БКС доводиться до непарної. Так, кодова комбінація 01010 в результаті кодування перетвориться в комбінацію 010101.