High speed syndrome-based FEC encoder and decoder and system using same

• US 6,990,624 B2
• Filed: 10/12/2001
• Issued: 01/24/2006
• Est. Priority Date: 10/12/2001
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Song, Leilei, Yu, Meng-Lin Mark, Schuering, Timo Frithjof, Dohmen, Ralf
• Primary Examiner(s): Torres, Joseph D.
• Application Number:
  US09/976,729
• Publication Number:
  US 20030106014A1
• Time in Patent Office: 1,565 Days
• Field of Search: 714/785, 714/784, 714/782, 714/781, 714/776, 714/757
• US Class Current: 714/785
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/1595 Parallel or block-wise remainder calculation

Abstract

A decoder, encoder and corresponding system are disclosed for providing fast Forward Error Correcting (FEC) decoding and encoding of syndrome-based error correcting codes. Three-parallel processing is performed by elements of the system. More particularly, in an illustrative embodiment, a decoder performs three-parallel syndrome generation and error determination and calculations, and an encoder performs three-parallel encoding. Low power and complexity techniques are used to save cost and power yet provide relatively high speed encoding and decoding.

Claims

1. A decoder comprising:

a plurality of N-parallel syndrome generators, each of the N-parallel syndrome generators coupled to a parallel data stream and being adapted to perform a calculation each cycle with N symbols from the parallel data stream, each N-parallel syndrome generator adapted to determine, after a predetermined number of cycles, a plurality of syndromes;

a plurality of key equation determination devices, each key equation determination device coupled to at least one of the N-parallel syndrome generators and being adapted to determine at least one error polynomial by using a corresponding plurality of syndromes from the at least one N-parallel syndrome generator; and

a plurality of N-parallel error determination and correcting devices, one for each of the N-parallel syndrome generators, each N-parallel error correction and determination device coupled to one of the key equation determination devices and being adapted to use the at least one error polynomial produced by the one key equation determination device to correct errors in the parallel data stream.

2. The decoder of claim 1, wherein N is three.

3. The decoder of claim 1, further comprising a device adapted to convert a serial input data stream into the parallel data stream.

4. The decoder of claim 3, wherein:

the device creates a parallel data stream having a width of 48 symbols, wherein the device outputs 48 symbols every clock cycle;

N is three;

there are 16 three-parallel syndrome generators, four key equation determination devices, and 16 three-parallel error determination and detection devices, wherein each four of the three-parallel syndrome generators and three-parallel error determination and detection devices share one of the four key equation determination devices; and

the decoder outputs a second parallel data stream having a width of 48 symbols, wherein the decoder outputs 48 symbols per clock cycle.

5. The decoder of claim 1, wherein each symbol is a symbol from one of a plurality codewords from a frame, and wherein the decoder further comprises a device adapted to determine if a codeword is uncorrectable and adapted to output a number of uncorrectable codewords in the frame.

6. The decoder of claim 1, wherein each symbol is a symbol from one of a plurality codewords in a frame, and wherein the decoder further comprises a device adapted to output a number of corrected bit errors per frame.

7. The decoder of claim 6, wherein the decoder further comprises a device adapted to disable error correction of the decoder when the number of corrected bit errors for each of a predetermined number of frames is less than a first predetermined value and adapted to disable the decoder when a deployed forward error correcting code cannot be processed by the decoder.

8. The decoder of claim 1, wherein:

each symbol is a symbol from one of a plurality of codewords;

the decoder further comprises a device adapted to output a second parallel data stream comprising corrected symbols; and

the decoder further comprises a device adapted to output a parallel stream of correction values, each bit in the parallel stream of correction values indicating a position in the second parallel data stream at which an error occurs.

9. The decoder of claim 8, further comprising a peripheral, the peripheral performing error analyses using the parallel stream of correction values.

10. The decoder of claim 1, wherein each key equation determination device further comprises a plurality of multiplication circuits, each of the plurality of multiplication circuits comprising a Mastrovito standard-basis multiplier.

11. The decoder of claim 10, wherein each Mastrovito standard-basis multiplier has a computation delay of (one DAND+five DXOR), where DAND denotes a delay of one AND gate and DXOR denotes a delay of one XOR gate.

12. The decoder of claim 10, wherein each N-parallel error determination and correcting device further comprises a division circuit, each division circuit comprising a composite-basis divider.

13. The decoder of claim 12, wherein each composite basis divider has a computation delay of (three DAND+nine DXOR), where DAND denotes a delay of one AND gate and DXOR denotes a delay of one XOR gate.

14. The decoder of claim 13, wherein each composite basis divider further comprises an inverter having a delay of (one DAND+three DXOR).

15. The decoder of claim 1, wherein:

the parallel data stream comprises a plurality of codewords; and

the decoder is adapted to route N symbols of a given codeword to a given N-parallel syndrome generator.

16. A method comprising the steps of:

converting a serial input data stream into a parallel data stream;

performing a plurality of N-parallel syndrome generations using the parallel data stream, each of the N-parallel syndrome generations determining, after a predetermined number of cycles, a plurality of syndromes;

performing, in parallel and by using each of the plurality of syndromes generated by each of the plurality of N-parallel syndrome generations, a plurality of N-parallel decodings of the parallel data stream to determine, in parallel, a plurality of error value and error locator polynomials;

correcting errors, by using a plurality of N-parallel correction and determination processes that use the error value and error locator polynomials, in the parallel data stream; and

outputting a second parallel data stream comprising a corrected version of the parallel data stream.