CIF: Small: Non-Asymptotic Information Theory

在实时语音和高速数据应用中，有限的延迟是一个关键的设计约束；实际上，在无线系统中，短至几百位的数据包大小很常见。本研究的目的是超越传统的对基本渐近信息理论极限的改进，并研究在给定块长度编码时产生的容量（在信道编码中）和熵（在无损压缩中）的开销以及率失真函数（在有损源编码中）。我们计划重新审视源于容量，率失真函数和最小源编码率分析的主要设计原则，并查看其中哪些仍然适用于非渐近制度，对于那些不适用的，评估因遵守短块长度而产生的惩罚。我们对可实现的最佳速率作为块长度和错误概率的函数的非渐近行为的研究涉及两个互补的目标：a)可计算的上界和下界足够紧密，以将非渐近操作基本极限上的不确定性降低到与长块长度渐近的差距相比可以忽略不计的水平；B)对即使对于短块长度也准确的边界的解析近似，从而提供对良好编码策略的见解，并使实际相关的优化问题成为可能。这些近似通常涉及我们称之为色散的参数，它量化了源和通道的随机可变性。

In real-time voice and high-speed data applications, limited delay is a key design constraint; indeed, packet sizes as short as a few hundred bits are common in wireless systems. The objective of this research is to go beyond traditional refinements to the fundamental asymptotic information theoretic limits and investigate the back-off from capacity (in channel coding) and the overhead over entropy (in lossless compression) and the rate-distortion function (in lossy source coding) incurred by coding at a given blocklength. We plan to revisit the major design principles stemming from the analysis of capacity, rate-distortion function and minimum source coding rate and see which of them still apply in the non-asymptotic regime, and for those that do not, assess the penalty incurred by abiding by them for short blocklengths. Our study of the non-asymptotic behavior of the optimum rate achievable as a function of both blocklength and error probability involves two complementary goals:a) computable upper and lower bounds tight enough to reduce the uncertainty on the non-asymptotic operational fundamental limit to a level that is negligible compared to the gap to the long-blocklength asymptotics; b) analytical approximations to the bounds that are accurate even for short blocklengths, so as to offer insights into good coding strategies and enable practically relevant optimization problems. Those approximations typically involve a parameter we refer to as dispersion, which quantifies the stochastic variability of sources and channels.