Расчет информационных характеристик источников сообщений сигналов и кодов (стр. 3 из 4)

.

Ответ: потенциальный минимум

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

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

Закодировать кодом Хаффмана, с объемом алфавита М=5, ансамбль

А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	1
А9	0,124	0,124	0,251
А2	0,122	0,122	0,124
A1	0,082	0,082	0,122
А4	0,04	0,0555
А11	0,0395	0,04
А8	0,034	0,0395
А12	0,0305	0,034
А5	0,012
А10	0,006
А7	0,005
А6	0,002

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

Рис.3.2

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

P1 = 0,82	24	n1 = 2
P2 = 0,122	0	n2 = 1
P3 = 0,503	3	n3 = 1
P4 = 0,004	22	n4 = 2
P5 = 0,012	233	n5 = 3
P6 = 0,002	230	n6 = 3
P7 = 0,005	231	n7 = 3
P8 = 0,034	20	n8 = 2
P9 = 0,124	1	n9 = 1
P10 = 0,006	232	n10 = 3
P11 = 0,0395	21	n11 = 2
P12 = 0,0305	234	n12 = 3

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

А₈А₇А₆А₅А₄

2023023023322.

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

;

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

.

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

;

Тогда потенциальный минимум

.

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

, где

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

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

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

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

.