Wyner-Ziv coding based on TCQ and LDPC codes

• US 8,207,874 B2
• Filed: 08/04/2008
• Issued: 06/26/2012
• Est. Priority Date: 08/04/2006
• Status: Active Grant

• Current Assignee: Texas A&M University System
• Original Assignee: Texas A&M University System
• Inventors: Yang, Yang, Xiong, Zixiang
• Primary Examiner(s): Lauture, Joseph
• Application Number:
  US12/185,545
• Publication Number:
  US 20090031191A1
• Time in Patent Office: 1,422 Days
• Field of Search: 341/50, 341/87, 714/801
• US Class Current: 341/50
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/6312 Error control coding in combination with data compression
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

An encoder employs a trellis coded quantization (TCQ) unit and a compression unit. The TCQ uses a set of polynomials that have been selected to maximize granular gain. The TCQ unit operates on a block of samples from a source. The compression unit compresses bit planes of the TCQ output, using parity check matrices of corresponding LDPC codes, to obtain corresponding syndromes. The parity check matrices are selected so their compression performance approaches close to the limit for Slepian-Wolf coding. A decoder employs a decoding unit and an estimation unit. The decoding unit decodes the syndromes using side information to produce an estimate for the TCQ output. The side information is correlated with the source. The estimation unit estimates the block of source samples using the estimated TCQ output and the side information. Trellis coded vector quantization may be used as an alternative to TCQ.

Claims

1. A computer system comprising:

a processor; and

memory storing program instructions, wherein the program instructions are executable by the processor to;

perform a trellis-based quantization on a block of samples of a source to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization are selected to maximize granular gain;

compress bit planes of the block of quantization indices using parity check matrices of corresponding low-density parity check (LDPC) codes to obtain corresponding syndromes; and

transmit the syndromes onto a channel.

2. The computer system of claim 1, wherein the source is a continuous source.

3. The computer system of claim 1, wherein each of the parity check matrices is selected to minimize bit error rate for the corresponding bit plane.

4. The computer system of claim 1, wherein at least one of the parity check matrices is optimized to minimize bit error rate for the corresponding bit plane.

5. The computer system of claim 1, wherein the trellis-based quantization is trellis-coded quantization (TCQ).

6. The computer system of claim 5, wherein a number of states of the TCQ is greater than 256.

7. The computer system of claim 5, wherein said TCQ includes a number of stages, wherein at least one of the stages is performed in a parallel fashion.

8. The computer system of claim 1, wherein the trellis-based quantization is trellis-coded vector quantization (TCVQ).

9. The computer system of claim 1, where each of the bit planes is compressed at a rate that approaches close to the limit for Slepian-Wolf coding.

10. The computer system of claim 1, wherein a first of the bit planes is compressed at a rate that approaches close to the limit for Slepian-Wolf coding for the first bit plane.

11. A computer-readable memory medium storing program instructions, wherein the program instructions are executable by one or more processors to:

perform a trellis-based quantization on a block of samples of a source to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization are selected to maximize granular gain;

compress bit planes of the block of quantization indices using parity check matrices of corresponding low-density parity check (LDPC) codes to obtain corresponding syndromes; and

transmit the syndromes onto a channel.

12. The memory medium of claim 11, wherein each of the parity check matrices is selected to minimize bit error rate for the corresponding bit plane.

13. The memory medium of claim 11, wherein at least one of the parity check matrices is optimized to minimize bit error rate for the corresponding bit plane.

14. The memory medium of claim 11, wherein the trellis-based quantization is trellis-coded quantization (TCQ).

15. The memory medium of claim 14, wherein said TCQ includes a number of stages, wherein at least one of the stages is performed in a parallel fashion.

16. The memory medium of claim 11, wherein the trellis-based quantization is trellis-coded vector quantization (TCVQ).

17. The memory medium of claim 11, where each of the bit planes is compressed at a rate that approaches close to the limit for Slepian-Wolf coding.

18. The memory medium of claim 11, wherein a first of the bit planes is compressed at a rate that approaches close to the limit for Slepian-Wolf coding for the first bit plane.

19. A computer system comprising:

a processor; and

memory storing program instructions, wherein the program instructions are executable by the processor to;

receive a set of syndromes from a channel, wherein the set of syndromes are generated by an encoder configured to;

perform trellis-based quantization on a block of samples of a source to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization are selected to maximize granular gain; and

compress bit planes of the block of quantization indices using parity check matrices of corresponding low-density parity check (LDPC) codes to obtain corresponding ones of the syndromes;

decode the syndromes, using side information, to obtain an estimate of the block of quantization indices; and

generate an estimate for the block of source samples using the estimate of the block of quantization indices and the side information.

20. The computer system of claim 19, wherein said decoding the syndromes includes performing an iterative message-passing algorithm.

21. The computer system of claim 19, wherein said decoding the syndromes includes performing a number of successive decoding stages, wherein the decoding stages include a first subset, wherein each decoding stage of the first subset decodes a corresponding bit plane of the syndromes using the side information and one or more decoded bit planes generated by one or more previous ones of the decoding stages.

22. The computer system of claim 19, wherein said generating an estimate for the block of source samples is performed using a nonlinear minimum mean-squared-error estimator.

23. The computer system of claim 19, wherein the trellis-based quantization is trellis-coded quantization (TCQ).

24. The computer system of claim 23, wherein the number of states of the TCQ is greater than 256.

25. The computer system of claim 19, wherein the trellis-based quantization is trellis-coded vector quantization (TCVQ).

26. A computer-readable memory medium storing program instructions, wherein the program instructions are executable by one or more processors to:

receive a set of syndromes from a channel, wherein the set of syndromes are generated by an encoder configured to;

perform trellis-based quantization on a block of samples of a source to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization are selected to maximize granular gain; and

compress bit planes of the block of quantization indices using parity check matrices of corresponding low-density parity check (LDPC) codes to obtain corresponding ones of the syndromes;

decode the syndromes, using side information, to obtain an estimate of the block of quantization indices; and

generate an estimate for the block of source samples using the estimate of the block of quantization indices and the side information.

27. The memory medium of claim 26, wherein said decoding the syndromes includes performing an iterative message-passing algorithm.

28. The memory medium of claim 26, wherein said decoding the syndromes includes performing a number of successive decoding stages, wherein the decoding stages include a first subset, wherein each decoding stage of the first subset decodes a corresponding bit plane of the syndromes using the side information and one or more decoded bit planes generated by one or more previous ones of the decoding stages.

29. The memory medium of claim 26, wherein said generating an estimate for the block of source samples is performed using a nonlinear minimum mean-squared-error estimator.

30. The memory medium of claim 26, wherein the trellis-based quantization is trellis-coded quantization (TCQ).

31. The memory medium of claim 30, wherein the number of states of the TCQ is greater than 256.

32. The memory medium of claim 26, wherein the trellis-based quantization is trellis-coded vector quantization (TCVQ).

33. A method comprising:

a computer system performing a trellis-based quantization on a block of samples of an input signal to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization have been designed to maximize granular gain;

the computer system compressing bit planes of the block of quantization indices using respective parity check matrices that correspond to low-density parity check (LDPC) codes in order to obtain corresponding syndromes; and

the computer system transmitting the syndromes onto a channel.

34. The method of claim 33, wherein each of the parity check matrices has been designed to minimize bit error rate for the corresponding bit plane.

35. The method of claim 33, wherein the trellis-based quantization is trellis-coded quantization (TCQ).

36. The method of claim 35, wherein said TCQ includes a number of stages, wherein at least one of the stages is performed in a parallel fashion.

37. The method of claim 33, wherein the trellis-based quantization is trellis-coded vector quantization (TCVQ).

38. A method, comprising:

receiving, at a computing system, a set of syndromes from a channel, wherein the set of syndromes are generated by an encoding device configured to perform operations comprising;

performing trellis-based quantization on a block of samples of a source to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization are selected to maximize granular gain; and

compressing bit planes of the block of quantization indices using parity check matrices of corresponding low-density parity check (LDPC) codes to obtain corresponding ones of the syndromes;

decoding by the computing system the syndromes, using side information, to obtain an estimate of the block of quantization indices; and

generating by the computing system an estimate for the block of source samples using the estimate of the block of quantization indices and the side information.

39. A non-transitory computer-readable storage medium which stores program instructions executable by a computer system to cause the computer system to:

receive a set of syndromes from a channel, wherein the set of syndromes are generated by an encoder configured to;

perform trellis-based quantization on a block of samples of a source to obtain a block of quantization indices, wherein polynomials of the trellis-based quantization are selected to maximize granular gain; and

compress bit planes of the block of quantization indices using parity check matrices of corresponding low-density parity check (LDPC) codes to obtain corresponding ones of the syndromes;

decode the syndromes, using side information, to obtain an estimate of the block of quantization indices; and

generate an estimate for the block of source samples using the estimate of the block of quantization indices and the side information.