Построение кодовых деревьев и таблиц эффективного кода Хаффмана

Цель работы:

Исследование методов построения кодовых деревьев на примере кода Хаффмана. Закрепление навыков синтеза структурных схем кодера и декодера кода Хаффмана.

Задание на лабораторную работу:

Разработать программный модуль для реализации кодирования / декодирования методом Хаффмана для источников сообщений с заданными статистическими характеристиками: p(S1) = 0,300, p(S2) = 0.30, p(S3) = 0.150, p(S4) = 0.100, p(S5) = 0.060, p(S6) = 0.050, p(S7) = 0.040.

Ход работы:

Теоретическая справка:

При равномерном кодировании информации на сообщение отводится одно и то же число бит, независимо от вероятности его появления. Вместе с тем логично предположить, что общая длина передаваемых сообщений уменьшится, если часто встречающиеся сообщения кодировать короткими кодовыми словами, а редко встречающиеся – более длинными. Возникающие при этом проблемы связаны с необходимостью использования кодов с переменной длиной кодового слова. Существует множество подходов к построению подобных кодов. Одним из широко используемых на практике является код Хаффмана, кодер и декодер которого имеют достаточно простую аппаратную реализацию. Процедура синтеза кода предполагает наличие априорной информации о статистических характеристиках источника сообщений. Иначе говоря, разработчику должны быть известны вероятности возникновения тех или иных сообщений (символов).