Теория информации |
Конспект лекций |
7. АДАПТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ
7.1 Основная идея адаптивного кодирования
При решении реальных задач истинные значения вероятностей источника, как правило, неизвестны или могут изменяться с течением времени, поэтому для кодирования сообщений применяют адаптивные модификации методов кодирования, которые дополнительно включают в себя оценку неизвестной статистики источников.
Большинство адаптивных методов для учета изменений статистики исходных данных используют так называемое окно. Окном называют последовательность символов, предшествующих кодируемой букве, а длиной окна - количество символов в окне.
Обычно окно имеет фиксированную длину и после кодирования каждой буквы сообщения окно передвигается на один символ вправо. Таким образом, код для очередной буквы строится с учетом информации, хранящейся в данный момент в окне (см. рис. 8).
Рисунок 8 Схема перемещения окна при кодировании
При декодировании окно передвигается по закодированному сообщению аналогичным образом. Информация, содержащаяся в окне, позволяет однозначно декодировать очередной символ.
Оценка избыточности при адаптивном кодировании является достаточно сложной математической задачей, поскольку общая избыточность складывается из двух составляющих: избыточность кодирования и избыточность, возникающая при оценке вероятностей появления символов, поэтому эффективность методов адаптивного кодирования зачастую оценивают экспериментальным путем.
Однако для всех методов адаптивного кодирования, которые приводятся в этой главе, справедлива следующая теорема:
Теорема. Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству
,
где H – энтропия источника информации, C – константа, зависящая от размера алфавита источника и длины окна.