Сжатие неравнозначными символами информации, порожденной неизвестным источником

• Автор: Храмова, Татьяна Викторовна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 143 с. : ил.

Оглавление
Введение

1. Основные понятия теории информации

1.1. Канал передачи информации

1.2. Дискретные источники информации

1.2.1. Понятие источника информации.

1.2.2. Энтропия источника информации

1.3. Кодирование источника сообщений

1.3.1. Определение кодирования источника . .

1.3.2. Префиксное кодирование.

1.3.3. Некоторые методы кодирования.

1.4. Пропускная способность канала
1.5. Избыточность кодирования информации .
1.6. Универсальное кодирование
2. Кодирование множества бернуллиевских источников буквами кодового алфавита с неравнозначными длительностями
2.1. Основные определения и обозначения. Постановка задачи.
2.2. Разбиение отрезка, порожденное кодовым алфавитом с буквами неравнозначных длительностей .
2.3. Общая схема кодирования неравнозначными символами информации, порожденной неизвестным источником.
2.4. Кодирование неравнозначными символами информации, порожденной неизвестным бернуллиевским источником.
2.5. Оценки избыточности универсального кодирования символами алфавита с неравнозначными длительностями для множества бернуллиевских источников
2.5.1. Верхняя оценка избыточности универсального кодирования множества бернуллиевских источников символами неравнозначной длительности.
2.5.2. Нижняя оценка средней избыточности универсального кодирования множества бернуллиевских источников символами неравнозначной длительности.
2.5.3. Асимптотика Л А, ПоДу
2.5.4. Примеры построения кодирования неравнозначными символами.
Кодирование множества марковских источников буквами кодового алфавита с неравнозначными длительностями
3.1. Основные определения и обозначения. Постановка задачи
3.2. Кодирование неравнозначными символами информации, порожденной неизвестным марковским источником .
3.3. Оценки избыточности универсального кодирования символами алфавита с неравнозначными длительностями для множества марковских источников
3.3.1. Верхняя оценка избыточности универсального кодирования множества марковских источников символами неравнозначных длительностей .
3.3.2. Нижняя оценка избыточности универсального кодирования множества марковских источников символами неравнозначных длительностей .
3.3.3. Асимптотика КАт,3,1у
4. Кодирование множества стационарных источников буквами кодового алфавита с неравнозначными длительностями
4.1. Слабо универсальное кодирование множества стационарных источников символами алфавита с неравнозначными длительностями
5. Анализ использования универсальных алгоритмов сжатия информации
5.1. Сравнение коэффициентов сжатия различных типов изображений универсальными алгоритмами .
Заключение
Литература


Построение хорошего кодирования при заданной длине блока основная задача при передаче сообщений по каналу связи без шума. Решение этой задачи позволяет установить, какой избыточности можно достичь при заданном значении длины блока. Если множество источников содержит единственный элемент 0, то величина 1i совпадает с избыточностью кодирования для известного источника. Кодирование сообщений, порожденных известным источником, как при ii, так и при i достаточно хорошо изучены в работах К. Шеннона , Кричевского 7, Г. I. Ходака , Ф. Джелинека и К. Шнайдера , Г. Катоны , И. Чиссара , и многих других авторов. При . Универсальное кодирование для множества марковских источников с памятью , 0 5 оо, впервые рассмотрено Б. М. Фитингофом . Асимптотическое равенство
при 0 получено Кричевским 7. Лг, П5,1 получена Ю. М. Штарьковым , а нижняя оценка принадлежит В. К. Трофимову . В.Ф. Бабкиным и Ю. М. Штарьковым доказано существование слабоуниверсального кодирования для множества всех стационарных источников. Б.Я. Рябко построил код одновременно хороший
для каждого из подмножеств множества П и и получил
оценки избыточности. Таким образом, в работах, посвященных универсальному кодированию, полностью не изучены вопросы кодирования сообщений источника при 1у т1 й и кроме того, не изучено поведение избыточности универсального кодирования при неравнозначности длительностей символов кодового алфавита. Цель работы. Целью диссертационной работы является построение универсальных методов кодирования символами выходного алфавита, имеющими неравнозначные длительности, для множеств бернуллиевских, марковских и стационарных источников доказательство оптимальности предложенных методов кодирования эксперементальное подтверждение полученных теоретических результатов. Построение алгоритмов универсального кодирования множества бернуллиевских и марковских источников буквами неравнозначной длительности. Доказательство асимптотической оптимальности предложен ных алгоритмов сжатия в каждом рассматриваемом случае. Доказательство существования слабоуниверсального кодирования множества стационарных источников буквами неравнозначной длительности. Анализ эмпирических данных для коэффициентов сжатия информации при кодировании универсальными методами. Методы исследования. В работе использованы методы теории информации, комбинаторики, теории функций, теории вероятностей, машинное моделирование. Методы построения универсальных кодирований для сообщений, символами неравной длительности, основанные на распределении, предложенном в работах Кричевского и В. К. Трофимова. Оценки избыточности и доказательство оптимальности предложенных алгоритмов кодирований для множеств бернуллневских источников и множеств марковских источников. Доказательство существования слабоуниверсального равномерного по вход кодирования алфавитом с неравнозначными длительностями символов для множества стационарных источников. Анализ результатов использования алгоритмов универсального кодирования и сравнение их с хорошо известными. Научная новизна работы. Г. Катоны , применимому к К Трасп ре делению. Доказано, что для множества бернуллиевских и марковских источников предложенное кодирование является асимптотически оптимальным. Для указанных множеств источников получено асимптотически точное равенство для избыточности универсального кодирования при При из полученных результатов следуют хорошо известные результаты Кричсвского, В. К. Трофимова и Ю. М. Штарькова. Проведено сравнение предложенных методов кодирования с методом ЛемпелаЗива. Разработан общий подход к построению универсального кодирования буквами неравнозначной длительности для множества бернуллиевских и марковских источников. Доказана асимптотическая оптимальность предлагаемого метода кодирования в случае бернуллиевских и марковских источников. Доказано существование слабоуниверсального кодирования неравнозначными символами для множества стационарных источников. Проведен анализ эмпирических данных, подтверждающий результаты диссертационной работы. Проведено сравнение коэффициентов сжатия для универсальных алгоритмов блочного кодирования и алгоритма ЛемпелаЗива .