автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Сжатие неравнозначными символами информации, порожденной неизвестным источником

На правах рукописи

005057141

Храмова Татьяна Викторовна

УДК 621.391

СЖАТИЕ НЕРАВНОЗНАЧНЫМИ СИМВОЛАМИ ИНФОРМАЦИИ, ПОРОЖДЁННОЙ НЕИЗВЕСТНЫМ ИСТОЧНИКОМ

Специальность 05.13.17 - Теоретические основы информатики

Автореферат диссертации соискание учёной степени кандидата технических наук

6 ДЕК 2012-

Новосибирск — 2012

005057141

Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования "Сибирский государственный университет телекоммуникаций и информатики" Федерального аген-егва связи.

Научный руководитель: доктор технических наук, профессор

Трофимов Виктор Куприянович • Официальные оппоненты: Резник Александр Львович, доктор

технических наук, профессор, заведующий лабораторией вероятностных методов исследования информационных процессов ФГБУН СОРАН Институт автоматики и электрометрии.

Потапов Владимир Николаевич, кандидат физико-математических наук, старший научный сотрудник ФГБУН СОРАН Института математики им. С.Л. Соболева.

Ведущая организация: ФГБУН СОРАН Институт систем ин-

форматики имени А.П. Ершова, г. Новосибирск

Защита состоится И) декабря 2012 г. в '¿»"""часов на заседании диссертационного совета Д 219.005.02 при ФГОБУ ВПО "Сибирский государственный университет телекоммуникаций и информатики" по адресу 630102, г. Новосибирск, ул. Кирова д. 86, ауд. 625.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО СибГУТИ.

Автореферат разослан " ноября 2012 г.

Ученый секретарь

диссертационного совета Д 219.005.02 кандидат технических наук, доцент

И.И.Резван

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Исследованию свойств универсального кодирования также посвящены работы Л.Д. Дэвиссона, Т.Д. Линча, Т. Ковера, Н. Фаллера, Р.Г. Галлагера, Д. Кнута, Й.С. Виттера, Б.Я. Рябко, А.Н. Фионова, М. Борроуза и Д. Виллера, А. Лемпела, Я. Зива, ТА. Велча и А.Д. Вайнера, Й. Риссайнена, Ф. Уиллемса, М.Ю. Штарь-кова, В.Ф. Бабкина, В.К. Трофимова, Ч. Чокенса, С. Савари, С. Верду, В.Н. Потапова. Последним двум авторам принадлежат подробные обзорные работы.

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

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

Пусть fis — множество источников с памятью s, порождающих последовательности из букв конечного входного алфавита X. В частности, По — множество

бернуллиевских источников, fi^ — множество стационарных источников. Если i2 С П, состоит из единственного источника G, то мы имеем дело с известным источником. Рассмотрим кодирование ip, ставящее в соответствие каждому слову источника б 6 f! последовательности букв некоторого конечного кодового алфавита Y. Предположим, что буквы кодового алфавита могут иметь различные длительности, определяемые вектором длительностей ty = (t(y))yeY, t(y) — длительность символа у 6 У. Если длительности всех кодовых символов одинаковы, то ty = ti = (1; 1; 1; ...1). Кодовый алфавит Y определяет пропускную способность канала City), определяемую равенством С (ty) = log wo (ty), где oja(t) — наибольший положительный корень уравнения = 1. Среднюю длительность

ySY

L (N, <р,&, ty) букв кодового алфавита У, приходящихся на одну букву входного алфавита при кодировании <р блоков длины N источника 9, назовем стоимостью кодирования. Эффективность кодирования <р определяется его избыточностью, которая связывает основные характеристики источника, кодирования и канала и определяется равенством г (N, 0, tp, ty) = L (N, 0, <р, ty) - где Я(0) — энтропия источника сообщений.

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

R (N, П, ty) = inf sup г (N, Q,tp,ty). v Seil

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

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

Кодирование сообщений, порожденных известным источником, как при i„ = fx, так и при ty ± ii достаточно хорошо изучены в работах К. Шеннона, P.E. Кри-чёвского, Г.Л. Ходака, Ф. Джелинека и К. Шнайдера, Г. Катоны, И. Чиссара и многих других авторов. При ty = ?i величина R (N, П, ti) является избыточностью универсального кодирования множества источников П. Универсальное кодирование для множества марковских источников fls с памятью з, 0 < s < оо, впервые рассмотрено Б.М. Фитингофом. Асимптотическое равенство

при s = 0 получено P.E. Кричевским. При s > 0 оценка сверху для Я (N, ü„, ti) получена Ю.М. Штарьковым , а нижняя оценка принадлежит В.К. Трофимо-

ву. В.Ф. Бабкиным и Ю.М. Штарьковым доказано существование слабо универсального кодирования для множества всех стационарных источников. Б.Я. Рябко построил код, одновременно хороший для каждого из подмножеств множества

оо

Г1 = и Пг, и получил оценки избыточности. й=0

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

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

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

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

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

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

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

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

Положения, выносимые на защиту:

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

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

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

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

Научная новизна работы.

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

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

3. Для указанных множеств источников получено асимптотически точное равенство для избыточности универсального кодирования при iy ^ ij. При ty — t\ из полученных результатов следуют хорошо известные результаты P.E. Кричевского, В.К. Трофимова и Ю.М. Штарькова.

4. Проведено эксперементальное сравнение универсальных методов кодирования с методом Лемпела-Зива.

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

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

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

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

Проведен анализ эмпирических данных, подтверждающий результаты диссертационной работы. Проведено сравнение коэффициентов сжатия для универсальных алгоритмов блочного кодирования и алгоритма Лемпела-Зива (LZMA).

Некоторые результаты исследования внедрены в учебный процесс СибГУГИ и используются при чтении курса "Основы построения инфокоммуникационных систем и сетей

Результаты диссертационной работы были использованы при выполнении работ по созданию набора инструментов для осуществления пространственного анаг лиза в рамках геоинформационного проекта «Feature Finder» для обеспечения эффективной компрессии картографических данных.'

Результаты данной работы использовались при выполнении научных исследований по следующим грантам:

— Грант Президента Российской Федерации ведущим научным школам Российской федерации (НШ-2175.2012.9);

- Российского фонда фундаментальных исследований (гранты 12-07-00106 1107-00109, 12-07-00188);

— Гранты ФГОВУ ВПО СибГУТИ.

Результаты внедрения подтверждены соответствующими документами.

Апробация работы. Основные положения работы докладывались на следующих конференциях и семинарах: Всероссийская научная конференция «Научное и техническое обеспечение исследований и освоения шельфа северного ледовитого океана» (Новосибирск, 2010), Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций», (Новосибирск, 2011), Международная конференция «Современные проблемы математики, информатики и биоинформатики», посвященная ЮСклетшо со дня рождения A.A. Ляпунова (Новосибирск, 2011), Российская научная конференция с участием зарубежных исследователей «Моделирование систем информатики» (Новосибирск, 2011), Всероссийская научная конференция молодых ученых «Наука. Технологии Инно вации» (Новосибирск, 2011), Российская научно-техническая конференция Юб-работка информационных сигналов и математическое моделирование» (Новосибирск, 2012), 13я международная научнотехничёская конференции «Измерение контроль, информатизация» (Барнаул, 2012), Всероссийская молодежная научшм школа «Управление, информация и оптимизация в машиностроении», Юргинский технологический институт (Томск, 2012), XI международная научная конференция АПЭП (Новосибирск, 2012), 18-я международная научно-практическая конференция «Сибресурс-18-2012» (Томск-Новосибирск, 2012), семинары ИМ СОРАН, ИФП СОРАН, СибГУТИ. По теме диссертации опубликовано 13 работ, из них три — в изданиях из списка ВАК.

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

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

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

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

Во второй главе поставлена задача универсального кодирования множества бернуллиевских источников с входным алфавитом X и кодовым (выходным) У, буквы которого имеют неравнозначную длительность. Рассматриваются только источники, порождающие блоки длины N. Предложен метод универсального кодирования, принцип которого заключается в построении соотвествия между интервалами разбиений ([0; 1)) единичного отрезка и значениями средних вероятностей слов источника. Упомянутое выше разбиение определяется длительностями букв кодового алфавита, а именно, имеет место следующее утверждение.

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

Сформулирована и доказана лемма о свойствах предлагаемого разбиения. Лемма 2.2.1. (о свойствах О?- ([о; Ь))-разбиения). Пусть на интервале [а; Ъ) задано разбиение

Щ ([а; ъ)) = ([а; Ь))Ь=т^ •

Тогда

1) границы и интервала

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

= а + (Ь - а) £ х.... х и**",

11<2—<пЧШ2 —Зп

= « + №-«) Е цТ*1«^ * - х -о-"";

—Зп

(здесь и далее символы " Ч " и " ■< " обозначают лексикографический порядок)

2) длина интервала ([а; &)) Равна

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

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

Для построения универсального метода блочного кодирования упорядочим слова источника по убыванию их средних вероятностей, затем каждому слову w € XN поставим в соответствие величину a(w) — сумму средних вероятностей слов, расположенных левее, согласно установленному частичному порядку. Каждое из значений a(w), w е XN, принадлежит множеству интервалов разбиений ÖJ-([0; 1)) для различных значений п. Код определен формулой {w{) = У^У^-У^, которая ставит в соответствие каждой кодовой последовательности w, е XN слово УзтУъ—У^ из букв кодового алфавита, где jij2--jn — набор индексов интервала [hh ^ ([0; 1)) с Эу ([0; 1)), содержащего a{wi) и выбираемого так, чтобы значения aOi_i) и a(>i+i) не попадали в интервал Ijlj2...j„ ([0; 1)), но хотя бы одно из них содержалось в Ij^.j^ ([0; 1))-

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

Г(|)ПГ(п, + 1)

далее соответствие w i—У p{w) будем обозначать через р.

Глава содержит примеры, иллюстрирующие построение описываемого метода ! кодирования Дешифруемость кодирования tpUotр обеспечивает следующая

лемма.

Лемма 2.3.1. Для кодирования <Ры„,р - XN -> У, где ) К) = УьУп-Уь

имеют место неравенства:

Далее во второй главе проводится оценка плотности энтропии источника и информационной дивергенции закона распределения источника и КТ-распределения: Лемма 2.4.1. (оценка плотности энтропии источника). Для произвольного бер-нуллиевского источника 9, в 6 П0, с алфавитом X = {11,12,-,^} « законом распределения рэ(щ) = Р» генерирующего последовательности уц = х^хь ■ ■ ■ имеет место неравенство:

logPi<\ogpi-log(^^) 2 + ^ + 1ое ^ + ~~~2~) •

Соответствие уз 1—* рв(и>) в дальнейшем будем обозначать через р.

Лемма 2.4.2. (оценка информационной дивергенции закона распределения источника и КТ-распределения). Для произвольного бернуллиевского источника е, в 6 По, С алфавитом X = {х1,х2,...,хк} и законом распределения ре(од) = р., генерирующего последовательности и)^ = ■■•х{„, имеет место неравенство:

-D(PIIP) < -log (~2е~) 2 + $ + + ° .

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

Теорема 2.5.1. Для избыточности кодирования <р^р пройзвольного бернуллиевского источника ©, © € По, имеет место оценка

- ч T(k) + g(iV + ^r) , Г г (N, 0, ipuef, ty) <-C{p)N N '

где N - длина входного блока, C{tY) - пропускная способность канала, Т{к) -константа, определяемая алфавитом источника, Г* - константа, зависящая только от канала.

Теорема 2.5.2. Для средней избыточности R (N, П, ty) универсального кодирования множества бернуллиевских источников П, П € П0, справедливо асимптотическое неравенство

k- 1 logiV

Л(ЛГ,П0,<у)>

2C(iy) N

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

Теорема 2.5.3. Для избыточности Н (./V, По, универсального кодирования множества бернуллиевских источников П0 буквами неравнозначного выходного алфавита справедливо асимптотическое равенство

к-1 1окЛГ

В третьей главе рассматривается задача блочного кодирования неизвестного марковского источника порядка 5 буквами алфавита с неравнозначными символами. Алгоритм сжатия информации, предложенный в предыдущей главе для бер-нуллиевских источников, модифицирован для источников марковского типа здесь используется КТ-распределение

ps(Wi) = р? =

'г(Ю

Tlr(rw + i)

Г (п„ +

где Г (г) — гамма-функция, и щ, nvi, nv — число вхождений в слово w е XN соответственно буквы хи последовательности v £ X" после буквы ж<, последовательности v е Xs. Соответствие w i—> p"{w) в дальнейшем будем обозначать через р°.

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

Лемма 3.2.1. Для произвольного марковского источника Qs, 0„ € с алфавитом X, |Х| = к, и законом распределения p"(w) с условными вероятностями p^(w) = Pvj, w е XN, V 6 Xs, Xj 6 X, имеет место неравенство:

^ y(fc -l) (r(fc) + a[Ni Stk) +log (JV_e)) +logp»,

p" (w) 2.

где T*(k) — некоторая постоянная относительно N величина,

a(N, k,s) 0 — бесконечно малая при N -> оо величина, v ' 'jtf-мо — средние вероятности.

Лемма 3.2.2. Длл произвольного марковского источника 0, G € Пs с ал^а-витом X, |Х| = к и законом распределения p'e[w) с условными вероятностями p*j(w) = p„j, w 6 XN, v e Xs, имеет место неравенство:

- £ / («,) log Г И ^ Я (в.) + fcS(A2"1} log (*-*) + ^(fc2~1} СП*) + «).

«.a"

где — некоторая постоянная относительно N величина,

a(N s k) —>■ 0 — некоторая бесконечно малая величина,

к ' ' ' jv-+oo р® — средние вероятности.

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

Основные результаты третьей главы сформулированы в виде следующих теорем:

Теорема 3.3.1. Для избыточности кодирования <pw,p- произвольного марковского источника 6S, 6S е словами выходного алфавита с неравнозначными длительностями букв и определяемой этим алфавитом пропускной способностью канала передачи информации C(ty) имеет место неравенство•

k>{k-1) log(N — s) , fr(fc-l) T'(k)+a(N,s,k) t" r{N,e3,^f.,ty)< 2C{W) jj + 2C(fy) • N Ч- N-

где T'(k) — некоторая постоянная относительно N величина, a(N,s,k) 0 — некоторая бесконечно малая величина, t" — константа, зависящая только от канала.

Теорема 3.3.2. Для средней избыточности R(N,Q.,ty) универсального кодирования множества марковских источников П, П € справедливо асимптотическое неравенство

Теорема 3.3.3. Для избыточности R (Лг, Ds, t) универсального кодирования множества марковских источников П, кодовым алфавитом У с символами неравнозначных длительностей ty справедливо асимптотическое неравенство R(Nn г л ~ -1) bgiV

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

Основной результат четвертой главы представлен в виде следующей теоремы:

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

В пятой главе проведен анализ эмпирических данных. А именно, выполнено сравнение результатов равномерного по входу универсального кодирования с известным алгоритмом LZMA. Выполнен анализ результатов сжатия факсимильной информации нескольких видов: карандашный рисунок, фотография, печатный текст. В каждом случае представлено тестируемое изображение, на графиках

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

Рисунок 2. Динамика зависимости коэффициента сжатия образца рисунка (ось ординат), от длины N кодируемого блока

Максим Фргм «Лабиринт»

© СЬруг1д№(С} И. Сгепин, С. Мар-гынчик, 39?7 Оригинал этого текста расположен на о Финальной странице Максима Фрая http://www.frel ли 5ре11спеск: Рпйгвн Н£гоу

ПРЕДУПРЕЖДЕНИЕ ОБ АВТОРСКИХ ПРАВАХ

1. Ангорские права на текст книги принадлежат И.Сгегину и С.Мартыжик, текст размещен на страничке http://nveniiws.tnpod.com/~SYMl с разрешения граводержателей.

2. Испо/ьзоваже текста разрешена только физическим ладам только в лжных, некоммерческих целях. Любое рашространеже, размножение, тиражирование, перенос на бумажные носители могут быть прсижедеьы только этим фшическим лицом только для Л №1 но го пользования.

3. Продажа, грокат, публичный показ, публичное иотолнете, перевод переработка/аранжировка а также любая дзугая ферма сообщения текста или его фрагментов для „ , | | |_ч---—ы»с

Рисунок 3. Динамика зависимости коэффициента сжатия образца текста (ось ординат), от длины N кодируемого блока Общая картина исследования нескольких фотографий, рисунков и образцов текста представлена на следующей диаграмме.

Рисунок 4.

Диаграмма сравнения коэффициентов сжатия образцов изображений.

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

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

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

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

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

Публикации по теме диссертационной работы.

Публикации в рецензируемых изданиях.

1. Трофимов В.К., Храмова Т.В., Сжатие неравнозначными символами информации, порожденной неизвестным источником без памяти. // Автометрия. Новосибирск, 2012. - т.48, №1, стр.30-44.

2. V. К. TVofimov, Т. V. Khramova. Compression of information generated by an unknown memoryless source by nonequivalent symbols. //

Optoelectronics, Instrumentation and Data Processing. February 2012. — Volume 48, Issue 1, pp. 24-36.

3. Трофимов B.K., Храмова T.B., Сжатие информации, порожденной неизвестным источником. Электросвязь. Москва, 2012. — №4, стр. 41-44.

Публикации в метериалах научных конференций.

4. Храмова Т.В., Кодирование сообщений, порожденных неизвестным источником, при различных длительностях передаваемых сигналов. // Сборник трудов всероссийской научной конференции «Научное и техническое обеспечение исследований и освоения шельфа северного ледовитого океана». Новосибирск, 2010. — стр. 60-62.

5. Трофимов В.К., Храмова Т.В., Универсальное кодирование сообщений, порожденных неизвестным бернуллиевским источником буквами алфавита с различными длительностями.// Материалы российской научно - технической конференции «Информатика и проблемы телекоммуникаций». Новосибирск, 2011. — том 1, стр. 165-167.

6. Трофимов В.К., Храмова Т.В., Кодирование сообщений, порожденных неизвестным марковским источником при различных длительностях передаваемых сигналов.// Международная конференция «Современные проблемы математики, информатики и биоинформатики» посвященная 100-летию со дня рождения A.A. Ляпунова. Новосибирск, 2011. — стр. 72.

7. Трофимов В.К., Храмова Т.В., Универсальное кодирование сообщений, порожденных неизвестным марковским источником буквами алфавита с различными длительностями.// Российская научная конференция с участием зарубежных исследователей «Моделирование систем информатики». Новосибирск, 2011 — электорнное издание.

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

9. Трофимов В.К., Храмова Т.В., Об избыточности кодирования сообщений неизвестного марковского источника, при различных длительностях передаваемых сигналов.// Материалы российской научно - технической конференции «Обработка информационных сигналов и математическое моделирование». Новосибирск, 2012. — стр. 134-136.

10. Трофимов В.К., Храмова Т.В., Кодирование неизвестного марковского источника информации при неравнозначных длительностях кодовых символов. Материалы 13й международной научно - технической конференции «Измерение, контроль, информатизация». Барнаул, 2012. — том 2, сгр. 227-228.

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

12. Храмова Т.В., Павленко М.С. Сжатие факсимильной информации с применением универсальных методов.// Материалы XI международной научной конференции "Актуальные проблемы электронного приборостроения"АПЭП -2012. Новосибирск, 2012. — том 6, стр. 56-57.

13. Храмова Т.В., Кодирование неизвестного стационарного источника символами неравной длительности. // Материалы 18-й международной научно-практической конференции «Природные и интеллектуальные ресурсы Сибири (Сибресурс-18-2012)» . Томск-Новосибирск, 2012. — стр. 77-81.

Личный вклад автора. В работах [1—3] имеет место неделимое соавторство в разработке общего подхода к методу построения кодирования и доказательстве асимптотической оценки избыточности кодирования; автору принадлежит вывод верхних оценок избыточности универсального кодирования в случае бернуллиев-ских и марковских источников. В работах [5—10] имеет место неделимое соавторство. В работах [11—12] автору принадлежит описание схемы универсального равномерного по входу кодирования и анализ эффективности универсального кодирования.

Введение

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.

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. Тел.: 383 3320320, Факс: 383 3325785, www.daiaeast.ru, e-mail: ¡nfo@dataeast.ru1. УТВЕРЖДАЮ

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

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

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