Пример выполнения работы

Рассмотрим 30 вариант. Согласно заданию имеем восемь сообщений: , , , , , , , . Известна вероятность появления каждого из этих сообщений: ; ; ; ; ; ; ; .

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

0,091+0,0825+0,00928+0,03591+0,2689+0,00778+0,291+0,21363=1

Построим оптимальные коды для данных восьми сообщений по алгоритму, рассмотренному в разд.2.3.4.

Разобьем исходные сообщения на две группы таким образом, чтобы сумма вероятностей в каждой группе была примерно одинакова. В результате в первую группу попадут сообщения , , и , а во вторую группу – , , и . Суммарная вероятность сообщений первой группы равна 0,091+0,0825+0,03591+0,291=0,50041. Суммарная вероятность сообщений второй группы равна 0,00928+0,2689+0,00778+0,21363=0,49959. Первую группу пометим символом 1, вторую группу – символом 0.

Первый шаг разбиения исходного множества сообщений проиллюстрирован на рис. Л1.1.

Далее по тому же принципу разобьем сообщения , , и на две группы. В результате в первую группу попадут сообщения , , , а во вторую группу – . Суммарная вероятность сообщений первой группы равна 0,091+0,0825+0,03591=0,50041. Вероятность сообщения m7 равна 0,291. Первую группу пометим символом 1, вторую группу – символом 0. Данный шаг разбиения проиллюстрирован на рис. Л1.2.

Выполним аналогичное разбиение сообщений , , и . В результате в первую группу попадет сообщение m5, а во вторую группу – , , . Вероятность сообщения равна 0,2689. Суммарная вероятность сообщений второй группы равна 0,00928+0,00778+0,21363=0,23069. Первую группу пометим символом 1, вторую группу – символом 0. Данный шаг разбиения проиллюстрирован на рис.Л.1.3.

Продолжая процесс разбиения, окончательно получим дерево, представленное на рис.Л1.4.

Концевые вершины данного дерева соответствуют исходным сообщениям. Сообщению соответствует вершина 9, – 12, – 14, – 13, – 6, – 15, – 5, – 10. Для определения кода некоторого сообщения требуется найти путь из корня дерева (вершина 1) в вершину, соответствующую данному сообщению. Код образуют пометки дуг, образующих такой путь. Например, сообщение имеет код 110, который соответствует пути 1,2,4,9.

Коды сообщений сведены в таблицу Л1.2.

Таблица Л1.2
Оптимальные коды
Сообщение	Код сообщения	Сообщение	Код сообщения
	110		01
	1111		0000
	0001		10
	1110		001

Итак, сообщение кодируется 3 битами, – 4 битами, – 4 битами, – 4 битами, – 2 битами, – 4 битами, – 2 битами, – 3 битами.

Определим среднее число бит, приходящихся на одно сообщение (n). , где - число бит, требуемое для кодирования i-го сообщения.

n= 0,0913+0,08254+0,009284+0,035914+

0,26892+0,007784+0,2912+ 0,213633=2,57557

Используя формулу , найдем энтропию.

Вывод. В лабораторной работе получены оптимальные коды для восьми сообщений с заданными вероятностями, рассчитана средняя длина кода и количество информации, приходящееся на одно сообщение (энтропия ).

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

При используемом алгоритме оптимального кодирования значение n лежит в пределе от H до .