Теория информации |
Конспект лекций |
4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ
4.2 Теоремы Шеннона
Взаимосвязь между средней длиной кодового слова и энтропией дискретного вероятностного источника при побуквенном кодировании выражает следующая теорема.
Теорема 1 (Шеннон). Для бернуллиевкого источника с алфавитом и вероятностями
,
и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии
и можно построить разделимый побуквенный код, у которого средняя длина кодового слова превосходит энтропию не больше, чем на единицу:
Можно получить более сильные результаты, если кодовые слова приписывать не отдельным буквам, а сообщениям (блокам из L букв) источника. Так, для неравномерных блоковых кодов справедлива следующая теорема.
Теорема 2. Пусть - энтропия на букву в блоке длины L дискретного источник. Тогда существует префиксный код для кодирования блоков длины L, такой, что средняя длина кодового слова
будет удовлетворять неравенствам:
Кроме того, в случае бернуллиевского стационарного источника для любого можно выбрать достаточно большое L, чтобы величина
удовлетворяла неравенствам:
и левое неравенство для никогда не нарушается для разделимого кода.