DATA COMPRESSION WITH SOURCE CODING FOR UNKNOWN SOURCE STATISTICS

Previous source coding methods, i.e., Shannon coding, Fano coding and Huffman coding, require precise knowledge of the statistical description of the process to be compressed. This demand is rarely met in practice. Source coding with unknown statistical description or with incomplete or inaccurate statistical description is called universal coding. Minimax redundancy is an performance measure for universal coding. Two universal noiseless source coding methods, source matching and efficient universal source coding, were developed as an approximation to minimax universal coding by Davisson, Leon-Garcia, Pursley, McEliece and Wallace. The redundancies of the source matching game and efficient universal coding are lower and upper bounds of minimax redundancy respectively for finite block length. Both of them are arbitrarily close to the redundancy of minimax coding as block length increases. In this dissertation, these two methods are considered and compared to each other for the class of first-order Markov sources with finite alphabet.