Topics in the analysis of universal compression algorithms
Sanjeev R. Kulkarni, Sergio Verdú, Karthik Visweswariah · 1999
Universal data compression algorithms store data compactly without knowledge of the statistics of the source. In the first part of this thesis we study an application of universal compression algorithms to random bit generation. A random number generator is a deterministic transformation which transforms a given source of randomness into a sequence of independent, equally likely bits. Given a stationary, ergodic input source the highest rate (number of output bits per input symbol) at which such bits can be generated, is the entropy rate of the source. Optimal data compression algorithms store data in a way in which no further compression is possible, so it is natural to postulate that the output of these algorithms is truly random. We show under general conditions that optimal source codes also generate ‘nearly’ random bits at the optimal rate. Thus optimal universal data compression algorithms (like the Lempel-Ziv codes) can be used to generate ‘nearly’ random bits from stationary ergodic sources with unknown distributions. We then consider variable-to-fixed length codes which have been less widely studied than fixed-to-variable length codes. A universal variable-to-fixed length algorithm which converges to the entropy of the source at the optimal rate is known for binary memoryless sources. We study the problem of universal variable-to-fixed length coding for the class of Markov sources with finite alphabets. We give an upper bound on the performance of the code for large dictionary sizes and show that the code is optimal in the sense that no codes exist that have better asymptotic performance. The optimal redundancy is shown to be H log log M/2 log M where H is the entropy rate of the source and M is the code size. This result is analogous to Rissanen's result for fixed-to-variable length codes. We investigate the performance of a variable-to-fixed coding method which does not need to store the dictionaries, either at the coder or the decoder. We also consider the performance of both these codes on individual sequences. For individual sequences we bound the performance in terms of the best code length achievable by a class of codes. We also show that universal variable-to-fixed length codes can be used for transmitting a fixed rate source optimally over a fixed rate channel. Finally we consider universal coding of non-stationary sources. We show that for lossless coding of non-stationary sources Lempel-Ziv coding methods perform as well as any finite state coding scheme. We also investigate some structured classes of non-stationary sources and provide some preliminary results towards finding the optimal redundancy rates for these classes.