Fixed-rate universal codes for Markov sources
David L. Neuhoff, Paul C. Shields · IEEE Transactions on Information Theory · 1978
The existence of a fixed-rate block source code whose performance for each source in a class of Markov sources is uniformly close to the distortion-rate function of that source is investigated. Such a code is called strong universal. It is found that strong universal codes of all rates exist for the class of all binary first-order Markov sources. But for a larger alphabet or for the class of allnth-order Markov sources withn > 2, there is a critical rateR\astsuch that strong universal codes exist for rates greater than or equal toR\ast, but not for rates less thanR\ast.