The Research On Integer Coding And Slepian-Wolf Coding

Two important problems in lossless source coding are studied in this thesis.The first problem is the integer coding problem, one of the problems in universal source coding. The performance of Golomb codes for arbitrary probability distributions is analyzed, and then a class of universal codes called extended 7 codes is constructed based on Golomb codes. To understand these integer codes, we present the concept of maximum entropy code, and then prove that Golomb codes and extended 7 codes are maximum entropy codes for two classes of sources respectively. Furthermore, the coding problem of a block of integers is considered, and four practical coding schemes of a block of integers are proposed and then applied to the design of compression algorithm based on Burrows-Wheeler transform. Experimental results of the algorithm indicate lossless coding rates better than those achieved by BWT-based compression algorithms using integer codes.The second problem is the Slepian-Wolf coding problem, one of the problems in distributed source coding. An upper bound on the average MAP decoding error probability of Slepian-Wolf systems for correlated general sources is derived, and a new proof of the direct part of the Slepian-Wolf theorem for correlated general sources is given based on this bound. Moreover, an improved upper bound on the average MAP decoding error probability of linear Slepian-Wolf systems for stationary memoryless sources is derived. Based on this improved bound, we analyze the performance of Slepian-Wolf systems based on LDPC codes and random permutations, and prove that under some conditions, all but diminishingly small proportion of LDPC encoders and permutations are good enough for the design of practical Slepian-Wolf systems when the coding length is very large. Finally, the problem of universal Slepian-Wolf coding is considered. With the power of information spectrum methods, we establish the connection between a priori general sources and universal Slepian-Wolf coding. As an example, we explain the principle of the minimum entropy decoder by finding its corresponding a priori general source.