2015-02-27
1015
Если разобьем дерево на уровни и тогда каждому коду можно присвоить определённый вес.
- вес j -кода j=1,М, где М - число допустимых кодов, k - уровень дерева. Дерево может иметь и более двух ветвей D>2.
Тогда вес j - кода будет равен 
, где D - основание системы счисления.
Теорема 1. Неравенство Крафта.
Неравенство 
является необходимым и достаточным условием существования кодовых слов, соответствующих концевым узлам дерева с длинами, равными kj.
Теорема 2. Средняя длина кода 
меньшая, чем 
является недостижимой ни при каком кодировании.
Доказательство:
Покажем, что
Теорема 3. Можно указать такой способ кодирования равно распределенных независимых сообщений, что средняя длина кода будет удовлетворять следующим требованиям:
Доказательство.
Пусть D=2, M=20. В этом диапазоне заведомо имеется одно целое число
Теорема 4. Существуют такие способы кодирования для достаточно длинного сообщения x1, x2, …, что средняя длина кодового слова может быть сделана сколь угодно близкой к 
.
Доказательство. Возьмем произвольное целое N>1 и разобьем последовательность x1, x2, …, на группы N случайных величин. Каждую такую группу будем рассматривать как одну случайную величину Y=(x1, x2, …,xN) и применим к ней теорему (3).
,
где HY=NHX, 
средняя длина слова, передающего сообщение Y=(x1, x2, …,xN). Очевидно, что 
, тогда получим
Увеличивая N, Величину 1/N можно сделать сколь угодно малой, что доказывает теорему.
