Лк 10 кодування

Кодування.

Загальні положення. Кодова комбінація, рівномірний. нерівномірне кодування, завадостійке кодування.

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

Найпростішим прикладом дискретного повідомлення є текст. Будь-який текст складається з кінцевого числа елементів: букв, цифр, розділових знаків. Їх сукупність називається алфавітом джерела повідомлення. Так як число елементів в алфавіті звичайно, то їх можна пронумерувати і тим самим звести передачу повідомлення до передачі послідовності чисел.

Так, для передачі букв українського алфавіту (їх 32) необхідно передати числа від 1 до 32. Для передачі будь-якого числа, записаного в десяткового формі, потрібно передача однією з десяти цифр від 0 до 9 для кожного десяткового розряду. Тобто для передачі букв українського алфавіту потрібно мати технічну можливість передачі і прийому десяти різних сигналів, що відповідають різним цифрам.

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

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

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

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

Коди, у яких всі комбінації мають однакову довжину, називають рівномірними. Для рівномірного коду число можливих комбінацій одно m n. Прикладом такого коду є пятізначнийкод Бодо. містить п'ять довічних елементів (m = 2, n = 5). Число можливих кодових комбінацій дорівнює 2 +5 = 32, що досить для кодування всіх букв алфавіту. Застосування рівномірних кодів не вимагає передачі розділових знаків між кодовими комбінаціями.

Нерівномірні коди характерні тим, що у них кодові комбінації відрізняються один від одного не тільки взаємним розташуванням символів, але і їх кількістю. Це призводить до того, що різні комбінації мають різну тривалість. Типовим прикладом нерівномірних кодів є код Морзе. в якому символи 0 і 1 використовуються тільки в двох поєднаннях - як поодинокі (1 і 0) або як потрійні (111 і 000). Сигнал, відповідний одній одиниці, називається точкою, трьом одиницям - тире. Символ 0 використовується як знак, що відокремлює точку від тире, крапку від точки і тире від тире. Сукупність 000 використовується як розділовий знак між кодовими комбінаціями.

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

коригувальні коди

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

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

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

Нагадаємо, що відстанню Хеммінга між двома кодовими n-послідовностями, bi і bj. яке будемо далі позначати d (i; j), є число розрядів, в яких символи цих послідовностей не збігаються.

Кажуть, що в каналі сталася помилка кратності q, якщо в кодової комбінації q символів прийняті помилково. Легко бачити, що кратність помилки є не що інше, як відстань Хеммінга між переданої і прийнятої кодовими комбінаціями, або, інакше, вага вектора помилки.

Розглядаючи всі дозволені кодові комбінації і визначаючи кодові відстані між кожною парою, можна знайти найменше з них d = min d (i; j), де мінімум береться по всім парам дозволених комбінацій. Це мінімальне кодове відстань є важливим параметром коду. Очевидно, що для простого коду d = 1.

Виявляє здатність коду характеризується наступною теоремою. Якщо код має d> 1 і використовується декодування за методом виявлення помилок, то всі помилки кратністю q

Виправляюча здатність коду при цьому правилі декодування визначається наступною теоремою. Якщо код має d> 2 і використовується декодування з виправленням помилок по найменшій відстані, то всі помилки кратністю q

Завдання кодування полягає у виборі коду, що володіє максимально досяжним d. Втім, таке формулювання завдання неповна. Збільшуючи довжину коду n і зберігаючи число кодових комбінацій М, можна отримати як завгодно велике значення d. Але таке "рішення" завдання не представляє інтересу, тому що зі збільшенням n зменшується можлива швидкість передачі інформації від джерела.

Якщо довжина коду n задана, то можна отримати будь-яке значення d, що не перевищує n, зменшуючи число комбінацій М. Тому завдання пошуку найкращого коду (в сенсі максимального d) слід формулювати так: при заданих M і n знайти код довжини n, що містить М комбінацій і має найбільшу можливу d. У загальному вигляді це завдання в теорії кодування не вирішена, хоча для багатьох значень n і М її рішення отримані.

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

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

Однак навіть при помірних значеннях n такий спосіб вельми складний. Покажемо це на прикладі. Нехай вибрана довжина кодової комбінації n = 100, а швидкість коду приймемо рівної 0.5 (число інформаційних і перевірочних символів одно). Тоді число дозволених комбінацій коду буде 2 50 10 15. Відповідно розмір таблиці буде 10010 15 = 10 17 біт10 16 байт = 10000 Тбайт.

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

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

Питання для самоконтролю

1.У чому полягає операція кодування сигналу?

2. Що таке кодова комбінація?

3.Від чого залежить число елементів в кодової групі, відповідне відліку?

4.От чого залежить стійкість коду?

5.Перечислите відомі Вам, види кодів?

6.Віди коригувальних кодів?