Оптимальні нерівномірні коди. Код Хафмена

Технології кодування із компресією даних. Оптимальні нерівномірні коди

Лекція № 4.2

Теорія інформації та кодування

Вступ

В попередній лекції були розглянуті оптимальні коди Шеннона-Фано для компресії інформаційних об‘єктів, які дають змогу одержати як рівномірні так нерівномірні коди. Оскільки рівномірні оптимальні коди Шеннона-Фано не дають виграшу в стиснені даних, будемо в подальшому орієнтуватися на нерівномірні коди. Звернемо, окрім того увагу на те, що при побудові кодів цього типу слід мати такі імовірності генерації відповідних символів, що є дробовими числами із знаменниками, ступенями, які є ступенями основи коду ( , S = 1,2, …). Зрозуміло, що такі ситуації є вкрай малоймовірними.

Таким чином, при усій привабливості оптимальних кодів Шеннона-Фано слід використовувати інші нерівномірні коди із довільними значеннями ймовірностей можливих символів, що генеруються відповідним джерелом. Однією із таких технологій є код Хафмена, який розглядається в цій лекції разом із іншими технологіями.

Лекція № 4.2 − “Технології кодування із компресією даних. Оптимальні нерівномірні коди”.В лекції будуть розглянуті наступні учбові питання:

Вступ...................................................................................................... 2

1. Оптимальні нерівномірні коди. Код Хафмена................................ 3

2. Технології стиснення даних. Надлишковість даних та методи її зменшення 9

2.1. Особливості телекомунікаційних протоколів щодо
стиснення даних........................................................................................... 9

2.2. Алгоритм RLE........................................................................ 11

2.3. Алгоритми групи KWE.......................................................... 11

Алгоритм Хафмена є деревоподібним кодом, заснованим на статистичному кодуванні, тобто на кодування, яке враховує статистичні характеристики символів, тобто імовірності їх існування в усіх можливих повідомленнях.

Деревоподібним кодом називають код, кодовими словами якого є тільки ті, що відповідають кінцевим вершинам кодового дерева.

Кодове дерево – спеціальний граф, що відображає запис всіх можливих S-кових n-розрядних чисел, використовуваних як кодові комбінації для кодування повідомлень в кількості M = Sⁿ. При цьому кожне число відображається одним з вузлів графа. З кожного вузла виходить S гілок, які пов’язують цей вузол з іншими. Кількість символів, що входять до числа, відповідного даному вузлу, називається його порядком.

Розглянемо граф для двійкового трьохелементного коду (рис. 3).

1. Кодове дерево двійкового трьохелементного коду

На початковому (нульовому) ярусі розташований один вузол, який називається коренем дерева.

Кінцевим вузлом називається вузол, якщо з нього не виходить жодного ребра.

Для побудови оптимального коду на базі кодового дерева треба дотримуватися наступного:

· повідомленню з найбільшою імовірністю повинен відповідати вузол якнайменшого порядку;

· принаймні два повідомлення з мінімальною імовірністю повинні кодуватися вузлами максимального порядку;

· якщо вибрано деякий вузол порядку і, то всі вузли вищого порядку, пов’язані з ним, не можуть бути використані для кодування, інакше не виконуватиметься однозначна відмінність комбінацій, заснована на тому, що жодна з них не повинна бути початком іншої;

· для кодування повідомлень можуть не бути використані всі можливі вузли максимального порядку; це означає, що не всі вузли попереднього порядку є повними (повним називається вузол, з якого виходять всі можливі S гілок);

· якщо об’єднати всі повідомлення, закодовані вузлами і-го порядку, то вузлу (і – 1) – го порядку відповідатимуть повідомленню з еквівалентною імовірністю

.