面向逐级细化压缩的两阶段通用随机编码系综与无类型可达性构造

《Poultry》：Universal Random Coding for Successive Refinement of Individual Sequences Based on Lempel–Ziv Complexity

　　摘要本工作将此前针对个体序列的逐样本有损压缩所提出的通用随机编码系综扩展到两阶段（逐级细化）设置中——如后文所述，这一扩展并非十分直接。该构建包含三个层次。第一层：在类型类和典型序列的语言下，给出一个完整的、自包含的充分/必要条件匹配，即Rimoldi经典刻画（应用于块构成的超级字母表）的两阶段类比。第二层：通过一种基于Lempel–Ziv（LZ78）复杂度的随机编码方案来实现相同的码率，而非依赖第一层所依赖的类型类均匀测度，原因在于基于LZ的系综在信源统计和失真度量上都是通用的，其码本本身不携带块长参数，且可直接实现。第三层：我们给出一个完全无类型的可达性构造（在其搜索准则的任何地方都不出现?维向量的联合类型），并证明它精确匹配第一层的必要条件，从而到达可达区域的每一个点：第一层的同一必要条件已经约束了任何码——包括无类型方案在内——因此无需额外的论证即可确认二者匹配。我们还描述了（但不给出证明）如何将无类型构造推广到任意固定数量的阶段。最后，我们证明本文所得的可达区域是另一篇姊妹论文的可达区域的超集，后者基于有限状态建模方法来处理类似的二阶段问题，并将已知的单阶段支配结果推广到了二阶段情形。