Common circuitry supporting both bit node and check node processing in LDPC (Low Density Parity Check) decoder

• US 7,395,487 B2
• Filed: 06/30/2005
• Issued: 07/01/2008
• Est. Priority Date: 08/15/2002
• Status: Expired due to Fees

• 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): Chung; Phung M
• Application Number:
  US11/171,568
• Publication Number:
  US 20050268206A1
• Time in Patent Office: 1,097 Days
• Field of Search: 714/755, 714758-759, 714/776, 714/786, 714/794, 714/795, 714/801, 375/341
• US Class Current: 714/758
• 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/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• 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/658 Scaling by multiplication or division
• CPC Class Codes: H04L 27/18 Phase-modulated carrier systems, i.e. using phase-shift keying H04L27/32 takes precedence
• CPC Class Codes: H04L 27/34 Amplitude- and phase-modulated carrier systems, e.g. quadrature-amplitude modulated carrier systems

Abstract

Common circuitry supporting both bit node and check node processing in LDPC (Low Density Parity Check) decoder. A novel approach is presented by which a decoder may use the same circuitry to perform updating of edge messages with respect to bit nodes as well as updating of edge messages with respect to check nodes in the context of decoding LDPC coded signals. In addition, several very efficient architectures are presented to performing check node processing that involves the updating of edge messages with respect to check nodes. One embodiment performs check node processing using min** (min-double-star) processing in conjunction with min**− (min-double-star-minus) processing. Another embodiment performs check node processing using min†† (min-double-dagger) processing in conjunction with min†− (min-dagger-minus) processing. In addition, a single FIFO may be implemented to service a number of macro blocks in a parallel decoding implementation.

Claims

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

a FIFO (First-In First-Out) buffer that is operable to receive and subsequently to provide a plurality of edge messages with respect to a plurality of check nodes;

a bit node processing functional block that is operable to receive a bit metric that corresponds to a symbol of the LDPC coded signal, the plurality of edge messages with respect to the plurality of check nodes, and one edge message of the plurality of edge messages with respect to the plurality of check nodes from the FIFO buffer, and that comprises;

an accumulator that is operable to add each edge message of the plurality of edge messages with respect to the plurality of check nodes with the bit metric thereby generating a summed value; and

a subtraction functional block that is operable to subtract the one edge message of the plurality of edge messages with respect to the plurality of check nodes provided from the FIFO buffer from the summed value thereby generating one updated edge message of a plurality of updated edge messages with respect to a plurality of bit nodes;

wherein the FIFO buffer is also operable to receive and subsequently to provide the plurality of updated edge messages with respect to the plurality of bit nodes; and

a check node processing functional block that is operable to receive the plurality of updated edge messages with respect to the plurality of bit nodes from the bit node processing functional block and that comprises;

a min** (min-double-star) processing functional block that is operable to perform min** processing using the plurality of updated edge messages with respect to the plurality of bit nodes thereby generating a min** resultant; and

a min**−

(min-double-star-minus) processing functional block that is operable to perform min**−

processing using one updated edge message with respect to the plurality of bit nodes provided from the FIFO buffer and the min** resultant received from the min** processing functional block thereby generating an updated edge message with respect to the plurality of check nodes.

2. The decoder of claim 1, wherein:

the bit node processing functional block is operable to provide the plurality of updated edge messages with respect to the plurality of bit nodes to the check node processing functional block in 2s complement format.

3. The decoder of claim 1, wherein the min** processing functional block further comprises:

a MUX (Multiplexor) that is operable to select a minimum value from one updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes and a previously calculated min** resultant;

a first log correction factor functional block that is operable to provide a first log correction factor;

a second log correction factor functional block that is operable to provide a second log correction factor; and

a summer that is operable to add the selected minimum value, the first log correction factor, and the second log correction thereby generating the min** resultant.

4. The decoder of claim 3, wherein:

the first log correction factor functional block comprises a first LUT (Look-Up Table) that comprises a predetermined plurality of first log correction factors; and

the second log correction factor functional block comprises a second LUT that comprises a predetermined plurality of second log correction factors.

5. The decoder of claim 1, wherein the min**−

processing functional block further comprises;

a MUX (Multiplexor) that is operable to select a minimum value from the min** resultant and updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes received from the FIFO buffer;

a first log correction factor functional block that is operable to provide a first log correction factor;

a second log correction factor functional block that is operable to provide a second log correction factor; and

a summer that is operable to add the selected minimum value, the first log correction factor, and the second log correction thereby generating the updated edge message with respect to the plurality of check nodes.

6. The decoder of claim 5, wherein:

the first log correction factor functional block comprises a first LUT (Look-Up Table) that comprises a predetermined plurality of first log correction factors; and

the second log correction factor functional block comprises a second LUT that comprises a predetermined plurality of second log correction factors.

7. The decoder of claim 1, wherein:

during a first clock cycle, the accumulator is operable to add a first edge message of the plurality of edge messages with respect to the plurality of check nodes with the bit metric thereby generating a first intermediate summed value;

during a second clock cycle, the accumulator is operable to add a second edge message of the plurality of edge messages with respect to the plurality of check nodes with the first intermediate summed value thereby generating a second intermediate summed value; and

during a third clock cycle, the accumulator is operable to add a third edge message of the plurality of edge messages with respect to the plurality of check nodes with the second intermediate summed value thereby generating the summed value.

8. The decoder of claim 1, further comprising a plurality of macro blocks that is arranged in a parallel configuration such that each macro block of the plurality of macro blocks comprises one FIFO buffer and a plurality of bit/check processors, wherein:

each bit/check processor of the plurality of bit/check processors comprises a corresponding bit node processing functional block and a corresponding check node processing functional block; and

the one FIFO buffer of each macro block of the plurality of macro blocks includes a plurality of parallel paths such that each parallel path corresponds to one bit/check processor of the corresponding plurality of bit/check processors.

9. The decoder of claim 1, wherein:

the LDPC coded signal is a variable code rate signal and is also a variable modulation signal;

the first symbol of the LDPC coded signal has a first code rate and 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 code rate and a second modulation having a second constellation shape and a corresponding second mapping.

10. The decoder of claim 9, wherein:

at least one of the first modulation and the second modulation is QPSK (Quadrature Phase Shift Key) modulation, 8 PSK (Phase Shift Key) modulation, 16 APSK (Asymmetric Phase Shift Keying) modulation, or 16 QAM (Quadrature Amplitude Modulation).

11. 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 (10GBASE-T) Task Force.

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

a FIFO (First-In First-Out) buffer that is operable to receive and subsequently to provide a plurality of edge messages with respect to a plurality of check nodes;

a bit node processing functional block that is operable to receive a bit metric that corresponds to a symbol of the LDPC coded signal, the plurality of edge messages with respect to the plurality of check nodes, and one edge message of the plurality of edge messages with respect to the plurality of check nodes from the FIFO buffer, and that comprises;

an accumulator that is operable to add each edge message of the plurality of edge messages with respect to the plurality of check nodes with the bit metric thereby generating a summed value; and

a subtraction functional block that is operable to subtract the one edge message of the plurality of edge messages with respect to the plurality of check nodes provided from the FIFO buffer from the summed value thereby generating one updated edge message of a plurality of updated edge messages with respect to a plurality of bit nodes;

wherein the FIFO buffer is also operable to receive and subsequently to provide absolute values of each updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes; and

a check node processing functional block that is operable to receive the plurality of updated edge messages with respect to the plurality of bit nodes from the bit node processing functional block and that comprises;

a min†

†

(min-double-dagger) processing functional block that is operable to perform min†

†

processing thereby generating a min* (min-star) resultant generated using the plurality of updated edge message with respect to the plurality of bit nodes and also thereby outputting a minimum updated edge message of the plurality of updated edge message with respect to the plurality of bit nodes; and

a min†

−

(min-dagger-minus) processing functional block that is operable to perform min†

−

processing using an absolute value of one updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes provided from the FIFO buffer, the min* resultant received from the min†

†

processing functional block, and the minimum updated edge message received from the min†

†

processing functional block thereby generating an updated edge message with respect to the plurality of check nodes.

13. The decoder of claim 12, wherein:

the bit node processing functional block further comprises a sign-magnitude format processor that is operable to provide the plurality of updated edge messages with respect to the plurality of bit nodes to the check node processing functional block in sign-magnitude format.

14. The decoder of claim 12, wherein:

the FIFO buffer is operable to provide an MSB (Most Significant Bit) of one updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes to the min†

−

processing functional block for use in determining a final value of the updated edge message with respect to the plurality of check nodes.

15. The decoder of claim 12, wherein:

during a first clock cycle, the accumulator is operable to add a first edge message of the plurality of edge messages with respect to the plurality of check nodes with the bit metric thereby generating a first intermediate summed value;

during a second clock cycle, the accumulator is operable to add a second edge message of the plurality of edge messages with respect to the plurality of check nodes with the first intermediate summed value thereby generating a second intermediate summed value; and

during a third clock cycle, the accumulator is operable to add a third edge message of the plurality of edge messages with respect to the plurality of check nodes with the second intermediate summed value thereby generating the summed value.

16. The decoder of claim 12, further comprising a plurality of macro blocks that is arranged in a parallel configuration such that each macro block of the plurality of macro blocks comprises one FIFO buffer and a plurality of bit/check processors, wherein:

each bit/check processor of the plurality of bit/check processors comprises a corresponding bit node processing functional block and a corresponding check node processing functional block; and

the one FIFO buffer of each macro block of the plurality of macro blocks includes a plurality of parallel paths such that each parallel path corresponds to one bit/check processor of the corresponding plurality of bit/check processors.

17. The decoder of claim 12, wherein:

the LDPC coded signal is a variable code rate signal and is also a variable modulation signal;

the first symbol of the LDPC coded signal has a first code rate and 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 code rate and a second modulation having a second constellation shape and a corresponding second mapping.

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

19. A decoder, comprising a plurality of macro blocks that is arranged in a parallel configuration such that each macro block of the plurality of macro blocks comprises one FIFO (First-In First-Out) buffer and a plurality of bit/check processors, that is operable to decode an LDPC (Low Density Parity Check) coded signal, wherein:

the FIFO buffer of each macro block of the plurality of macro blocks is operable to receive and subsequently to provide a plurality of edge messages with respect to the plurality of check nodes;

the FIFO buffer of each macro block of the plurality of macro blocks includes a plurality of parallel paths such that each parallel path corresponds to one bit/check processor of the corresponding plurality of bit/check processors;

each bit/check processor of the plurality of bit/check processors comprises a corresponding bit node processing functional block and a corresponding check node processing functional block, wherein;

each corresponding bit node processing functional block is operable to receive a bit metric that corresponds to a symbol of the LDPC coded signal, the plurality of edge messages with respect to the plurality of check nodes, and one edge message of the plurality of edge messages with respect to the plurality of check nodes from the FIFO buffer, and comprises;

an accumulator that is operable to add each edge message of the plurality of edge messages with respect to the plurality of check nodes with the bit metric thereby generating a summed value; and

a subtraction functional block that is operable to subtract the one edge message of the plurality of edge messages with respect to the plurality of check nodes provided from the FIFO buffer from the summed value thereby generating one updated edge message of a plurality of updated edge messages with respect to a plurality of bit nodes;

the FIFO buffer of each macro block of the plurality of macro blocks is also operable to receive and subsequently to provide the plurality of updated edge messages with respect to the plurality of bit nodes; and

each check node processing functional block is operable to receive the plurality of updated edge messages with respect to the plurality of bit nodes from a corresponding bit node processing functional block and comprises;

a min** (min-double-star) processing functional block that is operable to perform min** processing using the plurality of updated edge messages with respect to the plurality of bit nodes thereby generating a min** resultant; and

a min**−

(min-double-star-minus) processing functional block that is operable to perform min**−

processing using one updated edge message with respect to the plurality of bit nodes provided from the FIFO buffer and the min** resultant received from the min** processing functional block thereby generating an updated edge message with respect to the plurality of check nodes.

20. A decoder, comprising a plurality of macro blocks that is arranged in a parallel configuration such that each macro block of the plurality of macro blocks comprises one FIFO (First-In First-Out) buffer and a plurality of bit/check processors, that is operable to decode an LDPC (Low Density Parity Check) coded signal, wherein:

the FIFO buffer of each macro block of the plurality of macro blocks is operable to receive and subsequently to provide a plurality of edge messages with respect to the plurality of check nodes;

the FIFO buffer of each macro block of the plurality of macro blocks includes a plurality of parallel paths such that each parallel path corresponds to one bit/check processor of the corresponding plurality of bit/check processors;

each bit/check processor of the plurality of bit/check processors comprises a corresponding bit node processing functional block and a corresponding check node processing functional block, wherein;

each corresponding bit node processing functional block is operable to receive a bit metric that corresponds to a symbol of the LDPC coded signal, the plurality of edge messages with respect to the plurality of check nodes, and one edge message of the plurality of edge messages with respect to the plurality of check nodes from the FIFO buffer, and comprises;

an accumulator that is operable to add each edge message of the plurality of edge messages with respect to the plurality of check nodes with the bit metric thereby generating a summed value; and

a subtraction functional block that is operable to subtract the one edge message of the plurality of edge messages with respect to the plurality of check nodes provided from the FIFO buffer from the summed value thereby generating one updated edge message of a plurality of updated edge messages with respect to a plurality of bit nodes;

the FIFO buffer of each macro block of the plurality of macro blocks is also operable to receive and subsequently to provide absolute values of each updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes; and

each check node processing functional block is operable to receive the plurality of updated edge messages with respect to the plurality of bit nodes from a corresponding bit node processing functional block and comprises;

a min†

†

(min-double-dagger) processing functional block that is operable to perform min†

†

processing thereby generating a min* (min-star) resultant generated using the plurality of updated edge message with respect to the plurality of bit nodes and also thereby outputting a minimum updated edge message of the plurality of updated edge message with respect to the plurality of bit nodes; and

a min†

−

(min-dagger-minus) processing functional block that is operable to perform min†

−

processing using an absolute value of one updated edge message of the plurality of updated edge messages with respect to the plurality of bit nodes provided from the FIFO buffer, the min* resultant received from the min†

†

processing functional block, and the minimum updated edge message received from the min†

†

processing functional block thereby generating an updated edge message with respect to the plurality of check nodes.