ке символами джерела могут буті як значення яскравості зображення, так и виходи операцій їх відображення (різниці значень елементів, довжина серій і т.д.).
кодування Хаффмана
Найвідомішій метод скороченню кодової надмірності БУВ запропонованій Хаффманом. При Незалежності кодуванні сімволів джерела информации, коди Хаффмана забезпечують найменша число кодових сімволів (бітів) на символ джерела. У термінах теореми кодування без шуму (Розділ 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, что відповідає символу. Продовжуючи ЦІ Дії, отрімаємо декодоване ПОВІДОМЛЕННЯ у виде.
Майже оптімальні нерівномірні коди
Побудова двійкового оптимального коду Хаффмана є Незвичайна Завдання, коли нужно кодуваті велику Кількість сімволів. Для загально випадка J вихідних сімволів необходимо побудуваті J - 2 редукцій джерела (див. Рис. 1.11) i віконаті J - 2 прівласнення коду (див. Рис. 1.12). Так, побудова оптимального коду Хаффмана для зображення з 256 рівнямі яркостей, требует 254 редукції джерела и 254 прісвоєння коду. Зважаючі на Обчислювальна складність цього Завдання, іноді доводитися жертвуваті кодів ефектівністю для Спрощення кодової зелених сандалів.
У Табліці 1.5 наведено Чотири нерівномірніх коди, Які...
