Distributed source coding (DSC) is an important problem in information theory and communication. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other."Distributed source coding for sensor networks" by Z. Xiong, A.D. Liveris, and S. Cheng By modeling the correlation between multiple sources at the decoder side together with channel codes, DSC is able to shift the computational complexity from encoder side to decoder side, therefore provide appropriate frameworks for applications with complexity-constrained sender, such as sensor networks and video/multimedia compression (see distributed video coding"Distributed video coding in wireless sensor networks" by Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K. ). One of the main properties of distributed source coding is that the computational burden in encoders is shifted to the joint decoder.
History In 1973, David Slepian and Jack Keil Wolf proposed the information theoretical lossless compression bound on distributed compression of two correlated i.i.d. sources X and Y."Noiseless coding of correlated information sources" by D. Slepian and J. Wolf After that, this bound was extended to cases with more than two sources by Thomas M. Cover in 1975,"A proof of the data compression theorem of Slepian and Wolf for ergodic sources" by T. Cover while the theoretical results in the lossy compression case are presented by Aaron D. Wyner and Jacob Ziv in 1976."The rate-distortion function for source coding with side information at the decoder" by A. Wyner and J. Ziv
Although the theorems on DSC were proposed on 1970s, it was after about 30 years that attempts were started for practical techniques, based on the idea that DSC is closely related to channel coding proposed in 1974 by Aaron D. Wyner."Recent results in Shannon theory" by A. D. Wyner The asymmetric DSC problem was addressed by S. S. Pradhan and K. Ramchandran in 1999, which focused on statistically dependent binary and Gaussian sources and used scalar and trellis coset constructions to solve the problem."Distributed source coding using syndromes (DISCUS): design and construction" by S. S. Pradhan and K. Ramchandran They further extended the work into the symmetric DSC case."Distributed source coding: symmetric rates and applications to sensor networks" by S. S. Pradhan and K. Ramchandran
Syndrome decoding technology was first used in distributed source coding by the DISCUS system of SS Pradhan and K Ramachandran (Distributed Source Coding Using Syndromes). 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 source and results in asymmetric DSC. This asymmetric DSC scheme can be easily extended to the case of more than two correlated information sources. There are also some DSC schemes that use parity bits rather than syndrome bits.
The correlation between two sources in DSC has been modeled as a virtual channel which is usually referred as a binary symmetric channel."Distributed code constructions for the entire Slepian–Wolf rate region for arbitrarily correlated sources" by Schonberg, D. Ramchandran, K. Pradhan, S.S."Generalized coset codes for distributed binning" by Pradhan, S.S. Ramchandran, K.
Starting from DISCUS, DSC has attracted significant research activity and more sophisticated channel coding techniques have been adopted into DSC frameworks, such as Turbo Code, LDPC Code, and so on. Sparse-matrix constructions are another coding-theoretic line: Muramatsu and Miyake introduced a hash-property framework for sparse matrix ensembles and maximum-likelihood coding, proving achievability for Wyner-Ziv coding and related source-coding problems.
Similar to the previous lossless coding framework based on Slepian–Wolf theorem, efforts have been taken on lossy cases based on the Wyner–Ziv theorem. Theoretical results on quantizer designs was provided by R. Zamir and S. Shamai,"Nested linear/lattice codes for Wyner–Ziv encoding" by R. Zamir and S. Shamai while different frameworks have been proposed based on this result, including a nested lattice quantizer and a trellis-coded quantizer.
Moreover, DSC has been used in video compression for applications which require low complexity video encoding, such as sensor networks, multiview video camcorders, and so on."Distributed Video Coding" by B. Girod, etc.
With deterministic and probabilistic discussions of correlation model of two correlated information sources, DSC schemes with more general compressed rates have been developed."On code design for the Slepian–Wolf problem and lossless multiterminal networks" by Stankovic, V. Liveris, A.D. Zixiang Xiong Georghiades, C.N."A general and optimal framework to achieve the entire rate region for Slepian–Wolf coding" by P. Tan and J. Li"Distributed source coding using short to moderate length rate-compatible LDPC codes: the entire Slepian–Wolf rate region" by Sartipi, M. Fekri, F. In these non-asymmetric schemes, both of two correlated sources are compressed.
Under a certain deterministic assumption of correlation between information sources, a DSC framework in which any number of information sources can be compressed in a distributed way has been demonstrated by X. Cao and M. Kuijper."A distributed source coding framework for multiple sources" by Xiaomin Cao and Kuijper, M. This method performs non-asymmetric compression with flexible rates for each source, achieving the same overall compression rate as repeatedly applying asymmetric DSC for more than two sources. Then, by investigating the unique connection between syndromes and complementary codewords of linear codes, they have translated the major steps of DSC joint decoding into syndrome decoding followed by channel encoding via a linear block code and also via its complement code,"Distributed Source Coding via Linear Block Codes: A General Framework for Multiple Sources" by Xiaomin Cao and Kuijper, M. which theoretically illustrated a method of assembling a DSC joint decoder from linear code encoders and decoders.
Theoretical bounds The information theoretical lossless compression bound on DSC (the Slepian–Wolf bound) was first purposed by David Slepian and Jack Keil Wolf in terms of entropies of correlated information sources in 1973. They also showed that two isolated sources can compress data as efficiently as if they were communicating with each other. This bound has been extended to the case of more than two correlated sources 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.
Slepian–Wolf bound Distributed Coding is the coding of two or more dependent sources with separate encoders and joint decoder. Given two statistically dependent i.i.d. finite-alphabet random sequences X and Y, Slepian–Wolf theorem includes theoretical bound for the lossless coding rate for distributed coding of the two sources as below:
If both the encoder and decoder of the two sources are independent, the lowest rate we can achieve for lossless compression is and for and respectively, where and are the entropies of and . However, with joint decoding, if vanishing error probability for long sequences is accepted, the Slepian–Wolf theorem shows that much better compression rate can be achieved. As long as the total rate of and is larger than their joint entropy and none of the sources is encoded with a rate larger than its entropy, distributed coding can achieve arbitrarily small error probability for long sequences.
A special case of distributed coding is compression with decoder side information, where source is available at the decoder side but not accessible at the encoder side. This can be treated as the condition that has already been used to encode , while we intend to use to encode . The whole system is operating in an asymmetric way (compression rate for the two sources are asymmetric).
Wyner–Ziv bound Shortly after Slepian–Wolf theorem on lossless distributed compression was published, the extension to lossy compression with decoder side information was proposed as Wyner–Ziv theorem. Similarly to lossless case, two statistically dependent i.i.d. sources and are given, where is available at the decoder side but not accessible at the encoder side. Instead of lossless compression in Slepian–Wolf theorem, Wyner–Ziv theorem looked into the lossy compression case.
The Wyner–Ziv theorem presents the achievable lower bound for the bit rate of at given distortion . It was found that for Gaussian memoryless sources and mean-squared error distortion, the lower bound for the bit rate of remain the same no matter whether side information is available at the encoder or not.
For more than two terminals, multiterminal source coding studies rate-distortion regions when several correlated observations are encoded separately and decoded jointly. Yasutada Oohama derived results for Gaussian multiterminal source coding, a central continuous-alphabet case of this problem.
Virtual channel Deterministic model
Probabilistic model
Asymmetric DSC vs. symmetric DSC Asymmetric DSC means that, different bitrates are used in coding the input sources, while same bitrate is used in symmetric DSC. Taking a DSC design with two sources for example, in this example and are two discrete, memoryless, uniformly distributed sources which generate set of variables and of length 7 bits and the Hamming distance between and is at most one. The Slepian–Wolf bound for them is:
This means, the theoretical bound is and symmetric DSC means 5 bits for each source. Other pairs with are asymmetric cases with different bit rate distributions between and , where , and , represent two extreme cases called decoding with side information.
Practical distributed source coding
Slepian–Wolf coding – lossless distributed coding It was understood that Slepian–Wolf coding is closely related to channel coding in 1974, and after about 30 years, practical DSC started to be implemented by different channel codes. The motivation behind the use of channel codes is from two sources case, the correlation between input sources can be modeled as a virtual channel which has input as source and output as source . The DISCUS system proposed by S. S. Pradhan and K. Ramchandran in 1999 implemented DSC with syndrome decoding, which worked for asymmetric case and was further extended to symmetric case.
The basic framework of syndrome based DSC is that, for each source, its input space is partitioned into several cosets according to the particular channel coding method used. Every input of each source gets an output indicating which coset the input belongs to, and the joint decoder can decode all inputs by received coset indices and dependence between sources. The design of channel codes should consider the correlation between input sources.
A group of codes can be used to generate coset partitions,"Coset codes. I. Introduction and geometrical classification" by G. D. Forney such as trellis codes and lattice codes. Pradhan and Ramchandran designed rules for construction of sub-codes for each source, and presented result of trellis-based coset constructions in DSC, which is based on convolution code and set-partitioning rules as in Trellis modulation, as well as lattice code based DSC. After this, embedded trellis code was proposed for asymmetric coding as an improvement over their results."Design of trellis codes for source coding with side information at the decoder" by X. Wang and M. Orchard