Mismatched codebooks and the role of entropy coding in lossy data compression
Mismatched codebooks and the role of entropy coding in lossy data compression
复制标题
不匹配的码本和熵编码在有损数据压缩中的作用
DOI：
10.1109/tit.2006.872845
复制
发表时间：
2003
影响因子：
2.5
通讯作者：
R. Zamir
中科院分区：
文献类型：
--
作者：
Ioannis Kontoyiannis;R. Zamir
我们基于随机编码引入了通用量化方案，并分析了其性能。该方案由无源无关的随机代码簿（通常与源分布不匹配），然后是最佳熵编码，该编码与量化的密码字发匹配。在给定失真中，该方案在大型代码书维度的限制下，该方案在给定的失真下得出的速率得出了单个字母公式。量化熵编码引起的速度降低，并表明它可以任意大。在“几乎统一”的代码书的特殊情况下（例如，具有较大差异的独立且相同分布的高斯密码书）和差异失真措施，在本方案实现的压缩和效果之间达成了新的联系”通用”熵编码的抖动晶格量化器。这种连接概括了“半右”结合在抖动晶格量化器的冗余上。此外，它表明了一个强烈的普遍性概念，其中单个“几乎统一”的代码本对于任何来源和任何差异失真度量都是最佳的。证据是基于以下事实：可以精确识别随机代码簿中第一个匹配代码字的经验分布。这是使用精美的大偏差技术完成的，该技术允许衍生有条件限制定理的新“几乎确定”版本。
We introduce a universal quantization scheme based on random coding, and we analyze its performance. This scheme consists of a source-independent random codebook (typically mismatched to the source distribution), followed by optimal entropy coding that is matched to the quantized codeword distribution. A single-letter formula is derived for the rate achieved by this scheme at a given distortion, in the limit of large codebook dimension. The rate reduction due to entropy coding is quantified, and it is shown that it can be arbitrarily large. In the special case of "almost uniform" codebooks (e.g., an independent and identically distributed (i.i.d.) Gaussian codebook with large variance) and difference distortion measures, a novel connection is drawn between the compression achieved by the present scheme and the performance of "universal" entropy-coded dithered lattice quantizers. This connection generalizes the "half-a-bit" bound on the redundancy of dithered lattice quantizers. Moreover, it demonstrates a strong notion of universality where a single "almost uniform" codebook is near optimal for any source and any difference distortion measure. The proofs are based on the fact that the limiting empirical distribution of the first matching codeword in a random codebook can be precisely identified. This is done using elaborate large deviations techniques, that allow the derivation of a new "almost sure" version of the conditional limit theorem.