The redundancy of source coding with a fidelity criterion - Part II: Coding at a fixed rate level with unknown statistics

The redundancy problem of universal lossy source coding at a fixed rate lev el is considered. Under some condition on the single-letter distortion meas ure, which implies that the cardinality K of the reproduction alphabet is n ot greater than the cardinality J of the source alphabet, it is shown that the redundancy of universally coding memoryless sources p by nth-order bloc k codes of rate R goes like \(partial derivative/partial derivativeR)d(p, R )\K In n/2n + o(ln n/n) for all memoryless sources p except a set whose vol ume goes to 0 as the block length n goes to infinity, where d(p, R) denotes the distortion rate function of p. Specifically, for any sequence {C-n}(n= 1)(infinity) of block codes, where C-n is an nth-order block code at the fi xed rate R, and any epsilon > 0, the redundancy D-n(C-n, p) of C-n for p is greater than or equal to \(partial derivative/partial derivativeR)d(p, R)\ (K - epsilon) In n/2n for all p satisfying some regular conditions except a set whose volume goes to ) as n --> infinity. On the other hand, there exi sts a sequence {C-n}(n=1)(infinity), of block codes at the rate R such that for any p satisfying some regular conditions, the super limit of D-n(C-n,p )/(ln n/n) is less than or equal to \(partial derivative/partial derivative R)d(p, R)\K/2.