Введение к работе
Актуальность темы. В условиях современной реальности мы постоянно сталкиваемся с лавинообразным потоком информации, которую необходимо обрабатывать, хранить и передавать. Передача информации по каналам связи сопровождается ее предварительной обработкой с целью уменьшения объема информации, подлежащей передаче, защиты ее от искажения в процессе передачи и т.д. Уменьшение объема передаваемой информации напрямую связано с увеличением скорости передачи, а также экономией процессорного времени, затрачиваемого на дальнейшую обработку. Задача уменьшения объема памяти, занимаемого информацией, частично решается за счет использования методов сжатия данных и методов кодирования дискретных источников. Следует отметить, что решение задач кодирования источников используется также в теории управления, при выявлении скрытой информации, при создании большемасштабных вычислительных систем, в криптографии. Теория информации, основанная в 1948 г. К. Шенноном, служит для получения различных методов сжатия данных. Разработанные К. Шенноном, Р. Фано, Д.А. Хаффманом, И. Чисаром, Г. Катоной алгоритмы кодирования дискретных источников существенно использовали статистику сообщений, что частично препятствовало их практическому применению. Вопросы кодирования источников с неизвестной статистикой впервые рассматривались в работах А.Н. Колмогорова и Б.М. Фитингофа. В случае неизвестной статистики источника кодирование называется универсальным. Точная постановка задачи универсального кодирования принадлежит Р.Е. Кричевскому.
Исследованию свойств универсального кодирования также посвящены работы Л.Д. Дэвиссона, Т.Д. Линча, Т. Ковера, Н. Фаллера, Р.Г. Галлагера, Д. Кнута, И.С. Виттера, Б.Я. Рябко, А.Н. Фионова, М. Борроуза и Д. Виллера, А. Лемпела, Я. Зива, ТА. Велча и А.Д. Вайнера, И. Риссайнена, Ф. Уиллемса, М.Ю. Штарь-кова, В.Ф. Бабкина, В.К. Трофимова, Ч. Чокенса, С. Савари, С. Верду, В.Н. Потапова. Последним двум авторам принадлежат подробные обзорные работы.
Однако вопросы, связанные с построением оптимальных методов универсального кодирования бернуллневских, марковских и стационарных источников символами неравнозначных длительностей, оставались открытыми. Решению задач универсального кодирования дискретных источников буквами алфавита с неравнозначными длительностями и посвящена данная диссертационная работа.
Состояние вопроса. Основные понятия, используемые в работе — источник сообщений, энтропия источника, пропускная способность канала, кодирование, избыточность кодирования и т.д. — были введены Клодом Шенноном в его основополагающих работах.
Пусть Qs — множество источников с памятью s, порождающих последовательности из букв конечного входного алфавита X. В частности, По — множество
бернуллиевских источников, Поо — множество стационарных источников. Если f] С fls состоит из единственного источника G, то мы имеем дело с известным источником. Рассмотрим кодирование р, ставящее в соответствие каждому слову источника G Є П последовательности букв некоторого конечного кодового алфавита Y. Предположим, что буквы кодового алфавита могут иметь различные длительности, определяемые вектором длительностей ty = {t{y))y&Yi t(y) —длительность символа у ЄУ. Если длительности всех кодовых символов одинаковы, то ty = t\ = (1; 1; 1; ...1). Кодовый алфавит Y определяет пропускную способность канала C(ty), определяемую равенством С (ty) = logwo(iy), где ojq (t) — наибольший положительный корень уравнения Y1 ш~^у' = 1. Среднюю длительность
L (N,ip,Q,ty) букв кодового алфавита Y, приходящихся на одну букву входного алфавита при кодировании р блоков длины N источника G, назовем стоимостью кодирования. Эффективность кодирования р определяется его избыточностью, которая связывает основные характеристики источника, кодирования и канала и определяется равенством г (N,Q,p,ty) = L(N,Q,p,ty) — с^~і, где Н(0) — энтропия источника сообщений.
Избыточностью универсального кодирования блоков длины N с заданным вектором длительностей букв выходного (кодового) алфавита ty, следуя Р.Е. Кричев-скому, назовем величину
R (N, Q,tY) = inf sup г (N, Q, p, tY).
Нижняя грань в последнем равенстве берется по всем дешифруемым кодированиям. Построение хорошего кодирования при заданной длине блока — основная задача при передаче сообщений по каналу связи без шума. Решение этой задачи позволяет установить, какой избыточности можно достичь при заданном значении длины блока.
Если множество источников П содержит единственный элемент G, то величина R(N,Q,ty) совпадает с избыточностью кодирования для известного источника.
Кодирование сообщений, порожденных известным источником, как при ty = t\1 так и при ty ф t\ достаточно хорошо изучены в работах К. Шеннона, Р.Е. Кри-чевского, Г.Л. Ходака, Ф. Джелинека и К. Шнайдера, Г. Катоны, И. Чиссара и многих других авторов. При ty = t\ величина R(N,Q,ti) является избыточностью универсального кодирования множества источников Q. Универсальное кодирование для множества марковских источников Qs с памятью s, 0 < s < оо, впервые рассмотрено Б.М. Фитингофом. Асимптотическое равенство
R(N,ns,tl) = I^-^logN 2N iogm
при s = 0 получено Р.Е. Кричевским. При s > 0 оценка сверху для R(N,Qs,ti) получена Ю.М. Штарьковым , а нижняя оценка принадлежит В.К. Трофимо-
ву. В.Ф. Бабкиным и Ю.М. Штарьковым доказано существование слабо универсального кодирования для множества всех стационарных источников. Б.Я. Рябко построил код, одновременно хороший для каждого из подмножеств множества
П = [J fls, и получил оценки избыточности.
s=0
Таким образом, в работах, посвященных универсальному кодированию, полностью не изучены вопросы кодирования сообщений источника при їу ф t\, и, кроме того, не изучено поведение избыточности универсального кодирования при неравнозначности длительностей символов кодового алфавита.
Цель работы. Целью диссертационной работы является построение универсальных методов кодирования символами выходного алфавита, имеющими неравнозначные длительности, для множеств бернуллиевских, марковских и стационарных источников; доказательство оптимальности предложенных методов кодирования; экспериментальное подтверждение полученных теоретических результатов.
Для достижения поставленных целей решаются следующие задачи:
-
Построение алгоритмов универсального кодирования множества бернуллиевских и марковских источников буквами неравнозначной длительности.
-
Доказательство асимптотической оптимальности предложенных алгоритмов сжатия в каждом рассматриваемом случае.
-
Доказательство существования слабо универсального кодирования множества стационарных источников буквами неравнозначной длительности.
-
Анализ эмпирических данных для коэффициентов сжатия информации при кодировании универсальными методами.
Методы исследования. В работе использованы методы теории информации, комбинаторики, теории функций, теории вероятностей, машинное моделирование. Положения, выносимые на защиту:
-
Методы построения универсальных кодирований для сообщений символами неравной длительности, основанные на распределении, предложенном в работах Р.Е. Кричевского и В.К. Трофимова.
-
Оценки избыточности и доказательство оптимальности предложенных алгоритмов кодирований для множеств бернуллиевских источников и множеств марковских источников.
-
Доказательство существования слабоуниверсального равномерного по входу кодирования алфавитом с неравнозначными длительностями символов для множества стационарных источников.
4. Анализ результатов использования алгоритмов универсального кодирования и сравнение их с хорошо известными.
Научная новизна работы.
-
В работе предложен общий подход к построению универсальных кодов для множества бериуллиевских, марковских и стационарных источников, основанный на методе Г. Катоны, применимом к КТ-распределению.
-
Доказано, что для множества бериуллиевских и марковских источников предложенное кодирование является асимптотически оптимальным.
-
Для указанных множеств источников получено асимптотически точное равенство для избыточности универсального кодирования при ty ф t\. При ty = t\ из полученных результатов следуют хорошо известные результаты Р.Е. Кричевского, В.К. Трофимова и Ю.М. Штарькова.
-
Проведено эксперементальное сравнение универсальных методов кодирования с методом Лемпела-Зива.
Практическая ценность результатов работы заключается в следующем:
Разработан общий подход к построению универсального кодирования буквами неравнозначной длительности для множества бериуллиевских и марковских источников.
Доказана асимптотическая оптимальность предлагаемого метода кодирования в случае бериуллиевских и марковских источников.
Доказано существование слабоуниверсального кодирования неравнозначными символами для множества стационарных источников.
Проведен анализ эмпирических данных, подтверждающий результаты диссертационной работы. Проведено сравнение коэффициентов сжатия для универсальных алгоритмов блочного кодирования и алгоритма Лемпела-Зива (LZMA).
Некоторые результаты исследования внедрены в учебный процесс СибГУТИ и используются при чтении курса "Основы построения инфокоммуникационных систем и сетей".
Результаты диссертационной работы были использованы при выполнении работ по созданию набора инструментов для осуществления пространственного анализа в рамках геоинформационного проекта «Feature Finder» для обеспечения эффективной компрессии картографических данных.
Результаты данной работы использовались при выполнении научных исследований по следующим грантам:
— Грант Президента Российской Федерации ведущим научным школам Российской федерации (НШ-2175.2012.9);
— Российского фонда фундаментальных исследований (гранты 12-07-00106, 11-
07-00109, 12-07-00188);
- Гранты ФГОБУ ВПО СибГУТИ.
Результаты внедрения подтверждены соответствующими документами.
Апробация работы. Основные положения работы докладывались на следующих конференциях и семинарах: Всероссийская научная конференция «Научное и техническое обеспечение исследований и освоения шельфа северного ледовитого океана» (Новосибирск, 2010), Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций» (Новосибирск, 2011), Международная конференция «Современные проблемы математики, информатики и биоинформатики», посвященная 100-летию со дня рождения А.А. Ляпунова (Новосибирск, 2011), Российская научная конференция с участием зарубежных исследователей «Моделирование систем информатики» (Новосибирск, 2011), Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации» (Новосибирск, 2011), Российская научно-техническая конференция «Обработка информационных сигналов и математическое моделирование» (Новосибирск, 2012), 13я международная научно-техническая конференции «Измерение, контроль, информатизация» (Барнаул, 2012), Всероссийская молодежная научная школа «Управление, информация и оптимизация в машиностроении», Юргинский технологический институт (Томск, 2012), XI международная научная конференция АПЭП (Новосибирск, 2012), 18-я международная научно-практическая конференция «Сибресурс-18-2012» (Томск-Новосибирск, 2012), семинары ИМ СОРАН, ИФП СОРАН, СибГУТИ. По теме диссертации опубликовано 13 работ, из них три — в изданиях из списка ВАК.
Структура и объем диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованной литературы. Работа содержит таблицы и рисунки. Список литературы составляет 120 наименований.
