Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-06-23
2004-02-03
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06687725
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an arithmetic circuit for performing all arithmetic operations in a finite field GF(2
m
).
2. Description of the Related Art
In recent years, finite fields have attracted much attention in computer and communication applications. For instance, forward error-correction codes have been widely used in digital communications. However, to design an error-correction circuit with both a high operation speed and a low circuit complexity, it is a necessity to have a multi-function arithmetic circuit. Therefore, there is a trend, when designing the multi-function arithmetic circuit, to reduce its complexity, shorten its calculating delay and increase its operation speed. As any skilled person knows, addition, multiplication, division, exponentiation and inverse multiplication are the most basic arithmetic operations in a finite field. To perform these arithmetic operations, several kinds of circuits have been proposed on different bases, such as dual basis, normal basis and standard basis. Usually, arithmetic operations on dual basis and normal basis need extra transformations, while arithmetic operations on standard basis need no more transformations. Consequently, the arithmetic circuit of the present invention applies the standard basis although some arithmetic operations are best implemented on dual basis or normal basis.
In a finite field GF(2
m
), an adder on standard basis is easily implemented by m XOR gates, and a parallel-in-parallel-out multiplier on standard basis is first implemented by B. A. Laws, Jr and C. K. Rushforth, see “A cellular-array multiplier for finite fields GF(2
m
)” in IEEE trans. Corput., vol.C-20, pp. 1573-1578, 1971. Further, to increase the operation speed of the cellular-array multiplier, another systolic-array product-sum multiplier is also disclosed by C. S. Yeh, Irving S. Reed and T. K. Truong, see “Systolic multipliers for finite fields GF(2
m
)” in IEEE trans. Comput., vol. C-33, pp.357-360, 1984. Comparing the operation speeds of these two multipliers, a multiplication needs 2
m
gate delays in the cellular-array multiplier and one celltime delays (about two gate delays) in the systolic-array product-sum multiplier. However, the circuit complexity of the systolic-array product-sum multiplier is far more complicated than that of the cellular-array multiplier. Also, the first input of the systolic-array product-sum multiplier has a latency (about 3 m celltime delays) before the first output is obtained, it is also improper to apply the systolic-array product-sum multiplier in a pipeline-structured circuit.
Theoretically, division in a finite field GF(2
m
) is implemented by a multiplication and an inverse multiplication, i.e., A/B=A*B
−1
, where A and B are elements in the finite field GF(2
m
). Inverse multiplication can be implemented by using a ROM table, applying Euclid's rule or combining a series of multiplications. Nowadays, inverse multiplication is mostly implemented on normal basis because square can be implemented by a simple cyclic shifting. Similarly, exponentiation can be also implemented by using a ROM table or combining a series of multiplication. Following is a list of references:
[1] B. A. Laws, m Jr., and C. K. Rushforth, “A cellular-array multipliers for finite fields GF(2
m
),”
IEEE Trans. Comput
., vol. C-20, pp. 1573-1578, 1971.
[2] C. -S. Yeh, Irving S. Reeds and T. K. Truong, “Systolic multipliers for finite fields GF(2
m
),”
IEEE Trans. Comput
., vol. C-33, pp. 357-360, 1984.
[3] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Dentsch, J. K. Omura, and I. S. Reed. “VLSI architectures for computing multiplications and inverses in GF(2
m
).”
IEEE Trans. Comput
., vol. C-34, pp. 709-716, 1985.
[4] H. Okano, and H. Imai “A construction method of high-speed decoders using ROM's for Bose-Chaudhuri-Hocquenghem and Reed-Solomon codes,”
IEEE Trans. Comput
., vol. C-36, pp. 1165-1171, 1987.
[5] K. Araki, I. Fujita, and M. Morisue “Fast inverter over finite field based in Euclid's algorithm,”
Trans. IEICE
, vol. E-72, pp. 1230-1234, November 1989.
[6] P. A. Scott, S. J. Simmons, S. E. Tavares, and L. E. Peppard, “Architectures for exponentiation in GF(2
m
),”
IEEE J. Selected Areas in Commun
., vol. 6, No. 3, pp. 578-586, April 1988.
[7] C. C. Wang, and D. Pei, “A VLSI design for computing exponentiations in GF(2
m
) and its application to generate pseudorandom number sequences,”
IEEE Trans. Comput
., vol. C-39, No.2 pp. 258-262, February 1990.
Wei has also proposed another cellular-array power-sum circuit in 1996, for performing AB
2
+C, where A, B and C are elements in the finite field GF(2
m
). Under this structure, other arithmetic circuits for performing exponentiation, inverse multiplication and division are also disclosed.
However, the mentioned arithmetic circuits are respectively designed for a specific arithmetic operation, which is never enough, for example, a forward error-correction decoder. In a finite field GF(2
m
), an arithmetic circuit with high-speed, low complexity, and versatile features is required. For example, the decoding process of Peterson's direct solution method for decoding the 3-error-correcting Reed-Solomon code are:
(i) Calculate the syndrome value of the received word,
S
i
=r
(&agr;
i
)=
r
0
+r
1
·(&agr;
i
)+
r
2
·(&agr;
i
)
2
+ . . . r
n−1
·(&agr;
i
)
n−1
, where
i
=1, 2, 3, 4, 5, 6.
(ii) Determine error-location polynomial &sgr;(X) from the syndrome values. For example, if there are 3 errors in the received word, the error-location polynomial
&sgr;(
X
)=
X
3
+&sgr;
1
X
2
+&rgr;
2
X
+&sgr;
3
, where
σ
1
=
S
1
S
3
S
6
+
S
1
S
4
S
5
+
S
2
2
S
6
+
S
2
S
3
S
5
+
S
2
S
4
2
+
S
3
2
S
4
S
1
S
3
S
5
+
S
1
S
4
2
+
S
2
2
S
5
+
S
3
3
σ
2
=
S
1
S
4
S
6
+
S
1
S
5
2
+
S
2
S
3
S
6
+
S
2
S
4
S
5
+
S
3
2
S
5
+
S
3
S
4
2
S
1
S
3
S
5
+
S
1
S
4
2
+
S
2
2
S
5
+
S
3
3
σ
3
=
S
2
S
4
S
6
+
S
2
S
5
2
+
S
3
2
S
6
+
S
4
3
S
1
S
3
S
5
+
S
1
S
4
2
+
S
2
2
S
5
+
S
3
3
(iii) Find the roots of the error-location polynomial &sgr;(X) to obtain error locators.
(iv) Calculate error values at each error locator. For example, if the error locators are X
1
, X
2
and X
3
, the error values are respectively:
Y
1
=
S
1
X
2
2
X
3
3
+
S
2
X
2
3
X
3
+
S
3
X
2
X
3
3
+
S
1
X
2
3
X
3
2
+
S
2
X
2
X
3
3
+
S
3
X
2
2
X
3
X
1
X
2
2
X
3
3
+
X
1
3
X
2
X
3
2
+
X
1
2
X
2
3
X
3
+
X
1
3
X
2
2
X
3
+
X
1
X
2
3
X
3
2
+
X
1
2
X
2
X
3
3
Y
2
=
S
1
X
3
2
X
1
3
+
S
2
X
1
X
3
3
+
S
3
X
1
2
X
3
+
S
1
X
1
2
X
3
3
+
S
2
X
1
3
X
3
+
S
3
X
1
X
3
2
X
1
X
2
2
X
3
3
+
X
1
3
X
2
X
3
2
+
X
1
2
X
2
3
&ems
Chen Tung-Chou
Tsai Hung-Jen
Wei Shyue-Win
Darby & Darby
Ngo Chuong Dinh
Shyue-Win Wei
LandOfFree
Arithmetic circuit for finite field GF (2m) does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic circuit for finite field GF (2m), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic circuit for finite field GF (2m) will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3288501