IEEE Transactions on Information Theory · 1971 · 28 citations · 9 references
EngineeringComputer ScienceGame TheoryInformation TheoryProbability TheoryChannel CodingCoding TheoryError Control CodingError-correcting CodesRate-distortion TheorySource CodingFinite Blocklength CodingFinite Blocklength Rate-distortionFinite Blocklength Source CodingRandom Coding ArgumentsRate-distortion FunctionRate-distortion TradeoffSource Coding With Finite Blocklength
The encoding of a source whose probability distribution varies arbitrarily from letter to letter is considered. The problem is formulated as a two-person statistical game. The exponential rate of growth with block length of the minimum number of codewords needed to achieve a specified fidelity with respect to a single-letter distortion measure is determined. The rate distortion function of a source whose statistics are entirely unknown is obtained as a special case. The dependence of the results on the rules under which the game is played also is studied. The analysis is based on a refinement of the usual random coding argument for sources which sheds new light on the significance of the term that decays at a doubly exponential rate with block length.
9