Z. Zhang et al., THE REDUNDANCY OF SOURCE-CODING WITH A FIDELITY-CRITERION .1. KNOWN STATISTICS, IEEE transactions on information theory, 43(1), 1997, pp. 71-91
Citations number
45
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
The problem of redundancy of source coding with respect to a fidelity
criterion is considered, For any fixed rate R > 0 and any memoryless s
ource with finite source and reproduction alphabets and a common distr
ibution p, the nth-order distortion redundancy D-n(R) of fixed-rate co
ding is defined as the minimum of the difference between the expected
distortion per symbol of any block code with length n and rate R and t
he distortion rate function d(p, R) of the source p. It is demonstrate
d that for sufficiently large n, D-n(R) is equal to -(partial derivati
ve/partial derivative R)d(p, R) 1n n/2n + o(1n n/n), where (partial de
rivative/partial derivative)d(p, R) is the partial derivative of d(p,
R) evaluated at R and assumed to exist. For any fixed distortion level
d > 0 and any memoryless source p, the nth-order rate redundancy R(n)
(d) of coding at fixed distortion level d (or by using d-semifaithful
codes) is defined as the minimum of the difference between the expecte
d rate per symbol of any d-semifaithful code of length n and the rate-
distortion function R(p, d) of p evaluated at d, It is proved that for
sufficiently large n, R(n)(d) is upper-bounded by In nln + o(ln n/n)
and lower-bounded by In n/2n + o(ln n/n). As a by-product, the lower b
ound of R(n)(d) derived in this paper gives a positive answer to a rec
ent conjecture proposed by Yu and Speed.