A RATE OF CONVERGENCE RESULT FOR A UNIVERSAL D-SEMIFAITHFUL CODE
B YU, TP SPEED
IEEE TRANSACTIONS ON INFORMATION THEORY | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | Published : 1993
The problem of optimal rate universal coding in the context of rate-distortion theory is considered. A D-semifaithful universal coding scheme for discrete memoryless sources is given. The main result is a refined covering lemma based on the random coding argument and the method of types. The average codelength of the code is shown to approach its lower bound, the rate-distortion function, at a rate O(n-1 log n), and this is conjectured to be optimal based on a result of Pilc. Issues of constructiveness and universality are also addressed.