Класифікація кодів і їх характеристики

КОДУВАННЯ В ДИСКРЕТНИХ І НЕПЕРЕРВНИХ КАНАЛАХ

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

Для кращого розуміння процесу кодування повідомлень треба знати сис­теми числення, деякі основні операції над елементами поля GF(q). способи подання кодів, основні теореми кодування для каналів. Про все це йтиметься в цьому розділі. Крім того, тут викладено класифікацію кодів, наведено ха­рактеристики їх, описано основні принципи оптимального кодування.

Класифікація кодів і їх характеристики

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

Множина кодових комбінацій, побудованих за одним прави лом кодування, називається кодом. Залежно від алфавіту, який застосовується для побудови кодових комбінацій, коди поділяються на двійкові, алфавіт яких складається з двох символів (0 і 1), та недвійкоеі (багатопозиційні, q-коди), алфавіт яких містить більше двох символів.

Розрізняють дві групи кодів: безнадмірні (некоректувальні, пер­винні, прості) та надмірні (завадостійкі). Перші не дають змоги виявити та виправити спотворені елементи в своїх комбінаціях, другі – забезпечують можливість виявлення та/або виправлення елементів кодових комбінацій, спотворених унаслідок дії завад.

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

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

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

Подільні блокові коди бувають систематичними та несисте­матичними. Систематичним подільним блоковим кодом нази­вається такий код, у комбінаціях якого перші k позицій (розря­дів) зайнято інформаційними елементами, а решту r = n-k по­зицій, де n– загальна кількість позицій в кодовій комбінації, – перевірними. До несистематичних подільних блокових кодів належать коди, в яких інформаційними елементами не зайнято всі k перших позицій.

Різновидом подільних систематичних блокових кодів є цик­лічні коди.

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

- кількістю k інформаційних елементів;

- кількістю г перевірних елементів (для коректувальних кодів);

- довжиною (розрядністю) n– кількістю елементів (симво­лів), які входять до складу кодової комбінації (п = k + r );

- основою (алфавітом) q;

- потужністю N – кількістю дозволених кодових комбіна­цій, що використовуються для передачі повідомлень;

- повною кількістю /V кодових комбінацій, тобто кількістю всіх можливих комбінацій, яка дорівнює qⁿ (для двійкових кодів N = 2ⁿ);

- надмірністю

R_над= (для неподільних кодів)

або R_над=1-k/n=r/n(для подільних кодів при N_Д = 2^k і N = 2ⁿ);

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

R= або R= _над;

вагою кодової комбінації (для двійкового коду визначається кількістю одиниць у ній);

- мінімальною кодовою відстанню d= min d_ij, тобто мінімаль­ною відстанню між парами кодових комбінацій

,

де a_li, a_lj – елементи, що знаходяться в l-му місці в i- та j-й ком­бінаціях. Це значить, що d_ij, визначається кількістю одноймен­них розрядів з різними значеннями;

- імовірністю Р_НВ.П невиявленої помилки, тобто ймовірністю такої події, за якої прийнята кодова комбінація відрізняється від переданої, а властивості коду не дають змоги визначити факт наявності помилки;

- імовірністю Р_В.П виявленої помилки, тобто ймовірністю, за якої прийнята кодова комбінація відрізняється від переданої і завдяки властивостям коду встановлюється факт наявності помилки в кодовій комбінації;

- імовірністю Р_ВП.П виправленої помилки, тобто ймовірністю такої події, за якої прийнята кодова комбінація відрізняється від переданої і завдяки властивостям коду виправляється по­милка в кодовій комбінації;

- імовірністю Р_П виникнення помилки, тобто ймовірністю та­кої події, за якої прийнята кодова комбінація відрізняється від переданої (Р_п = Р_НВ.П + Р_В.П –для кодів, які виявляють помилки, та Р_п = Р_НВ.П + Р_В.П + Р_НВ.П – для кодів, які виправляють помил­ки, де Р_НВ.П – імовірність невиправленої виявленої помилки);

- кратністю ν помилки, що визначається кратністю v_в вияв­лених та ν_ΒΠ виправлених помилок;

- ефективністю

,

де P_i - ймовірність виявленої або виправленої помилки залеж­но від властивостей коду.

Ступінь захисту інформації від помилок відповідним спосо­бом кодування залежить головним чином від мінімальної ко­дової відстані d_min даного коду.

Розрізняють три види кодової відстані: Хеммінга, Лі та мат­ричну. Перша знайшла найбільше поширення в теорії кодуван­ня. Кодова відстань Хеммінга нероздільно пов'язана з поняттям ваги w кодової комбінації –кількістю її елементів, які не дорів­нюють нулю.

Кодова відстань Хеммінга d між двома комбінаціями однієї довжини n визначається як кількість однойменних розрядів (по­зицій), які мають неоднакові елементи. Так, для двійкових кодів, оскільки в двійковій арифметиці додавання однакових елемен­тів дає 0, а неоднакових – 1, відстань Хеммінга між двома кодо­вими комбінаціями можна визначити порозрядним додаванням їх за модулем 2 та подальшим підрахунком кількості ненульових елементів, тобто визначенням ваги w такої суми.

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

Щоб визначити кодову комбінацію, яка віддалена від зада­ної на відстань d, до цієї комбінації можна додати будь-яку комбінацію вагою w = d(3d одиницями та n - d нулями). Дода­вання – порозрядне за модулем 2.

Для виявлення всіх помилок кратністю v_B кодова відстань має становити d ≥ v_g + 1, а виправлення помилок кратністю ν_ΒΠ - d ≥ 2ν_ΒΠ + 1. Щоб виправити та виявити всі помилки, має виконуватися умова

d ≥ ν_ΒΠ +ν_Β + 1

Через те, що загалом кожний елемент (розряд) комбінації недвійкового (багатопозиційного) коду може мати на відміну від двійкового й понад однієї позиції (т ≥ 1) з алфавіту q, кодова відстань при цьому визначається виразом

,

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

У метриці Хеммінга кодова відстань, як і для двійкового коду, визначається кількістю однойменних розрядів з різними позиціями(символами):

У метриці Лі

де .

У модульній метриці , тобто слід виконува ти віднімання за модулем q.

Відзначимо, що коли значення кодової відстані для двійко вого коду в різних матрицях збігаються, для недвійкового код; при q = 3 значення d в метриках Хеммінга та Лі також збіга ються. При q > З значення d у різних метриках різняться.

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

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