ITR: Noiseless Data Compression Based on Error Correcting Codes

ITR：基于纠错码的无噪声数据压缩

• 批准号: 0312879
• 负责人: Sergio Verdu
• 金额: --
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0312879&HistoricalAwards=false
• 关键词: ITR; Noiseless; Data; Compression; Based

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.

无噪声数据压缩是一种关键的信息技术，用于无数的数据存储和传输应用，从计算机操作系统到调制解调器到有损压缩标准。 虽然目前的数据压缩算法已经达到了一定的成熟度，但在分组噪声信道中，数据压缩算法的计算复杂度已经达到了基本信息理论的极限，因此在第三代高速无线数据传输标准中没有实现有效载荷数据压缩。我们探索了一种替代传统方法的途径，该方法寻求设计和分析无噪声数据压缩器，该压缩器适用于通过噪声信道的分组数据传输，同时保留现有算法在复杂性和消除冗余方面的可替代特性。逼近纠错编解码算法（如低密度奇偶校验码和信念传播，分别）在一个新的方式，利用最近发现的可逆变换（块排序变换），PI和他的合作者先前的研究表明，遍历离散信息源中存在的所有记忆冗余都转移到了单个符号结果中的冗余。这类新算法最令人兴奋的应用是联合数据压缩/传输问题。 虽然Shannon的分离原理建立了当压缩和传输分别执行时不会损失渐近性能的概念，但人们一直期望在非渐近状态下通过联合设计可以获得增益。然而，这一承诺尚未实现，因为现有的在解码器处考虑信源统计的方案只能科普非常简单的模型。