Parallel finite field vector operators

• US 8,347,192 B1
• Filed: 03/08/2010
• Issued: 01/01/2013
• Est. Priority Date: 03/08/2010
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Kerveros, James C
• Application Number:
  US12/719,770
• Time in Patent Office: 1,030 Days
• Field of Search: 714/781, 714/784
• US Class Current: 714/784
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/1595 Parallel or block-wise remainder calculation
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

Parallel Reed Solomon error correction can be performed using dot products in finite fields while factoring out multiplier reduction. A finite field accumulator with left and right shifts of the polynomial dot products is used to generate the final result using a fixed dot product core and a small number of post processing Galois Field multiplies. An efficient Reed Solomon decoder for transmission, storage, and processing operations can be implemented in a small area while being easily scalable.

Claims

1. A finite field vector calculation circuit, comprising:

an interface configured to receive a codeword associated with a data stream and split the codeword into a plurality of symbols;

a plurality of multiplication circuits configured to receive the plurality of symbols and generate a plurality of expanded polynomials;

an exclusive OR (XOR) circuit configured to combine the plurality of expanded polynomials to generate an XOR output and forward said XOR output to a reduction circuit, wherein the reduction circuit performs a modulo reduction of the XOR output to generate a plurality of separate products.

2. The finite field vector calculation circuit of claim 1, wherein the separate products are used to generate forward error correction codes.

3. The finite field vector calculation circuit of claim 1, wherein the separate products are used to implement a Reed Solomon decoder.

4. The finite field vector calculation circuit of claim 1, wherein the plurality of multiplication circuits receive the plurality of symbols in parallel.

5. The finite field vector calculation circuit of claim 4, wherein the plurality of symbols are input in sequential order and the time/frequency shift within the codeword is provided by finite field multiplication by powers of the field.

6. The finite field vector calculation circuit of claim 5, wherein a vector result is shifted by a multiplication of a field power greater than the largest field power in the vector calculation, before finite field addition to the next vector result.

7. The finite field vector calculation circuit of claim 1, wherein if the number of elements in the codeword is not an even multiple of the number of symbols input to the vector, the final vector accumulation is shifted by the modulo difference of a codeword size and a vector size.

8. The finite field vector calculation circuit of claim 7, wherein the final vector accumulation is shifted by a finite field division of a power equal to the modulo difference.

9. The finite field vector calculation circuit of claim 7, wherein the final vector accumulation is shifted by a multiplication of the inverse power of this modulo difference.

10. The finite field vector calculation circuit of claim 7, wherein the entire codeword is shifted by the modulo difference by inserting the modulo difference number of “

0”

element before the codeword.

11. The finite field vector calculation circuit of claim 1, wherein the codeword is fixed size.

12. The finite field vector calculation circuit of claim 1, wherein the codeword is variable size.

13. The finite field vector calculation circuit of claim 12, wherein possible shift values for the variable size codeword are maintained in a table.

14. A syndrome calculation circuit, comprising:

multiplication circuitry configured to combine a plurality of operands associated with a data stream to generate a plurality of expanded polynomials;

an exclusive OR (XOR) circuit configured to combine the plurality of expanded polynomials multiplier results to generate an XOR output and forward said XOR output to a reduction circuit, wherein the reduction circuit performs a modulo reduction of the XOR output to generate a plurality of separate products used for syndrome calculation.

15. The syndrome calculation circuit of claim 14, wherein the syndromes are provided for a Reed Solomon Forward Error Correction (FEC) decoder.

16. The syndrome calculation circuit of claim 14, wherein the apparatus is implemented on a programmable chip.

17. The syndrome calculation circuit of claim 15, wherein the reduction circuit is connected to the output of the XOR circuit.

18. The syndrome calculation circuit of claim 14, wherein multiplication circuitry comprises a plurality of partial product multipliers coupled to a single XOR circuit coupled to a single reduction circuit.