Multi-dimensional galois field multiplier

Details Multi-dimensional galois field multiplier Multi-dimensional galois field multiplier

2000-02-18

2004-07-06

Chaki, Kakali (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06760742

ABSTRACT:

FIELD OF THE INVENTION
This invention relates in general to Galois Field arithmetic and more specifically to a single implementation of a multi-dimensional Galois Field multiplier.
BACKGROUND OF THE INVENTION
Galois Field arithmetic finds application in error correcting codes, particularly Reed Solomon Codes and cryptographic codes.
Galois Field arithmetic is a cyclic finite field arithmetic such that any operation performed on any two numbers within the field, yields a number in the field, i.e. there is no operation which can be done on any two numbers within the field which yields a number outside of the field. Finite field arithmetic uses real numbers that consist of the range of numbers shown in Table 1 below. For example, the range of integers from 0 to 7 (0,1,2,3,4,5,6,7) has a Galois Field representation or notation of GF(8) because the Galois Field has 8 elements, while the range of integers 0 to 1 has a Galois Field of GF(2) because it has only two elements, etc. In addition, digital systems transmit data in bits. Because bits are binary, they can only take on one of two values, either a 0 or a 1. Grouping these bits together to build a symbol is common in digital systems. These groupings are all based on a power of two. Table 1 lists the digital symbols vs. GF notation.
TABLE 1
Digital symbols vs. GF notation
Number of bits per symbol
Range of integers
GF notation
1
0 to 1
GF(2)
2
0 to 3
GF(4)
3
0 to 7
GF(8)
4
0 to 15
GF(16)
5
0 to 31
GF(32)
6
0 to 63
GF(64)
7
0 to 127
GF(128)
8
0 to 255
GF(256)
There are several ways of representing the numbers in the finite field of any given Galois Field. For example, the data shown on Table 2 illustrates the integer, binary and polynomial representations of the numbers of GF(8).
TABLE 2
Representations of Galois Field GF(8)
Integer
Binary
Polynomial
0
000
0
1
001
1
2
010
x
3
011
x + 1
4
100
x
2
5
101
x
2
+ 1
6
110
x
2
+ x
7
111
x
2
+ x + 1
In addition, each Galois Field has one or more primitive polynomials, or generator polynomials, which is analogous to a particular set of consecutive real integers which also has one or more prime numbers, depending upon how large is the particular set of consecutive integers. Primitive polynomials, p(x), g(x) are polynomials which are used to define the arithmetic functions for each field. For example, in Galois Field arithmetic, like arithmetic, certain mathematical properties exist such as laws of commutativity, associativity, etc. Therefore, when determining what is the sum or product of any two elements within a Galois Field, if after applying such laws, the sum or product will lie outside the Galois Field, that sum or product is divided by a predetermined primitive polynomial. In this way, the Galois Field is preserved. Table 3 lists the integer representation of all the primitive polynomials for GF(8) to GF(256).
TABLE 3
Primitive Polynomials for Various Galois Fields
GF(x)
P(x)
GF(x)
P(x)
GF(x)
P(x)
8
11
128
137
256
285
16
19
128
143
256
361
32
37
128
157
256
487
32
61
128
247
256
299
32
55
128
191
256
357
64
67
128
213
256
355
64
103
128
131
256
351
64
109
128
203
256
451
128
229
As can be seen from the above table, there is only one primitive polynomial for GF(8) and GF(16), due to the smallness of the field, however, GF(128) has 9 primitive polynomials and GF(256) has 8 primitive polynomials. As mentioned previously, each of these integer representations has a corresponding polynomial representation. For example, one primitive polynomial, p(x) for GF(256) is 285, which corresponds to p(x)=x
8
+x
4
+x
3
+X
2
+1.
Multiplication in finite fields is easily computed using the polynomial format. For the following examples, GF(8) and p(x)=x
3
+x+1 are used to build the multiplication Tables 4 and 5. The primitive polynomial is used to reduce or ‘fold’ the product or on results back into the field. For example:
x
2
*x
2
=x
4
where x
4
is not a member of the GF(8) field. The primitive polynomial, p(x), is then used in a polynomial division to generate the remainder of:
x
4
/p
(
x
)=
x
4
/x
3
+x
+1
=x
2
+x
The same primitive polynomial is used to generate the entire multiplication table per GF, even if more than one primitive polynomial exists for a particular GF.
TABLE 4
GF(8), p(x) = x
3
+ x + 1, Multiplication Example Part 1.
X
0
1
X
x + 1
x
2
x
2
+ 1
x
2
+ x
x
2
+ x + 1
0
0
0
0
0
0
0
0
0
1
0
1
X
x + 1
x
2
x
2
+ 1
x
2
+ x
x
2
+ x + 1
x
0
x
x
2
x
2
+ x
x + 1
1
x
2
+ x + 1
x
2
+ 1
x + 1
0
x + 1
x
2
+ x
x
2
+ 1
x
2
+ x + 1
x
2
1
x
x
2
0
x
2
x + 1
x
2
+ x + 1
x
2
+ x
x
x
2
+ 1
1
x
2
+ 1
0
x
2
+ 1
1
x
2
X
x
2
+ x + 1
x + 1
x
2
+ x
x
2
+ x
0
x
2
+ x
x
2
+ x + 1
1
x
2
+ 1
x + 1
x
x
2
x
2
+ x + 1
0
x
2
+ x + 1
x
2
+ 1
x
1
x
2
+ x
x
2
x + 1
Another way of representing Table 4 is in binary as shown in Table 5, below:
TABLE 5
GF(8), p(x) = 1011, Multiplication Example Part 2.
* 
000
001
010
011
100
101
110
111
000
000
000
000
000
000
000
000
000
001
000
001
010
011
100
101
110
111
010
000
010
100
110
011
001
111
101
011
000
011
110
101
111
100
001
010
100
000
100
011
111
110
101
101
001
101
000
101
001
100
010
111
011
110
110
000
110
111
001
101
011
010
100
111
000
111
101
010
001
110
100
011
Notice how each entry occurs once in each row or column. This set of numbers forms a field. The field has an identity of 001 and each entry in the field has an inverse (except zero) such that (a*inv a)=001. Because every element has in inverse, this group is called a field. The tables below illustrate the inverse in binary of GF(8), and then addition and subtraction tables for GF(8).
TABLE 6
Inverse of GF(8)
a
Inv(a)
000
NULL
001
001
010
101
011
110
100
111
101
010
110
011
111
100
Similarly under addition, GF(8) using the same primitive polynomial 1011 is:
TABLE 7
GF(8), p(x) = 1011, addition
+ 
000
001
010
011
100
101
110
111
000
000
001
010
011
100
101
110
111
001
001
000
011
010
101
100
111
110
010
010
011
000
001
110
111
100
101
011
011
010
001
000
111
110
101
100
100
100
101
110
111
000
001
010
011
101
101
100
111
110
001
000
011
010
110
110
111
100
101
010
011
000
001
111
111
110
101
100
011
010
001
000
TABLE 8
GF(8), p(x) = 1011, subtraction
− 
000
001
010
011
100
101
110
111
000
000
001
010
011
100
101
110
111
001
001
000
011
010
101
100
111
110
010
010
011
000
001
110
111
100
101
011
011
010
001
000
111
110
101
100
100
100
101
110
111
000
001
010
011
101
101
100
111
110
001
000
011
010
110
110
111
100
101
010
011
000
001
111
111
110
101
100
011
010
001
000
For addition and subtraction in GF(8), inspection determines that the elements of both Galois fields are identical and the operation is actually an Exclusive OR or XOR logic function. Again there is an identity element of 000 and each element has an inverse under addition/subtraction. As is illustrated in Table 9 below, all elements self-inverse under addition and subtraction.
TABLE 9
Inversion over + and − in GF(8)
A
Inv(a)
000
000
001
001
010
010
011
011
100
100
101
101
110
110
111
111
As is illustrated in the previous binary GF(8) example, implementation of the add and subtract is trivial in a general purpose microprocessor, but the multiplication operator is a non-standard element in both general purpose processors and digital signal processors alike. The algorithm to perform multiplication in Galois field arithmetic is now described. Step 1: Perform polynomial (carryless) multiply of the two elements. Field size N elements produce a 2N−1 degree polynomial (which doesn't fit in the field of N size elements), so, must perform Step 2: the result of the multiply is divided by the primitive polynomial and the remainder is the final answer. Step 2 has the following sub-parts: 1) Use the Most Significant Bi

Affiliated with

Also associated with

Rating

Multi-dimensional galois field multiplier does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-dimensional galois field multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-dimensional galois field multiplier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3198117