2006/02/13 by Emin Martinian, Martin J. Wainwright, Martinian, Emin +1
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0602046
5 pages; to appear in Workshop on Information Theory and its Applications, February 2006, San Diego
arxiv created 2006/02/13 · openalex publication_date 2006/02/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recent work has suggested that low-density generator matrix (LDGM) codes are likely to be effective for lossy source coding problems. We derive rigorous upper bounds on the effective rate-distortion function of LDGM codes for the binary symmetric source, showing that they quickly approach the rate-distortion function as the degree increases. We also compare and contrast the standard LDGM construction with a compound LDPC/LDGM construction introduced in our previous work, which provably saturates the rate-distortion bound with finite degrees. Moreover, this compound construction can be used to generate nested codes that are simultaneously good as source and channel codes, and are hence well-suited to source/channel coding with side information. The sparse and high-girth graphical structure of our constructions render them well-suited to message-passing encoding.