Galois field multiplication system and method

• US 20060080376A1
• Filed: 10/13/2004
• Published: 04/13/2006
• Est. Priority Date: 10/13/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Zhang, Ming, Nemat, Awais Bin, Bliss, David Edward
• Granted Patent: US 7,526,518 B2
• Time in Patent Office: Days
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A present invention Galois field multiplier system and method utilize lookup tables to generate one partial product term and one feedback term in one clock cycle. In one embodiment, a Galois field multiplier system includes a plurality of shift registers, a plurality of exclusive OR components, a partial product lookup table, and a feedback table lookup table. The plurality of shift registers perform shift multiplication operation and are coupled to the plurality of shift registers that perform addition operations. The partial product lookup table and feedback lookup tables are selectively coupled to the exclusive OR components and values from the partial product lookup table and feedback lookup tables are fed into the selectively coupled exclusive OR components. Coefficients of the partial product term and feedback term are utilized as indexes to the partial product lookup table and feedback lookup table respectively.

Claims

1. A Galois field multiplier system comprising:

a plurality of shift registers for performing shift multiplication operations;

a plurality of exclusive OR components coupled to said plurality of shift registers, said plurality of exclusive OR components for performing addition operations; and

a partial product lookup table selectively coupled to said exclusive OR components, wherein values from said partial product lookup table are fed into said selectively coupled exclusive OR components.

2. The Galois field multiplier system of claim 1 wherein coefficients of a partial product term are utilized as indexes to said partial product lookup table.

3. The Galois field multiplier system of claim 1 further comprising a feedback table lookup table selectively coupled to said exclusive OR components, wherein values from said feedback lookup table are fed into said selectively coupled exclusive OR components.

4. The Galois field multiplier system of claim 3 wherein coefficients of a feedback term are utilized as indexes to said feedback lookup table.

5. The Galois field multiplier system of claim 1 wherein Galois field multiplier system produces a codeword.

6. The Galois field multiplier system of claim 1 wherein Galois field multiplier system produces a syndrome.

7. The Galois field multiplier system of claim 1 wherein a value field of said partial product lookup table is the sum of partial products from non-zero index bits.

8. The Galois field multiplier system of claim 1 wherein a value field of said feedback lookup table is the sum of feedback terms from non-zero index bits.

9. The Galois field multiplier system of claim 1 wherein the index address of said feedback table is calculated by a look ahead method.

10. The Galois field multiplier method comprising:

utilizing a lookup table to provide resulting coefficient values of polynomial terms;

performing an exclusive OR operation on said resulting coefficient values; and

shifting results of said exclusive OR operation.

11. The Galois field multiplier method of claim 10 wherein said resulting coefficient values are resulting partial product coefficient values.

12. The Galois field multiplier method of claim 10 wherein said resulting coefficient values are resulting feedback coefficient values.

13. The Galois field multiplier method of claim 10 further comprising using multiple bits of a multiplier as an index to said lookup table to generate one partial product term.

14. The Galois field multiplier method of claim 10 further comprising using multiple bits of a feedback multiplier term as an index to said lookup table to generate one feedback term.

15. The Galois field multiplier method of claim 10 wherein an irreducible polynomial is fixed.

16. The Galois field multiplier method of claim 10 wherein an irreducible polynomial is programmable.

17. A Galois field multiplier system comprising:

a means for multiplying terms;

a means for adding terms; and

a means for supplying one partial product value from multiple bits of a partial product multiplier.

18. The Galois field multiplier system of claim 17 wherein said means for supplying one partial product value includes a means for looking up said partial product value.

19. The Galois field multiplier system of claim 17 further comprising a means for supplying one feedback value from multiple bits of a feedback multiplier.

20. The Galois field multiplier system of claim 19 wherein said means for supplying one feedback value includes a means for looking up said feedback value.

21. A computer usable medium having a computer readable program code embodied therein for causing a computer system to perform a finite field lookup table process comprising:

creating a finite field lookup table;

identifying a multiplier coefficient as an index to said finite field lookup table; and

utilizing an identified multiplier coefficient to return a value from said finite field lookup table.

22. The computer usable medium of claim 21 wherein said finite field lookup table is a partial product lookup table.

23. The computer usable medium of claim 21 wherein said finite field lookup table is a feedback lookup table.

24. The computer usable medium of claim 21 wherein said finite field lookup table maps finite field lookup table values with indexes associated with multiplier coefficients.

25. The computer usable medium of claim 21 further comprising:

parsing a Galois field multiplication expression; and

extracting coefficient values.