System and method for iterative denoising and error correction decoding

• US 7,971,131 B1
• Filed: 06/24/2005
• Issued: 06/28/2011
• Est. Priority Date: 05/06/2005
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ordentilch, Erik, Weissman, Itschak (Tsachy), Seroussi, Gadlel, Vlswanathan, Krishnamurthy, Weinberger, Marcelo, Verdu, Sergio
• Primary Examiner(s): Baderman; Scott T
• Assistant Examiner(s): Ahmed; Enam
• Application Number:
  US11/166,895
• Time in Patent Office: 2,195 Days
• Field of Search: 714/786
• US Class Current: 714/786
• 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/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/3738 with judging correct decoding
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/612 Aspects specific to channel or signal-to-noise ratio estimation H03M13/63 takes precedence
• CPC Class Codes: H03M 13/6337 Error control coding in combination with channel estimation
• CPC Class Codes: H03M 13/6511 Support of multiple decoding rules, e.g. combined MAP and Viterbi decoding
• CPC Class Codes: H03M 13/6561 Parallelized implementations
• CPC Class Codes: H03M 13/6577 Representation or format of variables, register sizes or word-lengths and quantization
• CPC Class Codes: H03M 13/6583 Normalization other than scaling, e.g. by subtraction
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation

Abstract

Systems and methods for iterative denoising and error correction decoding are presented. In an embodiment, a system iteratively processes a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal. A denoiser generates reliability information for symbols in the input signal. The reliability information is generated by forming a product of received reliability information and an estimate of the distribution of metasymbols in the input signal, each metasymbol includes context symbols and a corresponding input symbol, and summing over values for the context symbols corresponding to the particular input symbol. An error correction decoder performs error correction decoding using the generated reliability information. In another embodiment, the reliability information is generated by forming a hard-decision decoded signal from received reliability information, determining metasymbol counts from the hard-decision decoded signal and solving an equation whose coefficients are obtained from the received reliability information and the metasymbol counts.

Claims

1. A system comprising:

a denoiser that receives a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal and for generating reliability information for symbols in the input signal, said generating comprising for a particular input symbol forming a product of received reliability information and an estimate of the distribution of metasymbols in the input signal, each metasymbol including context symbols and a corresponding symbol, and summing over values for the context symbols corresponding to the particular input symbol; and

an error correction decoder for performing error correction decoding using the generated reliability information.

2. The system according to claim 1, wherein for each of a plurality of iterations of processing, the denoiser generates reliability information and the decoder performs error correction decoding to form new reliability information.

3. The system according to claim 2, wherein the new reliability information for an iteration of processing comprises the received reliability information used by the denoiser for performing a next iteration of processing.

4. The system according to claim 3, wherein the reliability information generated by the decoder for each iteration updates a-priori reliability information for systematic symbols for use by the decoder.

5. The system according to claim 4, wherein parameters for an internal state of the decoder other than the a-priori reliability information for systematic symbols are unchanged between iterations of the denoiser generating reliability information and the decoder performing error correction decoding.

6. The system according to claim 4, wherein parameters for an internal state of the decoder other than the a-priori reliability information for systematic symbols are reset between iterations of the denoiser generating reliability information and the decoder performing error correction decoding.

7. The system according to claim 1, further comprising a preliminary processing stage that performs an iteration of soft output denoising and soft input, soft output error correction decoding on a signal received from the noise-introducing channel.

8. The system according to claim 7, wherein the preliminary processing stage comprises a preliminary stage denoiser and wherein the preliminary stage denoiser counts occurrences of metasymbols in the noisy signal, a portion of each metasymbol providing a context for a symbol of the metasymbol and, for each metasymbol occurring in the noisy message blocks, determines preliminary stage reliability information from the counts obtained by the preliminary stage denoiser and from symbol-transition probabilities for the noise-introducing channel.

9. The system according to claim 1, wherein the estimate of the distribution of metasymbols in the input signal is determined by performing successive steps of matrix inversion to obtain a joint distribution of j input symbols and k-j output symbols and wherein for each step the value of j is advanced by one until j is equal to k, wherein k is the size of the metasymbol.

10. The system according to claim 9, wherein a smoothing operation is performed at each step of matrix inversion.

11. The system according to claim 1, wherein the estimate of the distribution of metasymbols in the input signal is derived from occurrence counts of metasymbols in a hard decision decoded signal formed from received reliability information.

12. A system comprising:

a denoiser that receives a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal and for generating reliability information for symbols in the input signal, said generating comprising forming a hard-decision decoded signal from received reliability information, determining metasymbol counts for the hard-decision decoded signal and solving an equation whose coefficients are obtained from the received reliability information and the metasymbol counts; and

an error correction decoder for performing error correction decoding using the generated reliability information.

13. The system according to claim 12, wherein the equation is quadratic.

14. The system according to claim 12, wherein for each of a plurality of iterations of processing, the denoiser generates reliability information and the decoder performs error correction decoding to form new reliability information.

15. The system according to claim 14, wherein the new reliability information for an iteration of processing comprises the received reliability information used by the denoiser for performing a next iteration of processing.

16. The system according to claim 15, wherein the reliability information generated by the decoder for each iteration updates a-priori reliability information for systematic symbols for use by the decoder.

17. The system according to claim 16, wherein parameters for an internal state of the decoder other than the a-priori reliability information for systematic symbols are unchanged between iterations of the denoiser generating reliability information and the decoder performing error correction decoding.

18. The system according to claim 16, wherein parameters for an internal state of the decoder other than the a-priori reliability information for systematic symbols are reset between iterations of the denoiser generating reliability information and the decoder performing error correction decoding.

19. The system according to claim 12, further comprising a preliminary processing stage that performs an iteration of soft output denoising and soft input, soft output error correction decoding on a signal received from the noise-introducing channel.

20. The system according to claim 19, wherein the preliminary processing stage comprises a preliminary stage denoiser and wherein the preliminary stage denoiser counts occurrences of metasymbols in the noisy signal, a portion of each metasymbol providing a context for a symbol of the metasymbol and, for each metasymbol occurring in the noisy message blocks, determines preliminary stage reliability information from the counts obtained by the preliminary stage denoiser and from symbol-transition probabilities for the noise-introducing channel.

21. The system according to claim 12, further comprising performing a smoothing operation on the reliability information generated by solving the quadratic equation.

22. The system according to claim 12, wherein solving the quadratic equation results in a first solution corresponding to an implicit binary symmetric channel having a smaller cross-over probability and a second solution corresponding to an implicit binary symmetric channel having a greater cross-over probability and wherein the first solution is selected for the generated reliability information.

23. A method of iteratively processing a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal comprising receiving the noisy signal and for an iteration, performing steps of:

generating reliability information for symbols in the input signal, said generating comprising for a particular input symbol forming a product of received reliability information and an estimate of the distribution of metasymbols in the input signal, each metasymbol including context symbols and a corresponding symbol, and summing over values for the context symbols corresponding to the particular input symbol; and

performing error correction decoding using the generated reliability information.

24. The method according to claim 23, wherein the estimate of the distribution of metasymbols in the input signal is determined by performing successive steps of matrix inversion to obtain a joint distribution of j input symbols and k-j output symbols and wherein for each step the value of j is advanced by one until j is equal to k and wherein k is the size of the metasymbol.

25. The system according to claim 24, wherein a smoothing operation is performed at each step of matrix inversion.

26. A method of iteratively processing a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal comprising receiving the noisy signal and for an iteration, performing steps of:

generating reliability information for symbols in the input signal, said generating comprising forming a hard-decision decoded signal from received reliability information, determining metasymbol counts for the hard-decision decoded signal and solving an equation whose coefficients are obtained from the received reliability information and the metasymbol counts; and

performing error correction decoding using the generated reliability information.

27. The method according to claim 26, wherein the equation is quadratic.

28. The method according to claim 26, further comprising performing a smoothing operation on the reliability information generated by solving the quadratic equation.

29. The method according to claim 27, wherein solving the quadratic equation results in a first solution corresponding to an implicit binary symmetric channel having a smaller cross-over probability and a second solution corresponding to an implicit binary symmetric channel having a greater cross-over probability and further comprising selecting the first solution for the generated reliability information.

30. A system comprising:

a de-multiplexer that receives a noisy error correction coded signal formed by a noise-introducing channel in response to an error correction coded input signal and for separating noisy message blocks from noisy check blocks in the noisy error correction coded signal;

a first denoiser, wherein for each metasymbol occurring in the noisy message blocks, the denoiser determines first reliability information, the first reliability information representing a probability that the value in the input signal corresponding to the symbol of the metasymbol assumed, each of the possible values; and

a first error correction decoder for performing error correction decoding and generating a first refined reliability information using the noisy check blocks and the first reliability information generated by the first denoiser;

a second denoiser for generating second reliability information for symbols in the input signal, said generating comprising forming a hard-decision decoded signal from the first refined reliability information and determining metasymbol counts for the hard-decision decoded signal; and

a second error correction decoder for performing error correction decoding and generating a second refined reliability information using the second reliability information from the second denoiser.

31. The system according to claim 30, wherein the second denoiser and the second error correction decoder perform a plurality of successive iterations of processing.

32. The system according to claim 30, wherein the second reliability information comprises the metasymbol counts and a conditional distribution of values that a symbol in the hard-decision decoded signal takes on for a particular context, the context being a portion of a metasymbol.

33. A method of denoising and decoding a noisy error correction coded signal received through a noise-introducing channel, the method comprising:

receiving the noisy error correction coded signal from the noise-introducing channel;

separating noisy message blocks from noisy check blocks in the noisy error correction coded signal;

determining first reliability information for each metasymbol occurring in the noisy message blocks, the first reliability information being in machine readable form and representing a probability that the value in the input signal corresponding to the symbol of the metasymbol assumed each of the possible values;

performing error correction decoding using the noisy check blocks and the first reliability information, thereby generating first refined reliability information;

generating second reliability information for symbols in the input signal, said generating comprising forming a hard-decision decoded signal from the first refined reliability information and determining metasymbol counts for the hard-decision decoded signal; and

performing error correction decoding using the second reliability information, thereby generating second refined reliability information.

34. The method according to claim 33, further comprising performing a plurality of successive iterations of said generating second reliability information and said performing error correction decoding using the second reliability information.

35. The method according to claim 33, wherein the second reliability information comprises the metasymbol counts and a conditional distribution of values that a symbol in the hard-decision decoded signal takes on for a particular context, the context being a portion of a metasymbol.

36. A computer readable medium comprising computer code for implementing a method of iteratively processing a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal the method comprising receiving the noisy signal and for an iteration, performing steps of:

generating reliability information for symbols in the input signal, said generating comprising for a particular symbol forming a product of received reliability information and an estimate of the distribution of metasymbols in the input signal, each metasymbol including context symbols and a corresponding symbol, and summing over values for context symbols corresponding to the particular symbol; and

performing error correction decoding using the generated reliability information.

37. A computer readable medium comprising computer code for implementing a method of iteratively processing a noisy signal formed by a noise-introducing channel in response to an error correction coded input signal the method comprising receiving the noisy signal and for an iteration, performing steps of:

generating reliability information for symbols in the input signal, said generating comprising forming a hard-decision decoded signal from received reliability information, determining metasymbol counts for the hard-decision decoded signal and solving a quadratic equation for which coefficients are obtained from the received reliability information and the metasymbol counts; and

performing error correction decoding using the generated reliability information.

38. A computer readable medium comprising computer code for implementing a method of denoising and decoding a noisy error correction coded signal received through a noise-introducing channel, the method comprising:

receiving the noisy error correction coded signal from the noise-introducing channel;

separating noisy message blocks from noisy check blocks in the noisy error correction coded signal;

determining first reliability information for each metasymbol occurring in the noisy message blocks, the first reliability information being in machine readable form and representing a probability that the value in the input signal corresponding to the symbol of the metasymbol assumed each of the possible values;

performing error correction decoding using the noisy check blocks and the first reliability information, thereby generating first refined reliability information;

generating second reliability information for symbols in the input signal, said generating comprising forming a hard-decision decoded signal from the first refined reliability information and determining metasymbol counts for the hard-decision decoded signal; and

performing error correction decoding using the second reliability information, thereby generating second refined reliability information.