Methods and apparatus for improving performance of information coding schemes

• US 20050193320A1
• Filed: 02/09/2004
• Published: 09/01/2005
• Est. Priority Date: 02/09/2004
• Status: Abandoned Application

• Current Assignee: President and Fellows of Harvard College (Harvard Corporation), University of Hawai'i
• Original Assignee: President and Fellows of Harvard College (Harvard Corporation), University of Hawai'i
• Inventors: Varnica, Nedeljko, Fossorier, Marc, Kavcic, Aleksandar
• Application Number:
  US10/774,763
• Publication Number:
  US 20050193320A1
• Time in Patent Office: Days
• US Class Current: 714/800
• 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/3723 using means or methods for the initialisation of the decoder
• CPC Class Codes: H03M 13/3738 with judging correct decoding

Abstract

Various modifications to conventional information coding schemes that result in an improvement in one or more performance measures for a given coding scheme. Some examples are directed to improved decoding techniques for linear block codes, such as low-density parity-check (LDPC) codes. In one example, modifications to a conventional belief-propagation (BP) decoding algorithm for LDPC codes significantly improve the performance of the decoding algorithm so as to more closely approximate that of the theoretically optimal maximum-likelihood (ML) decoding scheme. BP decoder performance generally is improved for lower code block lengths, and significant error floor reduction or elimination may be achieved for higher code block lengths. In one aspect, significantly improved performance of a modified BP algorithm is achieved while at the same time essentially maintaining the benefits of relative computational simplicity and execution speed of a conventional BP algorithm as compared to an ML decoding scheme. In another aspect, modifications for improving the performance of conventional BP decoders are universally applicable to “off the shelf” LDPC encoder/decoder pairs. Furthermore, the concepts underlying the various methods and apparatus disclosed herein may be more generally applied to various decoding schemes involving iterative decoding algorithms and message-passing on graphs, as well as coding schemes other than LDPC codes to similarly improve their performance. Exemplary applications for improved coding schemes include wireless (mobile) networks, satellite communication systems, optical communication systems, and data recording and storage systems (e.g., CDs, DVDs, hard drives, etc.).

Claims

1. A decoding method for a linear block code having a parity check matrix that is sparse or capable of being sparsified, the decoding method comprising an act of:

A) modifying a conventional decoding algorithm for the linear block code such that a performance of the modified decoding algorithm significantly approaches or more closely approximates a performance of a maximum-likelihood decoding algorithm for the linear block code.

2. The method of claim 1, wherein the act A) includes an act of:

modifying the conventional decoding algorithm for the linear block code such that the performance of the modified decoding algorithm in at least an error floor region significantly approaches or more closely approximates the performance of a maximum-likelihood decoding algorithm for the linear block code.

3. The method of claim 1, wherein the conventional decoding algorithm is an iterative decoding algorithm, and wherein the act A) includes at least one of the following acts:

B) modifying the iterative decoding algorithm such that a decoding error probability of the modified iterative decoding algorithm is significantly decreased from a decoding error probability of the unmodified iterative decoding algorithm at a given signal-to-noise ratio; and

C) modifying the iterative decoding algorithm such that an error floor of the modified iterative decoding algorithm is significantly decreased or substantially eliminated as compared to an error floor of the unmodified iterative decoding algorithm.

4. The method of claim 3, wherein either of the acts B) or C) includes the following acts:

D) executing the iterative decoding algorithm for a predetermined number of iterations;

E) upon failure of the iterative decoding algorithm to provide valid decoded information after the predetermined first number of iterations, altering at least one value used by the iterative decoding algorithm; and

F) executing at least a first round of additional iterations of the iterative decoding algorithm using the at least one altered value.

5. The method of claim 4, wherein the iterative decoding algorithm is a message-passing algorithm, and wherein:

the act D) includes an act of executing the message-passing algorithm for the predetermined first number of iterations to attempt to decode the received information;

the act E) includes an act of, upon failure of the message-passing algorithm to provide valid decoded information after the predetermined first number of iterations, altering the at least one value used by the message-passing algorithm; and

the act F) includes an act of executing at least the first round of additional iterations of the message-passing algorithm using the at least one altered value.

6. The method of claim 1, wherein the linear block code is a low-density parity check (LDPC) code, wherein the conventional decoding algorithm is a standard belief-propagation (BP) algorithm based on a bipartite graph for the LDPC code, and wherein the act A) includes at least one of the following acts:

B) modifying the standard BP algorithm such that a decoding error probability of the modified BP algorithm is significantly decreased from a decoding error probability of the standard BP algorithm at a given signal-to-noise ratio; and

C) modifying the standard BP algorithm such that an error floor of the modified BP algorithm is significantly decreased or substantially eliminated as compared to an error floor of the standard BP algorithm.

7. The method of claim 6, wherein either of the acts B) or C) includes the following acts:

D) executing the standard BP algorithm for a predetermined number of iterations;

E) upon failure of the standard BP algorithm after the predetermined number of iterations, selecting at least one candidate variable node of the bipartite graph for correction;

F) seeding the at least one candidate variable node with a maximum-certainty likelihood; and

G) executing additional iterations of the standard BP algorithm.

8. A method for decoding received information encoded using a coding scheme, the method comprising acts of:

A) executing an iterative decoding algorithm for a predetermined first number of iterations to attempt to decode the received information;

B) upon failure of the iterative decoding algorithm to provide valid decoded information after the predetermined first number of iterations, altering at least one value used by the iterative decoding algorithm; and

C) executing at least a first round of additional iterations of the iterative decoding algorithm using the at least one altered value.

9. The method of claim 8, wherein the iterative decoding algorithm is a message-passing algorithm, and wherein:

the act A) includes an act of executing the message-passing algorithm for the predetermined first number of iterations to attempt to decode the received information;

the act B) includes an act of, upon failure of the message-passing algorithm to provide valid decoded information after the predetermined first number of iterations, altering at least one value used by the message-passing algorithm; and

the act C) includes an act of executing at least the first round of additional iterations of the message-passing algorithm using the at least one altered value.

10. The method of claim 9, wherein the coding scheme is a low-density parity check (LDPC) coding scheme, and wherein the message-passing algorithm is a standard belief-propagation (BP) algorithm.

11. The method of claim 9, wherein before the act A), the method includes an act of:

receiving the received information from a coding channel that includes at least one data storage medium.

12. The method of claim 9, wherein before the act A), the method includes an act of:

receiving the received information from a coding channel that is configured for use in a wireless communication system.

13. The method of claim 9, wherein before the act A), the method includes an act of:

receiving the received information from a coding channel that is configured for use in a satellite communication system.

14. The method of claim 9, wherein before the act A), the method includes an act of:

receiving the received information from a coding channel that is configured for use in an optical communication system.

15. The method of claim 9, wherein the message-passing algorithm is based on a bipartite graph for the coding scheme, and wherein the act B) includes an act of:

altering at least one likelihood value associated with at least one check node of the bipartite graph.

16. The method of claim 9, wherein the message-passing algorithm is based on a bipartite graph for the coding scheme, and wherein the act B) includes an act of:

B1) altering at least one likelihood value associated with at least one variable node of the bipartite graph.

17. The method of claim 16, wherein the act B1) includes acts of:

D) selecting at least one candidate variable node of the bipartite graph for correction; and

E) seeding the at least one candidate variable node with the at least one altered likelihood value.

18. The method of claim 17, wherein the act D) includes acts of:

D1) determining a set of unsatisfied check nodes of the bipartite graph, the set including at least one unsatisfied check node; and

D2) selecting the at least one candidate variable node based at least in part on the set of unsatisfied check nodes.

19. The method of claim 18, wherein the act D1) includes acts of:

calculating a syndrome of an estimated invalid code word provided by the standard message-passing algorithm after the predetermined first number of iterations; and

determining the set of unsatisfied check nodes based on the syndrome.

20. The method of claim 18, wherein the act D1) includes an act of:

determining the set of unsatisfied check nodes based on aggregate likelihood information from all of the check nodes of the bipartite graph.

21. The method of claim 18, wherein the act D2) includes acts of:

determining a set of variable nodes associated with the set of unsatisfied check nodes, the set of variable nodes including at least one variable node; and

selecting the at least one candidate variable node randomly from the set of variable nodes.

22. The method of claim 18, wherein the act D2) includes acts of:

D3) determining a set of variable nodes associated with the set of unsatisfied check nodes, the set of variable nodes including at least one variable node; and

D4) selecting the at least one candidate variable node from the set of variable nodes according to a prescribed algorithm.

23. The method of claim 22, wherein the act D4) includes an act of:

determining a set of highest-degree variable nodes from the set of variable nodes.

24. The method of claim 23, further including an act of:

selecting the at least one candidate variable node randomly from the set of highest-degree variable nodes.

25. The method of claim 23, further including an act of:

D5) selecting the at least one candidate variable node intelligently from the set of highest-degree variable nodes.

26. The method of claim 25, wherein the act D5) includes an act of:

D6) selecting the at least one candidate variable node based at least in part on at least one neighbor of at least one variable node in the set of highest-degree variable nodes.

27. The method of claim 26, wherein the act D6) includes acts of:

determining all neighbors for each variable node in the set of highest-degree variable nodes;

determining the degree of each neighbor; and

for each degree, determining the number of neighbors having a same degree.

28. The method of claim 27, wherein the act D6) further includes acts of:

determining the highest degree for which only one variable node in the set of highest-degree variable nodes has the smallest number of neighbors; and

selecting the one variable node as the at least one candidate variable node.

29. The method of claim 27, wherein the act D6) further includes acts of:

determining the highest degree for which only two variable nodes in the set of highest-degree variable nodes have the smallest number of neighbors;

examining a number of neighbors for each of the two variable nodes at at least one lower degree;

identifying one variable node of the two variable nodes with the fewer number of neighbors at the next lowest degree at which the two variable nodes have different numbers of neighbors; and

selecting the one variable node as the at least one candidate variable node.

30. The method of claim 22, further including acts of:

determining an extended set of unsatisfied check nodes based on the set of variable nodes associated with the set of unsatisfied check nodes;

identifying at least one degree-two check node in the extended set of unsatisfied check nodes;

randomly selecting one variable node of two variable nodes connected to the at least one degree-two check node as the at least one candidate variable node for correction.

31. The method of claim 17, wherein the act E) includes an act of:

E1) seeding the at least one candidate variable node with a maximum-certainty likelihood value.

32. The method of claim 31, wherein the act E1) includes an act of:

replacing at least one channel-based likelihood provided as an input to the at least one candidate variable node with the maximum-certainty likelihood value.

33. The method of claim 32, further including an act of:

randomly selecting the maximum-certainty likelihood value.

34. The method of claim 32, further including an act of:

selecting the maximum-certainty likelihood value based at least in part on the channel-based likelihood value being replaced.

35. The method of claim 32, further including an act of:

selecting the maximum-certainty likelihood value based at least in part on a likelihood value present at the at least one candidate variable node.

36. The method of claim 8, wherein, if the act C) does not provide valid decoded information, the method further includes acts of:

F) selecting a different value for the at least one altered value; and

G) executing at least a second round of additional iterations of the iterative decoding algorithm using the different value for the at least one altered value.

37. The method of claim 8, wherein, if the act C) does not provide valid decoded information, the method further includes acts of:

F) altering at least one different value used by the iterative decoding algorithm; and

G) executing at least a second round of additional iterations of the iterative decoding algorithm using the at least one different altered value.

38. The method of claim 8, wherein if the act C) does not provide valid decoded information, the method further includes acts of:

F) performing one of the following;

selecting a different value for the at least one altered value; and

altering at least one different value used by the iterative decoding algorithm;

G) executing another round of additional iterations of the iterative decoding algorithm;

H) if the act G) does not provide valid decoded information, proceeding to act I; and

I) repeating the acts F), G) and H) for a predetermined number of additional rounds or until valid decoded information is provided, whichever occurs first.

39. The method of claim 8, further including acts of:

F) if the act C) provides valid decoded information, adding the valid decoded information to a list of valid decoded information;

G) performing one of the following;

selecting a different value for the at least one altered value; and

altering at least one different value used by the iterative decoding algorithm;

H) executing another round of additional iterations of the iterative decoding algorithm;

I) if the act H) provides valid decoded information, adding the valid decoded information to the list of valid decoded information;

J) repeating the acts G), H) and I) for a predetermined number of additional rounds; and

K) selecting from the list of valid decoded information an entry of valid decoded information that minimizes a Euclidian distance between the entry and the received information.

40. An apparatus for decoding received information that has been encoded using a coding scheme, the apparatus comprising:

a decoder block configured to execute an iterative decoding algorithm for a predetermined first number of iterations; and

at least one controller that, upon failure of the decoder block to provide valid decoded information after the predetermined first number of iterations of the iterative decoding algorithm, is configured to alter at least one value used by the iterative decoding algorithm and control the decoder block so as to execute at least a first round of additional iterations of the iterative decoding algorithm using the at least one altered value.

41. The apparatus of claim 40, wherein the apparatus is configured to receive the received information from a coding channel that includes at least one data storage medium.

42. The apparatus of claim 40, wherein the apparatus is configured to receive the received information from a coding channel that is configured for use in a wireless communication system.

43. The apparatus of claim 40, wherein the apparatus is configured to receive the received information from a coding channel that is configured for use in a satellite communication system.

44. The apparatus of claim 40, wherein the apparatus is configured to receive the received information from a coding channel that is configured for use in an optical communication system.

45. The apparatus of claim 40, wherein the iterative decoding algorithm is a message-passing algorithm.

46. The apparatus of claim 45, wherein the coding scheme is a low-density parity check (LDPC) coding scheme, and wherein the message-passing algorithm is a standard belief-propagation (BP) algorithm.

47. The apparatus of claim 45, wherein the message-passing algorithm is based on a bipartite graph for the coding scheme, and wherein:

the at least one controller includes seeding logic configured to alter at least one likelihood value associated with at least one variable node of the bipartite graph.

48. The apparatus of claim 47, wherein:

the at least one controller includes choice of variable nodes logic configured to select at least one candidate variable node of the bipartite graph for correction; and

the seeding logic is configured to seed the at least one candidate variable node with the at least one altered likelihood value.

49. The apparatus of claim 48, wherein:

the at least one controller includes parity-check nodes logic configured to determine a set of unsatisfied check nodes of the bipartite graph, the set including at least one unsatisfied check node; and

the choice of variable nodes logic is configured to select the at least one candidate variable node based at least in part on the set of unsatisfied check nodes.

50. The apparatus of claim 40, wherein the at least one controller is configured to select a different value for the at least one altered value and execute at least a second round of additional iterations of the iterative decoding algorithm using the different value for the at least one altered value if the decoder block does not provide valid decoded information after the first round of additional iterations.

51. The apparatus of claim 40, wherein the at least one controller is configured to alter at least one different value used by the iterative decoding algorithm and execute at least a second round of additional iterations of the iterative decoding algorithm using the at least one different altered value if the decoder block does not provide valid decoded information after the first round of additional iterations.

52. The apparatus of claim 40, wherein if the decoder block does not provide valid decoded information after the first round of additional iterations, the at least one controller is configured to:

A) perform one of the following;

select a different value for the at least one altered value; and

alter at least one different value used by the iterative decoding algorithm;

B) execute another round of additional iterations of the iterative decoding algorithm;

C) if another round of additional iterations does not provide valid decoded information, proceed to D); and

D) repeat A), B) and C) for a predetermined number of additional rounds or until valid decoded information is provided, whichever occurs first.

53. The apparatus of claim 40, wherein the at least one controller is configured to:

A) if the decoder block provides valid decoded information after the first round of additional iterations, add the valid decoded information to a list of valid decoded information;

B) perform one of the following;

select a different value for the at least one altered value; and

alter at least one different value used by the iterative decoding algorithm;

C) execute another round of additional iterations of the iterative decoding algorithm;

D) if another round of additional iterations provides valid decoded information, add the valid decoded information to the list of valid decoded information;

E) repeat A), B) and C) for a predetermined number of additional rounds; and

F) select from the list of valid decoded information an entry of valid decoded information that minimizes a Euclidian distance between the entry and the received information.