Курсовая работа: Расчет информационных характеристик источников сообщений сигналов и кодов

3.3 Задача № 3.84

Закодировать двоичным кодом Хаффмана ансамбль сообщений

А1	А2	А3	А4	А5	А6	А7	А8	А9	А10	А11	А12
0,082	0,122	0,503	0,04	0,012	0,002	0,005	0,034	0,124	0,006	0,0395	0,0305

Закодировать произвольную комбинацию, состоящую из пяти символов ансамбля А; Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля А; Определить среднее количество символов разработанного кода Хаффмана, приходящихся на одно сообщение из ансамбля А; Рассчитать эффективность разработанного кода.

Решение :

Для удобства закодирования расположим вероятности появления сообщений в порядке убывания. Две последние вероятности объединяем в одну вспомогательную букву, которой приписывается суммарная вероятность. Вероятности, не учитывающиеся в объединении, и суммарная вероятность снова расположим в порядке убывания. Полученный ряд вероятностей записываем в таблицу и две последние вновь объединяем. Процесс будем повторять до последней вспомогательной буквы, с вероятностью, равной единице.

А3	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	1
А9	0,124	0,124	0,124	0,124	0,124	0,124	0,124	0,1555	0,2175	0,2795	0,497
А2	0,122	0,122	0,122	0,122	0,122	0,122	0,122	0,124	0,1555	0,2175
A1	0,082	0,082	0,082	0,082	0,082	0,082	0,0955	0,122	0,124
А4	0,04	0,04	0,04	0,04	0,0555	0,0735	0,082	0,0955
А11	0,0395	0,0395	0,0395	0,0395	0,04	0,0555	0,0735
А8	0,034	0,034	0,034	0,034	0,0395	0,04
А12	0,0305	0,0305	0,0305	0,0305	0,034
А5	0,012	0,012	0,013	0,025
А10	0,006	0,007	0,012
А7	0,005	0,006
А6	0,002

Затем строится кодовое дерево, в процессе которого осуществляется кодирование: верхняя точка дерева равна единице; из нее направляется две ветви, причем, ветви с большей вероятностью приписывается значение «1», а с меньшей – «0». Такое последовательное ветвление продолжается до тех пор, пока не добираются вероятности каждой буквы.

Рис. 3.1

Затем, двигаясь по кодовому дереву сверху вниз, записываем для каждой буквы соответствующую ей кодовую комбинацию:

P1 = 0,82	0111	n1 = 4
P2 = 0,122	001	n2 = 3
P3 = 0,503	1	n3 = 1
P4 = 0,004	0000	n4 = 4
P5 = 0,012	000100	n5 = 6
P6 = 0,002	00010110	n6 = 8
P7 = 0,005	00010111	n7 = 8
P8 = 0,034	01100	n8 = 5
P9 = 0,124	010	n9 = 3
P10 = 0,006	0001010	n10 = 7
P11 = 0,0395	01101	n11 = 5
P12 = 0,0305	00011	n12 = 5

Выберем из ансамбля А произвольную комбинацию из пяти символов и закодируем их полученным кодом Хаффмана:

А₁ А₂ А₇ А₆ А₄

011100100010111000101100000.

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является двоичным, тогда основание кода N = 2 . Следовательно:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

, где

М – объем алфавита кода (М = 2 );

P_i – вероятность появления события;

n – количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

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

3.4 Задачи № 3.114