Глава
5.
Стационарные
дискретные
источника
с
памятью
Теорема
5.5.1.
Теорема
кодирования
стационарных марковских ис-
точников с памятью г и энтропией Н^х).
Для блока длины L > г
существует
D-ичный префиксный код, в
котором средняя длина кодового слова п удовлетворяет неравенству
L
Из
разложения марковского источника на иодисточники без па-
мяти непосредственно вытекает стратегия оптимального кодирова-
ния.
Если начальные состояния известны, то при кодировании источ-
ников
все последующие состояния однозначно определены. При этом
в
передатчике и приемнике для каждого множества нодисточников
возможно провести кодирование и декодирование Хаффмана, учи-
тывая распределение вероятностей символов и состояний.
Практическая
реализация кодов Хаффмана показывает, что для
достижения существенного кодового выигрыша, необходимо кодиро-
вать блоки достаточно большой длины. Кроме этого, базовые со-
стояния
всегда
должны определяться г символами для того, чтобы
переход
к блокам большей длины был относительно несложным.
Предлагаемая простая стратегия полностью
учитывает
память
источника и, следовательно, в предельном случае, позволяет полу-
чить оптимальный префиксный код.
Кодирование
стационарного
марковского
источника
X с памя-
тью г и энтропией, равной Н^Х).
1. Объединить в блоки / = г + 1 символов источника.
2. Провести
кодирование
Хаффмана
для блоков.
3. Если средняя длина кодового слова на символ существенно от-
личается от энтропии Н
Ж
(Х), то увеличить длину блока за
счет
последующих символов. Провести кодирование Хаффмана для
блоков большей длины. Продолжить этот процесс до
удовле-
творительного приближения средней длины кодового слова к
энтропии.
Пример:
Кодирование марковского источника с памятью г = 2
(продолжение).
Проверим эффективность предложенного алгоритма на числен-
ном
примере из предыдущего раздела.