Лекція № 5 завадостійке кодування

5.1 Класифікація завадостійких кодів.

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

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

Блочне (блокове) кодування полягає в тому, що кожній букві повідомлення або послідовності з k символів, що відповідає цій букві повідомлення, ставиться у відповідність блок з n символів, причому n> k, а кожен символ блоку формується з k символів вихідної послідовності за певним правилом . На практиці блок може досягати від 3 до декількох сотень одиниць.

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

Найбільш широке поширення серед безперервних кодів отримали згорткові коди.

Блокові коди поділяються на роздільні і нероздільні. До разделімого кодами відносяться ті, у яких кодова комбінація складається з двох частин, а саме інформаційної та перевірочної частин. Зазвичай перевірочні символи виходять за допомогою деяких операцій над інформаційними символами. Разделімие коди позначають (n, k).

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

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

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

Приклад формування блокового разделімого системного коду.

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

До несистематическим кодами відносяться ті, в яких перевірочні символи формуються за рахунок нелінійних операцій над інформаційними символами (код Бергера).

5.2 Параметри (характеристики) перешкодостійких кодів і їх межі. Коригувальні властивості кодів.

Основними характеристиками перешкодостійких кодів є:

2. Підстава коду m;

3. Загальна кількість кодових комбінацій N;

4. Число дозволених кодових комбінацій N р;

5. Надмірність коду;

6. Кодова відстань d.

Довжина коду - число символів в кодової комбінації n. Якщо кодові комбінації містять однакове число символів, то вони називаються рівномірними.

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

Якщо коди виконавчі, то.

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

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

Надмірність коду в загальному випадку визначається виразом:

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

Для двійкових кодів відповідно можна виразити через:

- відносна швидкість коду

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

Кодова відстань часто називають кодом Хеммінга. Кодова відстань між різними комбінаціями конкретного коду може бути різним.

Мінімальна кодова відстань - це мінімальна відстань між дозволеними кодовими комбінаціями даного коду. є основною характеристикою коректує здатності коду.

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

Наприклад, при d = 1 все кодові комбінації називають дозволеними. Нехай n = 3. кодові комбінації: 000, 001, 010, 100, 110, 111, 101. Будь-які одинарні помилка в такому коді переводить задану дозволену комбінацію в іншу дозволену комбінацію. Це випадок без надлишкового коду, який не володіє коректує здатністю.

Якщо припустити, що d = 2, і для n = 3 сформуємо набір дозволених комбінацій:

000, 011, 101, 110 - дозволені комбінації;

001, 010, 100, 111 - заборонені комбінації.

У загальному випадку при необхідності виявлення помилки з кратністю s очевидно, що (межа виявлення помилки кратністю s).

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

Розглянемо випадок, коли d = 3 і n = 3.