The redundancy of universal coding with fidelity criterion
Daiji Ishii and Hirosuke Yamamoto
- The redundancy of universal lossy data compression for discrete memoryless sources is considered in terms of type and $d$-ball covering. It is shown that there exists a universal $d$-semifaithful code whose rate redundancy is upper bounded by $(A-\frac12) n^{-1}\ln n +\mbox{o}(n^{-1}\ln n)$, where $A$ is the cardinality of source alphabet and $n$ is the block length of the code. This new bound is tighter than known ones, and moreover, it turns out to be the attainable minimum of the universal coding proposed by Davisson.
- Key words: universal d-semifaithful code, rate-distortion function, rate redundancy, n-type, d-ball covering
- PDF (416 Kbytes) Copyright(c)1997 IEICE