Distributed source coding

Distributed Source Coding (DSC) refers to the compression of multiple correlated information sources that do not communicate with each other . Unlike other source coding technologies, channel codes are used for data compression.

It is a highly interested data compression technology in sensor networks and video/multimedia compression (see Distributed Video Coding (DVC)). One of the main properties of Distributed source coding is that the computational burden in encoders has been shifted to the joint decoder.

Theoretical bounds

The theoretical lossless compression bound (Slepian-wolf bound) has been first purposed by David Slepian and Jack Keil Wolf in terms of entropies of correlated information sources in 1973. They have also proved that two isolated sources are able to be compressed as efficient as they communicating with each other. This bound has been extended to more than two correlated source case by Thomas M. Cover in 1975.

Similar results were obtained in 1976 by Aaron D. Wyner and Jacob Ziv with regard to lossy coding of joint Gaussian sources.

History

Syndrome decoding technology has been first used in distributed source coding by SS Pradhan and K Ramachandran so-called DIstributed Source Coding Using Syndromes (DISCUS). They compress binary block data from one source into syndromes and transmit data from the other source uncompressed as side information. This kind of DSC scheme achieves asymmetric compression rates per sources and so-called Asymmetric DSC. Obviously, this asymmetric DSC scheme can be easily extended to more than two correlated information source case. There are also some DSC schemes using parity-check bit rather than syndrome bits.

The correlation between two sources in DSC has been modelled as a virtual channel which is usually referred as a Binary symmetric channel.

With deterministic and probabilistic discussions of correlation model of two correlated information sources, DSC schemes with more general compressed rates have been developed. In these DSC schemes, both of two correlated sources are compressed. Therefore this kind of DSC scheme is called Non-asymmetric DSC.

Under a certain deterministic assumption of correlation between information sources, a DSC framework has been shown by X. Cao and M. Kuijper that any number of information sources is able to be compressed in the distributed way. This method performs non-asymmetric compression with flexible rates per source, achieving the same overall compression rate as repeatedly applying asymmetric DSC for more than two sources.

Slepian-Wolf bound

$R_{x}\geq H(x|y)$ ,

$R_{y}\geq H(y|x)$,

$R_{x}+R_{y}\geq H(x,y)$

Virtual Channel

Deterministic model

Probabilistic model