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

分析信息论、组合学和算法：精确冗余及相关问题

• 批准号: 0208709
• 负责人: Wojciech Szpankowski
• 金额: $ 21.5万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-01 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208709&HistoricalAwards=false
• 关键词: Analytic; Information; Theory; Combinatorics; Algorithmics

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.

信息论已经经历了五十多年的严格研究、发展和应用。尽管它相对成熟，但由于新的应用和新兴的理论发展（例如，在1997年的Shannon Lecture中，Jacob Ziv提出了一个令人信服的论点，即在一定程度上从信息系统的一阶渐近分析中"后退“，以预测具有有限（通常很小）长度（序列、文件、代码、数据库等）的真实的系统的行为。克服这些困难的一种方法是通过取代一阶分析（例如，平均码长的首项）通过完全渐近展开和更精确的分析（例如，大偏差，中心极限定律）。本研究主要集中在信源编码的一个重要方面，即冗余率问题。近年来，人们对无损和有损编码的冗余率重新产生了兴趣。我们描述了分析，组合和算法方法，携手合作，以解决这一问题和其他问题的信息论。冗余率问题为一类来源对应于确定实际码长超过最佳码长的程度。这个问题是二阶渐近的理想候选者，因为人们必须超越码长的首项，这是已知的源的熵。遵循Hadamard的原则，我们使用复分析技术，如生成函数，Rice公式，Mellin变换，傅立叶级数，序列分布模1，鞍点法、解析泊松化和去泊松化以及奇异性分析。 我们提出了新的结果forwell研究的问题（例如，用于最大冗余、无记忆和马尔可夫源的最优编码）以及旧问题的新公式（例如，混合源类的冗余、算术编码和Lemepl-Ziv码的冗余）。此外，我们应用的技术开发作为本研究的一部分，相关的问题，如预测（基于模式匹配），随机数发生器，平均最坏情况下的概率ofundetected错误的信道编码，模式匹配方法（精确和近似）运行长度编码，和其他。