A RATE OF CONVERGENCE RESULT FOR A UNIVERSAL D-SEMIFAITHFUL CODE

The problem of optimal rate universal coding in the context of rate-di stortion theory is considered. A D-semifaithful universal coding schem e for discrete memoryless sources is given. The main result is a refin ed covering lemma based on the random coding argument and the method o f types. The average codelength of the code is shown to appraoch its l ower 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.