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 年的香农讲座中，Jacob Ziv 提出了在一定程度上“放弃”信息系统的一阶渐近分析以预测真实系统行为的令人信服的论据具有有限（且通常很小）长度（序列、文件、代码、数据库等）的克服这些困难的一种方法是通过替换一阶分析（例如，平均代码长度的首项）来提高渐近分析的准确性完全渐近展开和更准确的分析（例如大偏差、中心极限定律）。这项研究主要集中在信源编码的一个重要方面，即冗余率问题。近年来人们对无损和有损编码的冗余率重新产生了兴趣。我们描述了分析、组合和算法方法，这些方法携手解决信息论中的这个问题和其他问题。一类源的冗余率问题对应于确定冗余率的程度实际代码长度超过最佳代码长度。这个问题是二阶渐近问题的理想候选者，因为我们必须超越代码长度的首项，已知它是遵循哈达玛的原则，我们使用复分析技术来研究这些问题，例如生成函数、赖斯公式、梅林变换、傅立叶级数、序列分布模 1、鞍点方法、解析泊松化和去泊松化以及奇异性分析。 我们提出了经过充分研究的问题的新结果（例如，最大冗余、无记忆和马尔可夫源的最优代码）以及旧问题的新颖表述（例如，混合源类的冗余、算术编码的冗余和 Lemepl-Ziv 代码） ）。此外，我们将作为本研究的一部分开发的技术应用于相关问题，例如预测（基于模式匹配）、随机数生成器、信道编码中未检测到的错误的平均最坏情况概率、（精确和近似）运行的模式匹配方法长度编码等。