Means and method for performing multiplication

Details Means and method for performing multiplication Means and method for performing multiplication

2000-01-14

2003-10-21

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06636882

ABSTRACT:

FIELD OF THE INVENTION
The invention relates in general to a multiplier for obtaining the multiplication product of elements in a Galois Field, and more particularly to a multiplier which effectively yields the product of Galois Field elements by using a combination circuit implementation.
DESCRIPTION OF THE RELATED ART
Conventionally, binary scales are utilized to store and read data in a computer. An 8-bit byte is taken as an example. The byte “00000000” represents the value 0, the byte “00000001” represents the value 1, and similarly, the byte “11111111” represents the value 255. Herein, the symbol F{2{circumflex over ( )}8} is used to represent the 8-bit binary field. In the field F{2{circumflex over ( )}8}, every element represents a byte which corresponds to a value in [0,255] respectively. Moreover, the 8-bit Galois Field is denoted by GF{2{circumflex over ( )}8}. Every byte in the field GF{2{circumflex over ( )}8} can be represented by a value in {0, &agr;, &agr;{circumflex over ( )}2, . . . , &agr;{circumflex over ( )}255}, respectively, wherein &agr; is “00000010”.
The multiplication operation, denoted by “*”, of any byte A (a
7
,a
6
,a
5
,a
4
,a
3
,a
2
,a
1
, a
0
) in GF{2{circumflex over ( )}8} and &agr; conventionally follows two steps. First, every bit b
i
(i=0~7) of the byte A should be first left-shifted for one bit. Then, according to the Equation (1), the product of A* &agr; can be obtained.
A*&agr;=(a
6
,a
5
,a
4
,a
3
,a
2
,a
1
,a
0
,0)⊕(0,0,0,a
7
,a
7
,a
7
,0,a
7
)  (1)
While any byte A (a
7
, a
6
, a
5
, a
4
, a
3
, a
2
, a
1
, a
0
) in GF{2{circumflex over ( )}8} is to be multiplied by &agr;, the multiplication, denoted by “*”, is performed as follows : every bit b
i
(i=0~7) in the byte A should be first left-shifted for one bit, and then according to the Equation (1), the value of A* &agr; can be obtained.
The operator “
⊕
” in the Equation (1) is an Exclusive OR (XOR) logic operation.
TABLE 1
A
A*&agr;
00000001
00000010(=&agr;)
00000010(=&agr;)
00000100(=&agr;{circumflex over ( )}2)
  .
  .
  .
  .
  .
  .
10000000(=&agr;{circumflex over ( )}7)
00011101(=&agr;{circumflex over ( )}8)
00011101(=&agr;{circumflex over ( )}8)
00111010(=&agr;{circumflex over ( )}9)
  .
  .
  .
  .
  .
  .
11001101(=&agr;{circumflex over ( )}12)
10000111(=&agr;{circumflex over ( )}13)
  .
  .
  .
  .
  .
  .
10000110(=&agr;{circumflex over ( )}254)
00000001(=&agr;{circumflex over ( )}255)
The result of the above-mentioned multiplication as shown in Table 1 can be obtained, basing on the equation &agr;{circumflex over ( )}8=&agr;{circumflex over ( )}4⊕&agr;{circumflex over ( )}3⊕&agr;{circumflex over ( )}2⊕&agr;{circumflex over ( )}0. Consequently, it is to be understood that &agr;{circumflex over ( )}2 is “00000100”, . . . , &agr;{circumflex over ( )}7 is “10000000”, and &agr;{circumflex over ( )}8 is “00001101”.
When the most significant bit (MSB), b
7
, of the byte A is “1”, according to the Equation (1), the value of A*&agr; is the result of (a
6
,a
5
,a
4
,a
3
,a
2
,a
1
,a
0
,0) ⊕ (0,0,0,0,1,1,0,1). Thus, &agr;{circumflex over ( )}9 is “00111010”, . . . , &agr;{circumflex over ( )}12 is “11001101”, &agr;{circumflex over ( )}13 is “10000111”, . . . , and accordingly, &agr;{circumflex over ( )}255 is “00000001”. The operation including the steps of left-shifting every bit by one bit and utilizing the XOR logic operation is called a “shift operation.”
It is demonstrated that each of the 256 values 0, &agr;, &agr;{circumflex over ( )}2, . . . , &agr;{circumflex over ( )}255, corresponds to each byte in [0,255], respectively.
Conventionally, the multiplication product of the two elements A, B in GF{2{circumflex over ( )}8} is obtained by first expressing the multiplier B(B≠0) in the form of &agr;{circumflex over ( )}n (n=1≠255). Time for finding the value n is assumed to be T. To obtain the product of A*B, the multiplicand A should be multiplied by &agr; n times, and each time, the shift operation mentioned above has to be performed once. Therefore, to multiply A by &agr; n times needs the shift operation to be applied n times. This shift operation takes about one period T. While the value of n is large, such as 250, the shift operation has to be performed 250 times, which takes at long as 250*T. Therefore, the time-consumption is high.
SUMMARY OF THE INVENTION
It is therefore a primary object of the invention to provide a multiplier for obtaining the product of elements in a Galois Field. By applying the features of elements in the Galois Field, and a combination circuit implementation in computer hardware, the product of the multiplication can be quickly obtained.
In order to accomplish the object of the invention, a multiplier for obtaining the product of elements in a Galois Field is proposed. The multiplier performs the multiplication of two n-bit elements A(a
n-1
, a
n-2
, . . . . , a
3
, a
2
, a
1
, a
0
) and B(b
n-1
, b
n-2
, . . . , b
3
, b
2
, b
1
, b
0
) in the Galois Field. Therefore, the product C=A*B=(c
n-1
,c
n-2
, . . . , c
3
, c
2
, c
1
, c
0
) is obtained, wherein n≧1 and a
i
(i=0~n-1), b
j
(j=0~n-1), and c
k
(k=0~n−1) are all binary bits. The multiplier includes an AND planer, that is, a circuit for performing an AND logic operation of every bit a
i
(i=0~n−1) in A(a
n-1
, a
n-2
, . . . , a
3
, a
2
, a
1
, a
0
) and every bit b
j
(j=0~n-1) in B(b
n-1
, b
n-2
, . . . , b
3
, b
2
, b
1
, b
0
) to obtain (a
n-1
b
n-1
, a
n-1
b
n-2
, . . . , a
n-1
b
0
, a
n-2
b
n-1
, a
n-2
b
n-2
, . . . . , a
n-2
b
0
, a
0
b
n-1
, a
0
b
n-2
, . . . , a
0
b
0
). The multiplier further includes an XOR planer, that is, a circuit for performing an XOR logic operation of (a
n-1
b
n-1
, a
n-1
b
n-2
, . . . , a
n-1
b
0
, a
n-2
b
n-1
, a
n-2
b
n-2
, . . . , a
n-2
b
0
, a
0
b
n-1
, a
0
b
n-2
, . . . , a
0
b
0
) to obtain (c
n-1
, c
n-2
, . . . , c
3
, c
2
, c
1
, c
0
).
As n=8,
c
0
=b
0
a
0
⊕b
1
a
7
⊕b
2
a
6
⊕b
3
a
5
⊕b
4
a
4
⊕b
5
a
3
⊕b
6
a
2
⊕b
7
a
1
⊕b
5
a
7
⊕b
6
a
6
⊕b
7
a
5
⊕b
6
a
7
⊕b
7
a
6
⊕b
7
a
7
;
c
1
=b
0
a
1
⊕b
1
a
0
⊕b
2
a
7
⊕b
3
a
6
⊕b
4
a
5
⊕b
5
a
4
⊕b
6
a
3
⊕b
7
a
2
⊕b
6
a
7
⊕b
7
a
6
⊕b
7
a
7
;
c
2
=b
0
a
2
⊕b
1
a
1
⊕b
2
a
0
⊕b
1
a
7
⊕b
2
a
6
⊕b
3
a
5
⊕b
4
a
4
⊕b
5
a
3
⊕b
6
a
2
⊕b
7
a
1
⊕b
3
a
7
⊕b
4
a
6
⊕b
5
a
5
⊕b
6
a
4
⊕b
7
a
3
⊕b
5
a
7
⊕b
6
a
6
⊕b
7
a
5
⊕b
6
a
7
⊕b
7
a
6
;
c
3
=b
0
a
3
⊕b
1
a
2
⊕b
2
a
1
⊕b
3
a
0
⊕b
1
a
7
⊕b
2
a
6
⊕b
3
a
5
⊕b
4
a
4
⊕b
5
a
3
⊕b
6
a
2
⊕b
7
a
1
⊕b
2
a
7
⊕b
3
a
6
⊕b
4
a
5
⊕b
5
a
4
⊕b
6
a
3
⊕b
7
a
2
⊕b
4
a
7
⊕b
5
a
6
⊕b
6
a
5
⊕b
7
a
4
⊕b
5
a
7
⊕b
6
a
6
⊕b
7
a
5
;
c
4
=b
0
a
4
⊕b
1
a
3
⊕b
2
a
2
⊕b
3
a
1
⊕b
4
a
0
⊕b
1
a
7
⊕b
2
a
6
⊕b
3
a
5
⊕b
4
a
4
⊕b
5
a
3
⊕b
6
a
2
⊕b
7
a
1
⊕b
2
a
7
⊕b
3
a
6
⊕b
4
a
5
⊕b
5
a
4
⊕b
6
a
3
⊕b
7
a
2
⊕b
3
a
7
⊕b
4
a
6
⊕b
5
a
5
⊕b
6
a
4
⊕b
7
a
3
⊕b
7
a
7
;
c
5
=b
0
a
5
⊕b
1
a
4
⊕b
2
a
3
⊕b
3
a
2
⊕b
4
a
1
⊕b
5
a
0
⊕b
2
a
7
⊕b
3
a
6
⊕b
4
a
5
⊕b
5
a
4
⊕b
6
a
3
⊕b
7
a
2
⊕b
3
a
7
⊕b
4
a
7
⊕b
5
a
6
⊕b
6
a

Affiliated with

Also associated with

Rating

Means and method for performing multiplication does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Means and method for performing multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Means and method for performing multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3118196