×

Coding of combinatorial sources and Hausdorff dimension. (English. Russian original) Zbl 0581.94007

Sov. Math., Dokl. 30, 219-222 (1984); translation from Dokl. Akad. Nauk SSSR 277, 1066-1070 (1984).
In this note we consider the problem of coding combinatorial (nonprobabilistic) sources given by an arbitrary set of infinite words in some finite alphabet. The main result is Theorem 1, which asserts that the Hausdorff dimension of the image of an arbitrary source J under the natural mapping of J into the interval [0,1] is the attainable infinum of the coding cost on J. This is an analogue of Shannon’s theorem on noiseless coding, with the Hausdorff dimension playing the role of the entropy. Moreoer, for ergodic sources the entropy is equal to the Hausdorff dimension; therefore, Theorem 1 is a generalization of Shannon’s theorem.

MSC:

94A29 Source coding
94A17 Measures of information, entropy
PDFBibTeX XMLCite