Теория информации
Конспект лекций
назад | содержание | вперед

5. ПОЧТИ ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

 

5.1 Код Шеннона

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

Код Шеннонапозволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме  Шеннона  

 


Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Упорядочим символы исходного алфавита  по убыванию их вероятностей .

2. Вычислим величины ,  которые называются кумулятивные вероятности


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

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова Li из соотношения

 

 

Пример 5.1.1. Пусть источник имеет алфавит  с вероятностями


Построенный код приведен в таблице 6.

Таблица 6 Код Шеннона

 

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана (H = 2.37), сравним его со значением средней длины кодового слова кода Шеннона



что полностью соответствует утверждению теоремы Шеннона.

 

 

Алгоритм на псевдокоде


 Построение кода Шеннона


Обозначим
n – количество символов исходного алфавита
P – массив вероятностей, упорядоченных по убыванию
Q– массив для величин Qi
L – массив длин кодовых слов
C – матрица элементарных кодов

 

 

наверх

 


назад | содержание | вперед