Multi-dimensional Galois field multiplier

Details Multi-dimensional Galois field multiplier Multi-dimensional Galois field multiplier

1998-03-20

2002-04-02

Ngo, Chuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06366941

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 is a cyclic finite field arithmetic such that any operation performed on any two numbers within the filed, 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 shows 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 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), 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 in Tables 4 and 5. The primitive polynomial is used to reduce or ‘fold’ the product or summation 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
x
2
+ 1
0
x
2
+ 1
1
x
2
x
x
2
+ x + 1
x
2
+ 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
Galois Field (GF) multiplication is an important and necessary function, i.e. performed many times, in Reed-Solomon (RS) codes. RS codes are used in many communication applications such as satellites, modems, audio compact disks, and set-top boxes as a digital data transmission forward error correction tool. Each one of these applications has a different standard. Each standard defines a symbol size, a GF, and a primitive polynomial. Each application requires a unique GF multiplier or a GF multiplier which has a unique configuration to be created which will at least depend on the symbol size, the size of the Galois Field and the primitive polynomial used. There has never been a GF multiplier which could implement all the different standards in a cost efficient manner.
SUMMARY OF THE INVENTION
An implementation of a multi-dimensional Galois Field multiplier for Galois Fields from a GF(8) up to a GF(256) is disclosed. This GF multiplier is able to support many different communication standards such as standards with different symbol sizes, different GFs, and different primitive polynomials. The key to allow a single implementation of a GF multiplier to perform for all different GF sizes is to shift input operand B and primitive polynomial PP signals to the left and to shift the output ZO to the right, depending upon the size of the GF, as will be further described in the following paragraphs and shown in
FIGS. 1
,
3
and
6
. The shifting of signals allows the MULT_XOR arrays to operate on all fields with the exact same hardware with a minimum delay of just two XOR gates per block. In other words, the critical path of each MULT_XOR block is just 2 XOR gates. The solution presented is a cost efficient multiplier configuration.


REFERENCES:
patent: 4847801 (1989-07-01), Tong
patent: 5046037 (1991-09-01), Cognault et al.
patent: 5502665 (1996-03-01), Im
patent: 5768168 (1998-06-01), Im

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-2862285