Low density parity check decoder for regular LDPC codes

• US 8,359,522 B2
• Filed: 05/01/2008
• Issued: 01/22/2013
• Est. Priority Date: 05/01/2007
• Status: Active Grant

• Current Assignee: Texas A&M University System
• Original Assignee: Texas A&M University System
• Inventors: Gunnam, Kiran K., Choi, Gwan S.
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US12/113,729
• Publication Number:
  US 20080276156A1
• Time in Patent Office: 1,727 Days
• Field of Search: 714/758, 714/801
• US Class Current: 714/758
• CPC Class Codes: H03M 13/1105 Decoding
• CPC Class Codes: H03M 13/1128 Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
• CPC Class Codes: H03M 13/116 Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
• CPC Class Codes: H03M 13/1177 Regular LDPC codes with parity-check matrices wherein all rows and columns have the same row weight and column weight, respectively
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A method and system for decoding low density parity check (“LDPC”) codes. An LDPC decoder includes an R select unit, a Q message first-in first-out (“FIFO”) memory, and a cyclic shifter. The R select unit provides an R message by selecting from a plurality of possible R message values. The Q message memory stores a Q message until an R message is generated by a CNU, the Q message and the R message are combined to provide a P message. The cyclic shifter shifts the P message.

Claims

1. A low density parity check code decoder, comprising:

a check node unit (“

CNU”

);

the CNU comprising;

a set of comparators for comparing stored minimum values to a received variable message Q, wherein;

a total number of comparators in the set is less than the check node degree;

a first comparator of the set determines a first minimum value, M₁, by comparing a first stored minimum value, M_1PS, and the received variable message Q; and

a second comparator of the set determines a second minimum value, M₂, by comparing a second stored minimum value, M_2PS, and the received variable message Q; and

final state storage that stores;

a modified version of M_1PS,

a modified version of a two'"'"'s complement of M_1PS, and

one of a modified version of M_2PS and a modified version of a two'"'"'s complement of M_2PS;

a selector that selects, from the final state storage, a message to a variable node unit to be one of;

the modified version of M_1PS,

the modified version of the two'"'"'s complement of M_1PS, and

the one of the modified version of M_2PS and the modified version of the two'"'"'s complement of M_2PS;

wherein the modified version of either of M_1PS and M_2PS is one of an offset corrected version and a scaled version.

2. The decoder of claim 1, wherein the set of comparators comprises no more than two comparators.

3. The decoder of claim 1, wherein the CNU reuses previously determined minimum values to determine a new minimum value.

4. The decoder of claim 3, wherein the two'"'"'s complement unit produces −

M_1PS as the two'"'"'s complement of M_1PS and produces −

M_2PS as the two'"'"'s complement of M_2PS.

5. The decoder of claim 1, further comprising a two'"'"'s complement unit that converts values from sign magnitude to two'"'"'s complement format, wherein the two'"'"'s complement unit converts at most two CNU output values to two'"'"'s complement format.

6. The decoder of claim 1, further comprising a partial state storage array wherein M₁ is stored as M_1PS, M₂ is stored as M_2PS, and indicia of the location of M_1PS is stored as M_1INDEX.

7. The decoder of claim 6, wherein the partial state storage array comprises storage for no more than M_1PS, M_2PS, and indicia of the location of M_1PS.

8. The decoder of claim 1, further comprising an offset correction unit that applies offset correction to M_1PS and M_2PS.

9. The decoder of claim 1, wherein the final state storage array stores indicia of the location of M_1PS.

10. The decoder of claim 9, wherein the final state storage array comprises storage for no more than an offset corrected version of M_1PS, an offset corrected version of the two'"'"'s complement of M_1PS, an offset corrected version of one of M_2PS and the two'"'"'s complement of M_2PS, and indicia of the location of M_1PS.

11. The decoder of claim 9, wherein the message to the variable node unit is selected based on the indicia of the location of M_1PS stored in final state storage.

12. The decoder of claim 9, wherein the final state storage array comprises storage for less than check node degree messages.

13. The decoder of claim 1, wherein the message to the variable node unit is selected based on the sign bit of a message sent to a variable node unit.

14. A method for decoding a low density parity check code, comprising:

comparing a received variable message to a first stored minimum value to determine a new first minimum value;

comparing the received variable message to a second stored minimum value to determine new second minimum value;

determining indicia of the location of the new first minimum value;

storing the new first minimum value, the new second minimum value and the indicia of the new first minimum value location in a partial state storage array;

storing final minimum values in a final state storage array of a check node unit, the final minimum values comprising modified versions of;

the first minimum value read from the partial state storage array,

a two'"'"'s complement of the first minimum value read from the partial state storage array, and

one of the second minimum value read from the partial state storage array and a two'"'"'s complement of the second minimum value read from the partial state storage array; and

selecting, by the check node unit, one of the final minimum values stored in the final state storage array to be a check node message;

providing the check node message to a variable node;

wherein the modified versions of the first minimum value and the second minimum value are one of offset corrected versions and scaled versions.

15. The method of claim 14, further comprising re-using a previously computed minimum value to determine a new minimum value.

16. The method of claim 14, further comprising applying offset correction to the stored first minimum value and the stored second minimum value.

17. The method of claim 14, further comprising computing the two'"'"'s complement of the stored first minimum value and the stored second minimum value.

18. The method of claim 14, further comprising:

storing the indicia of the first minimum value location read from the partial state storage array in a final state storage array.

19. The method of claim 14, further comprising determining the check node message based on the indicia of the first minimum value location stored in a final state storage array.

20. A low density parity check (“

LDPC”

) code decoder, comprising;

a plurality of check node unit (“

CNU”

) arrays, each array comprising a plurality of CNUs and each array processing a block row of an LDPC parity check matrix;

wherein the CNUs of each array are interconnected to perform a cyclic shift characteristic of the block row processed by the array;

wherein routing of messages between CNUs and between CNUs and variable node units (VNUs) is accomplished by passive wired interconnection, rather than by active routers.

21. The decoder of claim 20, wherein the CNUs of an array are not connected to one another and the array processes a block row containing blocks not cyclically shifted from one another.

22. The decoder of claim 21, wherein a message passing memory stores only the sign bit of a variable node message.

23. The decoder of claim 20, wherein a partial state output and a final state output of a first CNU (CNU_N) are connected, respectively, to a partial state input and a final state input of a successive CNU (CNU_N+1), and the array processes a block row containing blocks incrementally shifted by one bit.

24. The decoder of claim 20, wherein a partial state output and a final state output of a first CNU (CNU_N) are connected, respectively, to a partial state input and a final state input of a successive CNU (CNU_N+2), and the array processes a block row containing blocks incrementally shifted by two bits.

25. The decoder of claim 20, wherein the decoder implements a two phase message passing decoding algorithm.

26. The decoder of claim 20, further comprising a memory coupled to a CNU array variable message input, the memory stores a channel log-likelihood ratio (“

LLR”

) to be provided to a CNU array.

27. A method for low density parity check (“

LDPC”

) code decoding, comprising;

applying a log-likelihood ratio (“

LLR”

) as an initial variable message to a check node unit (“

CNU”

) array;

processing a layer of an LDPC parity check matrix in an array of CNUs, the CNUs of the array interconnected, without active routers, to provide incremental shifts in accordance with the number of incremental shifts characteristic of the blocks of the layer.

28. The method of claim 27, further comprising processing a layer of an LDPC parity check matrix in an array of dynamic CNUs, the CNUs interconnected, without active routers, to process a layer wherein each successive is block incrementally shifted by one bit from the previous block.

29. The method of claim 27, further comprising processing a layer of an LDPC parity check matrix in an array of dynamic CNUs, the CNUs interconnected, without active routers, to process a layer wherein each successive is block incrementally shifted by two bits from the previous block.

30. The method of claim 27, further comprising processing a layer of an LDPC parity check matrix in an array of simple CNUs, the CNUs interconnected to process a layer wherein the blocks have no incremental shift.

31. A low density parity check (“

LDPC”

) code decoder, comprising;

an R select unit that provides an R message by selecting from a plurality of possible R message values;

a Q message first-in first-out (“

FIFO”

) memory that stores a Q message until an R message is generated by a check node unit (“

CNU”

), the Q message and the R message are combined to provide a P message; and

a cyclic shifter that shifts the P message;

wherein the cyclic shifter shifts the P message by the difference of the shifts of a block currently being processed and the shifts of a block previously processed;

wherein the block currently being processed and the block previously processed are in a same block column.

32. The decoder of claim 31, further comprising a CNU array comprising a plurality of CNUs.

33. The decoder of claim 32, wherein the CNU array produces R messages in block-serial fashion.

34. The decoder of claim 31, further comprising an array of final state register banks, each bank comprising a plurality of registers for storing final state data for a layer of an LDPC parity check matrix.

35. The decoder of claim 31, further comprising an array of sign bit FIFO banks, each bank comprising a plurality of FIFOs, each bank storing sign bits for a layer of an LDPC parity check matrix.

36. The decoder of claim 31, wherein a CNU computes a check node (“

R”

) message based on a shifted Q message and the sign bit of a Q message.

37. The decoder of claim 31, further comprising a multiplexer that selects one of a channel log-likelihood ratio (“

LLR”

) values and a P message to input to the cyclic shifter, and wherein the multiplexer selects a channel LLR value to initialize the decoder.

38. The decoder of claim 31, further comprising a P sum adder that produces a P message by adding a delayed version of a Q message to an R message output by a CNU.

39. The decoder of claim 31, further comprising a Q subtractor array, wherein an R message generated by the R select unit based on information from an FS register array and an R sign FIFO is subtracted from a shifted P message to produce a Q message provided to a CNU.

40. The decoder of claim 31, wherein CNU processing is divided into a minimum finder stage, a partial state stage, and an R selection stage, the minimum finder stage and partial state stage operating in parallel with the R selection stage on different block rows.

41. The decoder of claim 31, further comprising a control unit that controls the operation of the decoder, wherein the decoder decodes multiple code rates by changing LDPC array parameters stored in the control unit.

42. The decoder of claim 31, further comprising a multiplexer that selects one of a channel log-likelihood ratio (“

LLR”

) values and a Q message to input to the Q message FIFO, and wherein the multiplexer selects a channel LLR value to initialize the decoder.

43. The decoder of claim 31, wherein the cyclic shifter comprises hardware that can perform any shift varying from 0 to p−

1.

44. The decoder of claim 31, wherein the cyclic shifter comprises fewer shift stages than the number of elements in a block.

45. The decoder of claim 44, further comprising a P buffer memory coupled to the input of the cyclic shifter that stores intermediate P messages.

46. The decoder of claim 44, wherein the P message is shifted by a combination of shifts by the cyclic shifter and addressing of the P buffer.

47. The decoder of claim 31, further comprising a CNU array comprising fewer CNUs than the number of rows in a block.

48. The decoder of claim 47, further comprising a current layer partial state memory that stores intermediate partial state results of the layer being processed by the CNU array.

49. A method for decoding a low density parity check code, comprising:

selecting an R old message from a plurality of possible R old messages based on a message index value and a sign bit;

delaying a Q message in a FIFO memory until a check node unit (“

CNU”

) provides an R new message;

summing the R new message and the delayed Q message to produce a P message; and

cyclically shifting the P message by the difference of the shifts of a block currently being processed and the shifts of a block previously processed;

wherein the block currently being processed and the block previously processed are in a same block column.

50. The method of claim 49, further comprising generating, in a CNU, an R new message based on a shifted Q message and a sign bit from a Q message.

51. The method of claim 49, further comprising selecting one of a channel log-likelihood ratio (“

LLR”

) value and a P message to input to the cyclic shifter, the LLR value is selected to initialize decoding.

52. The method of claim 49, further comprising producing R new messages in block serial fashion.

53. The method of claim 49, further comprising storing final state data for a plurality of LDPC parity check matrix layers in an array of final state register banks, each bank storing final state data for a layer of the matrix.

54. The method of claim 49, further comprising sign bits for a plurality of LDPC parity check matrix layers in an array of sign bit FIFO banks, each bank storing sign bits for a layer of the matrix.

55. The method of claim 49, further comprising subtracting an R old message from a shifted P message to produce a Q message that is provided to a CNU.

56. The method of claim 49, further comprising dividing CNU processing into a minimum finder stage, a partial state stage, and an R selection stage, the partial state stage and the minimum finder stage operating in parallel with the R selection stage on different block rows.

57. The method of claim 49, further comprising changing LDPC array parameters stored in a control unit to allow decoding of multiple code rates.

58. The method of claim 49, further comprising shifting the P message by a combination of cyclic shifter shifts and memory addressing.

59. The method of claim 49, further comprising shifting the P message in a cyclic shifter.

60. The method of claim 49, further comprising selecting one of a channel log-likelihood ratio (“

LLR”

) value and a Q message to input to the FIFO memory, the LLR value is selected to initialize decoding.

61. The method of claim 49, further comprising producing R new messages in sub-block serial fashion, wherein a CNU array simultaneously processes fewer than all the rows of a block.

62. A low density parity check (“

LDPC”

) code decoder, comprising;

a first R select unit that provides an R message by selecting from a plurality of possible R message values,

a Q message generator that combines the R message with a P message to produce a Q message; and

a first cyclic shifter that shifts the P message;

wherein the decoder is configured to update the P message based on determination of a final state for each block row.

63. The decoder of claim 62, further comprising a second R select unit that selects from a plurality of possible R messages to provide an R prev message, wherein the first R select unit provides an R old message.

64. The decoder of claim 63, further comprising a P adder array that adds a shifted P message to the difference of an R new message and an R prey message to produce an updated shifted P message.

65. The decoder of claim 62, further comprising a second R select unit that selects from a plurality of possible R messages to provide an R old message, wherein the first R select unit provides an R prev message.

66. The decoder of claim 62, further comprising a sign bit FIFO coupled to the input of an R select unit that provides an R old message.

67. The decoder of claim 62, wherein the Q message generator comprises a Q subtractor array that generates a Q message by subtracting an R old message from a shifted P message.

68. The decoder of claim 62, wherein the first cyclic shifter is a cyclic down shifter.

69. The decoder of claim 62, further comprising an R subtractor array that subtracts an R prev message from an R new message.

70. The decoder of claim 62, further comprising a second cyclic shifter that is a cyclic up shifter, the second cyclic shifter shifts the difference of an R new message and an R prev message.

71. The decoder of claim 70, wherein the first cyclic shifter and the second cyclic shifter each comprise hardware that can perform any shift varying from 0 to p−

1, where p is the number of elements in a block row.

72. The decoder of claim 62, further comprising a P sum adder array that adds a P message to a shifted difference of an R prev message and an R new message to produce an updated P message.

73. The decoder of claim 62, further comprising a P message memory that stores an updated P message.

74. The decoder of claim 73, further comprising a multiplexer coupled to the P memory, the multiplexer selects one of an updated P message and a channel log-likelihood ratio (“

LLR”

) for storage in the P memory, and wherein the multiplexer selects a channel LLR value to initialize the decoder.

75. The decoder of claim 62, further comprising a CNU array comprising a plurality of CNUs.

76. The decoder of claim 75, wherein a CNU computes an R new message based on a shifted Q message and a sign bit of a Q message.

77. The decoder of claim 75, wherein the CNU array produces R messages in block-serial fashion.

78. The decoder of claim 75, wherein CNU processing is divided into a minimum finder stage, a partial state stage, and an R selection stage, the partial state stage and the minimum finder stage operating in parallel with the R selection stage on different block rows.

79. The decoder of claim 62, further comprising an array of final state register banks, each bank comprising a plurality of registers for storing final state data for a layer of an LDPC parity check matrix.

80. The decoder of claim 62, further comprising an array of sign bit FIFO banks, each bank comprising a plurality of FIFOs, each bank storing sign bits for a layer of an LDPC parity check matrix.

81. The decoder of claim 62, further comprising a control unit that controls the operation of the decoder, wherein the decoder decodes multiple code rates by changing LDPC array parameters stored in the control unit.

82. The decoder of claim 62, wherein the Q message generator comprises a Q subtractor array that generates a Q message by subtracting an R old message from an updated shifted P message.

83. The decoder of claim 62, further comprising a second cyclic shifter that is a cyclic up shifter, the second cyclic shifter shifts an updated shifted P message.

84. The decoder of claim 62, further comprising an R subtractor array that subtracts an R prev message from an R new message.

85. A method for decoding a low density parity check code, comprising:

selecting a first R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit;

generating a Q message by combining the first R message with a P message;

cyclically shifting the P message; and

updating the P message responsive to determination of a final state for each block row.

86. The method of claim 85, further comprising selecting a second R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit;

wherein the second R message is an R prev message, and the first R message is an R old message.

87. The method of claim 85, further comprising selecting a second R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit;

wherein the second R message is an R old message, and the first R message is an R prev message.

88. The method of claim 85, further comprising providing a delayed sign bit to an R select unit that provides an R old message.

89. The method of claim 85, further comprising subtracting an R old message from a shifted P message to generate a Q message.

90. The method of claim 85, further comprising adding a P message to a shifted difference of an R new message and an R prev message to produce an updated P message.

91. The method of claim 85, further comprising selecting one of an updated P message and a channel log-likelihood ratio (“

LLR”

) for storage in a P memory, wherein a channel LLR is selected to initialize decoding.

92. The method of claim 85, further comprising producing R new messages in block serial fashion in an array of check node units (“

CNU”

) comprising a plurality of CNUs.

93. The method of claim 92, further comprising computing an R new message in a CNU based on a shifted Q message and a sign bit of a Q message.

94. The method of claim 92, further comprising dividing CNU processing into a minimum finder stage, a partial state stage, and an R selection stage, the partial state stage and the minimum finder stage operating in parallel with the R selection stage on different block rows.

95. The method of claim 85, further comprising changing LDPC array parameters stored in a control unit to provide decoding of multiple code rates.

96. The method of claim 85, further comprising subtracting an R old message from an updated shifted P message to generate a Q message.

97. The method of claim 85, further comprising adding a shifted P message to the difference of an R new message and an R prev message to produce an updated shifted P message.

98. A low density parity check code decoder, comprising:

a check node unit (“

CNU”

);

the CNU comprising;

a set of comparators for comparing stored minimum values to a received variable message Q, wherein;

a total number of comparators in the set is less than the check node degree;

a first comparator of the set determines a first minimum value, M₁, by comparing a first stored minimum value, M_1PS, and the received variable message Q; and

a second comparator of the set determines a second minimum value, M₂, by comparing a second stored minimum value, M_2PS, and the received variable message Q; and

final state storage that stores;

a modified version of M_1PS, and

a modified version of M_2PS;

a selector that selects, from the final state storage, magnitude of a message

to a variable node unit to be one of;

the modified version of M_1PS, and

the modified version of M_2PS;

wherein the modified version of either of M_1PS and M_2PS is one of an offset corrected version and a scaled version.