Равномерное по выходу кодирование дискретных стационарных источников сообщений с неизвестной статистикой | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 1(14).

Равномерное по выходу кодирование дискретных стационарных источников сообщений с неизвестной статистикой

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

The uniform length-to-block coding of discrete stationary sources of messages with unknownstatistic..pdf Проблемы сжатия (кодирования) информации [1] относятся к фундаменталь-ным в области инфокоммуникаций. Как отмечено в книги В.Г. Хорошевского [2],решение этих проблем значимо и при создании большемасштабных распределён-ных вычислительных систем. Методы сжатия информации в таких системах, какправило, используют параллельные информационно-вычислительные технологии.Настоящая работа посвящена кодированию информации, порождённой источ-ником, в классической постановке К. Шеннона [1]. Вопросы сжатия данных такжерассматривались Ф.П. Тарасенко [3].1. Основные определения. Постановка задачиПусть буквы конечного алфавита A = {a1, a2, …, ak}, 2 ≤ k < , порождаютсяисточником . Мера, заданная на последовательности букв, порождаемой источ-ником, определяет тип источника. Если буквы порождаются независимо, то ис-точник называют бернуллиевским. В этом случае P(aj) = j, 1 + 1 + … + k = 1,где P(aj) - вероятность порождения буквы aj источником . Если же появлениеочередной буквы зависит от предыдущей, то для условной вероятности P(ai /aj)появления буквы ai после aj имеют место равенства P(ai /aj) = ij,11kiji= = ,j = 1, k , и в этом случае источник называют марковским. Если появление очеред-ной буквы зависит от s предшествующих букв, то условные вероятности( ) P aj определяются равенствами P(aj / v) = jv, где vAs , источник назы-вают марковским с памятью S. Следует отметить, что для любого слова vAs ,0 ≤ s < , выполняется равенство11kjj= = . Множество всех марковских источ-ников с памятью S обозначим s . Дискретный стационарный источник задаётсявсеми условными распределениями вероятностей P(aj / v) = jv порождения ис-точником букв aj, , j = 1, k , при заданных предшествующих v, VAs , s любое це-лое неотрицательное число, причём при любом заданном V, vAs , s = 0, 1, 2,… ,выполняется равенство 1+2+

Скачать электронную версию публикации

Загружен, раз: 327

Ключевые слова

capacity, redundancy, coding, стоимость кодирования, кодирование, избыточность

Авторы

ФИО	Организация	Дополнительно	E-mail
Трофимов Виктор Куприянович	Сибирский государственный университет телекоммуникаций и информатики (г. Новосибирск)	профессор, доктор технических наук, декан факультета информатики и вычислительной техники, заведующий кафедрой высшей математики	trofimov@sibsutis.ru

Всего: 1

Ссылки

Sergio Verdu. Fifty Years of Shannon Theory // IEEE Trans. Inform. Theory. 1998. VIT 44. No 6. P. 2057−2077.

Krichevsky R. Universal Compression and Retrieval. London, 1994. 219 p.

Трофимов В.К. Равномерное по выходу кодирование марковских источников при неизвестной статистике // Пятый Международный симпозиум по теории информации. 1979. Ч. II. C.172−175.

Shtarkov Yu.M., Babkin V.F. Combinatorial encoding for discrete stationary sources // 2 Internat. Sуmр. on Inform. Theory Tsahkadzor. 1973. P. 249−256.

Krichevskii R.E., Trofimov V.K. The performace of universal encoding // IEEE Trans. Inform. Theory. 1981. V. IT-27. No. 2. P. 199−207.

Ziv J. Variable-to-fixed length codes are better than fixed-to-variable length cоdes for marcov sources // IEEE Trans. Inform. Theory. 1990. V. 36. No.4. P. 861−863.

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

Трофимов В.К. Эффективное кодирование блоками слов различной длины, порождённых известным марковским источником // Обработка информации в системах связи. Л.: ЛЭИС, 1985. С. 9−15.

Jelinek F., Shneider K. On variable-length to block coding // IEEE Trans. Inform. Theory. 1972. V.18. No. 6. P. 756−774.

Khоdak G.L. Cоding оf markov sources with low redundancy // Рroc. of 2 International Sуmр. Inform. Theory Tsahkadzor. 1973. P. 201−204.

Гильберт Э.Н., Мур Э.Ф. Двоичные кодовые системы переменной длины // Кибернетический сборник. М.: ИЛ, 1961. № 3. C. 103−141.

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

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

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

Могульский А.А., Трофимов В.К. Тождество Вальда и стоимость кодирования для цепей Маркова // VII Всесоюзная конференция по теории кодирования и передачи информации (Теория информации). М.; Вильнюс, 1978. Ч. I. C. 112−116.

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

Фано Р. Передача информации. Статистическая теория связи. М.: Мир, 1965. 440 с.

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

Шеннон К. Математическая теория связи. Работы по теории информации и кибернетике. М.: ИЛ, 1969. С. 243−332.