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.