【作者】 杨胜天；

【导师】 仇佩亮；

【作者基本信息】 浙江大学 ， 通信与信息系统， 2005， 博士

【摘要】 论文研究了无损信源编码中两个重要的问题 第一个问题是通用信源编码中的整数编码问题。论文分析了任意分布下Golomb码的性能,并在Golomb码的基础上构造了一类通用的扩展γ码。为了理解这些整数码,论文提出了最大熵码的概念,并证明了Golomb码和扩展γ码分别是两类信源下的最大熵码。此外,论文还考虑了一组整数的编码问题,提出了四个实用的一组整数的编码方案,并将其应用于基于Burrows-Wheeler变换的压缩算法设计中,实验结果表明其压缩比率要优于采用整数码的BWT类压缩算法。 第二个问题是分布式信源编码中的Slepian-Wolf编码问题。论文在相关一般信源下推导出Slepian-Wolf系统平均MAP译码错误概率的一个上界,并在此基础上,给出了相关一般信源下Slepian-Wolf定理正命题部分的一个新证明。然后,论文在相关平稳无记忆信源下推导出线性Slepian-Wolf系统平均MAP译码错误概率的一个改进上界,并在这一改进上界的基础上,分析了基于LDPC码和随机置换的Slepian-Wolf系统的性能,证明了在一定的条件下,当编码长度非常大时,几乎所有的LDPC编码器和置换对于实际Slepian-Wolf系统的设计都是足够好的。最后,论文对通用Slepian-Wolf编码问题作了探讨,依靠信息谱方法建立了先验一般信源与通用Slepian-Wolf编码间的联系。作为一个例子,论文通过给出最小熵译码器所对应的先验一般信源,揭示了其通用编码的原理。更多还原

【Abstract】 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.更多还原