Data encoding and decoding using Slepian-Wolf coded nested quantization to achieve Wyner-Ziv coding
A system and method for realizing a Wyner-Ziv encoder may involve the following steps: (a) apply nested quantization to input data from an information source in order to generate intermediate data; and (b) encode the intermediate data using an asymmetric Slepian-Wolf encoder in order to generate compressed output data representing the input data. Similarly, a Wyner-Ziv decoder may be realized by: (1) applying an asymmetric Slepian-Wolf decoder to compressed input data using side information to generate intermediate values, and (b) jointly decoding the intermediate values using the side information to generate decompressed output data.
1. A method comprising:
(a) receiving compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receiving a block of samples of a second source Y;
(c) applying an asymmetric Slepian-Wolf decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values; and
(d) performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
2. The method of claim 1 , wherein the function is the conditional probability density function of the first source X given said corresponding sample of the second source block.
3. The method of claim 1 , wherein the region of space is a union of cells corresponding to a coset of a coarse lattice in a fine lattice, wherein the coset is identified by the intermediate value.
4. The method of claim 1 , wherein said determining the centroid estimate is performed by reading the centroid estimate from a table stored in memory using said corresponding sample of the second source block and the intermediate value as addresses.
5. The method of claim 1 , wherein said determining the centroid estimate comprises performing a Monte Carlo iterative simulation.
6. The method of claim 1 , wherein the intermediate values specify cosets of a coarse lattice in a fine lattice, wherein the coarse lattice is a sublattice of the fine lattice.
7. The method of claim 1 , wherein (a) and (b) are performed in parallel.
8. The method of claim 1 , wherein said asymmetric Slepian-Wolf decoder is a multi-layered decoder.
9. The method of claim 1 , wherein the asymmetric Slepian-Wolf decoder achieves a decoding rate that approaches close to the limit for Slepian-Wolf coding, wherein the decompressed output value is digital data.
10. The method of claim 1 , wherein said applying the asymmetric Slepian-Wolf decoder and said performing joint decoding are realized by any subset of:
(a) one or more processors executing program instructions;
(b) one or more programmable hardware elements; and
(c) dedicated circuitry.
11. The method of claim 1 , wherein the asymmetric Slepian-Wolf decoder is an iterative decoder based on one or more LDPC codes.
12. The method of claim 1 , wherein the asymmetric Slepian-Wolf decoder is an iterative decoder based on one or more turbo codes.
13. A method for computing a table representing a nested quantization decoder, the method comprising:
(a) computing a realization z of a first random vector;
(b) computing a realization y of a second random vector;
(c) adding z and y to determine a realization x of a source vector;
(d) quantizing the realization x to a point in a fine lattice;
(e) computing an index J identifying a coset of a coarse lattice in the fine lattice based on the fine lattice point;
(f) adding the realization x to a cumulative sum corresponding to the index J and the realization y;
(g) incrementing a count value corresponding to the index J and the realization y;
(h) repeating operations (a) through (g) a number of times;
(i) dividing the cumulative sums by their corresponding count values to obtain resultant values; and
(j) storing the resultant values in a memory medium.
14. A system for decoding compressed data, the system comprising:
a memory configured to store data and program instructions; and
a processor configured to read and execute the program instructions from the memory, wherein in response to execution of the program instructions, the processor is operable to:
(a) receive compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receive a block of samples of a second source Y;
(c) apply an asymmetric Slepian-Wolf decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values; and
(d) perform joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
15. The system of claim 14 , wherein the function is the conditional probability density function of the first source X given said corresponding sample of the second source block.
16. The system of claim 14 , wherein the asymmetric Slepian-Wolf decoder achieves a decoding rate that approaches close to the limit for Slepian-Wolf coding, wherein the decompressed output value is digital data.
17. The system of claim 14 , wherein the asymmetric Slepian-Wolf decoder is an iterative decoder based on one or more LDPC codes.
18. The system of claim 14 , wherein the asymmetric Slepian-Wolf decoder is an iterative decoder based on one or more turbo codes.
19. A system for computing a table representing a nested quantization decoder, the system comprising:
a memory configured to store data and program instructions; and
a processor configured to read and execute the program instructions from the memory, wherein in response to execution of the program instructions, the processor is operable to:
(a) computing a realization z of a first random vector;
(b) computing a realization y of a second random vector;
(c) adding z and y to determine a realization x of a source vector;
(d) quantizing the realization x to a point in a fine lattice;
(e) computing an index J identifying a coset of a coarse lattice in the fine lattice based on the fine lattice point;
(f) adding the realization x to a cumulative sum conesponding to the index J and the realization y;
(g) incrementing a count value corresponding to the index J and the realization y;
(h) repeating operations (a) through (g) a number of times;
(i) dividing the cumulative sums by their conesponding count values to obtain resultant values; and
(j) storing the resultant values in a memory medium.
20. A computer-readable memory medium configured to store program instructions, wherein the program instructions are executable to implement:
(a) receiving compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receiving a block of samples of a second source Y;
(c) applying an asymmetric Slepian-Woif decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values; and
(d) performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
21. The computer-readable memory medium of claim 20 , wherein the function is the conditional probability density function of the first source X given said corresponding sample of the second source block.
22. The memory medium of claim 20 , wherein the asymmetric Slepian-Wolf decoder achieves a decoding rate that approaches close to the limit for Slepian-Wolf coding, wherein the decompressed output value is digital data.
23. The memory medium of claim 20 , wherein the asymmetric Slepian-Wolf decoder is an iterative decoder based on one or more LDPC codes.
24. The memory medium of claim 20 , wherein the asymmetric Slepian-Wolf decoder is an iterative decoder based on one or more turbo codes.
25. A computer-readable memory medium configured to store program instructions, wherein the program instructions are executable to implement:
(a) computing a realization z of a first random vector;
(b) computing a realization y of a second random vector;
(c) adding z and y to determine a realization x of a source vector;
(d) quantizing the realization x to a point in a fine lattice;
(e) computing an index J identifying a coset of a coarse lattice in the fine lattice based on the fine lattice point;
(f) adding the realization x to a cumulative sum corresponding to the index J and the realization y;
(g) incrementing a count value corresponding to the index J and the realization y;
(h) repeating operations (a) through (g) a number of times;
(i) dividing the cumulative sums by their corresponding count values to obtain resultant values; and
(j) storing the resultant values in a memory medium.
26. A system comprising:
a first means for decompressing compressed input data using side information, wherein the compressed input data is a compressed representation of a block of samples of a first source X, wherein the side information is a block of samples of a second source Y, wherein said applying generates a block of intermediate values;
a second means for performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
27. A method comprising:
(a) receiving compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receiving a block of samples of a second source Y;
(c) applying an iterative decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values, wherein the iterative decoder is based on one or more low density parity check codes;
(d) performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
28. A method comprising:
(a) receiving compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receiving a block of samples of a second source Y;
(c) applying an iterative decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values, wherein the iterative decoder is based on one or more turbo codes;
(d) performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
29. A system for decoding compressed data, the system comprising:
a memory configured to store data and program instructions; and
a processor configured to read and execute the program instructions from the memory, wherein in response to execution of the program instructions, the processor is operable to:
(a) receive compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receive a block of samples of a second source Y;
(c) apply an iterative decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values, wherein the iterative decoder is based on one or more low density parity check codes;
(d) perform joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
30. A system for decoding compressed data, the system comprising:
a memory configured to store data and program instructions; and
a processor configured to read and execute the program instructions from the memory, wherein in response to execution of the program instructions, the processor is operable to:
(a) receive compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receive a block of samples of a second source Y;
(c) apply an iterative decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values, wherein the iterative decoder is based on one or more turbo codes;
(d) perform joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
31. A computer-readable memory medium configured to store program instructions, wherein the program instructions are executable to implement:
(a) receiving compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receiving a block of samples of a second source Y;
(c) applying an iterative decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values, wherein the iterative decoder is based on one or more low density parity check codes;
(d) performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.
32. A computer-readable memory medium configured to store program instructions, wherein the program instructions are executable to implement:
(a) receiving compressed input data, wherein the compressed input data is a compressed representation of a block of samples of a first source X;
(b) receiving a block of samples of a second source Y;
(c) applying an iterative decoder to the compressed input data using the block of samples of the second source Y, wherein said applying generates a block of intermediate values, wherein the iterative decoder is based on one or more turbo codes;
(d) performing joint decoding on each intermediate value and a corresponding sample of the block of second source samples to obtain a corresponding decompressed output value, wherein said performing joint decoding includes determining an estimate of a centroid of a function restricted to a region of space corresponding to the intermediate value, wherein said estimate determines the decompressed output value.