Глава 5. Стационарные дискретные источники с памятью I
5.2.
Теорема кодирования источников
2 /
Теперь мы можем дополнить теорию информации еще одной теоре-
мой.
Окалывается, что объединяя события источника в блоки длимы
L
и кодируя эти блоки, средняя длина кодового слова на событие
может достигнуть энтропию источника Н
х
(х) при
L—>оо
как угодно
близко.
При этом память источника полностью учитывается.
Теорема 5.2.1.
Теорема
кодирования
стационарного дискретного ис-
точника с энтропией Hi(X).
Для блока длины L
существует
.D-ичный префиксный код, в кото-
ром средняя длина кодового слова на одно событие п удовлетворяет
неравенству
М§^§ 1
(5.14)
Теорема
(5.14)
не нуждается в специальном доказательстве. Если
мы рассматриваем блоки длины L как новые независимые события
с энтропией, равной L
•
HL{X) И применяем теорему кодирования
источников 1, то мы имеем
^1
1.
(5.15)
Разделив все члены неравенства на L, получаем среднюю длину ко-
дового слова на событие
)^ШЛ.
(5.16)
При
L —» оо, Hi(x) —» Нос(х) = Н(х) мы имеем
LH
L
(X)
LH
L
{X)
(517)
+
6
-
(5Л8)
Таким образом, для любого сколь угодно малого S,
существует
метод кодирования блоков, содержащих L > 1/6 событий, при кото-
ром для средней длины кодового слова на событие п выполняется
неравенство (5.18). Теорема кодирования источников 2 показывает,
что увеличивая длину блока L, мы можем как угодно близко подойти
к
энтропии Н(х) =
Н
оо
(х).
Однако, на практике
существуют
неко-
торые ограничения. Для того, чтобы блок из L событий мог быть