Принципи побудови завадостійких кодів

Найчастіше як передумову при введенні кодів розглядають деякий початковий набір чи вектор із m b – розрядних символів (у випадку двійкових символів b =1 і тоді такими символами є “0”и “1”), званий часто базовим кодовим словом (БКС). Зрозуміло, що кількість можливих БКС при цьому дорівнює кількості можливих кодових комбінацій N₀ = 2^bm. Кожне таке БКС можна розглядати як представлене в деякій системі числення (при b =1 у двійковій системі числення) число А, діапазон представлення яких (робочий діапазон коду) знаходиться в межах від 0 до 2^bm, тобто А Î [0, 2^bm). Для такого коду будь-яке випадкове спотворення можна розглядати у вигляді суми (часто, порозрядної, по модулю 2) початкового коду і двійкового m символьного випадкового вектора Е. :

,

де .

На числовій вісі ці вектори, як числа із діапазону [0, 2^bm), можуть мати представлення, наведене на рис. 1.

0 ^{А Е} 2^bm

Рис. 1. Діапазон представлення ненадлишкових чисел

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

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

А Î [0, 2^bn),

де n = m + k. Для такого коду, як і раніше, будь-яке випадкове спотворення можна розглядати також у вигляді у вигляді суми по деякому модулю (наприклад, порозрядної по модулю 2 або простої суми по іншому модулю) початкового n символьного коду і двійкового n символьного випадкового вектору Е.

Процес завадостійкого кодування при цьому зводиться до наступного. Кожен перевірочний символ (або контрольна ознака в цілому) визначається (розраховується) як деяка функція (у деяких кодах, наприклад в кодах Хеммінга (див. нижче), як сукупність функцій) від початкового БКС або від сукупності його певних інформаційних символів. Які, конкретно, інформаційні символи беруть участь у формуванні цього перевірочного символу (або контрольної ознаки в цілому) і по якому закону він формується, визначається алгоритмом побудови даного коду. Дуже часто значення розрядів кожного перевірочного символу вибирається так, щоб порозрядна сума по модулю 2 цих розрядів інформаційних і даного перевірочного символів дорівнювала 0. Перевірочні символи, у принципі, можуть розташовуватися в кодовій комбінації на будь-якому місці. Для визначеності вважатимемо, що вони розміщуються в кінці початкового коду (повідомлення) . При цьому вимагають, щоб правильні, (не спотворені) числа в новому, розширеному діапазоні, як і раніше, відповідали вимозі А Î [0, 2^bm]. Цей розширений діапазон має вигляд, представлений на рис. 2.

0 2^bm 2^2bm (2^k – 1) 2^bm 2^bn

Рис. 2. Діапазони представлення чисел

Сукупність початкового числа А і його контрольної ознаки r(А) прийнято називати базовим кодовим словом (БКС) і, за певних умов, - завадостійким кодом і можна записати як:

А = (А, r(А)). (1)

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

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