Efficient prefix coding of uncertainty spaces (Q1905215)

In classical information theory the codeword length is a random variable, and a given code is regarded as efficient if the expected codeword length is sufficiently small. The information-theoretical notion of efficient coding, however, is neither the only possible one nor the best in any specific sense. Thus, many coding applications require minimizing not the expectation of codword length but the expectation of some function of this length. Other cases require minimizing the quantity which is not an expectation at all, for instance, the maximum codeword length or the total sum of lengths of all codewords. There are, of course, also more complex requirements, which do not fit the information-theoretical partial definition of efficiency. We show that the notion of uncertainty space [cf. ibid. 29, No. 4, 606-612 (1993; Zbl 0812.60002)]\ makes it possible to replace the many partial definitions of efficient code with one general definition, and then apply the apparatus of uncertainty spaces to solve efficient coding problems. The present paper is also closely related to the paper reviewed below, which provides various examples of interpretation of uncertainty spaces that can be applied to the corresponding coding problems.