ITR: Noiseless Data Compression Based on Error Correcting Codes

无噪声数据压缩是一种关键的信息技术，用于从计算机操作系统到调制解调器再到有损压缩标准的无数数据存储和传输应用。虽然最新的数据压缩算法已经达到了一定的成熟度，数据压缩算法以线性的计算复杂度达到了基本的信息论极限，但它们在分组噪声信道中应用时存在一些缺点。因此，目前第三代高速无线数据传输标准中没有实现有效载荷数据压缩。在本项目中，我们探索了一种替代传统方法的方法，该方法试图设计和分析适合于在有噪声的信道中使用分组数据传输的无噪声数据压缩器，同时保持现有算法在复杂性和消除冗余性方面的有利特性。新方法基于以一种新颖的方式使用现代接近容量的纠错编码和解码算法(例如分别是低密度奇偶校验码和信任传播)，该方法利用最近发现的可逆变换(块排序变换)，PI和他的合作者之前的研究表明，它基本上将遍历离散信息源中存在的所有存储冗余转移到单个符号结果中的冗余。这类新算法最令人兴奋的应用之一是联合数据压缩/传输问题。虽然香农的分离原理建立了当压缩和传输分别执行时不会损失渐近性能的结论，但人们早就期望在非渐近区域，通过联合设计可以获得增益，然而，这一承诺尚未实现，因为现有的考虑译码端信源统计的方案只能处理非常简单的模型。

Noiseless Data Compression is a key information technology used in innumerabledata storage and transmission applications ranging from computer operating systemsto modems to lossy compression standards. Although the state-of-the-art hasreached a certain level of maturity, with data compression algorithms that reachthe fundamental information theoretic limits with linear computational complexity,they suffer from several shortcomings when used in packetized noisy channels.For this reason, no payload data compression is currently implemented in third-generationstandards for high-speed wireless data transmission.In this project, we explore an alternative avenue to the conventional approachwhich seeks to design and analyze noiseless data compressors that are suitable for usein packetized data transmission through noisy channels while retaining the favorableproperties of existing algorithms in terms of complexity and elimination of redundancy.The new approach is based on the use of modern capacity-approachingerror-correcting encoding and decoding algorithms(such as low density parity check codes and belief propagation, respectively)in a novel way that capitalizes on the recent discovery of a reversibletransformation (block-sorting transform), whichprevious research by the PI and his collaborators has shown to transferessentially all the memory redundancy present in ergodicdiscrete information sources to redundancy in the individual symbol outcomes.One of the most exciting applications of the new class of algorithmsis the problem of joint data compression/transmission. While Shannon'sseparation principle establishes no loss in asymptotic performancewhen compression and transmission are performed separately, it has long beenexpected that, in the nonasymptotic regime, gains may accrue by joint design.However, this promise has not yet been realized as existing schemes that take intoaccount the source statistics at the decoder can only cope with very simplistic models.