A new source-splitting approach to Slepian-Wolf problem

We introduce new innovations for data compression to achieve all rates near the theoretical boundary in the Slepian-Wolf problem.

(1) We show that achieving an arbitrary rate point in the achievable region of the M-source Slepian-Wolf problem may be reduced via a practical `source-splitting' transformation to achieving a corner point in a 2M-1 source Slepian-Wolf problem. Moreover, each source must be split at most once. This extends the ideas introduced by Rimoldi and Urbanke ? to a practical setting: it does not require common randomness shared between splitters and the decoder, the cardinality of each source split is strictly smaller than that of the original, and practical iterative decoding methods can achieve rates near the theoretical boundary.

(2) We introduce a linear programming relaxation to maximum-likelihood sequence decoding (MLSD) for block source coding that exhibits the ML-certificate property: if an integral solution is found, it is the ML solution. Formulations for the single-source block coding case and the Slepian-Wolf vertex case are constructed. We show how this source coding LP relaxation is related to the channel coding LP relaxation proposed by Feldman et. al by interpreting the binary block coding case as a relaxation to `coset-leader' decoding on a binary symmetric channel (BSC). This shows the two formulations are equivalent. Establishing this connection with Feldman's LP relaxation also leads to the conclusion that for certain correlation models, easily constructible codes with provably good performance (exponential error decay) can be used with this LP decoder for the Slepian-Wolf problem.

Todd Coleman received B.S. degree from the Univ. of Michigan in 2000, M.S. degree from MIT 2002. He is pursuing his Ph.D. in MIT and is expected to graduate in 2006.