Abstract:
A bit-serial key-equation solver employs the modified Euclidean algorithm to determine an error location polynomial and an error evaluation polynomial for decoding Reed-Solomon codes. The key equation solver includes a one-bit quotient bus for bit-serially transmitting the digits of a quotient value and a plurality of processing units each of which bit-serially receives the quotient digits from the one-bit quotient bus and each of which can be configured as a serial-in parallel-out (SIPO) standard basis bit-serial multiplier. Swapping and shifting of the register contents is also bit-serial. The key equation solver needs only the standard basis.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates generally to error-correction coding in digital communications and storage devices. More specifically, the present invention relates to a method and apparatus for solving the key equation to decode Reed-Solomon (RS) codes utilizing the modified Euclidean algorithm to generate an error location polynomial and an error evaluation polynomial. 
     2. Description of the Related Art 
     Bose-Chaudhuri-Hocquenghem (BCH) codes form a large class of powerful random error correcting cyclic codes. Among the nonbinary BCH codes, the most important subclass is the class of Reed-Solomon codes. Reed-Solomon codes are equivalent to a BCH code with the code symbol field being the same as the field of the roots of the code generator polynomial. Reed-Solomon codes have been widely used in digital communications and data storage devices (e.g. compact discs) in such a way that induced errors are efficiently correctable. The most commonly used approach to constructing the Reed-Solomon codes is the generator polynomial construction represented by BCH codes. 
     The following references, incorporated by reference herein in their entireties, are helpful to achieve a general understanding of the principles of Reed-Solomon codes: (1) Stephen B. Wicker and Vijay K Bhargava,  Reed - Solomon  Codes and Their Applications, IEEE Press, 1994; (2) E. Dahlman, K. Shu Lin, and Daniel J. Costello, Jr.,  Error Control Coding: Fundamentals and Applications  Prentice-Hall, Inc. Englewood Cliffs, N.J., 1983. 
     Generally, the arithmetic of error correction codes is based on a finite (Galois) field GF(2 m ) which is the extension field of GF(2) and is generated by a field generator polynomial f(x) of degree m with binary coefficients (0,1) in GF(2). For example, assuming α is a primitive element in GF(2 m ) satisfying f(α)=0, then the set {1, α,α 2 , . . . , α m−1 } is called the standard basis that spans GF(2 m ). In field GF(2 m ), a primitive element is defined as an element that has order 2 m −1. The order n of an element α in GF(2 m ) is defined as the smallest positive integer such that α n =1. Any finite field element β can be expressed in the standard basis as 
     
       
         β=β 0 +β 1 α+β 2 α 2 +. . . +β m−1 α m−1   (1) 
       
     
     where the binary digits {β 0 , β 1 , . . . , β m−1 } represent the standard coordinates of β. 
     For convenience, β m−1  is referred to as the most significant bit (MSB) and β 0  as the least significant bit (LSB). All arithmetic operations in GF(2 m ) are performed by exclusive OR (XOR) gates which perform modulo 2 addition (modulo 2 subtraction is equivalent to addition) and AND gates which perform modulo 2 multiplication. 
     A Reed-Solomon code (n,k,t) over GF(2 m ) can correct up to t error symbols, where GF(2 m ) is a finite field with 2 m  m-bit symbols, n is the total number of symbols in a code word, k is the number of information symbols in a code word, n−k is the number of check symbols in a code word and t=(n−k)/2. 
     The RS code is defined by a code generator polynomial G(x) of degree 2t with {1, α, α 2 , . . . , α 2t−1 } as its roots. Any legal code word, treated as a polynomial of degree n−1, must be divided by G(x). 
     The following table represents the RS codes in the digital television standard of the United States Advanced Television Systems Committee (ATSC) and the Standard of Digital Video Broadcasting by Satellite (DVB-S) of the European Telecommunications Standard Institute (ETSI), where m=8 (eight-bit symbol=one byte). 
     
       
         
               
               
               
             
               
               
               
             
           
               
                   
                   
               
               
                   
                     ATSC 
                    DVB-S 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 k 
                  187 
                   188 
               
               
                 n 
                 207 
                 204 
               
               
                 t 
                 10 
                 8 
               
               
                 m 
                 8 
                 8 
               
               
                   
               
             
          
         
       
     
     A brief description of the conventional error correcting procedure with regard to a Reed-Solomon code (n,k,t) will be given below. In this description, we assume that R i , i=0,1,2, . . . ,n−1, are the n received error-corrupted m-bit symbols. 
     Step ( 1 ): Generate 2t syndrome values                  s   i     =       ∑     j   =   0       n   -   1                           R   j          (     α   i     )       j         ,                for                 0     ,   1   ,   2   ,   …              ,       2      t     -   1             (   2   )                                
     and then, based on these syndrome digits, form a syndrome polynomial S(x) of degree 2t−1 representing the received codeword                S        (   x   )       =       ∑     i   =   0         2      t     -   1                         s   i          x   i                 (   3   )                                
     Step ( 2 ): Solve the key equation 
     
       
         Ω( x )=Λ( x ) S ( x )mod  x   2t   (4) 
       
     
     using the modified Euclidean algorithm to generate an error location polynomial Λ(x) of degree t and an error evaluation polynomial Ω(x) of degree t−1; 
     Step ( 3 ): Determine the roots of Λ(x) by the Chien search method, each of which indicates an error location. If α −μ  is a root of Λ(x), there is an error in the received symbol R μ  and the associated error value is given by the Forney algorithm 
     
       
         Ω(α −μ )/Λ odd (α −μ )  (5) 
       
     
     where Λ odd (x) is the polynomial of preserving the odd terms of Λ′(x), the terms associated with {x,x 3 ,x 5 , . . .}. 
     Step ( 4 ): Correct the errors by subtracting the error magnitudes from the received codeword in the associated error locations. 
     It should be noted that, as used herein, the term “received codeword” refers to a codeword that is either received through a communication medium or reproduced from a storage medium. 
     The modified Euclidean algorithm for solving the key equation is mathematically described as follows, starting with S(x) generated in accordance with step ( 1 ) above: 
     
       
         Initialization:  A ( x )= S ( x ),  A′ ( x )=1,  B ( x )= x   2t   , B ′( x )=0  (6) 
       
     
     Euclidean Iteration: 
     if deg_A(x)&lt;deg_B(x) then 
     swap A(x) and B(x) 
     swap A′(x) and B′(x) 
     endif 
     
       
           Q=a   lead   /b   lead   (7) 
       
     
     
       
           A ( x )← A ( x )− Q·B ( x )· x   deg     —     A(x)−deg     —     B(x)   (8) 
       
     
     
       
           A ′( x )← A ′( x )− Q·B ′( x )· x   deg     —     A(x)−deg     —     B(x)   (9) 
       
     
     if deg A(x)&lt;t, then 
     algorithm finished 
     
       
         Ω( x )= A ( x )  (10) 
       
     
     
       
         Λ( x )= A ′( x )  (1) 
       
     
     endif 
     where a lead  represents the leading coefficient of A(x), b lead  represents the leading coefficient of B(x), and “deg” means the degree of polynomial. 
     The notation ← means “simultaneous assignment upon Euclidean iteration.” 
     As to Q, it is typically obtained by computing the multiplication of 
     
       
           Q=a    lead   ·INV   (12) 
       
     
     where 
     
       
           INV= ( b   lead ) −1   (13) 
       
     
     and the value of INV is typically generated by a look-up table. 
     A brief description of prior art hardware implementations of a key equation solver for Reed-Solomon codes is given below. 
     Conventional key equation solvers using parallel multipliers are illustrated by, for example, U.S. Pat. Nos. 4,873,688, 5,170,399, 5,396,502, 5,428,628, 5,442,578, and 5,570,378. In these systems, generally, a global m-bit parallel bus is used to transmit the m-bit quotient value Q, and m-by-m parallel multipliers are used to perform the multiplication function. The parallel multiplier operates in parallel-in parallel-out (PIPO) mode, completes its operation in one clock, and requires m 2  AND gates and at least m 2  XOR gates. Thus, these systems have the disadvantage of incurring large gate counts and requiring an m-bit quotient bus. 
     Systolic implementations of the key equation solver using parallel multipliers are disclosed in, e.g., U.S. Pat. Nos. 4,958,348 and 5,323,402. In these systems, a set of registers is used for storing A(x), A′(x), B(x), B′(x), INV, Q, deg_A(x), and deg_B(x), while another set of registers is used to pipeline data transfer and perform arithmetic operations. Thus, these systems have the disadvantage of needing extra registers to pipeline data transfer and processing. 
     In the prior art discussed above, m-by-m parallel multipliers are implemented by an array of m 2  AND gates and m 2  XOR gates such that the required multiplication task is completed in one clock cycle. In general, a key equation solver needs more than 2t multipliers. 
     One way to reduce the number of gates is to use bit-serial multipliers, each of which needs m sequential clock cycles to complete a multiplication while its gate number is only proportional to m. U.S. Pat. No. 4,845,713 is an example of a bit-serial multiplier configuration providing a key equation solver using parallel-in serial-out (PISO) dual-basis bit-serial multipliers. However, this system has the disadvantage of requiring a basis change; using dual-basis requires extra serial-to-parallel registers and extra circuitry for the basis change between standard basis and dual basis. 
     FIG. 1 shows a conventional cellular VLSI key equation solver  5  using the modified Euclidean algorithm. The arithmetic computations of equations (8) and (9) are performed using parallel multipliers  6  in a processing unit (PU)  7 , which includes m-bit registers REG U(i) and REG L(i), i=1,2, . . . ,2t+2. Other functions for realizing the modified Euclidean algorithm are carried out by processing unit  7 . As the modified Euclidean algorithm proceeds, the degrees of A(x) and B(x) decrease while the degrees of A′(x) and B′(x) increase. Register degA and register degB are used to indicate the degrees of A(x) and B(x) respectively. The upper-side m-bit registers U(i), i=1,2, . . . ,degA +1, are used to store the coefficients of A(x). The upper-side m-bit registers U(i), i=degA+2, . . . ,2t+2, are used to store the coefficients of B′(x). The lower-side m-bit registers L(i), i=1,2, . . . .degB+1, are used to store the coefficients of B(x). The lower-side m-bit registers L(i), i=degB+2, . . . ,2t+2, are used to store the coefficients of A′(x). Registers U( 1 ), L( 1 ), U(2t+2), and L(2t+2) represent the leading coefficients of A(x), B(x), B′(x), and A′(x), respectively. The m-bit register REG_Q and the m-bit register REG_INV are used to store the values Q and INV, respectively. In particular, the m-bit register REG_Q produces an m-bit quotient value that is transmitted in parallel by a global m-bit parallel quotient bus  18 . 
     FIG. 2, is a flow chart showing the operations of the key equation solver circuit of FIG.  1 . In FIG. 2, S(i), Λ(i), and Ω(i) represent the coefficients of x i  of the syndrome polynomial S(x), the error location polynomial ·(x), and the error evaluation polynomial Ω(x), respectively. 
     The INITIALIZATION block  20  represents an algorithm initialization stage in which (1) syndrome polynomial S(x) is assigned to A(x); (2) x 2t  is assigned to B(x); (3) degA and degB are set to 2t; (4) A′(x) is set to one; and (5) B′(x) is set to zero. The Euclidean iteration starts in the CONTROL block  22 . In decision block  22 A, the ending condition is checked to determine whether the modified Euclidean algorithm is completed. If yes, then, in ending block  28 , the error location polynomial Λ(x) is given by the polynomial A′(x), and the error evaluation polynomial Ω(x) is given by the polynomial A(x). On the other hand, if decision block  22 A determines that the modified Euclidean algorithm is not completed, then the CONTROL block  22  will decide which of ARITH block  24 , SHIFT block  25  or SWAP block  26  is to be performed for the present Euclidean iteration. 
     In the ARITH block  24 , the arithmetic computations of equations (8) and (9) are executed. In SHIFT block  25 , the contents of registers U(•) are shifted left by one register position, and the register degA is decreased by one. In SWAP block  26 , the contents of registers U(Ω) and registers L(•) are swapped, and the registers degA and degB are adjusted accordingly. If ARITH block  24  is performed in the present iteration, U( 1 ) will become zero. Then, in the next iteration, SHIFT block  25  or SWAP block  26  will be performed to adjust the contents of U(•) and/or L(•) and to recompute the value of Q. 
     Due to the implementation of the parallel multipliers, the CONTROL block  22 , ARITH block  24 , SHIFT block  25 , and SWAP block  26  are all completed in one clock cycle. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing disadvantages of the prior art, it is an object of the present invention to provide an improved method and apparatus for decoding an error correction code. It is a further object to provide a method and apparatus for solving the key equation to decode a Reed-Solomon code using the modified Euclidean algorithm while utilizing bit-serial multipliers of the serial-in parallel-out (SIPO) type to reduce the required combinational logic gates. 
     In accordance with this invention there is provided an apparatus for solving the key equation for decoding an error correction code defined over GF(2 m ), the apparatus comprising a one-bit quotient bus for bit-serially transmitting m quotient digits of an m-bit quotient value Q; and a plurality of processing units each bit-serially receiving the quotient digits from the one-bit quotient bus and each including: (i) a first m-bit register; (ii) an m-by-one multiplier; (iii) a second m-bit register; and (iv) an adder. The m-by-one multiplier multiplies the m-bit contents of the first register by one of the quotient digits received from the one-bit quotient bus to generate an m-bit multiplication output. The second register and the adder are in the form of an accumulator for accumulating the m-bit multiplication output of the m-by-one multiplier. The first register is wired to form a linear feedback shift register which replaces its m-bit contents by the m-bit value resulting from multiplying its m-bit contents by α, with α being a non-zero element of GF(2 m ). The first and second m-bit registers can be configured as bit shift registers. The apparatus may further comprise an inversion means for generating an m-bit output in response to an m-bit value received from one of the processing units; and a quotient means for generating the m quotient digits by multiplying the m-bit output of the inversion means by an m-bit value received from one of the processing units and for transmitting the m quotient digits bit-serially on the one-bit quotient bus. 
     In accordance with this invention there is further provided an error correction circuit for correcting bit errors in a received codeword encoded by an error correction code over GF(2 m ), the circuit comprising: means for generating a syndrome polynomial S(x) by computing power sums of symbols of the received codeword; means for solving the key equation Ω(x)=Λ(x)S(x) mod x 2t  to generate an error location polynomial Λ(x) representing error locations of the errors in the codeword and an error evaluation polynomial Ω(x) used to determine error values of the errors; means for determining roots of the error location polynomial Λ(x), each of the roots indicating an error location; means for determining error values from the roots; and means for generating a corrected codeword from the error locations, the error values and the received codeword, wherein the means for solving the key equation comprises a one-bit quotient bus for bit-serially transmitting m quotient digits of an m-bit quotient value and a plurality of processing units each bit-serially receiving the quotient digits from the bus and each including: (i) a first m-bit register; (ii) an m-by-one multiplier for multiplying contents of the first register by one of the quotient digits received from the bus to produce an m-bit parallel multiplication result; (iii) a second m-bit register; and (iv) an adder for adding the m-bit multiplication result with contents of the second register to provide an m-bit addition result for replacing the contents of the second register, wherein the m-by-one multiplier comprises m AND gates, the adder comprises m exclusive OR gates, and the second register and the adder are configured to provide an accumulator for accumulating the m-bit multiplication result of the m-by-one multiplier. The apparatus may further comprise an inversion means for generating an m-bit output in response to an m-bit value received from one of the processing units; and a quotient means for generating the m-bit quotient value by multiplying the m-bit output of the inversion means by an m-bit value received from one of the processing units and for transmitting the m-bit quotient value bit-serially on the bus. The first m-bit register forms a linear feedback shift register which multiplies contents of the first register by α and stores the multiplication result back to the first register, where α is a non-zero element of GF(2 m ). 
     In accordance with this invention there is further provided a method of performing arithmetic operations for solving the key equation for decoding an error correction code defined over GF(2 m ), each of the arithmetic operations including m computation steps each comprising: receiving one of m quotient digits of an m-bit quotient value; multiplying contents of a first plurality of m-bit registers by the received quotient digit to produce a plurality of first m-bit parallel multiplication results; accumulating the plurality of first m-bit parallel multiplication results in a second plurality of m-bit registers; and replacing the contents of the first plurality of m-bit registers by the results of multiplying themselves by α. 
     In accordance with yet another aspect of this invention, there is provided a method of correcting bit errors in a received codeword encoded by an error correction code over GF(2 m ), the method comprising: generating a syndrome polynomial S(x) by computing power sums of symbols of the received codeword; solving the key equation Ω(x)=Λ(x)S(x) mod x 2t  to generate an error location polynomial Λ(x) representing error locations of the errors in the received codeword and an error evaluation polynomial Ω(x) used to determine error values of the errors; determining roots of the error location polynomial Λ(x), each of the roots indicating an error location; determining error values from the roots; generating a corrected codeword from the error locations, the error values and the received codeword, wherein the step for solving the key equation performs arithmetic operations each including m computation steps each of which includes receiving one of m quotient digits of an m-bit quotient value, multiplying contents of a first plurality of m-bit registers by the received quotient digit to produce a plurality of first m-bit parallel multiplication results, accumulating the plurality of first m-bit parallel multiplication results in a second plurality of m-bit registers, multiplying the contents of the first plurality of m-bit registers by α to produce a plurality of second m-bit parallel multiplication results, where α is a non-zero element of GF(2 m ), and storing the plurality of second m-bit parallel multiplication results back to the first plurality of m-bit registers. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic illustration of a conventional Euclidean algorithm based key equation solver using parallel multipliers; 
     FIG. 2 is a flow chart describing the operation of the key equation solver of FIG. 1; 
     FIG. 3 is a schematic illustration of a bit-serial multiplier of the serial-in parallel-out type to implement equations (8) and (9) in accordance with the present invention; 
     FIG. 4 is an expanded circuit diagram of the FIG. 3 embodiment illustrating a degree m equal to 4; 
     FIG. 5 is a schematic illustration of a circuit structure using the bit-serial multiplier of FIG. 3 to implement the arithmetic of equations (8) and (9) in accordance with the present invention; 
     FIG. 6 is a schematic illustration of an alternative bit-serial multiplier of the serial-in parallel-out type to implement equation (12) in accordance with the present invention; 
     FIG. 7 is an expanded circuit diagram associated with the FIG. 6 system with a degree m equal to 4; 
     FIG. 8 is a schematic illustration of a bit-serial implementation of the shift operation in accordance with the present invention; 
     FIG. 9 is a schematic illustration of a bit-serial implementation of the swap operation in accordance with the present invention; 
     FIG. 10 illustrates the system structure of the bit-serial key equation solver of the present invention; 
     FIG. 11 shows an embodiment of a processing unit of the bit-serial key equation solver of the present invention with a degree m=4; and 
     FIG. 12 is a circuit diagram of the quotient unit of the bit-serial key equation solver of the present invention with a degree m equal to 4. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 3 schematically illustrates a serial-in parallel-out (SIPO) standard basis bit-serial multiplier  30  employed in the present invention to implement equations (8) and (9). The multiplier  30  of FIG. 3 includes an accumulator  32 , an m-by-one multiplier  34 , a linear feedback shift register (LFSR)  36  wired to multiply itself by α, and an LSB-first serial input  38 . Multiplier  30  requires m sequential clock cycles to complete an operation. 
     To illustrate the operation of FIG. 3, assume that a +Q·b is to be computed, where α and b are two elements in GF(2 m ). Then, as a matter of necessity, Q is expressed in the standard basis as: 
     
       
           Q=q   o   q   1   α+q   2 α 2   +. . . +q   m−1 α m−1   (14) 
       
     
     To compute a+Q·b, multiplier  30  performs m sequential computation cycles as described below. 
     
       
         Initialization:  REG   ACCU   =a, REG   LFSR   =b   (15) 
       
     
     Begin 
     do i=1,2, . . . , m 
     
       
           REG   ACCU   ←REG   ACCU   +q   i−1   REG   LFSR   (16) 
       
     
     
       
           REG   LFSR   ←α·REG   LFSR   (17) 
       
     
     enddo 
     End 
     where REG ACCU  designates the accumulation register  32 -A, REG LFSR  designates the LFSR register  36 -A, index “i” indicates the i-th computation cycle, and the notation ← means “simultaneous assignment upon a clock trigger.” 
     It can be seen by those skilled in the art that, after m clock cycles, REG LFSR  contains α m ·b and REG ACCU  contains the desired value of a+Q·b. It should be noted that the serial input  38  receives the binary digits of Q in the order of q 0 , q 1 , . . . , and q m−1 , i.e., LSB first. 
     By employing the multiplier  30  of FIG. 3, the bit-serial realization of equations (8) and (9) is given by 
     do i=1,2, . . . ,m 
     
       
         INV←α −1 . INV  (18) 
       
     
     
       
           A ( x )← A ( x )− q   i−1   B ( x )· x   deg     —     A(x)−deg     —     B(x)   (19) 
       
     
     
       
           B ( x )←α· B ( x )  (20) 
       
     
     
       
           A ′( x )← A ′( x )− q   i−1   B ′( x )· x   deg     —     A(x)−deg     —     B(x)   (21) 
       
     
     
       
           B ′( x )←α B ′( x )  (22) 
       
     
     enddo 
     where index “i” indicates the i-th computation cycle. 
     It should be noted that INV is updated along with B(x) because INV is the inverse of the leading coefficient of B(x). With the above bit-serial computations, the present invention makes some further modifications to the foregoing conventional modified Euclidean algorithm. 
     As shown, B(x) and B′(x) are multiplied by α a total of m times in each Euclidean iteration; it follows that 
     
       
           B ( x )←α m   −B ( x )  (23) 
       
     
     and 
     
       
           B ′( x )←α m   ·B ′( x )  (24) 
       
     
     which should be appended to equations (8) and (9), respectively. 
     This modification does not affect the validity of the solutions of Λ(x) and Ω(x). 
     FIG. 4 is a circuit diagram implementing the system of FIG.  3 . The four upper-side bit resisters correspond to REG ACCU  of FIG.  3 . The four lower-side bit registers correspond to REG LFSR  of FIG.  3 . For illustration, m=4 and the associated field generator polynomial is 
     
       
           f ( x )= x   4   +x+ 1  (25) 
       
     
     According to a convention followed by those skilled in the art, the left-most bit registers  42  and  43  correspond to the most significant bits (MSBs) and the right-most bit registers  44  and  45  correspond to the least significant bits (LSBs). As shown in FIG. 4, a plurality of XOR gates  46  are implemented to perform the function of addition and a plurality of AND gates  47  are implemented to perform the function of multiplication. 
     FIG. 5 schematically illustrates a circuit structure using the bit-serial multiplier of FIG. 3 to perform the arithmetic of equations (8) and (9) in accordance with the present invention. More specifically, the ARITH block  24  in FIG. 2 is replaced by the following m computation cycles: 
     do i=1,2, . . . ,m 
     SEL_q selects q i−1   
     
       
           REG   —   INV←REG   —   INV/α   (26) 
       
     
     do j=1,2, . . . ,degB+1 
     
       
           U ( j )← U ( j )+ q   i−1   L ( j )  (27) 
       
     
     
       
           L ( j )← L ( j )  (28) 
       
     
     enddo 
     do j=degB+2, . . . ,degA+1 
     
       
           U ( j )← U ( j );  L ( j )← L ( j )  (29) 
       
     
     enddo 
     do j=degA+2 , . . . ,2t+2 
     
       
           L (j)← L ( j )+q i−1   U ( j )  (30) 
       
     
     
       
           U ( j )←α· U ( j )  (31) 
       
     
     enddo 
     enddo 
     It should be noted that the multipliers used for register U(j) and register L(j), j=degA+2, . . . ,2t+2, are upside-down reversed. Moreover, the register REG_INV is wired to divide itself by α, and transmission of the digits of register REG_Q is controlled by the m-to-one multiplexer  53  based on a signal SEL-q received from a system controller unit (not shown in FIG.  5 ). The value of Q is computed in the previous Euclidean iteration. 
     The advantages of implementing the key equation solver of the present invention as shown in FIG. 5 as compared with the conventional key equation solver as shown in FIG. 1 are at least two-fold. First, FIG. 1 utilizes m-by-m parallel multipliers  6 , while FIG. 5 uses bit-serial multipliers  57 , thereby reducing the complexity of the combination logic from m 2  to m. Secondly, FIG. 5 uses a global quotient bus q_BUS  58  which is bit-serial and one-bit only. By contrast, FIG. 1 uses an m-bit parallel (e.g., 8 bits) quotient bus  18 . 
     As noted above, in FIG. 5, each LFSR is wired to multiply itself by α, and the quotient bus  58  is LSB first. A straightforward modification is as follows: 
     The LFSRs are wired to multiply by α −1 , the serial digits transmitted via the one-bit quotient bus  58  are MSB first, and the value transmitted by the quotient bus  58  is α m−1 ·Q. Then, the value of α m−1 ·Q can be generated by multiplying α m−1 ·INV by a lead , and the value of α m−1 •INV can be obtained by a look up table. Additionally, while the LFSRs are multiplied by α −1 , INV should be multiplied by α. 
     FIG. 6 schematically illustrates another SIPO standard basis bit-serial multiplier unit  60  to determine quotient value Q. In FIG. 6, multiplier  60  includes an m-by-one multiplier  62 , a linear feedback accumulator  64 , a parallel input  66 , and a MSB-first serial input  68 . 
     First, assume that a lead ·INV, the value of Q given by equation (12), is to be computed and that a lead  is expressed in the standard basis as 
     
       
         a lead =d 0 +d 1 α+d 2 α 2 + . . . +d m−1   (32) 
       
     
     To compute Q, the bit-serial multiplier  60  of FIG. 6 performs the following operations: 
     Initialization: REG LF     —     ACCU =0 
     Begin 
     do i=1,2, . . . ,m 
     
       
           REG   LF     —     ACCU   ←α·REG   LF     —     ACCU   +d   m−i   INV   (33) 
       
     
     enddo 
     End 
     where REG LF     —     ACCU  designates m-bit register  64 -A of the linear feedback accumulator  64  and index “i” indicates the i-th computation clock cycle. After m computation cycles, register REG LF     —     ACCU  will contain the desired value of Q. 
     By employing the multiplier of FIG. 6, the bit-serial realization of equation (12) is given below as: 
     Initialization: Q=0 
     Begin 
     do i=1,2, . . . ,m 
     
       
           Q←α·Q+d   m−i   INV   (34) 
       
     
     enddo 
     End 
     The serial input  68  receives the binary digits of a lead  in the order of d m−1 , d m−2 , . . . , and d 0 , i.e., MSB first. The parallel input  66  receives the binary digits of INV which is (b lead ) −1 . As noted above, Q=a lead /b lead . 
     FIG. 7 is an expanded circuit diagram of FIG. 6 with a degree m equal to 4. In particular, AND gates  72  are used to perform the multiplication, and XOR gates  74  are used to perform accumulation. In FIG. 7, each of the four registers  69  is a bit register; together, registers  69  construct the m-bit REG LF     —     ACCU  of FIG.  6 . 
     FIG. 8 schematically illustrates a bit-serial implementation in accordance with the present invention of the SHIFT block  25  of FIG. 2 with a degree m equal to four. In particular, the contents of upper-side registers U(i) are shifted to registers U(i−1) for i=2,3, . . . ,2t+2, while lower-side registers L(•) remain unchanged. Additionally, register U(2t+2) is filled by zeros. 
     FIG. 9 schematically illustrates a bit-serial implementation in accordance with the present invention of the SWAP block  26  of FIG.  2 . The contents of registers {U(1), . . . ,U(2t+2)} are replaced with those of registers {L(1), . . . ,L(2t+2)} and the contents of registers {L(1), . . . , L(2t+2)} are replaced, simultaneously, with those of registers {U(2), . . . , U(2t+2)}. Additionally, register L(2t+2) is filled with zeros. 
     In SHIFT block  25  or SWAP block  26 , binary digits in every m-bit register for shifting or swapping are shifted in and shifted out in the order of MSB first. While registers are shifting or swapping (FIGS.  8  and  9 ), the value of Q must be computed, which value will be used in the next Euclidean iteration. In this condition, REG_INV is kept frozen and REG_Q is configured as a SIPO multiplier of FIG.  6 . The corresponding bit-serial operations are given by 
     
       
           REG   —   Q= 0  (35) 
       
     
     do i=1,2, . . . , m 
     
       
           REG_Q←α   REG   —   Q+d   m−i   REG   —   INV   (36) 
       
     
     enddo 
     where the initialization of resetting the register value REG_Q to zero is completed in the preceding CONTROL block  22  of FIG.  2 . 
     FIG. 10 illustrates a system structure of the key equation solver of FIGS. 5,  8  and  9 . Registers U(i) and L(i) are contained in the i-th processing unit PU(i), i=1,2, . . . ,(2t+2). Each PU(i), 1≦i≦2t +2 is followed by a 2-to-1 multiplexer  114 . REG_Q and REG_INV are contained in a quotient unit  115 . Register degA and register degB are contained in a controller unit  119 . The one-bit quotient bus q_BUS  120  is used to transmit Q in bit-serial mode. Additionally, an inversion unit  121  is used to generate the value of INV typically by a look-up table. 
     In FIG. 10, each processing unit PU( 1 ), PU( 2 ), . . . , PU(2t+2) is followed by a 2-to-1 multiplexer  114  which is controlled by SEL_S input  122  from controller  119 . In accordance with SEL_U input  123  and SEL_L input  124  from controller  119 , a processing unit PU is able to perform various configurations as shown below in Table 1. 
     
       
         
               
               
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Configuration of PU 
                 SEL_U 
                 SEL_L 
                 SEL_S 
                 Usage 
               
               
                   
               
             
             
               
                 Frozen 
                       0 
                  0 
                  x 
                    CONTROL or 
               
               
                   
                   
                   
                   
                 ARITH 
               
               
                 MAC 
                 1 
                 3 
                 x 
                 ARITH 
               
               
                 Upside-down MAC 
                 3 
                 1 
                 x 
                 ARITH 
               
               
                 Shifting 
                 2 
                 0 
                 0 
                 SHIFT 
               
               
                 Swapping 
                 2 
                 2 
                 1 
                 SWAP 
               
               
                   
               
             
          
         
       
     
     where notation “x” in the column of SEL_S represents “don&#39;t-care.” 
     A circuit for implementing INITIALIZATION block  20  of FIG. 2 (i.e., for carrying out equation (6)) in the system of FIG. 10 can be readily devised by those of ordinary skill in the art. 
     FIG. 11 illustrates a preferred circuit embodiment of the processing unit PU of FIG. 10 with a degree m=4. In FIG. 11, the four upper-side registers are bit registers which construct the m-bit register U(i). The four lower-side registers are bit registers which construct the m-bit register L(i). Registers U(•) and L(•) can be configured so as to perform the various bit-serial operations required by the ARITH block, SHIFT block, and SWAP block as disclosed in, e.g., FIGS. 5,  8 , and  9 . 
     In the frozen configuration as shown in Table 1, registers U(•) and L(•) are kept unchanged. In the MAC configuration, the processing unit becomes equivalent to the MAC shown in FIG.  4 . In the upside-down MAC configuration, the processing unit becomes equivalent to the upside-down version of the MAC shown in FIG.  4 . In the shifting configuration, registers U(•) become bit shift registers to shift in and out their contents while registers L(•) are kept unchanged. In the swapping configuration, registers U(•) and L(•) become bit shift registers. While shifting or swapping, the SEL_S input controls the routing of the flow of bit streams. 
     The circuit shown in FIG. 11 can be implemented for all processing units PU( 1 ), PU( 2 ), . . . , PU(2t+2) shown in FIG.  10 . With regard to prior art FIG. 2, the present inventor has realized that the register U( 1 ) in the processing unit PU( 1 ) may be replaced with a single bit register to indicate whether U( 1 ) is zero or not, the configuration of the normal MAC is not necessary for the processing unit PU(2t+2), and the configuration of the upside-down MAC is not necessary for the processing units PU( 1 ), PU( 2 ), . . . , and PU(t+1), and hence the circuits of the above mentioned processing units can be reduced. 
     FIG. 12 is a circuit diagram of the quotient unit  115  shown in FIG. 10 with a degree m=4. In accordance with the present invention, register REQ_Q and register REG_INV can be configured so as to perform the various bit-serial operations required by the CONTROL block, ARITH block, SHIFT block, and the SWAP block as shown in FIGS. 5,  8 , and  9 . For example, if a selector SEL_INV selects 0, then the value in the register REG_INV is wired to divide by α. If the selector SEL_INV selects 1, then the value in the register REG_INV is loaded with the value of parallel input INV_IN. If the selector SEL_INV selects 2, then the value of register REG_INV is frozen. On the other hand, if a selector SEL_Q selects 0, then the value of register REG_Q is frozen. If the selector SEL_Q selects 1, then the value in register REG_Q is reset to zero. If the selector SEL_Q selects 2, then register REG_Q is configured to perform the operation of the multiplier of FIG.  7 . 
     The selector SEL_q is used to control a 4-to-1 multiplexer 127 to transmit the digits of the quotient over the one-bit quotient bus q_BUS  120 . In FIG. 12, the upper-side bit registers form REG_INV, and the lower-side bit registers form REG_Q. 
     The advantages of the present invention include (1) using only standard basis representation to avoid complexities relating to basis change; (2) serially transmitting the m-bit quotient value bit-serially on a one-bit bus; (3) performing swapping and shifting of registers bit-serially to reduce cross-wiring between registers; (4) eliminating the need for a serial-to-parallel conversion register; and (5) reducing the complexity of combination logic from m 2  to m. 
     While particular embodiments of the present invention have been shown and described, it will be apparent to those skilled in the art that various changes and modifications may be made therein without departing from the spirit or scope of the invention. Accordingly, it is intended that the appended claims cover such changes and modifications that come within the spirit and scope of the invention. For example, various bit-serial multipliers or other multipliers may be used as the multiplier in the quotient unit of the present invention.