3.3.2. Дискретные стационарные источники
В
предыдущем разделе мы описали эффективное кодирование выхода дискретного
источника без памяти (ДИБП). В этом разделе мы рассмотрим дискретные источники,
для которых последовательность символов выхода является статистически
зависимой. Мы ограничим наше исследование источниками, которые являются
статистически стационарными (однородными во времени).
Оценим
энтропию некоторой последовательности символов от стационарного источника. Из
определения в (3.2.13) и результата, данного в (3.2.15), энтропия блока случайных
переменных 
,
…
равна
, (3.3.14)
где
-
условная энтропия 
-го
символа при условии, что источник выдал предыдущие 
символов. Энтропия на символ
для 
-символьного
блока определяется как
. (3.3.15)
Мы
определяем количество информации стационарного источника как энтропию на символ
в (3.3.15) в пределе при 
, т.е.
. (3.3.16)
Существование
этого предела установлено ниже.
В
качестве альтернативы мы можем определять энтропию на символ источника как
условную энтропию 
в пределе при . К счастью, этот предел
также существует и идентичен пределу в (3.3.16). То есть
. (3.3.17)
Этот
результат также установлен ниже. Наше изложение использует подход Галлагера
(1968). Во-первых, мы покажем, что
(3.3.18)
для
. С учётом
предыдущего результата, согласно которому наложение условий на случайную
переменную не может увеличивать её энтропию, мы имеем
. (3.3.19)
В
силу стационарности источника имеем
. (3.3.20)
Следовательно,
(3.3.18) следует немедленно. Этот результат демонстрирует, что - не возрастающая
последовательность (с ростом ).
Во-вторых,
мы имеем результат
, (3.3.21)
который
следует непосредственно из (3.3.14) и (3.3.15) и того факта, что последний член
в сумме (3.3.14) является нижней границей для каждого из остальных 
членов.
B-третьих,
по определению 
мы
можем записать
что
приводит к
. (3.3.22)
Следовательно,
- не
возрастающая последовательность (с ростом ).
Поскольку
и
условная энтропия не отрицательны и не возрастающие (с
ростом ),
оба предела должны существовать. Их предельные выражения могут быть установлены
с использованием (3.3.14) и (3.3.15), чтобы выразить 
как
Так
как условная энтропия не возрастает, первый член в квадратных скобках является
верхней границей для других слагаемых. Следовательно,
. (3.3.23)
Для
фиксированного в
пределе для (3.3.23) при 
получаем
. (3.3.24)
Но
(3.3.24) справедливо для всех ; следовательно, это справедливо и для . Поэтому
. (3.3.25)
С
другой стороны, с учётом (3.3.21) мы получаем в пределе для
, (3.3.26)
устанавливает
(3.3.17).
Теперь
предположим, что мы имеем дискретный стационарный источник, который даёт 
символов с
энтропией на символ 
. Мы можем кодировать
последовательность символов кодом Хаффмена переменной
длины, который удовлетворяет префиксному условию при использовании процедуры,
описанной в предыдущем разделе. Результирующий код имеет среднее число бит для
блока с символами,
который удовлетворяет условию
. (3.3.27)
Деля
обе части (3.3.27) на , мы получаем границы для среднего
числа 
бит
на исходный символ как
. (3.3.28)
Увеличивая
размер блока ,
мы можем приближаться к сколь угодно близко, и в пределе,
когда 
, 
удовлетворяет
соотношению
, (3.3.29)
где
стремится
к нулю как 
.
Таким образом, эффективное кодирование стационарных источников может быть
выполнено, если кодировать большие блоки символов в кодовые слова. Мы должны
подчеркнуть, однако, что конструкция кода Хаффмена требует знания совместных ФПВ
для -символьных
блоков.
