Noiseless pression with LDPC codes.pdf

DIMACS Series in Discrete Mathematics and puter Science Noiseless pression with Low-Density Parity-Check Codes Giuseppe Caire, Shlomo Shamai, and Sergio Verd′u paper presents a new approach to universal - pression based on error correcting codes. The scheme is based on the con- catenation of the Burrows-Wheeler block sorting transform (BWT) with the syndrome former of a Low-Density Parity-Check (LDPC) code. The proposed scheme has linear encoding and decoding times and uses a new closed-loop iterative doping algorithm that works in conjunction with belief-propagation decoding. Unlike the leading pression methods our method is resilient against errors, and lends itself to joint source-channel encoding/decoding; fur- thermore it o?ers petitive pression performance. 1. Introduction Lossless pression algorithms ?nd numerous applications in information technology. To name some of the major ones: ?packing utilities (such asgzip) in operating systems such as Windows, Linux and Unix; ?modem standards such as and ; ?fax standards such ITT; ?the back-end of pression algorithms such as JPEG and MPEG; ?compression of headers of TCP/IP packets in works. Indeed, the ?eld of lossless pression has achieved a state of maturity, with algorithms that admit fast (plexity) implementations and achieve asymptotically the fundamental information theoretic limits. However, emerging high-speed wireless data transmission systems send their payloads pressed. The main reasons for the failure of the state-of-the-art in wireless works to take into account source redundancy in those applications are: ?Lack of resilience of pressors to transmission errors. 1991Mathematics Subject Classi? 68P30, 94A29; Secondary 94A45, 62B10. Key words and pression, Universal algorithms, Error Correcting Codes, Source Coding, Sources with Memory, Block Sorting Transform. c°0000 (copyright holder) 1 2 GIUSEPPE CAIRE, SHLOMO SHAMAI, AND SERGI