Теоретичні відомості
Оптимальний код - Хаффмана
Один зі способів нерівномірного кодування запропонований Хаффменом. Побудова нерівномірного коду Хаффмана для передачі одного з восьми повідомлень хi з різними імовірностями подано в таблиці 4.1.
Таблиця 4.1 – Побудова нерівномірного коду Хаффмана
|
Буква |
Р(хi ) |
|
I |
|
II |
|
III |
|
IV |
|
V |
|
VI |
Код |
ni Pi |
|
А |
0.6 1 |
|
0.6 1 |
|
0.6 1 |
|
0.6 1 |
|
0.6 |
|
0.6 1 |
|
0.6 1 |
1 |
0.6 |
|
Б |
0.2 01 |
|
0.2 01 |
|
0.2 01 |
|
0.2 01 |
|
0.2 01 |
|
0.2 01 |
} |
0.4 0 |
01 |
0.4 |
|
В |
0.1 001 |
|
0.1 001 |
|
0.1 001 |
|
0.1 001 |
|
0.1 001 |
} |
0.2 00 |
|
001 |
0.3 | |
|
Г |
0.04 0000 |
|
0.04 0000 |
|
0.04 0000 |
|
0.06 0001 |
} |
0.1 000 |
|
|
|
0000 |
0.16 | |
|
Д |
0.025 00010 |
|
0.025 00010 |
|
0.035 00011 |
} |
0.04 0000 |
|
|
|
|
|
00010 |
0.125 | |
|
Е |
0.015 000111 |
|
0.020 000111 |
} |
0.025 00010 |
|
|
|
|
|
|
|
000111 |
0.09 | |
|
Ж |
0.01 0001111 |
} |
0.015 000110 |
|
|
|
|
|
|
|
|
|
0001111 |
0.07 | |
|
З |
0.01 0001110 |
|
|
|
|
|
|
|
|
|
|
|
0001110 |
0.07 |
Алгоритм побудови кодового дерева коду Хаффмана.
1. Складаємо список повідомлень які потрібно закодувати , кожному з яких відповідає його ймовірність.
2. Доти, поки число повідомлень більше одиниці повторюються наступні дії:
У списку неопрацьованих вузлів знаходимо два вузли з найменшими ймовірностями. Вони виключаються зі списку і замість них уводиться новий вузол, якому приписується сумарна ймовірність двох виключених вузлів. Новий вузол зв'язується ребрами з виключеними вузлами. Число неопрацьованих вузлів зменшується на одиницю.
Після виконання алгоритму буде отримане кодове дерево, по якому можна побудувати код, як показано в табл. 2.5.
Для отриманого в такий спосіб коду середнє число двійкових символів, що приходяться на одну букву, дорівнює
,
а надмірність коду складе
тобто величину меншу , ніж перелічені вище коди.
Зверніть увагу на той факт, що як для коду Хаффмана, так і для коду Шеннона-Фано середня кількість двійкових символів, що приходиться на символ джерела, наближається до ентропії джерела, але не дорівнює їй. Даний результат являє собою наслідок теореми кодування без шуму для джерела (першої теореми Шеннона), що стверджує:
Любе джерело можна закодувати двійковою послідовністю при середній кількості двійкових символів на символ джерела хi, як завгодно близькому до ентропії, і неможливо домогтися середньої довжини коду, меншої, ніж ентропія H(х).
Ця теорема встановлює границі в компактності представлення інформації, яких можна досягти при правильному її кодуванні.