The uniform length-to-block coding of discrete stationary sources of messages with unknownstatistic.
The problem of compression by steady code of data emitted by a discrete stationary source isconsidered. A uniform-to-block coding of Bernuly's sources was considered first in papers of G.Hodack, F.Jelinek, E.Shredenger. Markov's sources with known messages statistic were studiedby the author and L. Ziv. The universal uniform-to-block coding of Bernuly's and Markov'ssources is studied by D. Lourenz, Y. Shtar'kov.The question of existence of universal uniform-to-block codes for stationary sources remainedopen. The goal of this paper is to proof the following statements.Theorem 1. Weak universal uniform -to-block coding exists for set of all stationary sources.Let S(n) be the approximation of stationary source of by Markov's one with thememory S(n). The following statement holds.Theorem 2. For existing of the universal uniform-to-block coding for the stationary source'sset it is necessary and sufficient that entropy ( ) H S(n) evenly converges to entropy H () onthe set , with S(n)tending to infinity.Remark. The statement of theorem 1 guarantees the existence of code which redundancytends to 0 for any stationary source, but not uniformly on .The second theorem gives the conditions which the set of sources has to satisfy, in order forredundancy's tendingg to 0 were uniform.
Keywords
capacity,
redundancy,
coding,
стоимость кодирования,
кодирование,
избыточностьAuthors
| Trofimov Victor K. | Siberian State University of Telecommunications and Information Sciences | trofimov@sibsutis.ru |
Всего: 1
References
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.
