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

4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ

 

4.2 Теоремы Шеннона

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

Теорема 1 (Шеннон). Для бернуллиевкого источника с алфавитом  и вероятностями ,  и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии  



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


Можно получить более сильные результаты, если кодовые слова приписывать  не отдельным буквам, а сообщениям (блокам из L букв) источника. Так, для  неравномерных блоковых кодов справедлива следующая теорема.

Теорема 2. Пусть  - энтропия на букву в блоке длины L дискретного источник. Тогда существует префиксный код для кодирования блоков длины L, такой, что средняя длина кодового слова  будет удовлетворять неравенствам:



Кроме того, в случае бернуллиевского стационарного источника для любого можно выбрать достаточно большое L, чтобы величина  удовлетворяла неравенствам:



и левое неравенство для  никогда не нарушается для разделимого кода.

 

 

наверх

 


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