Efficient design to implement LDPC (Low Density Parity Check) decoder

• US 7,409,628 B2
• Filed: 06/30/2005
• Issued: 08/05/2008
• Est. Priority Date: 08/15/2002
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Shen, Ba-Zhong, Tran, Hau Thien, Cameron, Kelly Brian
• Primary Examiner(s): Baker; Stephen M.
• Application Number:
  US11/171,998
• Publication Number:
  US 20050262424A1
• Time in Patent Office: 1,132 Days
• Field of Search: 714/780
• US Class Current: 714/780
• 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/1117 using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule
• CPC Class Codes: H03M 13/112 with correction functions for the min-sum rule, e.g. using an offset or a scaling factor
• CPC Class Codes: H03M 13/1134 Full parallel processing, i.e. all bit nodes or check nodes are processed in parallel
• CPC Class Codes: H03M 13/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• 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/1165 QC-LDPC codes as defined for the digital video broadcasting [DVB] specifications, e.g. DVB-Satellite [DVB-S2]
• CPC Class Codes: H03M 13/255 with Low Density Parity Check [LDPC] codes
• CPC Class Codes: H03M 13/6505 Memory efficient implementations
• CPC Class Codes: H03M 13/658 Scaling by multiplication or division

Abstract

Efficient design to implement LDPC decoder. The efficient design presented herein provides for a solution that is much easier, smaller, and has less complexity than other possible solutions. The use of a ping-pong memory structure (or pseudo-dual port memory structure) in conjunction with a metric generator near the decoder'"'"'s front end allows parallel bit/check node processing. An intelligently operating barrel shifter operates with a message passing memory that is operable to store updated edges messages with respect to check nodes as well as updated edges messages with respect to bit nodes. Using an efficient addressing scheme allows the same memory structure to store the two types of edges messages with respect to bit nodes: (1) corresponding to information bits and (2) corresponding to parity bits. In addition, an intelligently designed hardware macro block may be instantiated a number of times into the decoder design to support ever greater design efficiency.

Claims

1. A decoder that is operable to decode an LDPC (Low Density Parity Check) coded signal, the decoder comprising:

a metric generator that is operable to;

receive first I, Q (In-phase, Quadrature) values corresponding to a first symbol of the LDPC coded signal and is operable to generate a first plurality of bit metrics there from;

receive second I, Q values corresponding to a second symbol of the LDPC coded signal and is operable to generate a second plurality of bit metrics there from;

a metric memory that is operable to;

store the first plurality of bit metrics and the second plurality of bit metrics;

support dual port memory management thereby outputting the first plurality of bit metrics while receiving the second plurality of bit metrics from the metric generator;

support dual port memory management thereby outputting the second plurality of bit metrics while receiving a third plurality of bit metrics from the metric generator;

a plurality of bit/check processors that is operable to;

successively receive the first plurality of bit metrics, the second plurality of bit metrics, and the third plurality of bit metrics;

perform both bit node processing that involves updating a plurality of edge messages with respect to a plurality of bit nodes and check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes;

a message passing memory that is operable to;

store the plurality of edge messages with respect to the plurality of bit nodes after undergoing bit node processing within the plurality of bit/check processors;

store the plurality of edge messages with respect to the plurality of check nodes after undergoing check node processing within the plurality of bit/check processors;

a barrel shifter that is operable to;

shift the plurality of edge messages with respect to the plurality of bit nodes that is accessed from the memory passing memory;

provide the shifted plurality of edge messages with respect to the plurality of bit nodes to the plurality of bit/check processors for subsequent check node processing;

shift the plurality of edge messages with respect to the plurality of check nodes that is accessed from the memory passing memory; and

provide the shifted plurality of edge messages with respect to the plurality of check nodes to the plurality of bit/check processors for subsequent bit node processing.

2. The decoder of claim 1, further comprising:

an output processor that is operable to receive soft output from the plurality of bit/check processors that corresponds to most recently updated plurality of edge messages with respect to the plurality of bit nodes and is operable to make hard decisions thereon thereby generating best estimates of bits of at least one of the first symbol of the LDPC coded signal and the second symbol of the LDPC coded signal.

3. The decoder of claim 1, further comprising:

a syndrome calculation functional block that is operable to receive soft output from the plurality of bit/check processors that corresponds to most recently updated plurality of edge messages with respect to the plurality of bit nodes and is operable to determine whether each of a plurality of syndromes of an LDPC code by which the LDPC coded signal is generated is equal to zero.

4. The decoder of claim 1, wherein:

the metric memory, the plurality of bit/check processors, and the message passing memory form a first macro block of a plurality of macro blocks;

each macro block of the plurality of macro blocks also includes a corresponding metric memory, a corresponding plurality of bit/check processors, and a corresponding message passing memory;

the barrel shifter is communicatively coupled to each corresponding message passing memory within each macro block of the plurality of macro blocks.

5. The decoder of claim 1, wherein:

the metric memory is a ping-pong memory structure that includes two separate metric memories.

6. The decoder of claim 1, wherein:

the metric memory is a pseudo dual port metric memory.

7. The decoder of claim 1, wherein:

the plurality of edge messages with respect to the plurality of bit nodes are stored in the message passing memory in sign-magnitude format; and

the plurality of edge messages with respect to the plurality of check nodes are stored in the message passing memory in 2s complement format.

8. The decoder of claim 1, wherein:

the plurality of edge messages with respect to the plurality of bit nodes comprises a first plurality of edge messages corresponding to information bits and a second plurality of edge messages corresponding to parity bits; and

each of the first plurality of edge messages corresponding to information bits and the second plurality of edge messages corresponding to parity bits is stored in the message passing memory.

9. The decoder of claim 1, wherein:

the check node processing involves min** (min-double-star) processing and min**−

(min-double-star-minus) processing.

10. The decoder of claim 1, wherein:

the check node processing involves min†

†

(min-double-dagger) processing and min†

−

(min-dagger-minus) processing.

11. The decoder of claim 1, wherein:

the LDPC coded signal is a variable code rate signal;

the first symbol of the LDPC coded signal has a first code rate; and

the second symbol of the LDPC coded signal has a second code rate.

12. The decoder of claim 1, wherein:

the LDPC coded signal is a variable modulation signal;

the first symbol of the LDPC coded signal has a first modulation having a first constellation shape and a corresponding first mapping; and

the second symbol of the LDPC coded signal has a second modulation having a second constellation shape and a corresponding second mapping.

13. The decoder of claim 1, wherein:

the decoder is operable to decode LDPC coded signals that are compliant with at least one of DVB-S2 (Digital Video Broadcasting Project-Satellite Version

     2) standard and recommended practices provided by IEEE (Institute of Electrical &

Electronics Engineers) P802.3an (10 GBASE-T) Task Force.

14. A decoder that is operable to decode an LDPC (Low Density Parity Check) coded signal, the decoder comprising:

a plurality of bit/check processors that is operable to;

receive a plurality of bit metrics;

perform both bit node processing that involves updating a plurality of edge messages with respect to a plurality of bit nodes and check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes;

a message passing memory that is operable to;

store the plurality of edge messages with respect to the plurality of bit nodes after undergoing bit node processing within the plurality of bit/check processors;

store the plurality of edge messages with respect to the plurality of check nodes after undergoing check node processing within the plurality of bit/check processors;

a barrel shifter that is operable to;

shift the plurality of edge messages with respect to the plurality of bit nodes that is accessed from the memory passing memory;

provide the shifted plurality of edge messages with respect to the plurality of bit nodes to the plurality of bit/check processors for subsequent check node processing;

shift the plurality of edge messages with respect to the plurality of check nodes that is accessed from the memory passing memory; and

provide the shifted plurality of edge messages with respect to the plurality of check nodes to the plurality of bit/check processors for subsequent bit node processing.

15. The decoder of claim 14, further comprising:

a metric generator that is operable to receive I, Q (In-phase, Quadrature) values corresponding to a plurality of symbols of the LDPC coded signal and is operable to generate the plurality of bit metrics there from.

16. The decoder of claim 14, further comprising:

an output processor that is operable to receive soft output from the plurality of bit/check processors that corresponds to most recently updated plurality of edge messages with respect to the plurality of bit nodes and is operable to make hard decisions thereon thereby generating best estimates of bits of at least one of the first symbol of the LDPC coded signal and the second symbol of the LDPC coded signal.

17. The decoder of claim 14, further comprising:

a syndrome calculation functional block that is operable to receive soft output from the plurality of bit/check processors that corresponds to most recently updated plurality of edge messages with respect to the plurality of bit nodes and is operable to determine whether each of a plurality of syndromes of an LDPC code by which the LDPC coded signal is generated is equal to zero.

18. The decoder of claim 14, further comprising a metric memory that is operable to store and subsequently output the plurality of bit metrics to the plurality of bit/check processors;

wherein;

the metric memory, the plurality of bit/check processors, and the message passing memory form a first macro block of a plurality of macro blocks;

each macro block of the plurality of macro blocks also includes a corresponding metric memory, a corresponding plurality of bit/check processors, and a corresponding message passing memory;

the barrel shifter is communicatively coupled to each corresponding message passing memory within each macro block of the plurality of macro blocks.

19. The decoder of claim 14, wherein:

the metric memory is a ping-pong memory structure that includes two separate metric memories.

20. The decoder of claim 14, wherein:

the metric memory is a pseudo dual port metric memory.

21. The decoder of claim 14, wherein:

the plurality of edge messages with respect to the plurality of bit nodes are stored in the message passing memory in sign-magnitude format; and

the plurality of edge messages with respect to the plurality of check nodes are stored in the message passing memory in 2s complement format.

22. The decoder of claim 14, wherein:

the plurality of edge messages with respect to the plurality of bit nodes comprises a first plurality of edge messages corresponding to information bits and a second plurality of edge messages corresponding to parity bits; and

each of the first plurality of edge messages corresponding to information bits and the second plurality of edge messages corresponding to parity bits is stored in the message passing memory.

23. The decoder of claim 14, wherein:

the check node processing involves min** (min-double-star) processing and min**−

(min-double-star-minus) processing.

24. The decoder of claim 14, wherein:

the check node processing involves min†

†

(min-double-dagger) processing and min†

−

(min-dagger-minus) processing.

25. The decoder of claim 14, wherein:

the LDPC coded signal is a variable code rate signal;

the first symbol of the LDPC coded signal has a first code rate; and

the second symbol of the LDPC coded signal has a second code rate.

26. The decoder of claim 14, wherein:

the LDPC coded signal is a variable modulation signal;

the first symbol of the LDPC coded signal has a first modulation having a first constellation shape and a corresponding first mapping; and

the second symbol of the LDPC coded signal has a second modulation having a second constellation shape and a corresponding second mapping.

27. The decoder of claim 14, wherein:

the decoder is operable to decode LDPC coded signals that are compliant with at least one of DVB-S2 (Digital Video Broadcasting Project-Satellite Version

     2) standard and recommended practices provided by IEEE (Institute of Electrical &

Electronics Engineers) P802.3an (10GBASE-T) Task Force.

28. A method for decoding an LDPC (Low Density Parity Check) coded signal, the method comprising:

receiving first I, Q (In-phase, Quadrature) values corresponding to a first symbol of the LDPC coded signal and generating a first plurality of bit metrics there from;

receiving second I, Q values corresponding to a second symbol of the LDPC coded signal and generating a second plurality of bit metrics there from;

storing the first plurality of bit metrics and the second plurality of bit metrics;

supporting dual port memory management thereby outputting the first plurality of bit metrics while receiving the second plurality of bit metrics;

supporting dual port memory management thereby outputting the second plurality of bit metrics while receiving a third plurality of bit metrics;

successively receiving the first plurality of bit metrics, the second plurality of bit metrics, and the third plurality of bit metrics;

performing both bit node processing that involves updating a plurality of edge messages with respect to a plurality of bit nodes and check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes;

storing the plurality of edge messages with respect to the plurality of bit nodes after undergoing bit node processing;

storing the plurality of edge messages with respect to the plurality of check nodes after undergoing check node processing;

shifting the plurality of edge messages with respect to the plurality of bit nodes into an appropriate arrangement for subsequent check node processing; and

shifting the plurality of edge messages with respect to the plurality of check nodes into an appropriate arrangement for subsequent bit node processing.

29. The method of claim 28, further comprising:

receiving soft output that corresponds to most recently updated plurality of edge messages with respect to the plurality of bit nodes and making hard decisions thereon thereby generating best estimates of bits of at least one of the first symbol of the LDPC coded signal and the second symbol of the LDPC coded signal.

30. The method of claim 28, further comprising:

receiving soft output that corresponds to most recently updated plurality of edge messages with respect to the plurality of bit nodes; and

determining whether each of a plurality of syndromes of an LDPC code by which the LDPC coded signal is generated is equal to zero.

31. The method of claim 28, wherein:

the storing of the plurality of edge messages with respect to the plurality of bit nodes is performed in sign-magnitude format; and

the storing of the plurality of edge messages with respect to the plurality of check nodes is performed in 2s complement format.

32. The method of claim 28, wherein:

the plurality of edge messages with respect to the plurality of bit nodes comprises a first plurality of edge messages corresponding to information bits and a second plurality of edge messages corresponding to parity bits; and

further comprising;

storing each of the first plurality of edge messages corresponding to information bits and the second plurality of edge messages corresponding to parity bits in a single memory device.

33. The method of claim 28, wherein:

the check node processing involves min** (min-double-star) processing and min**−

(min-double-star-minus) processing.

34. The method of claim 28, wherein:

the check node processing involves min†

†

(min-double-dagger) processing and min†

−

(min-dagger-minus) processing.

35. The method of claim 28, wherein:

the LDPC coded signal is a variable code rate signal;

the first symbol of the LDPC coded signal has a first code rate; and

the second symbol of the LDPC coded signal has a second code rate.

36. The method of claim 28, wherein:

the LDPC coded signal is a variable modulation signal;

the first symbol of the LDPC coded signal has a first modulation having a first constellation shape and a corresponding first mapping; and

the second symbol of the LDPC coded signal has a second modulation having a second constellation shape and a corresponding second mapping.

37. The method of claim 28, wherein:

the method is operable to decode LDPC coded signals that are compliant with at least one of DVB-S2 (Digital Video Broadcasting Project-Satellite Version

     2) standard and recommended practices provided by IEEE (Institute of Electrical &

Electronics Engineers) P802.3an (10 GBASE-T) Task Force.