METHOD AND SYSTEM OF IMPROVED GALOIS MULTIPLICATION

• US 20140280408A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Echelon Corporation (Renesas Electronics Corporation)
• Original Assignee: Echelon Corporation (Renesas Electronics Corporation)
• Inventors: Downey, Walter J.
• Granted Patent: US 9,235,554 B2
• Time in Patent Office: Days
• US Class Current: 708/204
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2207/72 Indexing scheme relating to groups G06F7/72 - G06F7/729
• 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

Abstract

Embodiments of the invention include an apparatus for performing Galois multiplication using an enhanced Galois table. Galois multiplication may include converting a first and second multiplicand to exponential forms using a Galois table, adding the exponential forms of the first and second multiplicands, and converting the added exponential forms of the first and second multiplicands to a decimal equivalent binary form using the Galois table to decimal equivalent binary result of the Galois multiplication.

Claims

1. An apparatus comprising:

a processor; and

a memory to store a Galois multiplication routine which when executed by the processor causes the processor to perform actions comprising;

converting a first and second multiplicand to exponential forms using a Galois table;

adding the exponential forms of the first and second multiplicands;

converting the added exponential forms of the first and second multiplicands to a decimal equivalent binary form using the Galois table to decimal equivalent binary result of the Galois multiplication.

2. The apparatus of claim 1, wherein the routine further comprises:

converting the decimal equivalent binary form into binary.

3. The apparatus of claim 1, wherein the Galois table is Table II.

4. The apparatus of claim 1, wherein the Galois table comprises:

a first part with columns for an index, exponential, binary conversion, and exponential conversion;

a second part with columns for an index, exponential, and binary conversion; and

a third part with columns for an index, exponential, and binary conversion, wherein each binary conversion has a value of 0.

5. The apparatus of claim 1, wherein the Galois table comprises:

a first part with all the Galois field elements except zero listed in order of exponents, with a first column of binary numbers for each field element wherein there is a consistent mapping of polynomial coefficients of the field element polynomial'"'"'s powers to bit positions, and a second column of reverse look-up values wherein the offset for the value is taken from first column and the value is the offset from which the value is taken; and

a second part with a first column that is a repeat of the first column of the first part and at an offset directly after the end of the first part.

6. The apparatus of claim 5 further comprising:

a third part of the table with zeros of length equal to two times the number of Galois elements minus 2 wherein the offset of the start of the table is listed as the value in the first row of the second column of the first part of the table.

7. The apparatus of claim 5 further comprising:

a third part of the table with zeros of length equal the number of Galois elements minus 1 wherein the offset of the start of the table is listed as the value in the first row of the second column of the first part of the table and containing a last zero which is at offset 2 times the value in the first row of the second column of the first part of the table.

8. The apparatus of claim 5 wherein the Galois field is GF256.

9. The apparatus of claim 1, wherein the routine is a part of a Reed-Solomon decoding routine.

10. The apparatus of claim 1, wherein the apparatus is a modem.

11. A method of performing Galois multiplication comprising:

converting a first and second multiplicand to exponential forms using a Galois table;

adding the exponential forms of the first and second multiplicands;

converting the added exponential forms of the first and second multiplicands to a decimal equivalent binary form using the Galois table to decimal equivalent binary result of the Galois multiplication.

12. The method of claim 11, further comprising:

converting the decimal equivalent binary form into binary.

13. The method of claim 11, further comprising:

converting the first and second multiplicands to a decimal value from binary.

14. The method of claim 11, wherein the Galois table is Table 3.

15. The method of claim 11, wherein the Galois table comprises:

a first part with columns for an index, exponential, binary conversion, and exponential conversion;

a second part with columns for an index, exponential, and binary conversion; and

a third part with columns for an index, exponential, and binary conversion,

wherein each binary conversion has a value of 0.

16. The method of claim 11, wherein the method is a part of a Reed-Solomon decoding routine.

17. The method of claim 11, wherein the Galois table comprises:

a first part with all the Galois field elements except zero listed in order of exponents, with a first column of binary numbers for each field element wherein there is a consistent mapping of polynomial coefficients of the field element polynomial'"'"'s powers to bit positions, and a second column of reverse look-up values wherein the offset for the value is taken from first column and the value is the offset from which the value is taken; and

a second part with a first column that is a repeat of the first column of the first part and at an offset directly after the end of the first part.

18. The method of claim 17 further comprising:

a third part of the table with zeros of length equal to two times the number of Galois elements minus 2 where the offset of the start of the table is listed as the value in the first row of the second column of the first part of the table.

19. The method of claim 17 further comprising:

a third part of the table with zeros of length equal the number of Galois elements minus 1 where the offset of the start of the table is listed as the value in the first row of the second column of the first part of the table and containing a last zero which is at offset 2 times the value in the first row of the second column of the first part of the table.

20. The method of claim 17, wherein the Galois field is GF256