2018-03-09
95
Взаимосвязь между средней длиной кодового слова и энтропией дискретного вероятностного источника при побуквенном кодировании выражает следующая теорема.
Теорема 1 (Шеннон). Для источника с алфавитом А= { a 1, …, an } и вероятностями pi =P (ai), 
и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии
Lcp ≥ H (p 1, …, pn)
и можно построить разделимый побуквенный код, у которого средняя длина кодового слова превосходит энтропию не больше, чем на единицу:
Lcp < H(p 1, …, pn)+ 1
Рассмотрим несколько классических побуквенных кодов, у которых средняя длина кодового слова близка к оптимальной. Пусть имеется дискретный вероятностный источник, порождающий символы алфавита А= { a 1,…, an } с вероятностями pi = P (ai).
Код Шеннонапозволяет построить почти оптимальный код с длинами кодовых слов 
. Тогда по теореме Шеннона:
.
Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:
1. Упорядочиваются символы исходного алфавита А={ a 1 ,a 2, …, an } по убыванию их вероятностей: p 1 ≥ p 2 ≥ p 3 ≥ … ≥ pn.
2. Вычисляются величины Qi, которые называются кумулятивными вероятностями:
Q 0 = 0, Q 1 = p 1, Q 2 = p 1 +p 2, Q 3 = p 1 +p 2 +p 3, …, Qn = 1.
3. Представляется Qi в двоичной системе счисления и берутся в качестве кодового слова первые 
знаков после запятой.
Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова Li из соотношения:
, 
.
Пример 1. Пусть дан алфавит A={ a 1, a 2, a 3, a 4, a 5, a 6} с вероятностями p 1=0.36, p 2=0.18, p 3=0.18, p 4=0.12, p 5=0.09, p 6=0.07. Построенный код приведен в таблице 1.
Таблица 1
Код Шеннона
| ai | Pi | Qi | Li | Кодовое слово |
| a 1 a 2 a 3 a 4 a 5 a 6 | 1/22≤0.36<1/2 1/23≤0.18<1/22 1/23≤0.18<1/22 1/24≤0.12<1/23 1/24≤0.09<1/23 1/24≤0.07<1/23 | 0 0.36 0.54 0.72 0.84 0.93 | 2 3 3 4 4 4 | 00 010 100 1011 1101 1110 |
Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана в лабораторной работе № 2 (H = 2.37), сравним его со значением средней длины кодового слова кода Шеннона:
Lср = 0.36 . 2+(0.18+0.18) . 3+(0.12+0.09+0.07) . 4 = 2.92 < 2.37 + 1,
что полностью соответствует утверждению теоремы Шеннона.
