Код

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

1. Кодування

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

2. Кодові дерева

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

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

3. Префіксний код

Префіксним називається код, який не має жодного кодового слова, яке було б префіксом (початком) будь-якого іншого кодового слова даного коду. Будь префіксний код є разделімие (тобто будь-яку послідовність кодових слів завжди можна однозначно розділити на окремі з них). ^[1] Прикладами префіксних кодів є коди Шеннона, Шеннона-Фано і Хаффмана.

4. Приклади

Рівномірний кодування: для алфавіту з m _{1 символ} використовуються кодові слова з довжиною , Де up - округлення до більшого цілого. У цьому випадку невикористаними залишаються кодових слів, а іншим проставляються у відповідність символи первинного алфавіту. Код Бодо має фіксовану довжину 5 символів.

Префіксние коди: Код Шеннона-Фано - перший алгоритм нерівномірного кодування. Код Хаффмана - відомий метод побудови оптимального нерівномірного коду (ОНК) з використанням дерев. Арифметичне кодування - узагальнення коду Хаффмана.

Література

Цимбал В. П. Теорія інформації та кодування. - К.: Вища Школа, 1977. - 288 с.

Примітки