Международная конференция «Математические и информационные технологии, MIT-2011»
(IX конференция «Вычислительные и информационные технологии в науке,
технике и образовании») № гос. регистрации 0321102644, ISBN 978-5-905569-02-9

Врнячка Баня, Сербия, 27–31 августа 2011 г.

Будва, Черногория, 31 августа – 5 сентября 2011 г.

Монарев В.А.  

Нумерационное кодирование источников Маркова

     Предложен новый метод нумерации последовательностей, порожденных источником Маркова. Нумеруются равновероятные последовательности фиксированной длины. Предполагается, что известна память источника, но не известны переходные вероятности. Ранее известные методы имеют экспоненциальную сложность с ростом длины последовательности, числа состояний и памяти источника, что делает их неприменимыми на практике.  Последний результат в этой области описывает нумерацию для источника Маркова над алфавитом {0, 1} и памяти, равной одному. Описанный в работе метод имеет сложность, эквивалентную сложности нумерации источника Бернулли, описанному в работе Рябко Б.Я., и может быть применен для сжатия информации. Метод также применим в идеальной стеганографической системе, описанной в работе Рябко Б.Я. и Рябко Д.Б.
     Основная идея метода заключается в том, что нумеруется не всё множество равновероятных последовательностей, а его подмножества. С ростом длины последовательностей количество таких подмножеств остается постоянным, что делает метод асимптотически оптимальным.
 

Файл тезисов: Monarev.doc
Файл с полным текстом: monarevVA.pdf


К списку докладов

© 1996-2017, Институт вычислительных технологий СО РАН, Новосибирск