Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems

点击翻译按钮获取中文摘要

Information theory has enjoyed over fifty years of rigorous research,development, and application.In spite of its relative maturity,new challenges arise due to novel applications and emerging theoreticaldevelopments (e.g., there is a resurgence of interest in sourcecoding in multimedia applications, molecular biology, and security).In the 1997 Shannon Lecture Jacob Zivpresented compelling arguments for ``backing off'' to a certain extentfrom first-order asymptotic analysis of informationsystems in order to predict the behavior of real systems withfinite (and often small) lengths (of sequences, files, codes,databases, etc.) One way of overcoming these difficulties is toincrease accuracy of asymptotic analysis by replacing first-orderanalyses (e.g., a leading term of the average code length)by full asymptotic expansions and moreaccurate analyses (e.g., large deviations, central limit laws).This research primarily focuses on an important aspect ofsource coding, namely, the redundancy rate problem.Recent years have seen a resurgence of interest inredundancy rates of lossless and lossy coding.We describe analytic, combinatorial and algorithmic methods thatwork hand in hand to solve this and other problems in information theory.The redundancy rate problem fora class of sources corresponds to determining the extent to whichthe actual code length exceeds the optimal code length.This problem is an ideal candidatefor second-order asymptoticssince one must look beyond the leading term of the code length,which is known to be the entropy of the source.Following Hadamard's precept we study these problems usingtechniques of complex analysis such as generating functions,Rice's formula, Mellin transform, Fourier series,sequence distributed modulo 1, saddle point methods,analytic poissonization and depoissonization, andsingularity analysis. We present new results forwell-studied problems (e.g., optimal codes for maximal redundancy,memoryless and Markovian sources) as well as novel formulations of old problems(e.g., redundancy of the class of mixing sources, redundancy ofarithmetic coding and the Lemepl-Ziv codes). Furthermore,we apply the techniques developed as a part of this studyto related problems such as prediction (based on pattern matching),random number generators, the average worst case probability ofundetected error in channel coding, pattern matching approach to(exact and approximate) run length coding, and others.