Кодування Хаффмана

Найвідоміший метод скорочення кодової надмірності був запропонований Хаффманом. При незалежному кодуванні символів джерела інформації, коди Хаффмана забезпечують найменше число кодових символів (бітів) на символ джерела. У термінах теореми кодування без шуму (Розділ 1.3.3), результат є оптимальним для фіксованого значення n, при умові, що символи джерела кодуються окремо.

Першим кроком у підході Хаффмана є побудова серії (безлічі рівнів) зредукованих джерел шляхом послідовності ймовірностей розглянутих символів і «склеювання» символів з найменшими ймовірностями в один символ, який буде заміщати їх у редукованому джерелі наступного рівня.

Рис.1.11. Модифікації джерела по Хаффману.

Цей процес ілюструється на Рис. 8.11 для двійкового кодування (аналогічно можуть бути побудовані К -символьні коди Хаффмана). У двох лівих колонках гіпотетичний набір символів джерела та їх ймовірності впорядковані зверху вниз у порядку знищення ймовірностей. Для формування першої редукції джерела, символи з найменшими ймовірностями - в даному випадку 0,06 і ​​0,04 - об'єднуються в деякий «складовий символ» з сумарною ймовірністю 0,1. Цей складовий символ і пов'язана з ним ймовірність поміщаютьються в список символів редукованого джерела, який знову упорядковується в порядку знищення значень отриманих ймовірностей. Цей процес повторюється до тих пір, поки не утвориться модифіковане джерело всього лише з двома, що залишилися символами (сама права колонка на малюнку).

Другий крок в процедурі кодування по Хаффману полягає в кодуванні кожного з модифікованих джерел, починаючи з джерела з найменшим числом символів (тобто правого на Рис. 1.11), і повертаючись назад до вихідного джерела. Для джерела з двома символами найменшим двійковим кодом є, звичайно, символи 0 і 1. Як показано на Рис. 1.12, ці символи приписуються символам джерела праворуч (вибір символів довільний - змінні 0 на 1 і навпаки дасть абсолютно той же результат). Оскільки символ поточного модифікованого джерела, що має ймовірність 0,6, був отриманий об'єднанням двох символів попереднього модифікованого джерела, то кодовий біт 0, вибраний для даного варіанта, приписується кожному з двох відповідних символів попереднього джерела, потім ці коди довільним чином доповнюються символами 0 і 1, для відмінності їх один від одного. Ця операція потім повторюється для модифікованих джерел всіх інших рівнів, поки не буде досягнутий рівень вихідного джерела. Результуючий код приведений в самій лівій колонці (Код) на Рис. 1.12. Середня довжина цього коду складе:

Рис. 1.12. Процедура побудови коду Хаффмана.

біта/символ.

Оскільки ентропія джерела дорівнює 2,14 біта/символ, то, згідно (1.3-21), ефективність коду Хаффмана складе 0,973.

Процедура Хаффмана будує оптимальний код для набору символів і їх ймовірностей за умови, що символи кодуються по одному. Після того, як код побудований, процес кодування/декодування здійснюється простим табличним перетворенням. Код Хаффмана є миттєвим однозначно декодіруемий блоковою кодом. Він називається блоковим кодом, оскільки кожен символ джерела відображається в фіксовану послідовність кодових символів. Він є миттєвим, тому що кожне кодове слово в рядку кодових символів може бути декодовано незалежно від подальших символів. Він є відповідно декодованим, тому будь-який рядок з кодових символів може бути декодована єдиним чином. Таким чином, будь-який рядок кодованих по Хаффману символів може декодувати аналізом окремих символів в рядку зліва направо. Для двійкового коду, представленого на Рис. 1.12, аналіз зліва направо показує, що в закодованому рядку 010100111100 першим правильно кодовим словом є 01010, яке є код для символу . Наступним правильним кодовим словом є 011, що відповідає символу . Продовжуючи ці дії, отримаємо декодоване повідомлення у вигляді .

Поиск по сайту: