International Conference «Mathematical and Informational Technologies, MIT-2011»
(IX Conference «Computational and Informational Technologies for Science,
Engineering and Education»)

Vrnjacka Banja, Serbia, August, 27–31, 2011

Budva, Montenegro, August, 31 – September, 5, 2011

Монарев В.А.  

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

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

Abstracts file: Monarev.doc
Full text file: monarevVA.pdf


To reports list

© 1996-2019, Institute of computational technologies of SB RAS, Novosibirsk