Независимых сообщений.

При заданном ансамбле из N независимых сообщений с энтропией возможно так закодировать сообщения ансамбля посредством последовательности символов, что среднее число символов на сообщение удовлетворяет неравенству

, (3.1)

где - основание кода. Среднее число символов на сообщение не может быть сделано меньше, чем .

Величина - количество информации, приходящееся на один символ при кодировании кодом с основанием D. (При кодировании двоичным кодом =1)

Доказательство. Рассмотрим левую часть неравенства, составим разность и используем неравенство , где знак равенства реализуется при z = 1.

. (3.2)

Рассмотрим разность . Пусть - количество символов, употребляемых для кодирования -го сообщения, - наибольшее количество символов, употребляемых для кодирования сообщения в ансамбле X. Число кодов, содержащих символов, которое можно было бы создать, исходя из узла, состоящего из символов, равно . (Для иллюстрации этого предложения на рисунке 3.4 выделено сообщение , имеющий код 100, т. е. . Наибольшее число символов на пятом уровне. На рисунке показаны ветви, исходящие из кода 100 на третьем уровне и останавливающиеся на пятом уровне. Число неиспользуемых кодов равно .)

Сумма всех неиспользуемых кодов не превышает числа кодов, образованных разрядными кодами, т.е или

(3.3)

Неравенство (3.3) называется неравенством Крафта. Используя неравенство Крафта, из (3.1) получим

. (3.4)

Знак равенства в (3.2) достигается тогда, когда

. (3.5)

Из выражения (3.5) получим

, . (3.6)

Как видно из (3.6), чем меньше вероятность реализации события , тем больше требуется символов для кодирования этого сообщения. Число символов - величина целая, но на практике при произвольной вероятности получим дробную величину. Поэтому величину округляют до ближайшего целого числа

, (3.7)

где .

Умножим левую и правую части равенства (6) на и просуммируем полученное выражение

. (3.8)

Положим, .Тогда после соответствующих подстановок получим правую часть неравенства (3.1)

. (3.9)

Как видно из неравенства (1) среде число символов, применяемое при кодировании, зависит от метода кодирования и распределения вероятностей реализации сообщений. Теорема не отвечает на вопрос, как оптимально кодировать сообщения, она показывает границы среднего числа символов.

- шум кодирования.