Efficient design to implement min**/min**- or max**/max**- functions in LDPC (low density parity check) decoders

• US 7,447,985 B2
• Filed: 06/30/2005
• Issued: 11/04/2008
• Est. Priority Date: 08/15/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Shen, Ba-Zhong, Tran, Hau Thien, Cameron, Kelly Brian
• Primary Examiner(s): Chase; Shelly A
• Application Number:
  US11/172,165
• Publication Number:
  US 20050246618A1
• Time in Patent Office: 1,223 Days
• Field of Search: 714/800, 714/801, 714/807
• US Class Current: 714/801
• 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/3911 Correction factor, e.g. approximations of the exp(1+x) function
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

Efficient design to implement min**/min**− or max**/max**− functions in LDPC (Low Density Parity Check) decoders. When compared to prior art approaches, the novel and efficient implementation presented herein allows for the use of substantially less hardware and surface area within an actual communication device implemented to perform these calculations. In certain embodiments, the min** processing (and/or max** processing) is implemented to assist in the computationally intensive calculations required to decoded LDPC coded signals. In one instance, this is operable to assist in check node processing when decoding LDPC coded signals. However, the efficient principles and architectures presented herein may be implemented within other communication device types to decode other types of coded signals as well. For example, the processing presented herein may perform calculations within a variety of decoders including LDPC decoders, turbo decoders, TTCM decoders, and/or other decoder types without departing from the scope and spirit of the invention.

Claims

1. A functional block that is operable to perform min** (min-double-star) processing in a decoder, the functional block comprising:

a subtractor that is operable to calculate a difference between a first value and a second value;

a summer that is operable to calculate a sum of the first value and the second value;

a MUX (Multiplexor) that is operable to receive the first value, the second value, an opposite in sign value of the first value, and an opposite in sign value of the second value and whose select signals comprise a first sign bit corresponding to the difference between the first value and the second value and a second sign bit corresponding to the sum of the first value and the second value;

a first log correction functional block that is operable to provide a first log correction factor based on an absolute value of the difference between the first value and the second value; and

a second log correction functional block that is operable to provide a second log correction factor based on an absolute value of the sum of the first value and the second value.

2. The functional block of claim 1, further comprising:

at least one additional summer that is operable to calculate min** resultant that comprises a sum of the first log correction factor, the second log correction factor, and an output of the MUX that is selected from the first value, the second value, an opposite in sign value of the first value, and an opposite in sign value of the second value.

3. The functional block of claim 1, wherein:

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

the second log correction functional block includes a second LUT that comprises a predetermined plurality of possible values of the second log correction factor.

4. The functional block of claim 3, wherein:

the predetermined plurality of possible values of the first log correction factor comprises a first bounded plurality of values; and

the predetermined plurality of possible values of the second log correction factor comprises a second bounded plurality of values.

5. The functional block of claim 1, wherein:

the MUX outputs the opposite in sign value of the second value when the first sign bit is less than zero and the second sign bit is less than zero;

the MUX outputs the opposite in sign value of the first value when the first sign bit is greater than zero and the second sign bit is less than zero;

the MUX outputs the first value when the first sign bit is less than zero and the second sign bit is greater than zero; and

the MUX outputs the second value when the first sign bit is greater than zero and the second sign bit is greater than zero.

6. The functional block of claim 1, wherein:

the functional block that is operable to perform min** processing is communicatively coupled, via at last one register, to at least one additional functional block that is operable to perform min**−

(min-double-star-minus) processing;

the functional block and the at least one additional functional block operate cooperatively to perform check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes using a plurality of edge messages with respect to the plurality of bit nodes; and

the functional block and the at least one additional functional block are implemented within an LDPC (Low Density Parity Check) decoder that is operable to decode an LDPC coded signal.

7. A functional block that is operable to perform max** (max-double-star) processing in a decoder, the functional block comprising:

a subtractor that is operable to calculate a difference between a first value and a second value;

a summer that is operable to calculate a sum of the first value and the second value;

a MUX (Multiplexor) that is operable to receive the first value, the second value, an opposite in sign value of the first value, and an opposite in sign value of the second value and whose select signals comprise a first sign bit corresponding to the difference between the first value and the second value and a second sign bit corresponding to the sum of the first value and the second value;

a first log correction functional block that is operable to provide a first log correction factor based on an absolute value of the difference between the first value and the second value; and

a second log correction functional block that is operable to provide a second log correction factor based on an absolute value of the sum of the first value and the second value.

8. The functional block of claim 7, further comprising:

at least one additional summer that is operable to calculate max** resultant that comprises a sum of the first log correction factor, the second log correction factor, and an output of the MUX that is selected from the first value, the second value, an opposite in sign value of the first value, and an opposite in sign value of the second value.

9. The functional block of claim 7, wherein:

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

the second log correction functional block includes a second LUT that comprises a predetermined plurality of possible values of the second log correction factor.

10. The functional block of claim 9, wherein:

the predetermined plurality of possible values of the first log correction factor comprises a first bounded plurality of values; and

the predetermined plurality of possible values of the second log correction factor comprises a second bounded plurality of values.

11. The functional block of claim 7, wherein:

the MUX outputs the second value when the first sign bit is less than zero and the second sign bit is less than zero;

the MUX outputs the first value when the first sign bit is greater than zero and the second sign bit is less than zero;

the MUX outputs the opposite in sign value of the first value when the first sign bit is less than zero and the second sign bit is greater than zero; and

the MUX outputs the opposite in sign value of the second value when the first sign bit is greater than zero and the second sign bit is greater than zero.

12. The functional block of claim 7, wherein:

the functional block that is operable to perform max** processing is communicatively coupled, via at last one register, to at least one additional functional block that is operable to perform max**−

(max-double-star-minus) processing;

the functional block and the at least one additional functional block operate cooperatively to perform check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes using a plurality of edge messages with respect to the plurality of bit nodes; and

the functional block and the at least one additional functional block are implemented within an LDPC (Low Density Parity Check) decoder that is operable to decode an LDPC coded signal.

13. A method for performing min** (min-double-star) processing, min**−

(min-double-star-minus) processing, max** (max-double-star) processing or max**−

(max-double-star-minus) processing, the method comprising;

calculating a difference between a first value and a second value;

calculating a sum of the first value and the second value;

calculating an opposite in sign value of the first value;

calculating an opposite in sign value of the second value;

based on a first sign bit corresponding to the difference between the first value and the second value and based on a second sign bit corresponding to the sum of the first value and the second value, selecting the first value, the second value, the opposite in sign value of the first value, or the opposite in sign value of the second value;

determining a first log correction factor based on an absolute value of the difference between the first value and the second value; and

determining a second log correction factor based on an absolute value of the sum of the first value and the second value.

14. The method of claim 13, further comprising:

calculating a min** resultant, a min**−

resultant, a max** resultant, or a max**−

resultant using the first log correction factor, the second log correction factor, and the selected one of the first value, the second value, the opposite in sign value of the first value, and the opposite in sign value of the second value.

15. The method of claim 13, further comprising:

selecting the first log correction factor from a first LUT (Look-Up Table) that comprises a predetermined plurality of possible values of the first log correction factor; and

selecting the second log correction factor from a second LUT that comprises a predetermined plurality of possible values of the second log correction factor.

16. The method of claim 15;

wherein;

the predetermined plurality of possible values of the first log correction factor comprises a first bounded plurality of values; and

the predetermined plurality of possible values of the second log correction factor comprises a second bounded plurality of values.

17. The method of claim 13, when the method performs min** processing, further comprising:

selecting the opposite in sign value of the second value when the first sign bit is less than zero and the second sign bit is less than zero;

selecting the opposite in sign value of the first value when the first sign bit is greater than zero and the second sign bit is less than zero;

selecting the first value when the first sign bit is less than zero and the second sign bit is greater than zero; and

selecting the second value when the first sign bit is greater than zero and the second sign bit is greater than zero.

18. The method of claim 13, when the method performs max** processing, further comprising:

selecting the second value when the first sign bit is less than zero and the second sign bit is less than zero;

selecting the first value when the first sign bit is greater than zero and the second sign bit is less than zero;

selecting the opposite in sign value of the first value when the first sign bit is less than zero and the second sign bit is greater than zero; and

selecting the opposite in sign value of the second value when the first sign bit is greater than zero and the second sign bit is greater than zero.

19. The method of claim 13, further comprising:

cooperatively performing min** processing and min**−

(max-double-star-minus) processing to perform check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes using a plurality of edge messages with respect to the plurality of bit nodes during decoding of an LDPC (Low Density Parity Check) coded signal.

20. The method of claim 13, further comprising:

cooperatively performing max** processing and max**−

(max-double-star-minus) processing to perform check node processing that involves updating a plurality of edge messages with respect to a plurality of check nodes using a plurality of edge messages with respect to the plurality of bit nodes during decoding of an LDPC (Low Density Parity Check) coded signal.