Method and system of improved galois multiplication

• US 9,672,009 B2
• Filed: 01/11/2016
• Issued: 06/06/2017
• 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.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US14/992,918
• Publication Number:
  US 20160124717A1
• Time in Patent Office: 512 Days
• Field of Search: 708517
• 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. A method of performing Galois multiplication comprising:

converting a first and a second multiplicand of the Galois multiplication to exponential forms-using a Galois conversion data structure;

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 conversion data structure to decimal equivalent binary result of the Galois multiplication.

2. The method of claim 1, further comprising:

converting the decimal equivalent binary form into binary.

3. The method of claim 1, further comprising:

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

4. The method of claim 1, wherein the Galois conversion data structure 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 method of claim 1, wherein the method is a part of a Reed-Solomon decoding routine.

6. The method of claim 1, wherein the Galois conversion data structure 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.

7. The method of claim 6 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.

8. The method of claim 6 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.

9. The method of claim 6, wherein the Galois field is GF256.

10. The method of claim 1, wherein the Galois conversion data structure is stored in memory.

11. A non-transitory computer readable medium storing instructions which when executed by processor cause the processor to perform a method, the method comprising:

converting a first and a second multiplicand of the Galois multiplication to exponential forms-using a Galois conversion data structure;

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 conversion data structure to decimal equivalent binary result of the Galois multiplication.