Low density parity check decoder for regular LDPC codes

• US 8,656,250 B2
• Filed: 12/04/2012
• Issued: 02/18/2014
• 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 Kumar, Choi, Gwan S.
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US13/693,650
• Publication Number:
  US 20130097469A1
• Time in Patent Office: 441 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 (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 memory that stores a Q message until an R message is generated by the R select unit, the Q message and the R message are combined to provide a P message; and

a permuter that permutes the P message;

wherein the permuter permutes the P message by the difference of the permutation of a block currently being processed and the permutation of a block previously processed;

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

2. The decoder of claim 1, further comprising an array of sign bit memory banks, each bank comprising a plurality of memory elements, each bank storing sign bits for a layer of an LDPC parity check matrix.

3. The decoder of claim 1, wherein the check node (R) message is based on a permuted Q message and the sign bit of a Q message.

4. The decoder of claim 1, further comprising a multiplexer that selects one of a channel log-likelihood ratio (LLR) values and a P message to input to the permuter, and wherein the multiplexer selects a channel LLR value to initialize the decoder.

5. The decoder of claim 1, 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 an R select unit.

6. The decoder of claim 1, 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 a sign memory is subtracted from a permuted P message to produce a Q message provided to a check node unit (CNU).

7. The decoder of claim 1, 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 memory, and wherein the multiplexer selects a channel LLR value to initialize the decoder.

8. The decoder of claim 1, wherein the permuter comprises:

hardware that can perform any permutation on a vector of size p; and

fewer stages than the number of elements in a block.

9. The decoder of claim 1, wherein the P message is shifted by a combination of permutation by the permuter and addressing of a P buffer.

10. 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 memory until an R select unit provides an R new message;

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

permuting the P message by the difference of the permutation of a block currently being processed and the permutation of a block previously processed;

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

11. The method of claim 10, further comprising generating the R new message based on a permuted Q message and a sign bit from a Q message.

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

13. The method of claim 10, further comprising subtracting an R old message from a permuted P message to produce a Q message that is provided to a check node unit (CNU).

14. The method of claim 10, further comprising permuting the P message by a combination of permutation by a permuter and memory addressing.

15. The method of claim 10, further comprising selecting one of a channel log-likelihood ratio (LLR) value and a P message to input to a permuter, the LLR value is selected to initialize decoding.

16. The method of claim 10, further comprising selecting one of a channel log-likelihood ratio (LLR) value and a Q message to input to the memory, wherein the LLR value is selected to initialize decoding.

17. 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 permuter that permutes the P message;

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

18. The decoder of claim 17, 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.

19. The decoder of claim 17, 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.

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

21. The decoder of claim 17, wherein the first permuter is configured to perform any permutation on a vector of size p, where p is the number of elements in a block row.

22. The decoder of claim 17, further comprising a second permuter that permutes one of the difference of an R new message, an R prev message, and a updated permuted P message, wherein the second permuter is configured to perform any permutation on a vector of size p, where p is the number of elements in a block row.

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

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

25. The decoder of claim 24, further comprising a multiplexer coupled to a P memory, the multiplexer selects one of the 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.

26. The decoder of claim 17, wherein an R new message is computed based on a permuted Q message and a sign bit of a Q message.

27. The decoder of claim 17, further comprising an array of sign bit memory banks, each bank comprising a plurality of memories, each bank storing sign bits for a different layer of an LDPC parity check matrix.

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

29. The decoder of claim 17, further comprising a P adder array that adds a permuted P message to the difference of an R new message and an R prev message to produce an updated permuted P message.

30. The decoder of claim 17, further comprising:

an array of check node units (CNU) that performs block parallel processing;

wherein the array processes a plurality (U) of block columns of a plurality (M) of rows in a layer of an LDPC parity check matrix in one clock cycle, where M≦

p, and p is a total number of elements in a block row of the LDPC parity check matrix;

U≦

d_c, and d_c is check node degree of the block row.

31. The decoder of claim 17, 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 an R select unit.

32. 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;

permuting the P message; and

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

33. The method of claim 32, 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.

34. The method of claim 32, 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.

35. The method of claim 32, further comprising subtracting an R old message from a permuted P message to generate a Q message.

36. The method of claim 32, further comprising adding a P message to a permuted difference of an R new message and an R prev message to produce an updated P message.

37. The method of claim 32, 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.

38. The method of claim 32, further comprising subtracting an R old message from an updated permuted P message to generate a Q message.

39. The method of claim 32, further comprising adding a permuted P message to the difference of an R new message and an R prev message to produce an updated permuted P message.

40. The method of claim 32, further comprising performing block parallel processing wherein a plurality (U) of block columns of a plurality (M) of rows in a layer of an LDPC parity check matrix are processed in one clock cycle, and wherein M≦

p, and p is a total number of elements in a block row of the LDPC parity check matrix;

U≦

d_c, and d_c is check node degree of the block row of the LDPC parity check matrix.

41. 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, M1, by comparing a first stored minimum value, M1_PS, and the received variable message Q; and

a second comparator of the set determines a second minimum value, M2, by comparing a second stored minimum value, M2_PS, and the received variable message Q; and

final state storage that stores;

M1_PS, and

M2_PS; and

a computation unit that computes a message transferred from the check node to a variable node based on the values of M1_PS and M2_PS stored in the final state storage.

42. The decoder of claim 41, further comprising a two'"'"'s complement unit that converts values from sign magnitude to two'"'"'s complement format, wherein the two'"'"'s complement unit produces −

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

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

43. The decoder of claim 41, further comprising a partial state storage array wherein M1 is stored as M1_PS, M2 is stored as M2_PS, and indicia of the location of M1_PS is stored as M1_INDEX.

44. The decoder of claim 41, further comprising an offset correction unit that applies offset correction to M1_PS and M2_PS.

45. The decoder of claim 41, wherein the final state storage array stores indicia of the location of M1_PS, and the message to the variable node unit is selected based on the indicia, stored in the final state storage, of the location of M1_PS.

46. The decoder of claim 41, further comprising a scaling correction unit that applies scaling correction to M1_PS and M2_PS.

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

48. The decoder of claim 41, further 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 routing of messages between CNUs and variable node units (VNUs) is accomplished via active routers.

49. 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 location of the new first minimum value in a partial state storage array;

storing, in a final state storage array of a check node unit, a first final minimum value read from the partial state storage array, and a second final minimum value read from the partial state storage array; and

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

providing the check node message to a variable node.

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

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

52. The method of claim 49, further comprising:

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

determining the check node message based on the indicia of the first minimum value location stored in a final state storage array.

53. The method of claim 49, further comprising applying scaling correction to the stored first minimum value and the stored second minimum value.

54. The method of claim 49, further 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 coupled to variable node units via active routers.