ЦЕЛЬ РАБОТЫ
Изучение принципа эффективного кодирования источника дискретных сообщений.
ДОМАШНЕЕ ЗАДАНИЕ
1. Изучить принцип эффективного кодирования источника дискретных сообщений (метод Хаффмена).
2. Осуществить кодирование каждого сообщения алфавита (см. таблицу 1), используя двоичный код:
• равномерный;
• код Хаффмена, в соответствии с заданным вариантом.
Таблица 1 Вероятности появления сообщений алфавита
Знак
а1 0,07
а2 0,09
а3 0,01
а4 0,23
а5 0,27
а6 0,16
а7 0,17
3. Определить значения и .
4. Рассчитать значения и
.
Осуществим кодирование каждого сообщения алфавита равномерным кодом. При кодировании сообщений данного источника двоичным, равномерным кодом, потребуется двоичных элементов на кодирование каждого сообщения. К=7. .
Таблица 2. Кодирование при помощи двоичного равномерного кода.
Знак
Код 000 001 010 011 100 101 110
Определим значение .
Если вероятности появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равна .
.
В данном случае каждое сообщение источника имеет информационную емкость бит, и очевидно, что для его кодирования (перевозки) требуется двоичная комбинация не менее элементов. Каждый двоичный элемент, в этом случае, будет переносить 1 бит информации.
Осуществим кодирование каждого сообщения алфавита методом Хаффмена.
Алгоритм кодирования Хаффмена состоит в следующем:
- сообщения располагаются в столбец в порядке убывания вероятности их появления.
- два самых маловероятных сообщения и объединяем в одно сообщение , которое имеет вероятность, равную сумме вероятностей сообщений , т. е. . В результате получим сообщения , вероятности которых . Полученные сообщения вновь располагаем в порядке убывания вероятностей.
- Повторяем первые шаги до тех пор, пока не получим единственное