Сжатие неравнозначными символами информации, порожденной неизвестным источником тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Храмова, Татьяна Викторовна

• Храмова, Татьяна Викторовна
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Храмова, Татьяна Викторовна

Введение

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. Кодирование множества бернуллиевских источников буквами кодового алфавита с неравнозначными длительностями 39 2.1. Основные определения и обозначения. Постановка задачи.

2.2. Разбиение отрезка, порожденное кодовым алфавитом с буквами неравнозначных длительностей

2.3. Общая схема кодирования неравнозначными символами информации, порожденной неизвестным источником.

2.4. Кодирование неравнозначными символами информации, порожденной неизвестным бернуллиевским источником.

2.5. Оценки избыточности универсального кодирования символами алфавита с неравнозначными длительностями для множества бернуллиевских источников

2.5.1. Верхняя оценка избыточности универсального кодирования множества бернуллиевских источников символами неравнозначной длительности.

2.5.2. Нижняя оценка средней избыточности универсального кодирования множества бернуллиевских источников символами неравнозначной длительности.

2.5.3. Асимптотика R (N, fio Дг).

2.5.4. Примеры построения кодирования неравнозначными символами.

3. Кодирование множества марковских источников буквами кодового алфавита с неравнозначными длительностями 83 3.1. Основные определения и обозначения. Постановка задачи.

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

3.3. Оценки избыточности универсального кодирования символами алфавита с неравнозначными длительностями для множества марковских источников

3.3.1. Верхняя оценка избыточности универсального кодирования множества марковских источников символами неравнозначных длительностей

3.3.2. Нижняя оценка избыточности универсального кодирования множества марковских источников символами неравнозначных длительностей

3.3.3. Асимптотика Я (Ы, їу).

4. Кодирование множества стационарных источников буквами кодового алфавита с неравнозначными длительностями

4.1. Слабо универсальное кодирование множества стационарных источников символами алфавита с неравнозначными длительностями.

5. Анализ использования универсальных алгоритмов сжатия информации

5.1. Сравнение коэффициентов сжатия различных типов изображений универсальными алгоритмами

Введение диссертации (часть автореферата) на тему «Сжатие неравнозначными символами информации, порожденной неизвестным источником»

Актуальность темы. В условиях современной реальности мы постоянно сталкиваемся с лавинообразным потоком информации, которую необходимо обрабатывать, хранить и передавать. Передача информации по каналам связи сопровождается ее предварительной обработкой с целью уменьшения объема информации, подлежащей передаче, защиты ее от искажения в процессе передачи и т.д. Уменьшение объема передаваемой информации напрямую связано с увеличением скорости передачи, а также экономией процессорного времени, затрачиваемого на дальнейшую обработку. Задача уменьшения объема памяти, занимаемого информацией, частично решается за счет использования методов сжатия данных и методов кодирования дискретных источников. Следует отметить, что решение задач кодирования источников используется также в теории управления, при выявлении скрытой информации, при создании боль-шемасштабных вычислительных систем, в криптографии. Теория информации, основанная в 1948 г. К. Шенноном [93] служит для получения различных методов сжатия данных. Разработанные К. Шенноном [40], Р. Фано [29], Д.А. Хаффманом [35], И. Чисаром [33], Г. Катоной [72] алгоритмы кодирования дискретных источников существенно использовали статистику сообщений, что частично препятствовало их практическому применению. Вопросы кодирования источников с неизвестной статистикой впервые рассматривались в работах А.Н. Колмогорова [5] и Б.М. Фитингофа [30]. В случае неизвестной статистики источника кодирование называется универсальным. Точная постановка задачи универсального кодирования принадлежит P.E. Кричевскому [7].

Исследованию свойств универсального кодирования также посвящены работы Л.Д. Дэвиссона [60,61], Т.Д. Линча [80,81], Т. Ковера [59], Н. Фаллера [65], Р.Г. Галлагера [70], Д. Кнута [74], Й.С. Виттера [97], Б.Я. Рябко [18-22,90,91], А.Н. Фи-онова, М. Борроуза и Д. Виллера [56], А. Лемпела, Я. Зи-ва [102,103], Т. Велча [98] и А.Д. Вайнера [101], Й. Риссайнена [87-89], Ф. Уиллемса, Ю.М. Штарькова и Ч. Чокенса [48,49,99], В.Ф. Бабкина [94], В.К. Трофимова [26-28,77,78], С. Сава-ри [92], С. Верду [96], В.Н. Потапова [14-17]. Последним двум авторам принадлежат подробные обзорные работы.

Однако вопросы связанные с построением оптимальных методов универсального кодирования бернуллиевских, марковских и стационарных источников символами неравнозначных длительностей ранее оставались открытыми. Решению задач универсального кодирования дискретных источников буквами алфавита с неравнозначными длительностями и посвящена данная диссертационная работа.

Состояние вопроса. Основные понятия, используемые в работе — источник сообщений, энтропия источника, пропускная способность канала, кодирование, избыточность кодирования и т.д. — были введены Клодом Шенноном в его основополагающих работах [40,93].

Пусть Qs — множество источников с памятью s, порождающих последовательности из букв конечного входного алфавита X. В частности, fio — множество бернуллиевских источников, Qr^ — множество стационарных источников. Если Q С Qs состоит из единственного источника G, то мы имеем дело с известным источником. Рассмотрим кодирование (р, ставящее каждому слову источника © G fi в соответствие последовательности букв некоторого конечного кодового алфавита У. Предположим, что буквы кодового алфавита могут иметь различные длительности, определяемые вектором длительностей tY = {t{y))y& > t(y) — длительность символа у EY.

Если длительности всех кодовых символов одинаковы, то ty = t\ = (1; 1; 1; .1). Кодовый алфавит Y определяет пропускную способность канала C(ty), определяемую равенством

С (tY) = log {ty), где wo (t) — наибольший положительный корень уравнения Y^ со= 1. Среднюю длительность L (N,ip,Q,ty) букв коyeY дового алфавита Y, приходящихся на одну букву входного алфавита при кодировании уз блоков длины N источника 0, назовем стоимостью кодирования. Эффективность кодирования ср определяется его избыточностью, которая связывает основные характеристики источника, кодирования и канала и определяется равенством г (iV, ©, <Р, ty) = L (TV, ©, <р, ty) - Щ^-у где H(Q) — энтропия источника сообщений.

Избыточностью универсального кодирования блоков длины N с заданным вектором длительностей букв выходного (кодового) алфавита ty, следуя P.E. Кричевскому [7], назовем величину

R (iV, П, ty) = inf sup г (N, ©, <р, tY) ■

V ©бП

Нижняя грань в последнем равенстве берется по всем дешифруемым кодированиям. Построение хорошего кодирования при заданной длине блока — основная задача при передаче сообщений по каналу связи без шума. Решение этой задачи позволяет установить, какой избыточности можно достичь при заданном значении длины блока.

Если множество источников П содержит единственный элемент ©, то величина R(N,Q,,ty) совпадает с избыточностью кодирования для известного источника.

Кодирование сообщений, порожденных известным источником, как при ty = ¿1, так и при tY ф t\ достаточно хорошо изучены в работах К. Шеннона [40], P.E. Кричевского [7-11], Г.Л. Ходака [38], Ф. Джелинека и К. Шнайдера [66-68], Г. Ка-тоны [72], И. Чиссара [33,34] и многих других авторов. При ty — t\ величина R(N,ü,ti) является избыточностью универсального кодирования множества источников Q. Универсальное кодирование для множества марковских источников S7s с памятью s, 0 < s < сю, впервые рассмотрено Б.М. Фитинго-фом [30]. Асимптотическое равенство

2N log т при s = 0 получено P.E. Кричевским [7]. При s > 0 оценка сверху для Я (ЛГ, ¿х) получена Ю.М. Штарьковым [41], а нижняя оценка принадлежит В.К. Трофимову [26]. В.Ф. Бабкиным и Ю.М. Штарьковым [94] доказано существование слабоуниверсального кодирования для множества всех стационарных источников. Б.Я. Рябко [21] построил код одновременно хороший ос для каждого из подмножеств множества П = У и получил

5=0 оценки избыточности.

Таким образом, в работах, посвященных универсальному кодированию, полностью не изучены вопросы кодирования сообщений источника при 1у ф и, кроме того, не изучено поведение избыточности универсального кодирования при неравнозначности длительностей символов кодового алфавита.

Цель работы. Целью диссертационной работы является построение универсальных методов кодирования символами выходного алфавита, имеющими неравнозначные длительности, для множеств бернуллиевских, марковских и стационарных источников; доказательство оптимальности предложенных методов кодирования; эксперементальное подтверждение полученных теоретических результатов.

Для достижения поставленных целей решаются следующие задачи:

• Построение алгоритмов универсального кодирования множества бернуллиевских и марковских источников буквами неравнозначной длительности.

• Доказательство асимптотической оптимальности предложенных алгоритмов сжатия в каждом рассматриваемом случае.

• Доказательство существования слабоуниверсального кодирования множества стационарных источников буквами неравнозначной длительности.

• Анализ эмпирических данных для коэффициентов сжатия информации при кодировании универсальными методами.

Методы исследования. В работе использованы методы теории информации, комбинаторики, теории функций, теории вероятностей, машинное моделирование. Положения, выносимые на защиту:

1) Методы построения универсальных кодирований для сообщений, символами неравной длительности, основанные на распределении, предложенном в работах P.E. Кричевского и В.К. Трофимова.

2) Оценки избыточности и доказательство оптимальности предложенных алгоритмов кодирований для множеств бернул-лиевских источников и множеств марковских источников.

3) Доказательство существования слабоуниверсального равномерного по входу кодирования алфавитом с неравнозначными длительностями символов для множества стационарных источников.

4) Анализ результатов использования алгоритмов универсального кодирования и сравнение их с хорошо известными.

Научная новизна работы. В работе предложен общий подход к построению универсальных кодов для множества бер-нуллиевских, марковских и стационарных источников, основанный на методе Г. Катоны [72], применимому к КТ-распределе-нию. Доказано, что для множества бернуллиевских и марковских источников предложенное кодирование является асимптотически оптимальным. Для указанных множеств источников получено асимптотически точное равенство для избыточности универсального кодирования при ty При ty — i1, из полученных результатов следуют хорошо известные результаты P.E. Кричевского, В.К. Трофимова и Ю.М. Штарькова. Проведено сравнение предложенных методов кодирования с методом Лемпела-Зива.

Практическая ценность результатов работы заключается в следующем:

1. Разработан общий подход к построению универсального кодирования буквами неравнозначной длительности для множества бернуллиевских и марковских источников.

2. Доказана асимптотическая оптимальность предлагаемого метода кодирования в случае бернуллиевских и марковских источников.

3. Доказано существование слабоуниверсального кодирования неравнозначными символами для множества стационарных источников.

4. Проведен анализ эмпирических данных, подтверждающий результаты диссертационной работы. Проведено сравнение коэффициентов сжатия для универсальных алгоритмов блочного кодирования и алгоритма Лемпела-Зива (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 работ, из них три — в изданиях из списка ВАК.

Структура и объем диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованной литературы. Содержит 7 таблиц, 29 рисунков. Список литературы составляет 116 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Храмова, Татьяна Викторовна

Результаты работы докладывались на семинарах ИМ СО-РАН, ИФП СОРАН, СибГУТИ.

По теме диссертации опубликовано 13 работ, из них три — в изданиях из списка ВАК.

Заключение

В работе решены следующие задачи и получены следующие результаты.

1. Предложены методы построения универсальных кодов сообщений символами неравной длительности, основанные на КТ-распределении.

1.1. Предложен общий подход к построению универсального кодирования, опирающийся на КТ-распределении. Исследованы свойства данной схемы кодирования, обеспечивающие дешифруемость :

Утверждение. Разбиение ([а; Ь)) состоит из полузакрытых слева интервалов ([а; Ь)) = при этом длина интервала ([о;6))| обратно пропорциональна длительности буквы

Уз

Лемма 2.2.1. (о свойствах Щ- ([а; Ь))-разбиения). Пусть на интервале [а\ Ь) задано разбиение

Тогда

1) границы 1) и а]хП,,]п интервала

ЬгП-Зп (М)) = {а3132-(и-1уа3132-3п)

117 вычисляются по формулам aj\j2

-On-i) = а + (6 - a) Y, 'Ч 12 х - х ^о S а + (6 - а) ^ nw0 г2 х . х dijih-j П

2) длина интервала ([а; Ь)) равна п

Лемма 2.3.1. Для кодирования <£>Wo,p : XN —> Y*, где

Шо,р (Щ) = УзгУк-Узп имеют место неравенства:

1) |4j2.jn-i !))| >р(щ);

2) ([0; 1))| < где Г = max {¿,} .

1.2. Разработаны методы универсального равномерного по входу кодирования неравнозначными символами (рШо,р и </Wps в случае бернуллиевского и марковского источников, соответственно. В каждом случае, исследовано максимальное различие между распределением источника и КТ-распределением.

Лемма 2.4.1. (оценка плотности энтропии источника). ч k-1 к — ЗЛ"5" 1 ( к —1\~ J + - + log i N + J .

Лемма 2.4.2. (оценка информационной дивергенции закона распределения источника и КТ-распределения).

2 + \ + log (n + 2 .

Лемма 3.2.1. log < {к~ 1] (Г(к) + a{N, s, к) + log (N—s)) + log/

Лемма 3.2.2.

- Y psHlog^и<я(©s) + wexN kS{k~ 1} log (N-s) + {k~ 1} (T*(k) + a(N, s, k)). w'

2 оч у 2

2. Получены оценки избыточности и доказана оптимальность предложенных алгоритмов кодирований для множеств бернуллиевских источников и множеств марковских источников.

2.1 Получены верхняя и нижняя оценки избыточности универсального кодирования неравнозначными символами в случае множеств бернуллиевских и марковских источников. Приведено доказательство асимптотической оптимальности предложенных алгоритмов сжатия в каждом рассматриваемом случае.

Теорема 2.5.1. дглл т(к)+ (и+ г** г (К, е, < +

Теорема 2.5.2. к- 1 к^ДГ

R{N,n0,ty)

2C{tY) N Теорема 2.5.3. к- 1 log TV

R(N,too,tY) =

2C(t) N ' 119

Теорема 3.3.1. ks{k- 1) log (N — s)

2 C{tY) N ks(k-1) T*(k) + a(N,s,k)

2 C(tY) N N

Теорема 3.3.2.

Теорема 3.3.3.

PIN О f ^ ~ k'{k ~ 1} 1°SN

R{NA'tY) = IcW'

3. Доказано существования слабоуниверсального кодирования множества стационарных источников буквами неравнозначной длительности.

Теорема 4.1.1. Для произвольного стационарного источника с неизвестной статистикой существует слабоуниверсальное кодирование в алфавит с неравнозначными символами.

4. Проведен анализ эмпирических данных для коэффициентов сжатия информации при кодировании универсальными методами. Для сравнения использован алгоритм LZMA, применяемый в архаваторе 7z и универсальный алгоритм предложенный P.E. Кричевским и В.К. Трофимовым, основанный как и срШо$ и (pw0,ps на КТ-распределении. В некоторых рассматриваемых случаях проведено сравнение показателей сжатия с алгоритмом (р2ф. Общая картина исследования продемонстрирована на диаграммах и в таблицах.

Полученные результаты позволяют сделать следующие выводы.

Избыточность равномерного по входу кодирования неравнозначными по длительности или, что то же самое, стоимости реализации, символами в случае неизвестной статистики источника отличается на множитель, пропорциональный log N. При ty = h из полученных в данной работе результатов следуют хорошо известные ранне.

Анализируя поведение констант Т(к) и Т*(к) встречающихся в верхних оценках стоимости кодирования бернуллиевских и марковских источников, соответственно, можно сделать вывод, что при ограничении на длину кодируемого блока эффективность алгоритма растет с увеличением размера входного алфавита. Это следует из того, что Т(к) и Т*(к) отрицательны, начиная с некоторого момента, и убывают.

Для множества стационарных источников существует слабоуниверсальное кодирование в алфавит с неравнозначными символами. При этом имеет место условие

Сравнивая коэффициенты сжатия, полученные в результате использования универсальных алгоритмов, видим, что универсальные алгоритмы, построенные на КТ-распределении позволяют получить в некоторых случаях результаты, лучше, чем

Рисунок 6.1.1.

5 = О (log, log N).

LZMA. Показатель алгоритма <pUo,p в некоторых случаях так же превосходит LZMA.

Список литературы диссертационного исследования кандидат технических наук Храмова, Татьяна Викторовна, 2012 год

1. Бабкин, В.Ф. Метод универсального кодированиянезависимых сообщений неэкспоненциальной трудоемкости Текст. / В.Ф. Бабкин // Проблемы передачи информации. 1971. - Т. 7, № 4. - С. 13-21.

2. Бабкин, В.Ф. Сжатие данных Текст] / В.Ф. Бабкин,

3. A.Б. Крюков, Ю.М. Штарьков // Аппаратура для космических исследований. М.: Наука, 1972. - С. 172-209.

4. Галлагер, Р.Г. Теория информации и надежнаясвязь Текст. / Р.Г. Галлагер. М.: Советское радио, 1974.

5. Игнатов, В.А. Теория информации и передачи сигналов Текст.: Учебник для вузов / В.А. Игнатов. 2-е изд., перераб. и доп. - М.: Радио и связь, 1991.

6. Колмогоров, А.Н. Три подхода к определению понятия «количество информации» Текст. / А.Н. Колмогоров // Проблемы передачи информации. 1966. - Т. 1, № 1. - С. 3-11.

7. Колесник, В. Д. Курс теории информации Текст] /

8. B.Д. Колесник, Г.Ш. Полтырев. М.: Наука, 1982. - С. 416.

9. Кричевский, P.E. Связь между избыточностью кодирования и достоверностью сведений об источнике Текст. / P.E. Кричевский. // Проблемы передачи информации. 1968. - Т. 4. № 3. - С. 48-57.

10. Кричевский, P.E. Длина блока, необходимая для получения заданной избыточности Текст. / P.E. Кричевский. // Доклад АНСССР. 1966. - Т. 171, № 1.

11. Кричевский, Р. Е. Оптимальное кодирование источника на основе наблюдений Текст. /P.E. Кричевский. // Проблемы передачи информации. 1975. - Т. 11. № 4. -С. 37-42.

12. Кричевский, Р. Е. Универсальное кодирование и колмогоровская сложность Текст] / P.E. Кричевский. // Тр. V Междунар. симпоз. по теор. информ.: Тез. докл. Москва Тбилиси, 1979. - Ч. 2. - С. 22-25.

13. Кричевский, P.E. Сжатие и поиск информации Текст] / P.E. Кричевский. М.: Радио и связь, 1989.

14. Марков, A.A. Введение в теорию кодирования Текст] / A.A. Марков. М.: Наука, 1982.

15. Потапов, В.Н. Оценки избыточности кодирования последовательностей алгоритмом Лемпела

16. Зива Текст. / В.Н. Потапов. // Дискрет, анализ и исслед. операций., Сер. 1., 1999. Т. 6. № 2. - С. 70-81.

17. Потапов, В.Н. Обзор методов неискажающего кодирования дискретных источников Текст] / В.Н. Потапов. // Дискрет, анализ и исслед. операций., Сер. 1., 1999. Т. 6. № 4. - С. 49-91.

18. Потапов, В.Н. Теория информации. Кодирование дискретных вероятностных источников Текст] / В.Н. Потапов. Новосибирск: Изд. центр НГУ, 1999.

19. Рябко, Б.Я. Кодирование источника с неизвестными, но упорядоченными вероятностями Текст] / Б.Я. Рябко. // Пробл. передачи информ. 1979. Т. 15. № 2. - С. 71-77.

20. Рябко, Б.Я. Универсальное кодирование компактов Текст] / Б.Я. Рябко. // Доклад АН СССР. 1980. - Т. 252. № 6. - С. 1325-1328.

21. Рябко, Б. Я. Дважды универсальное кодирование

22. Текст. / Б.Я. Рябко. // Проблемы передачи информации. 1984. - Т. 20, № 3. - С. 24-28.

23. Рябко, Б. Я. Эффективный метод кодирования источников информации, использующий алгоритмбыстрого умножения Текст. / Б.Я. Рябко. // Проблемы передачи информации. 1995. - Т. 31. № 1. - С. 3-12.

24. Рябко, Б.Я. Эффективный метод арифметического кодирования для источников с большими алфавитами Текст] / Б.Я. Рябко, А.Н. Фионов. // Проблемы передачи информации. 1999. - Т. 35. № 4. - С. 95-108.

25. Семенюк, В. В. Экономное кодирование дискретной информации Текст] / В.В. Семенюк. СПб.: СПб ГИТМО (ТУ), 2001.

26. Сэломон, Д. Сжатие данных, изображений и звука

27. Текст. / Д. Сэлмон. М.: Техносфера, 2004.

28. Тарасенко, Ф.П. Введение в курс теории информации Текст] /Ф.П. Тарасенко. Томск: ТГУ, 1963.

29. Трофимов, В. К. Избыточность универсального кодирования произвольных марковских источников

30. Текст. / В.К. Трофимов. // Проблемы передачи информации. 1974. - Т. 10. № 4. - С. 16-24.

31. Трофимов, В. К. Универсальное равномерное по выходу кодирование бернуллиевских источников

32. Текст. / В.К. Трофимов. // Методы дискретного анализа в теории кодов и схем: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1976. - Вып. 29. - С. 3-11.

33. Трофимов, В. К. Слабоуниверсальное равномерное по выходу кодирование дискретных стационарных источников Текст] / В.К. Трофимов. // Вестник СибГУ-ТИ. 2010. № 2. - С. 101-111.

34. Фано, Р. Передача информации. Статистическая теория связи Текст] / Р. Фано. // «Мир», М.: 1965.

35. Фитингоф, Б. М. Оптимальное кодирование при неизвестной и меняющейся статистике сообщений Текст] / Б.М. Фитингоф. // Проблемы передачи информации. 1966. - Т. 2. № 2. - С. 3-11.

36. Фитингоф, Б. М. Сжатие дискретной информации Текст] / Б.М. Фитингоф. // Проблемы передачи информации. 1967. - Т. 3. № 3. - С. 28-36.

37. Фомин, А. А. Основы сжатия информации Текст] / А.А. Фомин. СПб.: СПГТУ, 1998.

38. Чисар, И. О каналах без шума Текст] / И. Чисар. // Проблемы передачи информации. 1970.- Т. 6. № 4. - С. 3-15.

39. Чисар, И. Теория информации. Теоремы кодирования для дискретных систем без памяти Текст] / И. Чисар, Я. Кернер. // М.: Мир, 1985.

40. Хаффман, Д.А. Метод построения кодов с минимальной избыточностью Текст]: Пер. с англ. / Д.А. Хаффман. // Кибернетический сборник. М.: ИЛ, 1961. - Вып. 3. - С. 79-87.

41. Хинчин, А. Я. Понятие энтропии в теории вероятностей Текст] / А.Я. Хинчин. // Успехи математических наук. 1953. - Т. 8. № 3 - С. 3-20.

42. Хинчин, А. Я. Об основных теоремах теории информации Текст] / А.Я. Хинчин. // Успехи математических наук. 1956. - Т. 11. № 1 - С. 17-75.

43. Ходак, Г. Л. Оценки избыточности при пословном кодировании сообщений, порожденных бернулли-евскими источниками Текст] / Г.Л. Ходак. // Проблемы передачи информации. 1972. - Т. 8. № 2. - С. 21-32.

44. Хорошевский, В.Г. Архитектура вычислительных систем Текст] / В.Г. Хорошевский. М.: МГТУ им. Н.Э. Баумана, 2005.

45. Шеннон, К. Математическая теория связи Текст] / К. Шеннон.// Работы по теории информации и кибернетике. М.: ИЛ, 1963. - С. 243-332.

46. Штарьков, Ю.М. Кодирование сообщений конечной длины на выходе источника с неизвестной статистикой Текст] / Ю.М. Штарьков. // Материалы V конф. по теории кодирования и передачи информации. — Москва-Горький. 1972. - Ч. 1. - С. 147-152.

47. Штарьков, Ю.М. Кодирование длин серий в условиях априорной неизвестности Текст] / Ю.М. Штарьков, В.Ф. Бабкин. // Тематический выпуск "Аппаратура для космических исследований ИКИ АН СССР. М.: Наука, 1973. - С. 3-9.

48. Штарьков, Ю.М. Метод построения нижних границ избыточности универсального кодирования Текст] / Ю.М. Штарьков. // Пробл. передачи информации. 1982. - Т. 18. № 2. - С. 3-11.

49. Штарьков, Ю.М. Обобщенные коды Шеннона Текст] / Ю.М. Штарьков. // Проблемы передачи информации. 1984. - Т. 20. № 3. - С. 3-16.

50. Штарьков, Ю.М. Универсальное последовательное кодирование отдельных сообщений Текст] / Ю.М. Штарьков. // Проблемы передачи информации. -1987. Т. 23. № 3. - С. 3-17.

51. Штарьков, Ю.М. Равномерное по выходу универсальное кодирование дискретных источников без памяти Текст] /Ю.М. Штарьков. // Проблемы передачи информации. 1991. - Т. 27. № 1. - С. 3-13.

52. Штарьков Ю.М. Кодирование источников без памяти, универсальное по критерию относительной избыточности Текст] / Ю.М. Штарьков. // Проблемы передачи информации. 1991. - Т. 27. № 4. - С. 9-16.

53. Штарьков, Ю. М. Оптимальное универсальное кодирование по критерию максимальной индивидуальной относительной избыточности Текст] / Ю.М. Штарьков, Ч.Дж. Чокенс, Ф.М.Дж. Виллемс. // Проблемы передачи информации. 1997. - Т. 33. № 1. • С. 21-34.

54. Штарьков, Ю. М. Мультиалфавитное взвешенное универсальное кодирование древовидно-контекстных источников. Текст] /Ю.М. Штарьков, Ч.Дж. Чокенс, Ф.М.Дж. Виллемс. // Проблемы передачи информации. 2004. - Т. 40. № 1. С. 98-110.

55. Яглом, A.M. Вероятность и информация Текст] / A.M. Яглом, И.М. Яглом. 3-е изд., перераб. и доп. М.: Наука, 1973.

56. Abramson, N. Information theory and coding Текст] / N. Abramson. McGraw-Hill, New York, 1963.

57. Aravind, R. Image and video coding standards Текст] / R. Aravind, G. Cash, D. Duttweiler, H. Hang, B. Haskell, A. Puri. // ATT Tech. J. Jan.-Feb. 1993. - V. 72. - P. 67-89.

58. Babkin, V. F. Method of universal coding for an independent Текст] / V.F. Babkin.// Probl. Inform. Transm. 1971. - V. 7. № 4.

59. Bell, Т. C. Modeling For Text Compression Текст] / T.C. Bell, I.H. Witten, J.G. Cleary. // ACM Computing Surveys. Dec. 1989. - V. 21. № 4. P. 557-591.

60. Bell, Т. C. Text compression. Текст] / T.C. Bell, LH. Witten, J.G. Cleary. // Englewood Cliffs. NJ: Prentice Hall, Inc. - 1990.

61. Burrows, M. A block-sorting lossless data compression algorithm Текст] / M. Burrows, D.J. Wheeler // Tech. Rep. 124, Digital Systems Res. Ctr. Palo Alto, CA, May 10. - 1994.

62. Capocelli, R. M. New bounds on the redundancy of Huffman codes Текст] / R.M. Capocelli, A.A. De Santis. // IEEE Trans. Inform. Theory. 1991. - V. 37. № 4. - P. 1095-1104.

63. Csiszar, I. Information theory and ergodic theory

64. Текст. / I. Csiszar // Probl. Contr. Inform. Theory. 1987.1. V. 16. P. 3-27.

65. Cover, T. Enumerative source coding Текст] / T. Cover // IEEE Trans. Inform. Theory. Jan. 1973. - V. IT-19. - P. 73-76.

66. Davisson, L. D. Comments on 'Sequence time coding for data compression' Текст] / L.D. Davisson. // Proc. IEEE (Corresp.). Dec. 1966. - V. 54. - P. 2010.

67. Davisson, L. D. Universal Noiseless Coding Текст] / L.D. Davisson. //IEEE Trans. Inform. Theory. 1973. - V. 19. m 6. - P. 783-795.

68. Elias, P. The efficient construction of an unbiased random sequence Текст] / P. Elias. // Ann. of Math. Statist. 1972. - V. 43. № 3. - P. 864-870.

69. Elias, P. Universal codeword sets and representations of the integers Текст] / P. Elias. // IEEE Transaction on Information Theory. Mar. 1975. - V. 21. № 2. - P. 194-203.

70. Elias, P. Interval and recency rank source encoding: two on-line adaptive variable-rate schemes Текст] / P. Elias. // IEEE Transactions on Information Theory. -January 1987. V. 33. № 1. - P. 3-10.

71. Faller, N. An adaptive system for data compression

72. Текст. / N. Faller. //in 7th Asilomar Conf. on Circuits, Systems, and Computing. 1973. - P. 593-597.

73. Jelinek, F. Probabilistic information theory Текст] / F. Jelinek. New York: McGraw-Hill, 1968. P. 476-489.

74. Jelinek, F. On variable length-to-block coding Текст] / F. Jelinek, K. Schneider. // IEEE. Trans. Inform. Theory. -Nov. 1972. V. IT-18. - P. 765-774.

75. Jelinek, F. Variable-length encoding of fixed-rate Markov sources for fixed-rate channels Текст] / F. Jelinek, К. Schneider. // IEEE Transactions on Information Theory. 1974. - V. 20. № 6. - P. 750 - 755.

76. Gabor, D. Theory of communication Текст] / D. Gabor. // J. Inst. Elec. Eng. Sept. 1946. - V. 93. - P. 429-457.

77. Gallager, R. G. Variation on a theme by Human

78. Текст. / R. Gallager. // IEEE Transactions on Information Theory. November 1978. - V. 24. № 6. - P. 668-674.

79. Hartley, R. V. L. Transmission of information Текст] / R. V.L. Hartley. // Bell Syst. Tech. J. July 1928. - V. 7, P. 535-563.

80. Katona, G. General theory of noiseless channels Текст] / G. Katona. // UDINE 1970. Courses and lectures - № 31. - P. 69.

81. Khinchin, A. I. The entropy concept in probability theory Текст] / A. Khinchin. // Usp. Mat. Nauk. English translation in Mathematical Foundations of Information Theory. New York: Dover, 1957. - V. 8. - P. 3-20.

82. Knuth, D. E. Dynamic Huffman coding Текст] / D. Knuth. // J. Algorithms. 1985. V. 1985. - P. 163-180.

83. Kolmogorov, A. N. On the shannon theory of information transmission in the case of continioussignals Текст. / A. Kolmogorov. // IRE Transactions on Information Theory. 1956. - V. 2. - P. 102-108.

84. Kraft, L.G. A device for quantizing, grouping, and coding amplitude modulated pulses Текст] / L.G. Kraft. // Cambridge, MA: MS Thesis. Electrical Engineering Department, Massachusetts Institute of Technology. - 1949.

85. Krichevsky, R.E. Optimal sample based encoding Markov sources Текст] / R.E. Krichevsky, V.K. Trofimov. / / Third Czechoslovak-Soviet-Hungarian seminar on information theory. Liblice, 1980. -P. 131-138.

86. Krichevsky, R.E. The performance of universal encoding Текст] / R.E. Krichevsky, V.K. Trofimov. // IEEE Transactions on Information Theory. 1981. - V. 27. № 2. - P. 199-207.

87. Krichevsky, R. Universal Compression and Retrieval Текст] / R.E. Krichevsky. Dordrecht: Kluwer Academic Publishers. 1994.

88. Lynch, T. J. Sequence time coding for data compression Текст] / Т. Lynch // Proc.IEEE (Corresp.). Oct. 1966 - V. 54. - P. 1490-1491.

89. Lynch, T. J. Data compression with error-control coding for space telemetry Текст] / Т. Lynch. Ph.D. dissertation, Univ. Maryland, College Park, May 1966.

90. McMillan, B. The basic theorems of information theory Текст] / В. McMillan. // Ann. Math. Statist. June 1953. - V. 24. - P. 196-219.

91. McMillan, В. Two inequalities implied by unique decipherability Текст] / В. McMillan. // IEEE Trans. Information Theory. 1956. - V. 2. № 4. - P. 115-116.

92. Manstetten, D. Tight bounds on the redundancy of Human codes Текст] / D. Manstetten. // IEEE Transactions on Information Theory. Jan. 1992. - V. 38. № 1. - P. 144-151.

93. Pierce, J.R. The early days of information theory Текст] / J.R. Pierce. // IEEE Trans. Inform. Theory. Jan. 1973 - V. IT-19. - P. 3-8.

94. Price, J.R. A conversation with Claude Shannon Текст] / J.R. Pierce. //IEEE Commun. Mag. May 1984. - V. 22. - P. 123-126.

95. Rissanen, J. Generalized Kraft inequality and arithmetic coding Текст] / J. Rissanen. // IBM J. Res. Develop. 1976. - V. 20. No. 3. - P. 198 - 203.

96. Rissanen, J. Universal modelling and coding Текст] / J. Rissanen. G. Langdon. // IEEE Trans. Inform. Theory. -1981. V. IT-27. № 1. - P. 12 - 23.

97. Rissanen, J. A universal data compression system

98. Текст. / J. Rissanen. // IEEE Trans. Inform. Theory. Sept. 1983. - V. IT-29.- P. 656-663.

99. Ryabko, B. A fast on-line adaptive code Текст] / В. Ryabko. // IEEE Trans. Inform. Theory. July 1992. -V. 38.- P. 1400-1404.

100. Ryabko, В. Data compression by means of a book stack Текст] / В. Ryabko. // Probl. Inform. Transm. 1980.- V. 16. P. 265-269.

101. Savari, S. A., Gallager, R. G. Generalized Tunstall codes for sources with memory Текст] / S. A. Savari, R. G. Gallager // IEEE Trans. Inform. Theory. 1997. - V. 43. № 2. - P. 658-668.

102. Shannon, Claude E. A Mathematical Theory of Communication Текст] / С. Shannon // Bell System Technical Journal. July/October 1948. V. 27. № 3. - P. 379-423.

103. Shtarkov, Y. M., Babkin, V. F. Combinatorial encoding for discrete stationary sources Текст] / Y. M. Shtarkov, V. F. Babkin. // 1973 IEEE International Symposium on Information Theory. Budapest, 1973. - P. 249-257.

104. Tjalkens, T. J., Willems, F. M. J. A universal variable-to-fixed length source code based on Lawrence's algorithm Текст] / T. J. Tjalkens , F. M. J. Willems. // IEEE Trans. Inform. Theory. Mar. 1992. - V. 38. - P. 247-253.

105. Verdu, S. Fifty Years of Shannon Theory Текст] / S. Verdu. // IEEE Transactions on Information Theory. 1998.- V. 44. № 6. P. 2057-2078.

106. Vitter, J. S. Dynamic Huffman coding Текст] / J.S. Vitter // ACM Trans. Math. Software. June 1989. -V. 15. - P. 158-167.

107. Welch, Т. A. A technique for high performance data compression Текст] / T.A. Welch // Computer. June 1984. - V. 17. - P. 8-19.

108. Willems, F. M. J. The context-tree weighting method: Basic properties Текст] / F.M.J. Willems , Y.M. Shtarkov, T.J. Tjalkens // IEEE TYans. Inform. Theory. May 1995. -V. IT-28.- P. 653-664.

109. Witten, I. H. Arithmetic coding for data compression Текст] / I.H. Witten , R. Neal R., J.G. Cleary // Comm. of the Assoc. Сотр. Math. 1987. - V. 30. № 6. - P. 520-540.

110. Wyner, A. D. The sliding-window Lempel-Ziv algorithm is asymptotically optimal Текст] / A.D. Wyner, J. Ziv. // Proc. IEEE. June 1994. - V. 82.- P. 872-877.

111. Lempel, A. A universal algorithm for sequential data compression Текст] / J. Ziv, A. Lempel. // IEEE Transactions on Information Theory. May 1977.- V. 23. № 3. P. 337-343.

112. Ziv, J. Compression of individual sequences via variable-rate coding Текст] / J. Ziv, A. Lempel. // IEEE Transactions on Information Theory. Nov. 1978. - V. IT-24. No 5. - P. 530-536.

113. Трофимов, В.К. Об оценке избыточности кодирования дискретных источников информации Текст] / Т.В. Храмова, В.К. Трофимов. // Материалы ВНК молодых ученых «Наука. Технологии. Инновации». Новосибирск, 2011. - Ч. 1. -С. 27-30.

114. Трофимов, В.К. Сжатие неравнозначными символами информации, порожденной неизвестным источником без памяти Текст] / Т.В. Храмова,

115. B.К. Трофимов. // Автометрия. Новосибирск, 2012. - Т. 48. № 1. - С. 30- 44.

116. Трофимов, В.К. Сжатие информации порожденной неизвестным источником Текст] / Т.В. Храмова, В.К. Трофимов. // Электросвязь. Москва, 2012. - № 4. - С. 41-44.

117. Храмова, Т.В. Применение универсальных методов для сжатия факсимильных данных Текст]

118. Т.В. Храмова, M.С. Павленко. // Управление, информация и оптимизация в машиностроении: сборник трудов Всероссийской молодежной научной школы. Юргинский технологический институт. Томск: Изд-во Томского политехнического университета, 2012. - С. 286-288.

119. Trofimov, V. К. Compression of information generated by an unknown memoryless source by nonequivalent symbols. Текст] / V.K. Trofimov, T.V. Khramova. // Optoelectronics, Instrumentation and Data Processing. February 2012. - V. 48. I. 1. -P. 24-36.

120. Пр-т Академика Лаврентьева 2/2 Новосибирск, 630090, Россия

121. Дата" 20 " октября 2012 г.1. АКТо внедрении результатов диссертационной работы

122. Храмовой Татьяны Викторовны

123. Сжатие неравнозначными символами информации, порожденной неизвестным источником", представленной на соискание учёной степеникандидата технических наук по специальности0513.17 — «Теоретические основы информатики»

124. Результатом внедрения стала программная база для других коммерческих продуктов компании.1. Генеральный директор,1. Руководитель проекта,1. Ананьев B.A.f1. Бернштейн Ю.Б.

125. Тел.: [phone], Факс: [phone], www.daiaeast.ru, e-mail: ¡[e-mail]1. УТВЕРЖДАЮ

126. Декан Факультета автоматической электросвязи ФГОБУ ВПО "СибГУТИ", д.т.н. профессор1. О. Г. Мелентьев

127. Заведующий кафедрой ПДСиМ, д.т.н., профессор1. В. П. Шувалов1. Начальник ООУП1. Е.П. Киселева1. УТВЕРЖДАЮ

128. Проректор по научной работе ФГОБУ ВПО "СибГУТИ", д.т.н. профессорпроректор по учебной работе ФГОБУ ВПО "СибГУТИ", к.т.н., доцентк.т.н., доцент1. Фионов А.Н.1. Мамойленко С.Н.1. Поляков А.Ю.