Division circuits based on power-sum circuit for finite field GF(2.sup.m)

Circuits, designed on the basis of power-sum circuits and inversion (B.sup.-1) computation structure where B is an arbitrary elements of GF(2.sup.m), for performing division computations in finite field GF(2.sup.m), are presented. The circuit can be deemed an extension of the circuit performing inversion (B.sup.-1) computations. With pipeline architecture and on the basis of power-sum circuits, the circuit is featured by simplicity, regularity, and broader application (applicable to arbitrary elements of the finite field) GF(2.sup.m).

FIELD OF THE INVENTION 
The present invention generally relates to a circuit for performing, based 
on the power-sum circuit disclosed in the application "power-sum circuit 
for finite field GF(2.sup.m)" filed in November of 1997, computations of 
K/H (dividing K by H) in a finite field GF(2.sup.m) where K and H are 
arbitrary elements of the finite field GF(2.sup.m). 
BACKGROUND OF THE INVENTION 
Index Terms: Coding theory, finite field, power-sum, division, 
exponentiation, multiplicative inverse, VLSI architecture. 
References: 
[1] T. R. N. Rao, and E. Fujiwara, Error-Control Coding for Computer 
Systems. Pretice-Hall, Englewood Cliffs, N.J., 1989. 
[2] R. E. Blahut, Theory and Practice of Error Control Codes. 
Addison-Wesley, Reading, Mass., 1983. 
[3] W. W. Peterson, and E. J. Weldon, Jr., Error-Correcting Codes. 2nd ed., 
The MIT Press, Cambridge, Mass., 1972. 
[4] S. Lin, and D. J. Costellor, Jr., Error Control Coding. Prentice Hall, 
Englewood Cliffs, N.J., 1983. 
[5] S. W. Wei, and C. H. Wei, "High speed decoder of Reed-Solomon codes," 
IEEE Trans. Commun., vol.COM-41, no. 11, pp. 1588-1593, November 1993. 
[6] S. R. Whitaker, J. A. Canaris, and K. B. Cameron, "Reed Solomon VLSI 
codec for advanced television," IEEE Trans. Circuits and Systems for Video 
Technology, vol.1, No.2, pp.230-236, June 1991. 
[7] S. W. Wei , and C. H. Wei, "A high-speed real-time binary BCH decoder," 
IEEE Trans. Circuits and Systems for Video Technology , vol.3 , no.2 , pp. 
138-147, April 1993. 
[8] E. R. Berlekamp, "Bit-serial Reed-Solomon encoders," IEEE Trans. Inform 
Theory, vol. IT-28, pp. 869-874, 1982. 
[9] 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.sup.m)," IEEE Trans. Comput., vol. C-34, pp. 709-716, 1985. 
[10] C. -S. Yeh, Iving S. Reed, and T. K. Truong, "Systolic multipliers for 
finite fields GF(2.sup.m)," IEEE Trans. Comput., vol. C-33, pp.357-360, 
1984. 
[11] B. A. Laws, Jr., and C. K. Rushforth, "A cellular-array multiplier for 
GF(2.sup.m)," IEEE Trans. Comput., vol. C-20, pp. 1573-1578, 1971. 
[12] 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. 
[13] K. Araki, I. Fujita, and M. Morisue, "Fast inverter over finite field 
based on Euclid's algorithm," Trans. IEICE, vol. E-72, pp.1230-1234, 
November 1989. 
[14] P. A. Scott, S. J. Simmons, S. E. Tavares, and L. E. Peppard, 
"Architectures for exponentiation in GF(2.sup.m)," IEEE J. Selected Areas 
in Commmun., vol.6, No.3, pp.578-586, April 1988. 
[15] C. C. Wang, and D. Pei, "A VLSI design for computing exponentiations 
in GF(2.sup.m) and its application to generate pseudorandom number 
sequences," IEEE Trans. Comput., vol. C-39, No.2, pp. 258-262, February 
1990. 
[16] A. M. Odlyzko, "Discrete logarithms in finite fields and their 
cryptographic significance," in Adv. Cryptol., Proc. Eurocrypt'84, 
pp.224-314, Paris, France, April 1984. 
Arithmetic Operations based on Finite Field GF(2.sup.m) have recently 
called significant attention because of their important and practical 
applications in the areas of computers and communications, such as the 
forward error-correction codes (recommended references [1]-[4]). To 
configure an error-correcting decoder with a high decoding speed and low 
circuit complexity, well designed basic arithmetic circuits in association 
with a powerful decoding algorithm are required. Therefore improvements in 
the design of finite field arithmetic circuits that yield lower circuit 
complexity, shorter computation delay, and higher computation speed is an 
extensive research topic in finite field arithmetic. Not only addition and 
multiplication, but also exponentiation and multiplicative inverse as well 
as division are essential arithmetic operations for error-correcting 
codes. For example, the most popular decoding procedure for a 
quat-error-correcting binary primitive BCH code consists of three main 
steps (recommended references [2]-[4]): (i) calculating the syndrome 
values S.sub.i, i=1, 3, 5, 7 from the received word; (ii) determining the 
error-locator polynomial .sigma.(x)=x.sup.4 +.sigma..sub.1 x.sup.3 
+.sigma..sub.2 x.sup.2 +.sigma..sub.3 x+.sigma..sub.4 from the syndrome 
values, where .sigma..sub.1 =S.sub.1, .sigma..sub.2 ={{S.sub.1 [S.sub.7 
+(S.sub.1).sup.7 ]}+{S.sub.3 [S.sub.5 +(S.sub.1).sup.5 ]}}/{{S.sub.3 
[S.sub.3 +(S.sub.1).sup.3 }+{S.sub.3 [S.sub.5 +(S.sub.1).sup.5 }}, 
.sigma..sub.3 =(S.sub.1).sup.3 +S.sub.3 +S.sub.1 .sigma..sub.2, and 
.sigma..sub.4 ={[S.sub.5 +S.sub.3 (S.sub.1).sup.2 ]+[S.sub.3 
+(S.sub.1).sup.3 ].sigma..sub.2 }/S.sub.1 [2]; (iii) solving for the roots 
of .sigma.(x), which are the error locators. To determine the coefficients 
of the error locator polynomial, .sigma..sub.2, .sigma..sub.3, and 
.sigma..sub.4 in such a way, not only operations for additions, 
multiplications, exponentiations, and inversions, but also that for 
divisions are required. The arts for additions and multiplications 
suggested by the inventor of the present invention have been disclosed in 
the application filed in November of 1997. One can obviously see from the 
above example that multiplication is one of the most frequently used field 
arithmetic operations. However, performing some operations, e.g. 
exponentiation, using ordinary multiplication might be inefficient. For 
instance, the above example of quat-error-correcting binary primitive BCH 
code requires several multiplications to calculate [S.sub.7 
+(S.sub.1).sup.7 ] in .sigma..sub.2, but requires only two AB.sup.2 +C 
operations to obtain the same result (that is, S.sub.1 [S.sub.1 
(S.sub.1).sup.2 +0].sup.2 +S.sub.7). It is confirmed by these references 
that the AB.sup.2 +C operation is an efficient tool to implement such a 
computation. As will be discussed in the present invention, the AB.sup.2 
+C operation can also be used to efficiently execute exponentiations and 
inversions as well as divisions. It must be noted the AB.sup.2 +C 
operations, exponentiations, inversions, and divisions are also frequently 
used in decoding other binary BCH and Reed-Solomon (RS) codes (recommended 
references [5]-[7]). Computations for exponentiations and inversions based 
on the above AB.sup.2 +C operations have been disclosed by the same 
inventor in an application filed earlier. Division computations using the 
algorithm for the above exponentiations/inversions computations based on 
the above AB.sup.2 +C operation is now disclosed in the present invention 
suggested by the same inventor. 
As stated in the application disclosed by the same inventor and filed in 
November of 1997, many architectures over GF(2.sup.m) have already been 
developed upon various bases, such as a bit-serial multiplier that uses a 
dual basis (recommended reference [8]), a multiplicative inverter that 
uses a normal basis (recommended reference [9]), and a systolic multiplier 
that uses a standard basis (recommended reference [10]). The finite field 
operations of the first two types need basis conversion, whereas the third 
one does not. Each type of finite field operation possesses distinct 
features that make it suitable for specific applications. For decoders 
used in computers and digital communications, the standard basis is still 
the most frequently used basis. Therefore the division circuits suggested 
by the present invention are operated over the standard basis. 
It is difficult to design a finite field arithmetic circuit having low 
circuit complexity while simultaneously maintaining a high computation 
speed. In general, a trade-off between computation speed and circuit 
complexity is often necessary. 
Since division computations can be implemented by combining multiplication 
and inversion computations (E/F=E*F.sup.-1, for example, where * is the 
multiplication operation in the Finite field and F.sup.-1 is the inversion 
of F), a brief introduction to multiplication and inversion computations 
is shown as follows: 
In principle, a multiplicative inverse can be implemented using a read-only 
memory (ROM) (recommended reference [12]), Euclid's algorithm (recommended 
reference [13]), or a number of consecutive multiplications (recommended 
reference [9]). Most of the architectures for computing multiplicative 
inverses have been developed upon the normal basis. A major reason for the 
development is that the squaring operation in the normal basis is just a 
simple cyclic shift (recommended reference [9]). Computation of 
exponentiation resembles the computation of multiplicative inverse. 
Exponentiation can also be implemented using ROM and successive 
multiplications. Several architectures for computing exponentiation in 
GF(2.sup.m) have been developed upon the standard as well as the normal 
bases (recommended reference [14]-[15]). 
SUMMARY OF THE INVENTION 
OBJECTS OF THE INVENTION 
The general object of the present invention is to provide a circuit of 
simple and systematic structure for performing division computations 
(K/H=K*H.sup.-1) in a finite field GF(2.sup.m) where H and K are arbitrary 
elements of GF(2.sup.m). 
The specific object the present invention is to utilize power-product 
(AB.sup.2) or power-sum (AB.sup.2 +C) computation circuits for configuring 
a circuit of simple and systematic structure (pipeline architecture) to 
perform K/H (divide K by H) or K/H+S computations in a finite field 
GF(2.sup.m), where K, H, and S are arbitrary elements in the finite field 
GF(2.sup.m), based on which, error-correction coding, that are relevant to 
communication, can be more conveniently and efficiently implemented. 
Introduction to Algorithm for Pipeline Architecture for Division 
Computations in GF(2.sup.M) Based on Power-sum Circuits 
Because division computations based on power-sum circuits are actually 
extensions of inversion computations which in turn are extensions of 
exponentiation computations, discussion hereinafter is made to trace the 
algorithm for exponentiation and inversion computations as suggested by 
the same inventor in another application filed earlier. 
Let P be an element of GF(2.sup.m), the conventional exponentiation over 
GF(2.sup.m) is defined as (recommended reference [14], [16]) 
EQU P=R.sup.N, where 0.ltoreq.N.ltoreq.n-1, and n=2.sup.m -1 (12) 
in which R (representing .alpha. which is popularly used in the field) is 
the primitive element of GF(2.sup.m). A more general definition of 
exponentiation for GF(2.sup.m) (recommended reference [17]) defines 
EQU P=b.sup.N, 0.ltoreq.N.ltoreq.n-1, (13) 
in which b (representing .beta. which is popularly used in the field) may 
be an arbitrary element of GF(2.sup.m). For the special case of b=R, (13) 
[hereinafter (n) means equation (n) and hence (13) means equation (13)] 
represents a conventional definition, as shown in (recommended reference 
[14], [16]). In this paper, we consider the more general definition of 
(13). For an integer N.ltoreq.n-1, N can be expressed as 
EQU N=N.sub.0 +N.sub.1x 2+N.sub.2x 2.sup.2 + . . . +N.sub.m-1x 2.sup.m-1, where 
N.sub.i.epsilon. {1,0}, i=0, 1, 2, . . . , m-1, (14) 
and may also be represented by an m-tuple vector [N.sub.0 N.sub.1 N.sub.2 . 
. . N.sub.m-1 ], with N.sub.0 called the least significant bit (LSB) and 
N.sub.m-1 called the most significant bit (MSB). It is inferred from (13) 
and (14) that the exponentiation of b can be expressed as 
##EQU1## 
Based on (15), a simple algorithm for computing exponentiation in 
GF(2.sup.m) is presented as follows (recommended reference [17]): 
##EQU2## 
Multiplicative inverse (inverting computation) can be considered as a 
special case of exponentiation because .beta..sup.-1 
=.beta..sup..lambda..spsp.-1 (where .lambda.=2.sup.m -1 and .beta.=b which 
is mentioned hereinbefore). The concept of computing inverse using 
consecutive multiplications may be implemented for the standard basis as 
well as the normal basis. Most architectures have been presented for the 
normal basis since squaring is only a simple cyclic shift in the normal 
basis and a multiplicative inverse can be obtained from the condition of 
.lambda.=2.sup.m -1 as follows (recommended reference [9]): 
EQU .beta..sup..lambda..spsp.-1 =(.beta..sup.2)(.beta..sup.2.spsp.2) . . . 
(.beta..sup.2.spsp.m-1)=.beta..sup.2+2.spsp.2.sup.+ . . . +2.spsp.m-1.(17) 
(because .lambda.-1=2.sup.m -2=2+2.sup.2 + . . . +2.sup.m-1) 
For the standard basis, it is difficult to compute an inversion using (17) 
since the number of multiplications is very large. With the help of the 
power-sum circuit disclosed by the same inventor in the application filed 
November of 1997, and the architecture for exponentiation computation 
presented above, the task of consecutive multiplications becomes 
realizable with the standard basis. Since .lambda.-1 can be expressed, as 
can be seen from (17), as a fixed m-tuple vector [0 1 1 1 . . . 1], we 
have N.sub.0 =0 and N.sub.i =1 for i=1, 2, . . . , m-1, and it can be 
inferred from (15) & (16) that 
EQU .beta..sup.-1 =.beta..sup..lambda..spsp.-1 =R.sup.0 [.beta.[.beta.[ . . . 
[.beta.(.beta.).sup.2 ].sup.2 ].sup.2 ].sup.2 ].sup.2. (18) 
It shall be understood now that an inversion operaton may be shown as 
follows: 
##EQU3## 
As can be represented by FIG. 1 in which .alpha..sup.0 =R.sup.0 =the 
element 1 of the finite field GF(2.sup.4) with field size of 4 and PK0, 
PK1, and PK2 are power-sum circuits each for computing bP.sup.2 (power-sum 
AB.sup.2 with A applied to pin 1 and B applied to pin 2) where b 
representing .beta., is an arbitrary element of the finite field 
##EQU4## 
As can be represented by FIG. 2 in which .alpha..sup.0 =R.sup.0 =the 
element of 1 of the finite field GF(2.sup.4) with field size of 4 and PK0, 
PK1, PK2, and PK3 are power-sum circuits each for computing bP.sup.2 
(power-sum AB.sup.2 with A applied to pin 1 and B applied to pin 2) where 
b representing .beta., is an arbitrary element of the finite field. 
Realizing that R.sup.0 =the element 1 of the finite field, and K*R.sup.0 =K 
for an arbitrary element K of the finite field and the multiplication 
operation * in the finite field, the computation for division can then be 
represented as follows: 
since .beta..sup.-1 =.beta..sup..lambda..spsp.-1 =R.sup.0 [.beta.[.beta.[ . 
. . [.beta.(.beta.).sup.2 ].sup.2 ].sup.2 ].sup.2 ].sup.2, K*.beta..sup.-1 
=K*R.sup.0 [.beta.[.beta.[ . . . [.beta.(.beta.).sup.2 ].sup.2 ].sup.2 
].sup.2 ].sup.2 
Note that R.sup.0 =element of 1 of the finite field, K*R.sup.0 =K, hence 
K/.beta.=K*R.sup.0 [.beta.[.beta.[ . . . [.beta.(.beta.).sup.2 ].sup.2 
].sup.2 ].sup.2 ].sup.2 =K[.beta.[.beta.[ . . . [.beta.(.beta.).sup.2 
].sup.2 ].sup.2 ].sup.2 ].sup.2 
it can be seen its algorithm may be expressed as follows: 
##EQU5## 
The final result is P=K/b. 
The algorithm can be easily understood by referring to FIG. 3 for a finite 
field GF(2.sup.4) with field size of 4, in which H functions as b. 
Another version of computations related to division is K/b+S where + is the 
addition operation in the finite field and S is an arbitrary element of 
the finite field. It is described as follows: 
##EQU6## 
The final result is P=K/b+S. 
The algorithm can be easily understood by referring to FIG. 5 for a finite 
field GF(2.sup.4) with field size of 4, in which H functions as b. 
The third version of division computation algorithm is to have one more 
power-sum circuit with its first input pin and second input pin 
respectively receiving, in the beginning of the computation operation, 
.beta.(=b mentioned hereinbefore) and R.sup.0 =1, the algorithm may be 
represented as follows: 
##EQU7## 
The final result is P=K/b. 
The algorithm can be easily understood by referring to FIG. 4 for a finite 
field GF(2.sup.4) with field size of 4, in which H functions as b and 
.alpha..sup.0 =R.sup.0 =the element of 1 of the finite field GF(2.sup.4). 
Introduction to Embodied Circuits for Performing K/H and K/H+S Computations 
Based on the Present Invention 
A division circuit for performing K/H (dividing K by H) computations in a 
finite field GF(2.sup.m), where H and K are arbitrary elements of 
GF(2.sup.m), m is the field size of the finite field GF(2.sup.m), may be 
configured to comprise: 
a group of m-1 power-sum circuits PK i , where i ranges from 0 to m-2 (i=0, 
1, 2, . . . , m-2), each having a first input pin, a second input pin, and 
an output pin for providing an output signal Sp=A*B.sup.2 in response to 
the inputting of the A and the B respectively to the first input pin and 
the second input pin thereof, where * being a multiplication operation 
over the finite field and both the A and the B being arbitrary elements of 
the finite field, the second input pin of the PK i where i=m-2 inputting 
the H, and the first input pin of the PKi where i ranges from 1 to m-2 
also inputting the H, the output pin of the PK i providing the second 
input pin of the Pk.sub.i-1 with the output signal Sp for i ranging from 1 
to m-2 (i=1, 2, . . . , m-2), and the first input pin of the PK i for i=0 
inputting the K, the K/H is obtained from the output pin of the PK i where 
i=0. 
The above division circuit may further comprise a circuit PK.sub.m-1 having 
a first input pin thereof inputting the H, a second input pin thereof 
inputting the element 1 of the finite field GF(2.sup.m) , and an output 
pin thereof for providing an output signal Sp=H*1.sup.2 where * being a 
multiplication operation over the finite field, the second input pin of 
the power-sum circuit PK i where i=m-2 connecting the output pin of the 
PK.sub.m-1 instead of inputting H. 
The above division circuit may be so configured that each of the power-sum 
circuits PK.sub.i where i ranges from 0 to m-2 (i=0, 1, 2, . . . , m-2) 
respectively comprises a latch for controlling the time of providing the 
output signal Sp, and the H and the K pass a latch or delay element before 
being inputted to PKi, to assure that the first input pin and the second 
input pin of the power-sum circuit PK.sub.i where i ranges from 1 to m-3, 
respectively and simultaneously receives the H and the Sp which is 
provided by Pkj where j=i+1, and that the first input pin and the second 
input pin of the power-sum circuit PK.sub.i where i=0, respectively and 
simultaneously receives the K and the Sp which is provided by PKi where 
i=1. 
The above division circuit may comprise, instead of those latches or delay 
elements for latching or delaying H and K before inputting to PKi, a clock 
pulse generator for generating a sequence of clock pulses P.sub.n where n 
ranges from 1 to an integer G which is not smaller than m-1, the first 
input pin of the power-sum circuit PK.sub.i inputting the H in response to 
the clock pulses P.sub.n in such a way that when both the first input pin 
and the second input pin of the power-sum circuit PK.sub.m-i where i=2, 
inputs the H in response to the J-th (J is a positive integer) pulse of 
the clock pulses, the first input pin and the second input pin of the 
power-sum circuit PK.sub.m-k where k ranges from 3 to m-1, respectively 
inputs, in response to the (J+k-i)-th pulse of the clock pulses where i=2, 
the H and the Sp which is provided by the PK.sub.m-k+1, for 
(J+k-i).ltoreq.G, while the first input pin and the second input pin of 
the power-sum circuit PK.sub.m-k where k=m respectively inputs, in 
response to the (J+k-i)-th pulse of the clock pulses where i=2, the K and 
the Sp which is provided by the PK.sub.m-k+1 for (J+k-i).ltoreq.G. 
The above division circuit in which a clock pulse generator is configured 
may comprise an input auxiliary circuit for controlling the first input 
pin of the power-sum circuit PK.sub.m-k where k ranges from 3 to m, to 
input the element of zero of the finite field in response to the y-th 
pulse of the clock pulses where y ranges from J+1 to J+k-i for i=2. 
The above division circuit may be so configured that the power-sum circuit 
PK.sub.0 further comprises a third input pin thereof for inputting an 
arbitrary element S of the finite field to output an element K/H+the S 
through the output pin thereof, where + is a sum operation in the finite 
field GF(2.sup.m). 
Another version of a division circuit (called one-stage division circuit) 
for performing K/H (dividing K by H) computations in a finite field 
GF(2.sup.m), where H and K are arbitrary elements of GF(2.sup.m), m is the 
field size of the finite field GF(2.sup.m), may be configured to comprise: 
a multiplex circuit inputting the H and the K for providing a sequence of 
output signal Ou.sub.i (Ou.sub.1, . . . , Ou.sub.m) where Ou.sub.i =the H 
for i ranging from 1 to m-1 and Ou.sub.m the K; and 
a power-sum circuit PK having a first input pin thereof receiving the 
sequence of output signal Ou.sub.i, a second input pin thereof receiving 
an arbitrary element E of the finite field applied thereto, and an output 
pin thereof providing an output signal Sp=the Ou.sub.i *(the E).sup.2 
where * being a multiplication operation over the finite field, the 
element of 1 of the finite field being applied to the second input pin of 
the PK when the power-sum circuit PK receives the Ou.sub.i where i=1, and 
the output signal Sp being applied to the second input pin of the PK when 
the power-sum circuit PK receives the Ou.sub.i where i ranges from 2 to m, 
the output signal Sp provided by the output pin of the power-sum circuit 
when the power-sum circuit PK receives the Ou.sub.i where i=m, is the K/H. 
The division circuit (one-stage division circuit) may be so configured that 
the multiplex circuit further is controlled by a bit sequence of N.sub.i, 
where N.sub.i =1 for i ranging from 1 to m-1 (N.sub.1, . . . , N.sub.m-1), 
and N.sub.m =0, to set the Ou.sub.i which equals the H when N.sub.i =1, 
and equals the K when N.sub.m =0, whereby the Ou.sub.i =the H for i 
ranging from 1 to m-1, and the Ou.sub.i =K for i=m. 
The division circuit (one-stage division circuit) may also be configured to 
comprise a first switch and a second switch, the first switch inputting 
both the element of 1 of the finite field and the output signal Sp, to 
apply the element of 1 of the finite field to the second input pin of the 
PK when the power-sum circuit PK receives the Ou.sub.i where i=1, and to 
apply the output signal Sp to the second input pin of the PK when the 
power-sum circuit PK receives the Ou.sub.i where i ranges from 2 to m 
(i=2, . . . , m), the second switch inputting the output signal Sp to 
provide a controlled output signal when the power-sum circuit PK receives 
the Ou.sub.i where i=m, whereby the controlled output signal is the K/H. 
The division circuit (one-stage division circuit) may also be configured to 
comprise a clock pulse generator for generating a first sequence of pulses 
and a second sequence of pulses, the first sequence of pulses controlling 
the first switch and the multiplex circuit in such a way that when the 
multiplex circuit inputs the N.sub.i where i=1 in response to the J-th 
pulse of the first sequence of pulses, the first switch applies the 
element of 1 of the finite field to the second input pin of the PK in 
response to the J-th pulse of the first sequence of pulses, and the 
multiplex circuit inputs N.sub.i where i ranges from 2 to m, in response 
to the (J+i-1)-th pulse of the first sequence of pulses, while the first 
switch applies the output signal Sp to the second input pin of the PK in 
response to the (J+i-1)-th pulse of the first sequence of pulses where i 
ranges from 2 to m; the second sequence of pulses controlling the second 
switch to provide the controlled output signal only when the power-sum 
circuit PK receives the Ou.sub.i where i=m, whereby the controlled output 
signal is the K/H. 
The division circuit (one-stage division circuit) may also be configured to 
comprise a latch circuit to control the time for the power-sum circuit PK 
to receive the Ou.sub.i, and the time for the PK to receive both the 
element of 1 of the finite field and the output signal Sp which is applied 
thereto by the first switch, whereby the power-sum circuit PK 
simultaneously receives the element of 1 of the finite field and the 
Ou.sub.i where i=1, and simultaneously receives the Ou.sub.i and the 
output signal Sp which is provided by the power-sum circuit PK in response 
to the Ou.sub.i-1 where i ranges from 2to m. 
The division circuit (one-stage division circuit) may also be so configured 
that the power-sum circuit PK further comprises a third input pin thereof 
for inputting an arbitrary element S of the finite field when the second 
switch inputs the output signal Sp to provide the controlled output 
signal, whereby the controlled output signal is the K/H+the S, where + is 
a sum operation in the finite field GF(2.sup.m).

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
The present invention may best be understood through the following 
description with reference to the accompanying drawings, in which: 
Shown in FIG. 3 is a division circuit for performing K/H (dividing K by H) 
computations in a finite field GF(2.sup.4), where GF(2.sup.4) is a special 
case of GF(2.sup.m) for field size m=4, and both H and K are arbitrary 
elements of GF(2.sup.4). The division circuit comprises: 
a group of m-1 power-sum circuits PK i, where i ranges from 0 to m-2 (i=0, 
1, 2, . . . , m-2, here m=4, hence i=0, 1, 2), each having a first input 
pin 1, a second input pin 2, and an output pin for providing an output 
signal Sp=A*B.sup.2 in response to the inputting of A and B respectively 
to the first input pin and the second input pin thereof, where * being a 
multiplication operation over the finite field and both A and B being 
arbitrary elements of the finite field, the second input pin of the PK i 
where i=m-2 (i.e., Pk2 in this case) inputting the H, and the first input 
pin of the Pki where i ranges from 1 to m-2 also inputting the H, the 
output pin of the PK i providing the second input pin of the Pk.sub.i-1 
with the output signal Sp for i ranging from 1 to m-2 (i=1, 2, . . . , 
m-2), and the first input pin of the PK i for i=0 inputting the K, the K/H 
is obtained from the output pin of the PK i where i=0. 
The above division circuit may further comprise a circuit PK.sub.m-1 (i.e., 
PK3 in this special case) as shown in FIG. 4, having a first input pin 1 
thereof inputting the H, a second input pin 2 thereof inputting the 
element 1 of the finite field GF(2.sup.m), and an output pin thereof for 
providing an output signal Sp=H*1.sup.2 where * being a multiplication 
operation over the finite field GF(2.sup.m), the second input pin of the 
power-sum circuit PK i where i=m-2 connecting the output pin of the 
PK.sub.m-1 instead of inputting H. 
The above division circuit shown in FIG. 3 or FIG. 4 may be so configured 
that each of the power-sum circuits PK.sub.i where i ranges from 0 to m-2 
(i=0, 1, 2, . . . , m-2) respectively comprises a latch associated with 
its output pin for controlling the time of providing the output signal Sp, 
and the H and the K pass a latch or delay element before being inputted to 
PKi, as can be seen from FIG. 7 where an arbitrary element w of the finite 
field functions as H or K, to assure that the first input pin 1 and the 
second input pin 2 of the power-sum circuit PK.sub.i where i ranges from 1 
to m-3, respectively and simultaneously receives the H and the Sp which is 
provided by Pkj where j=i+1, and that the first input pin and the second 
input pin of the power-sum circuit PK.sub.i where i=0, respectively and 
simultaneously receives the K and the Sp which is provided by PKi where 
i=1. 
The above division circuit may be so configured that the power-sum circuit 
PK.sub.0 further comprises a third input pin thereof, as shown in FIG. 5, 
for inputting an arbitrary element S of the finite field to output an 
element K/H+S through the output pin thereof, where + is a sum operation 
in the finite field. 
Another version of a division circuit (called one-stage division circuit) 
for performing K/H (dividing K by H) computations in a finite field 
GF(2.sup.m), where H and K are arbitrary elements of GF(2.sup.m), m is the 
field size of the finite field GF(2.sup.m), may be configured as shown in 
FIG. 6 to comprise: 
a multiplex circuit MUX inputting the H and the K for providing a sequence 
of output signal Ou.sub.i (Ou.sub.1, . . . , Ou.sub.m) to the first input 
pin 1 of a power-sum circuit PK, where Ou.sub.i =the H for i ranging from 
1 to m-1 and Ou.sub.m =the K; and 
power-sum circuit PK having its first input pin thereof receiving the 
sequence of output signal Ou.sub.i provided by multiplex circuit MUX, a 
second input pin 2 thereof receiving an arbitrary element E of the finite 
field applied thereto, and an output pin 3 thereof providing an output 
signal Sp=the Ou.sub.i *E.sup.2 where * being a multiplication operation 
over the finite field, the element of 1 of the finite field being applied 
to the second input pin 2 of power-sum circuit PK when the power-sum 
circuit PK receives the Ou.sub.i where i=1, and the output signal Sp being 
applied to the second input pin 2 of the power-sum circuit PK when the 
power-sum circuit PK receives the Ou.sub.i where i ranges from 2 to m, the 
output signal Sp provided by the output pin 3 of the power-sum circuit PK 
when the power-sum circuit PK receives the Ou.sub.i where i=m, is the K/H. 
The division circuit (one-stage division circuit) may be so configured that 
the multiplex circuit further is controlled by a bit sequence of N.sub.i, 
where N.sub.i =1 for i ranging from 1 to m-1 (N.sub.1, . . . , N.sub.m-1), 
and N.sub.m =0, to set the Ou.sub.i which equals H when N.sub.i =1, and 
equals K for N.sub.m (=0), whereby the Ou.sub.i =H for i ranging from 1 to 
m-1, and the Ou.sub.i =K for i=m. 
The division circuit (one-stage division circuit) may also be configured to 
comprise a first switch sw1 and a second switch sw2, the first switch sw1 
inputting both the element of 1 of the finite field and the output signal 
Sp, to apply the element of 1 of the finite field to the second input pin 
2 of PK when the power-sum circuit PK receives the Ou.sub.i where i=1, and 
to apply the output signal Sp to the second input pin 2 of the PK when the 
power-sum circuit PK receives the Ou.sub.i where i ranges from 2 to m 
(i=2, . . . , m), the second switch sw2 inputting the output signal Sp to 
provide a controlled output signal when the power-sum circuit PK receives 
the Ou.sub.i where i=m, whereby the controlled output signal is the K/H. 
The division circuit (one-stage division circuit) in FIG. 6 may also be 
configured to comprise a clock pulse generator for generating a first 
sequence of pulses and a second sequence of pulses, the first sequence of 
pulses controlling the first switch sw1 and the multiplex circuit MUX in 
such a way that when the multiplex circuit MUX inputs the N.sub.i where 
i=1 in response to the J-th pulse of the first sequence of pulses, the 
first switch sw1 applies the element of 1 of the finite field to the 
second input pin 2 of the PK in response to the J-th pulse of the first 
sequence of pulses, and the multiplex circuit MUX inputs N.sub.i where i 
ranges from 2 to m, in response to the (J+i-1)-th pulse of the first 
sequence of pulses, while the first switch sw1 applies the output signal 
Sp to the second input pin 2 of the PK in response to the (J+i-1)-th pulse 
of the first sequence of pulses where i ranges from 2 to m; the second 
sequence of pulses controlling the second switch sw2 to provide the 
controlled output signal only when the power-sum circuit PK receives the 
Ou.sub.i where i=m, whereby the controlled output signal is the K/H. 
The division circuit (one-stage division circuit) may also be configured to 
comprise a latch circuit L1 and L2 to control the time for the power-sum 
circuit PK to receive the Ou.sub.i, and the time for the PK to receive 
both the element of 1 of the finite field and the output signal Sp which 
is applied thereto by the first switch sw1, whereby the power-sum circuit 
PK simultaneously receives the element of 1 of the finite field and the 
Ou.sub.i where i=1, and simultaneously receives the Ou.sub.i and the 
output signal Sp which is provided by the power-sum circuit PK in response 
to the Ou.sub.i-1 where i ranges from 2 to m. 
The division circuit (one-stage division circuit) may also be so configured 
that the power-sum circuit PK further comprises a third input pin 4 
thereof for inputting an arbitrary element S of the finite field when the 
second switch sw2 inputs the output signal Sp to provide the controlled 
output signal, whereby the controlled output signal is the K/H+the S, 
where + is a sum operation in the finite field. 
While the invention has been described in terms of what are presently 
considered to be the most practical and preferred embodiments, it is to be 
understood that the invention needs not be limited to the disclosed 
embodiment. On the contrary, it is intended to cover various modifications 
and similar arrangements included within the spirit and scope of the 
appended claims which are to be accorded with the broadest interpretation 
so as to encompass all such modifications and similar structures.