Средняя длина кода из таблицы 1 будет равна

Дата: 2025-05-01; Просмотры: 3

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Скачать

бит,

что совпадает со значением энтропии:

бит.

Еще одним способом построения оптимальных кодов является метод Хаффмана. Код Хаффмана строится следующим образом:

1) располагают символы в порядке убывания их вероятностей;

2) складывают вероятности двух последних символов и из них образуют новый составной символ с вероятностью, равной получившейся сумме;

3) повторяют шаги 1 и 2, пока не останется только один символ с вероятностью 1;

4) приписывают компонентам составных символов 0 и 1 – первой компоненте приписывают 0, а второй – 1.

Покажем процесс построения кодов Хаффмена для алфавита сообщений

X = (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈)

с распределением вероятностей появления символов

.

1. Исходный список букв X = {x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈} уже упорядочен, так как .

2. Объединим буквы x₇ и x₈ в одну букву x¹ с вероятностью и переупорядочим список:

, X¹ = {x₁, x₂, x₃, x₄, x¹, x₅, x₆}.

3. Повторим шаг 2 до тех пор, пока не останется одна буква в списке:

, X² = {x₁, x₂, x₃, x₄, x¹, x²};

, X³ = {x₁, x₂, x³, x₃, x₄};

, X⁴ = {x₁, x₂, x³, x⁴};

, X⁵ = {x⁵, x₁, x₂};

, X⁶ = {x⁵, x⁶};

, X⁷ = {x⁷}.

4. Присвоим двоичные коды символам:

x⁷: x⁵ = 0, x⁶ = 1;

x⁶: x₁ = 10, x₂ = 11;

x⁵: x³ = 00, x⁴ = 01;

x⁴: x₃ = 010, x₄ = 011;

x³: x¹ = 000, x² = 001;

x²: x₅ = 0010, x₆ = 0011;

x¹: x₇ = 0000, x₈ = 0001.

Таким образом, получены следующие коды исходных символов:

x₁ = 10, x₂ = 11, x₃ = 010, x₄ = 011, x₅ = 0010, x₆ = 0011, x₇ = 0000, x₈ = 0001.

Средняя длина кода равна

бит,

что совпадает со средней длиной кода Шеннона-Фано и с энтропией.

Способом добиться наименьшей средней длины кода на один символ является блочное кодирование. При блочном кодировании коды присваиваются не отдельным символам сообщений, а их сочетаниям. При увеличении числа символов в сочетании средняя длина кода на один символ приближается к энтропии. Например, пусть имеются две буквы алфавита – A и B, с вероятностями появления 0.9 и 0.1 соответственно. Закодировать их можно, присвоив 0 одному символу и 1 – другому:

A = 0, B = 1.

Средняя длина кода в этом случае будет равна 1 биту:

,

тогда как энтропия равна

бит.

Избыточность составляет около 53%. Если же закодировать двухбуквенные сочетания X_iX_j, X_i, X_j Î {A, B} с вероятностями p(X_iX_j) =p_ip_j, то по методу Шеннона-Фано можно получить коды, представленные в таблице 2.

Таблица 2

Блочное кодирование Шеннона-Фано

Тогда средняя длина кода двухбуквенного блока будет равна бит, а на одну букву будет приходиться бит. Избыточность в этом случае будет составлять уже только около 17%. Если мы возьмем сочетания из трех букв, то получим еще лучший результат и т.д. Увеличивая длину блоков можно как угодно близко приблизиться к оптимальному значению энтропии.

2. Порядок выполнения лабораторной работы

1. Ознакомиться с основными сведениями об оптимальном кодировании.

2. Получить задание на выполнение лабораторной работы.

3. Выполнить необходимые расчеты.

4. Сделать выводы о свойствах кодов.

5. Оформить отчет о выполнении лабораторной работы.

6. Ответить на контрольные вопросы.

3. Контрольные вопросы

1. В чем заключается кодирование и декодирование сообщений?

2. Что такое префиксные коды?

3. В чем заключается неравенство Крафта?

4. Как определить нижний предел средней длины кода?

5. Каковы принципы построения оптимальных кодов?

6. При каком условии равномерный код будет оптимальным?

7. Как построить коды Шеннона-Фано?

8. Как построить коды Хаффмена?

9. В чем заключается блочное кодирование?

4. Задания на лабораторную работу

1. Определить вероятности появления символов заданного источника с алфавитом A = {a, b, c, d} из таблицы 3 (использовать частоты символов).

2. Определить энтропию сообщения.

3. Построить коды Шеннона-Фано и Хаффмана для отдельных символов.

4. Построить коды Шеннона-Фано и Хаффмана для двухбуквенных блоков символов.

5. Закодировать сообщение.

6. Декодировать сообщение.

7. Определить среднюю длину и избыточность для всех кодов.

8. Определить наиболее оптимальное кодирование для источника сообщений.

Таблица 3

Сообщения дискретного источника