бітову довжину, вони можуть бути декодовані єдиним чином.
Цими властивостями володіє алгоритм Хаффмана [7], заснований на елегантною і простій процедурі побудови дерева ймовірностей.
Середня довжина слів L, знаходиться в діапазоні:
Н (В) < L < Н (В) +1 біт / піксел і L,> 1 біт / піксель, тобто середня довжина слів не більше ніж на 1 біт / піксель більше ентропії, але не менше 1 біт / піксел (в граничному випадку, коли ентропія дорівнює нулю).
Принцип побудови дерева ймовірностей можна досить про сто пояснити на конкретному прикладі. Нехай для передачі зображення використовується 8 рівнів квантування, розподіл яких визначається гистограммой з наступними даними:
Р (b0) - Р (b5)=Р (b6)=Р (b7)=0,06; Р (b,)=0,23; Р (b2)=0,30; Р (bз)=0.15; Р (b4)=0,08.
Дерево будується справа наліво наступним чином (малюнок 9 - верхня діаграма):
в секції I рівні пікселів упорядковано ймовірності від найбільшої до найменшої зверху вниз; при рівності Р (bi)=P (bj) вище ставиться рівень bi < bj;
в секції II дві самі нижні гілки об'єднуються у вузол, їх ймовірності складаються, і вузол утворює нову гілку; загальна кількість
кількість гілок зменшується на одну і вони знову упорядковано ймовірності від найбільшої до найменшої; в секціях III і IV і т.д. проводяться операції, аналогічні проведеним у секції II до тих пір, поки не залишиться одна гілка з імовірністю, рівною 1.
Все це дерево можна перебудувати (малюнок 9 - нижня діаграма), прибравши перетину.
Кодування здійснюється рухом зліва направо по дереву кожному кодованого рівню bi.
При цьому на кожному вузлі коду приписується, наприклад, двійковий «0» якщо здійснюється крок вгору і «1», якщо здійснюється крок вниз. Таким чином, для даного випадку найбільш імовірні значення і b2 кодуються двухбітовий кодом, величини b3 і b4 - трехбітовим кодом, а найменш вірогідні значення b0, b5, b6 і b7 - четирехбітовим кодом (на малюнку 9 - нижня діаграма, - вказані праворуч). Не важко зрозуміти, що ці коди легко помітні:
якщо другий біт коду є двійковим нулем, то код - двухбітовий; в іншому випадку кількість біт в коді більше двох;- Якщо третій біт коду є двійковим нулем, то код трехбітовий; в іншому випадку кількість біт в коді дорівнює чотирьом. Приймач декодує інформацію, використовуючи те ж саме дерево, рухаючись вве?? Х при отриманні «0» і вниз при отриманні «1». Середня бітова швидкість в даному випадку L,=2,71 біт / піксель при ентропії=2,68 біт / піксель (тобто L, практично збігається з Н).
Використовуються неадаптівний і адаптивний варіанти хаффманского кодування. У першому випадку перед передачею повідомлення передається таблиця щільності ймовірностей, якщо вона заздалегідь невідома на приймальній стороні. При адаптивному варіанті кодування таблиця щільності ймовірностей обчислюється як на передавальній, так і на приймальній стороні в міру надходження даних. При цьому до початку кодування початково передбачається, наприклад, равновероятно розподіл рівнів пікселів.
Розглянутий вище приклад показує високу ефективність хаффмановской процедури при відносно рівномірному розподілі рівнів пікселів.
