Теория информации |
Конспект лекций |
5. ПОЧТИ ОПТИМАЛЬНОЕ КОДИРОВАНИЕ
5.1 Код Шеннона
Рассмотрим несколько классических двоичных побуквенных кодов, у которых средняя длина кодового слова близка к оптимальной. Пусть имеется дискретный вероятностный источник, порождающий символы алфавита и вероятностями
.
Код Шеннонапозволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме Шеннона
Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:
1. Упорядочим символы исходного алфавита по убыванию их вероятностей
.
2. Вычислим величины ,
которые называются кумулятивные вероятности
3. Представим в двоичной системе счисления и возьмем в качестве кодового слова первые
двоичных знаков после запятой,
.
Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова Li из соотношения
Пример 5.1.1. Пусть источник имеет алфавит с вероятностями
Построенный код приведен в таблице 6.
Таблица 6 Код Шеннона
Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана (H = 2.37), сравним его со значением средней длины кодового слова кода Шеннона
что полностью соответствует утверждению теоремы Шеннона.
Алгоритм на псевдокоде
Построение кода Шеннона
Обозначим
n – количество символов исходного алфавита
P – массив вероятностей, упорядоченных по убыванию
Q– массив для величин Qi
L – массив длин кодовых слов
C – матрица элементарных кодов