Noiseless Data Compression is a key information technology used in innumerable data storage and transmission applications ranging from computer operating systems to modems to lossy compression standards. Although the state-of-the-art has reached a certain level of maturity, with data compression algorithms that reach the 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-generation standards for high-speed wireless data transmission.
In this project, we explore an alternative avenue to the conventional approach which seeks to design and analyze noiseless data compressors that are suitable for use in packetized data transmission through noisy channels while retaining the favorable properties of existing algorithms in terms of complexity and elimination of redundancy. The new approach is based on the use of modern capacity-approaching error-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 reversible transformation (block-sorting transform), which previous research by the PI and his collaborators has shown to transfer essentially all the memory redundancy present in ergodic discrete information sources to redundancy in the individual symbol outcomes. One of the most exciting applications of the new class of algorithms is the problem of joint data compression/transmission. While Shannon's separation principle establishes no loss in asymptotic performance when compression and transmission are performed separately, it has long been expected that, in the nonasymptotic regime, gains may accrue by joint design. However, this promise has not yet been realized as existing schemes that take into account the source statistics at the decoder can only cope with very simplistic models.
