ITR: Noiseless Data Compression Based on Error Correcting Codes

点击翻译按钮获取中文摘要

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.