HARD INPUT LOW DENSITY PARITY CHECK DECODER

• US 20110246862A1
• Filed: 03/31/2010
• Published: 10/06/2011
• Est. Priority Date: 03/31/2010
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Graef, Nils
• Granted Patent: US 9,544,090 B2
• Time in Patent Office: Days
• US Class Current: 714/785
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

A hard input low density parity check decoder is provided that shares logic between a bit-flipping decoder and a syndrome calculator. The hard-decision decoder decodes one or more error-correcting (EC) codewords and comprises a bit-flipping decoder that flips one or more bit nodes connected to one or more unsatisfied parity checks; and a syndrome calculator that performs a parity check to determine whether the bit-flipping decoder has converged on a valid codeword, wherein the bit-flipping decoder and the syndrome calculator share one or more logic elements. The decoder optionally includes means for updating a parity check equation of each flipped bit. Error-correcting (EC) codewords are decoded by flipping one or more bit nodes connected to one or more unsatisfied parity checks; and updating one or more parity check equations associated with the one or more bit nodes each time the one or more bit nodes are flipped. The parity check equations are updated whenever a bit is updated. The exemplary method terminates based on a predefined syndrome output.

Claims

1. A hard-decision decoder for decoding one or more error-correcting (EC) codewords, said decoder comprising:

a bit-flipping decoder that flips one or more bit nodes connected to one or more unsatisfied parity checks; and

a syndrome calculator that performs a parity check to determine whether said bit-flipping decoder has converged on a valid codeword, wherein said bit-flipping decoder and said syndrome calculator share one or more logic elements.

2. The decoder of claim 1, wherein said bit-flipping decoder is based on a variation of the Gallagher B algorithm.

3. The decoder of claim 1, wherein said bit-flipping decoder flips a bit if a substantial majority of parity check equations are unsatisfied.

4. The decoder of claim 1, wherein said bit-flipping decoder comprises one or more logic gates to perform said bit flipping.

5. The decoder of claim 4, wherein said one or more logic gates comprise one or more exclusive OR gates.

6. The decoder of claim 1, wherein said shared logic elements comprise one or more of cross connection circuit elements, exclusive OR gates and memory elements.

7. The decoder of claim 6, wherein said cross connection circuit elements comprise Barrel shifters.

8. The decoder of claim 1. further comprising means for updating a parity check equation of each flipped bit.

9. The decoder of claim 1, wherein an iterative operation of said decoder terminates based on a predefined output of said syndrome calculator.

10. A method for decoding one or more error-correcting (EC) codewords, said method comprising:

flipping one or more bit nodes connected to one or more unsatisfied parity checks; and

updating one or more parity check equations associated with said one or more bit nodes each time said one or more bit nodes are flipped.

11. The method of claim 10, wherein said updating step updates said one or more parity check equations whenever a bit is updated.

12. The method of claim 10, wherein said flipping step is based on a variation of the Gallagher B algorithm.

13. The method of claim 10, wherein said flipping step flips a bit if a substantial majority of parity check equations are unsatisfied.

14. The method of claim 10, wherein said method terminates based on a predefined syndrome output.

15. A method for decoding one or more error-correcting (EC) codewords, said method comprising:

flipping one or more bit nodes connected to one or more unsatisfied parity checks; and

performing a parity check to determine whether said bit-flipping decoder has converged on a valid codeword, wherein said flipping step and said performing step use one or more common logic elements.

16. The method of claim 15, wherein said flipping step is based on a Gallagher B algorithm.

17. The method of claim 15, wherein said flipping step flips a bit if a substantial majority of parity check equations are unsatisfied.

18. The method of claim 15, wherein said flipping step employs one or more logic gates to perform said bit flipping.

19. The method of claim 18, wherein said one or more logic gates comprise one or more exclusive OR gates.

20. The method of claim 15, wherein said common logic elements comprise one or more of cross connection circuit elements, exclusive OR gates and memory elements.

21. The method of claim 15, further comprising the step of updating a parity check equation of each flipped bit.

22. The method of claim 15, wherein said method terminates based on a predefined output of said syndrome calculator.