Эффективные методы кодирования низкоэнтропийных источников

• Автор: Шарова, Марина Павловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 94 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
Глава 1. Основные понятия и методы
1.1. Основные определения и понятия
1.2. Арифметическое кодирование источников
1.3. Известные методы кодирования низкоэнтропийных источников
Глава 2. Эффективное кодирование низкоэнтропийных бернуллиевских источников
2.1. Кодирование бернуллиевских источников с известной статистикой
2.2. Адаптивное кодирование низкоэнтропийных источников, эффективное с вероятностью
2.3. Кодирование источников, эффективное в среднем
2.4. Адаптивное кодирование с использованием мнимого скользящего окна
Глава 3. Низкоэнтропийные марковские источники
3.1. Алгоритм кодирования источников с известной статистикой
3.2. Адаптивные методы кодирования марковских источников
Заключение
Литература
Список работ автора по теме диссертации

ВВЕДЕНИЕ
Актуальность темы.
Задача эффективного кодирования источников является одной из центральных в теории информации, что объясняется ее теоретической важностью и многочисленными практическими приложениями к сжатию данных самой различной природы. Изучению этой задачи посвящены многочисленные работы В. Ф. Бабкина, Р. Е. Кричевского, Б. Я. Рябко, В. К. Трофимова, Ю. М. Штарь-кова, Р. Галлагера, Я. Зива, А. Лемпела, И. Риссанена, П. Элай-еса и других исследователей.
Задача кодирования обычно ставится следующим образом. Источник информации порождает сообщение X — х... ж*, вероятности появления отдельных символов которого могут быть известны или неизвестны. Необходимо поставить в соответствие каждому сообщению X кодовое СЛОВО С(Х) = С1С2 . Сцх) так5 чтобы по С(Х) можно было однозначно восстановить (декодировать) X и средняя длина Ь(Х) кодового слова по множеству всех сообщений была минимальной. Известно [32], что Ь(Х) ограничена снизу шенноновской энтропией источника. Разность между средней длиной кодового слова и энтропией называется избыточностью кода. Кроме избыточности, эффективность кода оценивается объемом памяти V кодера и декодера (в битах), который требуется при реализации метода на компьютере со свободным доступом к памяти (это модель ’’обычного” компьютера [1]), и средним временем Т кодирования и декодирования одного символа источника информации, измеряемым числом бинарных операций над однобитовыми словами.
Рассматриваются задачи кодирования источников с известной
и неизвестной статистикой. Методы, предназначенные для кодирования источников с известной статистической структурой, называют статическими (неадаптивными) методами. Адаптивные методы кодирования позволяют эффективно сжимать данные с заранее неизвестной статистикой. В настоящее время известно большое число адаптивных кодов. К ним относятся такие известные коды как арифметический [22, 35, 37], код ’’стопка книг” [12], адаптивный код Хаффмана [27, 31], частотный код [13], коды Зива-Лемпела [43, 44] и ’’быстрый” код [14, 40].
Во многих практических приложениях часто возникает задача кодирования источников с малой энтропией. Начиная с работы К. Шеннона [19], предложившего первый специальный код для таких источников, эта задача представляла и представляет интерес для исследователей, так как известно, что для низкоэнтропийных источников существуют значительно более простые методы кодирования, чем для произвольных источников. Для источников с малой энтропией ’’общие” методы кодирования (то есть методы, предназначенные для кодирования любых источников, а не только низкоэнтропийных) оказываются неэффективными. Различные методы кодирования низкоэнтропийных источников разрабатывались и изучались в работах П. Элайеса [25, 26], Э. Л. Блоха [3],
С. Голомба [29], Р. Галлагера и Д. Вурхиса [28], В. Ф. Бабкина и Ю. М. Штарькова [20], X. Танака и А. Леон-Гарсиа [41] и других исследователей.
Однако известные методы кодирования низкоэнтропийных источников не позволяют строить коды с наперед заданной избыточностью. Поэтому важной является задача построения методов, позволяющих достигать сколь угодно малой, наперед заданной

Кодируются буквы первого блока zqZqZj. Из (2.1.8) находим, что
fTiri = 1 - (6/7)3 = 381 ( 2г1 1 - (6/7)3
2/21 98’ 1 1} 1/21 49'
Значит, символ 25 = М.о кодируется с помощью кодера К с вероятностью (1 — т — rf) = 78/127. Переходим к букве zq. Из (2.1.8) следует, что
, ,.—1 381 (б/7)2 1/7 39 2 , 381 (6/7)М/7
' 2) 98 2/21 14’ k 2' 49 1/21 Т
Значит, zq = Мо кодируется с помощью кодера К2 с вероятностью
(1 — т/ — т22) = 6/13. Переходим к букве z-j. Из (2.1.8) следует, что , J J 39 6/7-1/7
(г,) =
с вероятностью т1 = 2/3. Аналогично кодируются буквы второго блока ZqZ\Z2- Так как (г/)-1 = 381/98, то zq = ЛЛ кодируется с помощью кодера К с вероятностью т = 98/381. Оставшиеся буквы 2ц И 212 кодируются с помощью кодера К с вероятностями p{zi) = р(М0) = 6/7; p(z12) = р(М2) = 1/21.
Так как в памяти хранятся вероятности только трех кодеров Ко, К{, К и счетчики нулей объема О (log ], то для предложен-
V PJ
ного метода память кодера и декодера по порядку равна памяти ”общих” методов.
Скорость кодирования и декодирования предложенного метода характеризует
Теорема 2.1.2. Пусть даны бернуллиевский источник, порождающий буквы из алфавита А = {ai,a2,..ап},п > 2, с известными вероятностями р{а),р{ач)