Method and apparatus for constructing efficient slepian-wolf codes with mismatched decoding

1. Field of the Invention

The present application generally relates to methods and apparatuses for construction of codes for data-compression and, more particularly, to a method and apparatus for constructing efficient Slepian-Wolf codes for mismatched coding.

2. Background Description

Slepian-Wolf codes refer to codes used for compressing source data at an encoder, where the decoder has access to side information not available to the encoder. There are many applications of these codes. Examples of such applications include, but are not limited to, low complexity encoding of media, distributed source coding for sensor networks, scalable video coding, etc.

FIG. 1 shows a generic Slepian-Wolf coding system. The signal X n =X 1 X 2 . . . X n , termed the Slepian-Wolf source 100 , is compressed by the encoder 101 using a Slepian-Wolf code, the output of which is a set of symbols termed syndromes 102 . These syndromes represent the compressed source signal. The decoder 103 receives a signal Y n =Y 1 Y 2 . . . Y n , termed the Slepian-Wolf side information 104 , which is used to decode the signal X n from the syndromes. Without loss of generality, it can be assumed that X i and Y i take values in discrete sets {0, 1, . . . , M−1} and {0, 1 . . . , N−1}, respectively, for all i=1, 2, . . . , n. The efficiency of compression (measured by the bit rate of the syndromes required to decode X successfully) depends, among other factors, on the joint distribution of X i and Y i (denoted by P XY ), the goodness of the Slepian-Wolf code employed, and the decoding method. The better the Slepian-Wolf code, the lower is the number of syndrome bit required for successful decoding for a given joint distribution and a decoding method.

Previous methods for designing Slepian-Wolf code are reported by S. S. Pradhan and K. Ramchandran, “Distributed source coding using syndromes (DISCUS): design and construction”, IEEE Transactions on Information Theory , pp. 626-643, March 2003, J. Garcia-Frais and Y. Zhao, “Compression of correlated binary sources using turbo codes”, IEEE Communication Letters, 5:417-419, October 2001, V. Stankovic, A. Liveris, Z. Xiong, and C. Georghiades, “On code design for the general Slepian-Wolf problem and for lossless multiterminal communications networks”, IEEE Transactions on Information Theory , pp. 1495-1507, April 2006, J. Bajcsy and P. Mitran, “Coding for the Slepian-Wolf problem with turbo codes”, IEEE Globecom . pp. 1400-1404, November 2001, A. Aaron and B. Girod, “Compression with side information using turbo codes”, Proceedings of the IEEE Data Compression Conference ( DCC ), pp. 252-261, April 2002, A. D. Liveris et al., “Compression of binary sources with side information at the decoder using LDPC codes”, IEEE Communication Letters , vol. 6, pp. 440-442, 2002, J. Chen, D. He and A. Jagmohan, “Slepain-Wolf code design via source-channel correspondence”, Proceedings of IEEE International Symposium on Information Theory , July 2006. These methods are developed under the assumption that the joint distribution P XY is perfectly known and the decoder uses a decoding metric that is matched to P XY .

FIG. 2 shows an exemplary conventional method for constructing Slepian-Wolf codes. The input 200 to the design method is the probability distribution P XY . The joint distribution 200 is first converted to a cyclic-symmetric channel distribution 201 , i.e., Q V|U , with input alphabet {0, 1, . . . , M−1} and output alphabet {0, 1, . . . , M−1}×{0, 1, . . . , N−1}. The channel Q V|U is related to P XY through the equation V=(U+ M X,Y), where U is independent of (X,Y) whose distribution is P XY , and + M denotes modulo-M addition. The cyclic-symmetric channel Q V|U is then used to compute the initial message value 202 , i.e., m 0 (ν), through the equation:

m 0 ⁡ ( v ) = [ log ⁢ Q V | U ⁡ ( v | 1 ) Q V | U ⁡ ( v | 0 ) , log ⁢ Q V | U ⁡ ( v | 2 ) Q V | U ⁡ ( v | 0 ) , … ⁢ , log ⁢ Q V | U ⁡ ( v | M - 1 ) Q V | U ⁡ ( v | 0 ) ] , v ∈ { 01 , … ⁢ , M - 1 } × { 0 , 1 , … ⁢ , N -

The initial message value m 0 (ν) and the probability distribution P XY are used to determine the probability distribution of m 0 (V), i.e., P m 0 203 by setting the probability distribution of V equal to P XY . Given P m 0 , the density evolution means 204 , which consists of the density evolution algorithm and the standard degree distribution optimization methods, outputs an optimized degree distribution 205 . The construction of Slepian-Wolf codes given the degree distribution is straightforward.

However, for real applications, it is impossible to obtain a completely accurate estimation of the joint probability distribution P XY . Let {circumflex over (P)} XY denote the estimated probability distribution that is used by the decoder to recover the source signal X n given the syndromes and the side information Y n . For the case in which {circumflex over (P)} XY is different from P XY , the decoder is mismatched to the true probability distribution (and therefore, the decoding is referred to as mismatched decoding). For practical Slepian-Wolf coding systems, it is essential that the imperfect knowledge of P XY is taken into account when designing Slepian-Wolf codes. It is also important to choose the optimal decoding metric in the mismatched decoding case, where the decoding metric is the joint probability distribution used for decoding. However, there are no previously known computationally feasible methods for constructing good Slepian-Wolf codes with mismatched decoding and choosing the optimum decoding metric.

Therefore, a need exists for an improved method for Slepian-Wolf code design wherein mismatched decoding resulting from the imperfect knowledge of joint probability distribution is taken into account. There also exists a need for an improved method for choosing the optimal decoding metric in the mismatched decoding case.

It is an object of this invention to improve methods for constructing efficient Slepian-Wolf codes with mismatched decoding.

Another object of the present invention is to provide a method for choosing the optimal decoding metric when the true probability distribution is not completely known.

These and other objectives are attained with a new method for designing Slepian-Wolf codes. The method includes the steps of: choosing representative probability distributions from a given set of possible probability distributions; computing a set of initial message probability distributions given the representative probability distributions and a fixed decoding metric; using density evolution to obtain an optimized degree distribution given a set of initial message probability distributions; optimizing the decoding metric so that the resulting degree distribution yields the lowest syndrome bit rate.

The preferred embodiment of the invention provides a method for constructing Slepian-Wolf codes with mismatched decoding. It allows the design of efficient and robust Slepian-Wolf codes for a prescribed set of probability distributions and a fixed decoding metric. The preferred embodiment of the invention also provides a method for choosing the optimal decoding metric when the true probability distribution is not completely known.

The key advantage of the present invention is that it can be used to construct Slepian-Wolf codes that are robust to mismatched decoding.

The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

FIG. 1 is a block diagram illustrating the Slepian-Wolf coding method;

FIG. 2 is a block diagram illustrating a conventional Slepian-Wolf code design system;

FIG. 3 is a block diagram illustrating an embodiment of the present invention for constructing Slepian-Wolf codes with mismatched decoding; and

FIG. 4 is a block diagram illustrating a data compress and decompression system based on the present invention.

Embodiments of the present invention disclosed herein are intended to be illustrative only, since numerous modifications and variations of these embodiments will be apparent to those of ordinary skill in the art. In reference to the drawings, like numbers will indicate like parts continuously throughout the views.

FIG. 3 depicts an exemplary embodiment of an apparatus which implements the method for constructing efficient Slepian-Wolf codes with mismatched decoding and choosing the optimal decoding metric. The inputs consist of a set of possible probability distributions 300 , i.e., P, and a decoding metric set 301 , i.e., {circumflex over (P)}. The output consists of a degree distribution 302 and a decoding metric 303 , i.e. P XY *.

The key component of the method is a Slepian-Wolf code generator 304 for mismatched decoding with two inputs: a set of representative probability distributions 305 (e.g., P XY (1) , P XY (2) , . . . , P XY (m) ) from P and a tentative decoding metric {circumflex over (P)} XY 306 from the decoding metric set {circumflex over (P)}. The decoding metric {circumflex over (P)} XY is first converted to a cyclic-symmetric channel 307 , i.e., {circumflex over (Q)} V|U , with input alphabet {0, 1, . . . , M−1} and output alphabet {0, 1, . . . , M−1}×{0, 1, . . . , N−1}. The channel {circumflex over (Q)} V|U is determined by {circumflex over (P)} XY through the equation V=(U+ M X,Y), where U is independent of (X,Y) whose distribution is {circumflex over (P)} XY , and + M denotes modulo-M addition. The cyclic-symmetric channel {circumflex over (Q)} V|U is then used to compute the initial message value 308 , i.e., {circumflex over (m)} 0 (ν), through the equation:

m ^ 0 ⁡ ( v ) = [ log ⁢ Q ^ V | U ⁡ ( v | 1 ) Q ^ V | U ⁡ ( v | 0 ) , log ⁢ Q ^ V | U ⁡ ( v | 2 ) Q ^ V | U ⁡ ( v | 0 ) , … ⁢ , log ⁢ Q ^ V | U ⁡ ( v | M - 1 ) Q ^ V | U ⁡ ( v | 0 ) ] , v ∈ { 01 , … ⁢ , M - 1 } × { 0 , 1 , … ⁢ , N -

The initial message value {circumflex over (m)} 0 (ν) and the probability distribution P XY (i) are used to determine the probability distribution of {circumflex over (m)} 0 (V), i.e., P {circumflex over (m)} 0 (i) (output 309 ) by setting the probability distribution of V equal to P XY (i) (i=1, 2, . . . , m). Given P {circumflex over (m)} 0 (1) , P {circumflex over (m)} 0 (2) , . . . , P {circumflex over (m)} 0 (m) , the density evolution means 310 , which consists of the density evolution algorithm and the standard degree distribution optimization methods, outputs an optimized degree distribution 311 such that the decoding error probability for every initial message distribution P {circumflex over (m)} 0 (i) (i=1, 2, . . . , m) converges to zero under density evolution.

The representative probability distributions are chosen from P by a distribution selector 312 . Only a few illustrative selection methods will be given here, since numerous modifications and variations will be straightforward to those of ordinary skill in the art. In the case where P is characterized by some parameters, the set of representative distributions can be chosen by sampling the parameters. For example, if P is a set of probability distributions {P (λ) } parameterized by λ with λ between 0 and 1, then P (1) and P (2) may be chosen as the representative probability distributions for P. In general, the number of representative probability distributions depends on the desired level of accuracy as well as the computational complexity constraints. In the case where P is a finite set, the set of representative probability distributions could be P itself.

The rate of degree distribution 311 outputted from the Slepian-Wolf code generator 304 is calculated using a rate computer 313 , and is stored in a rate buffer 314 .

The decoding metric set {circumflex over (P)} could be different from P. The size of {circumflex over (P)} can be chosen according to the computational complexity constraint. The tentative decoding metric {circumflex over (P)} XY is chosen from {circumflex over (P)} by a decoding metric selector 315 . The selection can be based on the rates in the rate buffer. In the case where {circumflex over (P)} is a finite set, the decoding metric selector can use exhaustive search to optimize over {circumflex over (P)} XY so that the resulting degree distribution yields the lowest syndrome bit rate. The decoding metric selector can also use gradient search. Modified selection rules based on other search methods are obvious to those of ordinary skill in the art.

Finally, the optimum {circumflex over (P)} XY is output as the decoding metric 303 , i.e., P XY *, and the associated degree distribution 302 . The construction of Slepian-Wolf codes given the degree distribution is straightforward to those of ordinary skill in the art.

FIG. 4 shows an exemplary embodiment of a Slepian-Wolf data compression and decompression system using the presented invention. Given a set of possible probability distributions 400 and a set of decoding metrics 401 , the presented new Slepian-Wolf code design outputs a degree distribution 402 and a decoding metric 403 . The data compressor 405 encodes the source data 404 using the degree distribution 402 (more precisely, the data compressor 405 encodes the source data 404 using the Slepian-Wolf code induced by the degree distribution 402 ) and sends the syndrome 406 to the data decompressor 407 . The data decompressor 407 reconstructs the data source 409 using the syndrome 406 , the decoding metric 403 and the side information 408 .

While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.