US 2006/0080377 A1Published application

Galois field multiplier and multiplication method thereof

OwnerHung-Ming Chieninventor

Life of this patent

Estimating the term…

Loading patent…

Abstract

A Galois field multiplier is provided. The Galois field multiplier comprises a lookup table device and an operation circuit. Wherein, the lookup table device obtains a coefficient matrix W by looking up a multiplicator coefficient table based on a multiplicator S. The operation circuit is coupled to the lookup table device for receiving a multiplicand A and the coefficient matrix W to calculate a product of multiplication R. The multiplicator S, the multiplicand A, and the product of multiplication R all belong to a Galois field (GF, 2m). In the present invention, a coefficient matrix W is provided to the operation circuit by looking up the multiplicator coefficient table based on the multiplicator S. Accordingly, the present invention can simplify the operation circuit and reduce the calculating time by looking up the lookup table. Moreover, a multiplication method applied in the Galois field is also provided.

Claims8

Dependent claims

A Galois field multiplier, comprising:

a lookup table device for obtaining a coefficient matrix W by looking up a multiplicator coefficient table based on a multiplicator S, wherein the multiplicator S belongs to a Galois field, S is represented as [sm-1 sm-2 . . . s0], and W is represented as:
[
w
m
-
1
,
m
-
1
w
m
-
1
,
m
-
2
⋯
w
m
-
1
,
0
w
m
-
2
,
m
-
1
w
m
-
2
,
m
-
2
⋯
w
m
-
2
,
0
⋮
⋮
⋮
⋮
w
0
,
m
-
1
w
0
,
m
-
2
⋯
w
0
,
0
]
;
⁢
and
an operation circuit coupled to the lookup table device for receiving a multiplicand A and the coefficient matrix W to obtain a product of multiplication R, and both the multiplicand A and the product of multiplication R belong to the Galois field, wherein A is represented as [am-1 am-2 . . . a0], R is represented as [rm-1 rm-2 . . . r0], and
r
m
-
1
=
w
m
-
1
,
m
-
1
⁢
a
m
-
1
+
w
m
-
1
,
m
-
2
⁢
a
m
-
2
+
…
+
w
m
-
1
,
0
⁢
a
0
r
m
-
2
=
w
m
-
2
,
m
-
1
⁢
a
m
-
1
+
w
m
-
2
,
m
-
2
⁢
a
m
-
2
+
…
+
w
m
-
2
,
0
⁢
a
0
⋮
r
0
=
w
0
,
m
-
1
⁢
a
m
-
1
+
w
0
,
m
-
2
⁢
a
m
-
2
+
…
+
w
0
,
0
⁢
a
0
wherein the sign + shown in the equation represents a logical XOR operation, and wiaj represents performing a logical AND operation on wi and aj.

197 more elements

A multiplication method applied in a Galois field, the multiplication method comprising:

inputting a multiplicand A and a multiplicator S, both the multiplicand A and the multiplicator S belonging to a Galois field, wherein A being represented as [am-1 am-2 . . . a0], and S being represented as [sm-1 sm-2 . . . s0];
using the multiplicator S to obtain a coefficient matrix W by looking up a multiplicator coefficient table, wherein W is represented as
[
w
m
-
1
,
m
-
1
w
m
-
1
,
m
-
2
⋯
w
m
-
1
,
0
w
m
-
2
,
m
-
1
w
m
-
2
,
m
-
2
⋯
w
m
-
2
,
0
⋮
⋮
⋮
⋮
w
0
,
m
-
1
w
0
,
m
-
2
⋯
w
0
,
0
]
;
⁢
and
obtaining a product of multiplication R of the coefficient matrix W by the multiplicand A, and the product of multiplication R belonging to the Galois field, wherein R is represented as [rm-1 rm-2 . . . r0], and
r
m
-
1
=
w
m
-
1
,
m
-
1
⁢
a
m
-
1
+
w
m
-
1
,
m
-
2
⁢
a
m
-
2
+
…
+
w
m
-
1
,
0
⁢
a
0
r
m
-
2
=
w
m
-
2
,
m
-
1
⁢
x
m
-
1
+
w
m
-
2
,
m
-
2
⁢
x
m
-
2
+
…
+
w
m
-
2
,
0
⁢
x
0
⋮
r
0
=
w
0
,
m
-
1
⁢
a
m
-
1
+
w
0
,
m
-
2
⁢
a
m
-
2
+
…
+
w
0
,
0
⁢
a
0
wherein the sign + shown in the equation represents a logical XOR operation, and wiaj represents performing a logical AND operation on wi and aj.

198 more elements

Dependencies are inferred from the claim text.