A Caltech Library Service

Low-Complexity Approaches to Slepian–Wolf Near-Lossless Distributed Data Compression

Coleman, Todd P. and Lee, Anna H. and Médard, Muriel and Effros, Michelle (2006) Low-Complexity Approaches to Slepian–Wolf Near-Lossless Distributed Data Compression. IEEE Transactions on Information Theory, 52 (8). pp. 3546-3561. ISSN 0018-9448. doi:10.1109/TIT.2006.878215.

See Usage Policy.


Use this Persistent URL to link to this item:


This paper discusses the Slepian–Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable region. The technique employs a simple “source-splitting” strategy that does not require common sources of randomness at the encoders and decoders. This approach allows for pipelined encoding and decoding so that the system operates with the complexity of a single user encoder and decoder. Moreover, when this splitting approach is used in conjunction with iterative decoding methods, it produces a significant simplification of the decoding process. We demonstrate this approach for synthetically generated data. Finally, we consider the Slepian–Wolf problem when linear codes are used as syndrome-formers and consider a linear programming relaxation to maximum-likelihood (ML) sequence decoding. We note that the fractional vertices of the relaxed polytope compete with the optimal solution in a manner analogous to that observed when the “min-sum” iterative decoding algorithm is applied. This relaxation exhibits the ML-certificate property: if an integral solution is found, it is the ML solution. For symmetric binary joint distributions, we show that selecting easily constructable “expander”-style low-density parity check codes (LDPCs) as syndrome-formers admits a positive error exponent and therefore provably good performance.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received October 5, 2004; revised March 30, 2006. [Posted online: 2006-07-24] This work was supported in part by an NSF Graduate Research Fellowship under NSF Grant CCR-0220039, the National Reconnaissance Office, and Caltech’s Lee Center for Advanced Networking. The material presented in this paper was presented in part at the IEEE Data Compression Conference, Snowbird, UT, March 2004, the IEEE International Symposium on Information Theory, Chicago, IL, July 2004, and the IEEE International Conference on Acoustics, Speech, and Signal Processing, Philadelphia, PA, March 2005. Communicated by V. A. Vaishampayan, Associate Editor At Large. The authors thank Jon Feldman, Ralf Koetter, and Karen Haigh for their helpful discussions and comments.
Subject Keywords:Block codes, communication systems, data compression, decoding, iterative methods
Issue or Number:8
Record Number:CaltechAUTHORS:COLieeetit06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4595
Deposited By: Archive Administrator
Deposited On:29 Aug 2006
Last Modified:08 Nov 2021 20:18

Repository Staff Only: item control page