LDPC Codes Can Approach the Slepian Wolf Bound for General Binary Sources

Daniel Schonberg and Sandeep Pradhan1
(Professor Kannan Ramchandran)
(DARPA) F30602-00-2-0538 and (NSF) CCR-0219722

We propose a constructive framework for distributed lossless source coding of two binary sources that have arbitrary correlation structures (Figure 1), i.e., not just symmetric correlation structures of the form of Y = X + N where X and N are independent. Our proposed framework accommodates the important special case of the absence of any correlation between the two sources, wherein it becomes an entropy coding scheme for a single source (Figure 2). This framework is obtained by combining Low-density parity check (LDPC) codes with the distributed source coding using syndromes (DISCUS) framework of [1]. This combined algorithm is powerful enough to reach the Slepian-Wolf bound for two memoryless binary sources and the entropy rate for a single memoryless binary source.


Figure 1: Block diagram of symmetric DISCUS. Two sources are compressed independently and reconstructed at the receiver.

Figure 2: Symmetric DISCUS construction used for lossless coding, or in the special case of zero correlation between sources.

[1]
S.S. Pradhan and K. Ramchandran, "Distributed Source Coding Using Syndromes (DISCUS): Design and Construction," IEEE Data Compression Conf., Snowbird, UT, March 1999.
1Professor, University of Michigan

Send mail to the author : (dschonbe@eecs.berkeley.edu)


Edit this abstract