трібно для передачі повідомлень даного джерела?
Відповідь на це запитання дав Шеннон.
Шеннон показав, що
. Не можна закодувати повідомлення двійковим кодом так, що б середня довжина кодового слова була чисельно менше величини ентропії джерела повідомлень. p>. Існує спосіб кодування, при якому середня довжина кодового слова дещо відрізняється від ентропії джерела
.
Залишається вибрати відповідний спосіб кодування.
Ефективність застосування оптимальних нерівномірних кодів може бути оцінена:
1. Коефіцієнтом статистичного стиснення, який характеризує зменшення числа довічних елементів на повідомлення, при застосуванні методів ефективного кодування в порівнянні з рівномірні
В
Коефіцієнт відносної ефективності
В
- дозволяє порівняти ефективність застосування різних методів ефективного кодування.
У нерівномірних кодах виникає проблема поділу кодових комбінацій.
Рішення даної проблеми забезпечується застосуванням префіксних кодів.
префіксних називають код, для якого ніяке більш коротке слово не є початком іншого більш довгого слова коду. Префіксние коди завжди однозначно декодіруемий. p> Введемо поняття кодового дерева для безлічі кодових слів.
Наочне графічне зображення безлічі кодових слів можна отримати, встановивши відповідність між повідомленнями і кінцевими вузлами двійкового дерева. Приклад двійкового кодового дерева зображений на малюнку. 3.2.1. p> Дві гілки, що йдуть від кореня дерева до вузлів першого порядку, відповідають вибору між 0 і 1 в якості першого символу кодового слова: ліва гілка відповідає 0, а права - 1. Дві гілки, що йдуть з вузлів першого порядку, відповідають другому символу кодових слів, ліва означає 0, а права - 1 і т. д. Ясно, що послідовність символів кожного кодового слова визначає необхідні правила просування від кореня дерева до кінцевого вузла, відповідного розглядався повідомленням .
В
Рис. 3.2.1 Кодова дерево
Формально кодові слова можуть бути приписані також проміжним вузлам. Наприклад, проміжного вузла другого порядку на Рис.3.2.1 можна приписати кодове слово 11, яке відповідає першим двом символам кодових слів, відповідних кінцевим вузлам, породжуваних цим вузлом. Однак кодові слова, відповідні проміжним вузлам, не можуть бути використані для представлення повідомлень, так як в цьому випадку порушується вимога префіксних коду. p> Вимога, щоб тільки кінцеві вузли зіставлялися повідомленнями, еквівалентно умові, щоб жодне з кодових слів не співпало з початком (префіксом) довшого кодового слова.
Будь-який код, кодові слова якого відповідають різним кінцевим вершин деякого двійкового кодового дерева, є префіксним, тобто однозначно декодіруемий.
Код Хаффмана
Одним з часто використовуваних методів ефективного кодування є так званий код Х...
