UNIVERSAL REDUNDANCY RATES DO NOT EXIST

被引:32
作者
SHIELDS, PC [1 ]
机构
[1] EOTVOS LORAND UNIV, DEPT PROBABIL & STAT, H-1364 BUDAPEST 5, HUNGARY
基金
美国国家科学基金会;
关键词
DATA COMPRESSION; REDUNDANCY; UNIVERSAL CODING;
D O I
10.1109/18.212281
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The expected redundancy per symbol R(n)BAR(mu) of an n-block prefix code C(n) on a source mu measures how far the code is from being optimal for that source. The existence of sequences of codes with R(n)BAR (mu) = O((log n)/n) for ''nice'' classes of sources, such as Markov sources of a given order, is well known. In this paper it is shown that some restriction on the class of processes is necessary in order to obtain such redundancy bounds, for there is no universal redundancy rate for any sequence of prefix codes on the class E of all ergodic sources.
引用
收藏
页码:520 / 524
页数:5
相关论文
共 10 条
[1]   UNIVERSAL NOISELESS CODING [J].
DAVISSON, LD .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (06) :783-795
[2]  
Levenshtein Vladimir I, 1966, SOV PHYS DOKL, V10, P707
[3]  
ORNSTEIN D, 1982, MEMOIRS AMS, V37
[4]   UNIVERSAL ALMOST SURE DATA-COMPRESSION [J].
ORNSTEIN, DS ;
SHIELDS, PC .
ANNALS OF PROBABILITY, 1990, 18 (02) :441-452
[5]   UPPER-BOUNDS ON THE PROBABILITY OF SEQUENCES EMITTED BY FINITE-STATE SOURCES AND ON THE REDUNDANCY OF THE LEMPEL-ZIV ALGORITHM [J].
PLOTNIK, E ;
WEINBERGER, MJ ;
ZIV, J .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1992, 38 (01) :66-72
[6]   STOCHASTIC COMPLEXITY AND MODELING [J].
RISSANEN, J .
ANNALS OF STATISTICS, 1986, 14 (03) :1080-1100
[7]  
SHIELDS PC, 1990, PROBL CONTROL INFORM, V19, P269
[8]  
SHTARKOV J, COMMUNICATION REDUND
[9]  
Shtarkov J., 1977, COLL MATH SOC J BOLY, V16, P559
[10]   UNIVERSAL ALGORITHM FOR SEQUENTIAL DATA COMPRESSION [J].
ZIV, J ;
LEMPEL, A .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1977, 23 (03) :337-343