Abstract:
A multi-mode Reed-Solomon decoder is disclosed. According to the invention, by simplifying the Peterson-Gorenstein-Zierler (PGZ) algorithm the goal of correcting different numbers of errors (t≦3) using a single hardware architecture is achieved. Through optimization without requiring finite field inversion operations, the hardware and the computing efficiency are both improved. The invention also discloses a register transistor level (RTL) hardware architecture to applied in error control codes (ECC) between a processor and a memory and other high-speed communication systems.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of Invention  
           [0002]    The invention relates to a Reed-Solomon decoder. More particularly, the invention relates to a multi-mode Reed-Solomon decoder based upon the Peterson-Gorenstein-Zierler (PGZ) algorithm.  
           [0003]    2. Related Art  
           [0004]    The Reed-Solomon (RS) codes have a strong error-correcting ability for burst transmission errors. Therefore, the RS codes have been widely used for error correction in digital communication and storage systems such as the xDSL, the cable modem, between a processor and a memory, the CD and the DVD.  
           [0005]    Among various RS decoding algorithms, the Peterson-Gorenstein-Zierler (PGZ) algorithm provides the simplest method for implementing a RS decoder for t≦3. This is a low-cost solution for such systems as the error control code (ECC) between a processor and a memory that requires smaller error-correcting ability. Unlike an iterated RS decoding algorithm, such as the Berlekamp-Massey algorithm, the main drawback of the conventional PGZ algorithm is that it can perform only single mode correction. In other words, the PGZ decoding circuit for t=3 cannot make t=1, 2 correction. Therefore, a PGZ decoding circuit for t≦3 conventionally requires three sets of different circuits to compute the t=1, t=2, and t=3 corrections independently, as shown in the circuit block diagram of FIG. 2.  
           [0006]    Apparently, implementing three sets of hardware circuits in an IC is a burden for manufacturing cost and chip design. To implement the Reed-Solomon decoder using the conventional PGZ algorithm, individual hardware circuits for different error corrections are required (the number of error correction abilities t=0, 1, 2, 3 . . . ). As the number of error codes increases, the required chip area also grows exponentially. This inevitably increases the manufacturing cost and lowers the efficiency of the hardware utility. In addition, the Reed-Solomon decoder has a finite field inverter (FFI), which occupies a large area and needs a long calculation time. With the increasing error-correcting abilities, the circuit design becomes very complicated. Moreover, the number of required finite field adders (FFA) and finite field multipliers (FFM) grows exponentially.  
         SUMMARY OF THE INVENTION  
         [0007]    In view of the foregoing, the invention provides a VLSI architecture to build a multi-mode Reed-Solomon decoder that can perform all sorts of corrections using the PGZ algorithm.  
           [0008]    An objective of the invention is to provide a multi-mode Reed-Solomon decoder that can make corrections in response to error situations based upon the PGZ algorithm.  
           [0009]    Another objective of the invention is to provide a multi-mode PGZ decoder circuit in a VLSI architecture that has a lower cost and uses fewer area resources to solve various error correction problems.  
           [0010]    A further objective of the invention is to provide an improved Reed-Solomon decoder based upon the PGZ algorithm that modifies the hardware circuit with error-correcting ability t=3, so that the circuit has the abilities to solve all t=0, 1, 2, 3 errors.  
           [0011]    For the implementation of a Reed-Solomon decoder based on the PGZ algorithm in the prior art, the VLSI architecture uses the redundant hardware circuits to achieve various types of error corrections (t=1, t=2, and t=3). The implementation requires a larger area and results in lowering the efficiency of hardware resources. Additionally, the implementation of the algorithm includes the operation of the FFI. This inevitably increases the complexity of the circuit calculation and deteriorates the calculation speed. Therefore, the invention ultilizes the derivation of the algorithm to obtain the disclosed Reed-Solomon decoder without requiring FFI. The occupied area resource is thus reduced, whereas the operation efficiency is enhanced. Furthermore, the invention improves the hardware circuit of the Reed-Solomon decoder with error-correcting ability t=3 based on the PGZ algorithm, so that it becomes a multi-mode PGZ decoder circuit that can process t≦3 error corrections.  
           [0012]    In one embodiment of the present invention, a Reed-Solomon decoding method comprises the steps of: computing the syndromes of received data; solving the key equation; and evaluating error locations and error value, wherein the step for solving the key equation is based upon a simplified PGZ algorithm and a solution that does not need FFI in operations. This greatly reduces the complexity of the computation and the area resources occupied by the hardware. A multi-mode decoding method is employed to obtain the number of errors. Accordingly, the invention proposes a multi-mode PGZ decoding architecture that can process t=0, 1, 2, 3 error corrections.  
           [0013]    In another embodiment of the invention, the Reed-Solomon decoder comprising: a syndrome calculator to compute the syndromes of received data; a key equation solver to receive a syndrome equation from the syndrome calculator; and an error location and error value evaluator to receive the syndrome equation and obtain the error locations and error value. The key equation solver uses a simplified PGZ decoder as the basis thereof. The PGZ decoding architecture comprises FFA and FFM without requiring FFI. The PGZ decoder contains a multi-mode decoding controller for obtaining the number of errors so that the PGZ decoding architecture can process t=0, 1, 2, 3 error corrections. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]    The present invention will become more fully understood from the detailed description given hereinbelow illustration only, and thus are not limitative of the present invention, and wherein:  
         [0015]    [0015]FIG. 1 shows a block diagram of the Reed-Solomon decoding procedure;  
         [0016]    [0016]FIG. 2 is a circuit block diagram for the conventional PGZ decoding architecture that uses the duplicate hardware circuits to achieve error corrections;  
         [0017]    [0017]FIG. 3 is a circuit block diagram of the multi-mode PGZ decoder with a single hardware to perform different error corrections according to one embodiment of the present invention;  
         [0018]    [0018]FIG. 4 shows an RTL hardware architecture of the t=1 PGZ decoding architecture;  
         [0019]    [0019]FIG. 5 shows an RTL hardware architecture of the t=2 PGZ decoding architecture;  
         [0020]    [0020]FIG. 6 shows an RTL hardware architecture of the simplified t=3 PGZ decoding architecture according to one embodiment of the present invention;  
         [0021]    [0021]FIG. 7 shows an RTL hardware architecture of the simplified t=3 PGZ decoding architecture that does not need FFI operations according to one embodiment of the present invention  
         [0022]    [0022]FIG. 8 shows a flowchart of the multi-mode decoding method according to one embodiment of the present invention; and  
         [0023]    [0023]FIG. 9 shows an RTL hardware architecture of the multi-mode PGZ decoding architecture according to one embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0024]    With reference to FIG. 1, a Reed-Solomon decoding procedure comprises computing the syndromes of a reception polynomial r(x) to obtain a syndrome polynomial S(x); solving the key equation to obtain an error location polynomial σ(x) and an error value polynomial ω(x) in accordance with the syndrome polynomial S(x); evaluating error locations and error value in accordance with the error location polynomial σ(x) and the error value polynomial ω(x); and correcting the errors in the received data in accordance with the error locations and the error value to obtain a transmitted codeword polynomial c(x).  
         [0025]    In the above-mentioned procedure, the transmitted codeword polynomial c(x) and the reception polynomial r(x) can be related by the following expression:  
           r ( x )= c ( x )+ e ( x ),  (1)  
         [0026]    where e(x) represents the error pattern. The syndrome values S i  obtained from α i  in the reception polynomial r(x) can be expressed as:  
                 S   i     =       r        (     α   i     )       =       ∑     j   =   0       n   -   1                r   j          (     α   i     )       j           ,                1   ≤   i   ≤     2        t   .                 (   2   )                               
 
         [0027]    Therefore, the syndrome polynomial S(x) is defined as:  
               S        (   x   )       =       ∑     i   =   0         2      t     -   1              S     i   +   1              x   i     .                 (   3   )                               
 
         [0028]    The PGZ algorithm for solving the key equation includes the step of solving the Newton Identity:  
                 [           S   2           S   3         …         S     t   +   1                 S   3           S   4         …         S     t   +   2               ⋮       ⋮       ⋰       ⋮             S     t   +   1             S     t   +   2           …         S     2      t             ]          [           σ     t   -   1                 σ     t   -   2               ⋮             σ   0           ]       =     [           -     S   1                 -     S   2               ⋮             -     S   t             ]             (   4   )                               
 
         [0029]    The syndrome values S i  are used to solve for σ in Eq. (4). The error location polynomial σ(x) is defined as:  
         σ( x )=σ 0 +σ 1   x+ . . . σ   t−1   x   t−1   +x   t .  (5)  
         [0030]    The key equation to be solved is shown in the following equation:  
         σ( x ) S ( x )=−ω( x )+μ· x   2t ,  (6)  
         [0031]    where the error value polynomial ω(x) is defined as:  
         ω( x )=ω 0   +ω   1   x+ . . . +ω   t−1   x   t−1 .  (7)  
         [0032]    When t=1:  
         [0033]    According to the PGZ algorithm, Eq. (8) is obtained from Eq. (4).  
                 [     S   2     ]          [     σ   0     ]       =         [     -     S   1       ]                   and                   σ   0       =       S   1       S   2                 (   8   )                               
 
         [0034]    Thus, the error location is computed as  
         σ( x )=σ 0   +x    
         [0035]    Then the t=1 key equation could be solved  
         σ( x ) S ( x )=−ω( x )+μ· x   2  ω( x )=−(σ 0   +x )( S   1   +S   2   x )mod  x   2 ,  
         [0036]    where the error value polynomial is  
         ω( x )=ω 0  and ω 0 =σ 0   S   1   (9)  
         [0037]    For t=1, the register transistor level (RTL) hardware architecture that uses the foregoing PGZ algorithm to solve Eqs. (8) and (9) is shown in FIG. 4, including:  
           FFA× 1 ; FFM× 2 ; FFI× 1  
         [0038]    When t=2:  
         [0039]    According to the PGZ algorithm, Eq. (10) is obtained from Eq. (4)  
                   [           S   2           S   3               S   3           S   4           ]          [           σ   1               σ   0           ]       =         [           -     S   1                 -     S   2             ]     ⇒     σ   0       =           S   1          S   3       +       (     S   2     )     2             S   2          S   4       +       (     S   3     )     2             ,       σ   1     =             S   2          S   3       +       S   1          S   4               S   2          S   4       +       (     S   3     )     2         .               (   10   )                               
 
         [0040]    The error value polynomial for solving the t=2 key equation is:  
         ω( x )=ω 0 +ω 1   x  and ω 0 =σ 0   S   1 , ω 1 =σ 0   S   2 +σ 1 S 1   (11)  
         [0041]    For t=2, the RTL hardware architecture using the PGZ algorithm to solve Eqs. (10) and (11) is shown in FIG. 5, which includes:  
           FFA× 4 ; FFM× 1 ; FFI× 1  
         [0042]    When t=3:  
         [0043]    According to the PGZ algorithm, Eq. (12) is obtained from Eq. (4):  
                 [           S   2           S   3           S   4               S   3           S   4           S   5               S   4           S   5           S   6           ]          [           σ   2               σ   1               σ   0           ]       =       [           -     S   1                 -     S   2                 -     S   3             ]     ⇒             σ   0     =           S   2          S   3          S   4       +       S   2          S   3          S   4       +       S   1          S   3          S   5       +       S   1          S   4          S   4       +       S   2          S   2          S   5       +       S   3          S   3          S   3               S   2          S   4          S   6       +       S   3          S   4          S   5       +       S   3          S   4          S   5       +       S   4          S   4          S   4       +       S   3          S   3          S   6       +       S   2          S   5          S   5                         σ   1     =           S   2          S   2          S   6       +       S   1          S   4          S   5       +       S   3          S   3          S   4       +       S   2          S   4          S   4       +       S   1          S   3          S   6       +       S   2          S   3          S   5               S   2          S   4          S   6       +       S   3          S   4          S   5       +       S   3          S   4          S   5       +       S   4          S   4          S   4       +       S   3          S   3          S   6       +       S   2          S   5          S   5                         σ   2     =           S   1          S   4          S   6       +       S   2          S   4          S   5       +       S   3          S   3          S   5       +       S   1          S   5          S   5       +       S   2          S   3          S   6       +       S   3          S   4          S   4               S   2          S   4          S   6       +       S   3          S   4          S   5       +       S   3          S   4          S   5       +       S   4          S   4          S   4       +       S   3          S   3          S   6       +       S   2          S   5          S   5                             (   12   )                               
 
         [0044]    The error value polynomial for solving the t=3 key equation is:  
         ω( x )=ω 0 +ω 1   x+ω   2   x   2  and ω 0 =σ 0   S   1 , ω 1 =σ 0   S   2 +σ 1 S 1 , ω 2 =σ 0   S   3 +σ 1 S 2 +σ 2 S 1   (13)  
         [0045]    For t=3, the RTL hardware architecture using the PGZ algorithm to solve Eqs. (12) and (13) includes:  
           FFA× 19 ; FFM× 49 ; FFI× 1  
         [0046]    Therefore, the Reed-Solomon decoder based upon the conventional PGZ algorithm requires a larger area in an IC and has a low hardware resource utilization. Furthermore, the implementation of the algorithm requires the FFI operations, which complicates the circuit design and deteriorates the calculation speed. The invention simplifies the algorithm so that the disclosed Reed-Solomon is less complicated in calculations. Furthermore, it requires no FFI operations when solving key equations. This can effectively reduce die size while increasing the calculation efficiency.  
         [0047]    The Reed-Solomon decoding procedure further simplifies Eq. (12) in the t=3 PGZ algorithm according to the present invention. For the denominators of σ 0 , σ 1 , σ 2 , two terms of S 3 S 4 S 5  are cancelled in FFA. Analogously, the numerator of σ 0  has two terms of S 2 S 3 S 4  that can be cancelled in FFA. In addition, the product terms S 2 S 2 S 5 , S 2 S 3 S 5 , S 2 S 4 S 5 , S 2 S 5 S 5  of σ 0 , σ 1 , σ 2  in Eq. (12) have a common term S 2 S 5 . Therefore, the disclosed solving procedure first computes the value of S 2 S 5  to reduce the calculation complexity. Other common terms S 2 S 6 , S 4 S 4 , S 3 S 3 , S 1 S 5 , and S 1 S 6  can be similarly computed, too. In this manner, the RTL hardware architecture of Eqs. (12) and (13) solved using the PGZ algorithm for t=3 can be simplified (FIG. 6) to include:  
           FFA× 12 ; FFM× 27 ; FFI× 1  
         [0048]    Moreover, the solving process of the PGZ algorithm involves FFI operation. This does not only lower the computing speed of the hardware but also occupy die size area. Thus, the invention further simplifies the PGZ algorithm so as to reduce FFI operation  106 .  
         [0049]    With reference to Eq. (4), we further define the syndrome matrix S the error location vector σ t×1 , and the syndrome vector s t×1  as follows:  
           S     t   ×   t       =     [           S   2           S   3         …         S     t   +   1                 S   3           S   4         …         S     t   +   2               ⋮       ⋮       ⋰       ⋮             S     t   +   1             S     t   +   2           …         S     2      t             ]       ,       σ     t   ×   1       =     [           σ     t   -   1                 σ     t   -   2               ⋮             σ   0           ]       ,       s     t   ×   1       =     [           -     S   1                 -     S   2               ⋮             -     S   i             ]                             
 
         [0050]    Therefore, the Newton Identity can be expressed as  
           S   t×t σ t×1   =s   t×1 ,  (14)  
         [0051]    and the determinant of the syndrome matrix S t×t  is denoted by  
           A   t   =det ( S   t×t )  (15)  
         [0052]    When multiplying the determinant A t  by Eqs. (5) and (7), a new error location polynomial Φ(x) and a new error value polynomial Ω(x) are obtained. They can be expressed as:  
         Φ( x )= A   t σ( x )= A   t σ 0   +A   t σ 1   x+ . . . +A   t σ t−1   t−1   +A   t   x   t    
         Φ( x )=Φ 0 +Φ 1   x+ . . . +Φ   t−1   x   t−1 +Φ t   x   t   (16)  
         Ω( x )= A   t ω( x )= A   t   ω+A   t ω 1   x+ . . . +A   t ω t−1   x   t−1    
         Ω( x )=Ω 0 +Ω 1   x + . . . +Ω t−1   x   t−1   (17)  
         [0053]    When t=1:  
         A 1 =S 2 ;  (18)  
         Φ 0   =A   t σ 0 , Φ 1 =A 1 ;  (19)  
         Ω 0 =A t σ 0   S   1   =A   1 ω 0 .  (20)  
         [0054]    When t=2:  
           A   2   =S   2   S   4 +( S   3 ) 2 ;  (21)  
         φ 0   =A   2 σ 0 , Φ 1   =A   2 σ 1 , Φ 2 =A 2 ;  (22)  
         Ω 0   =A   2 σ 0   S   1 =A 2 ω 0  Ω 1   =A   2 σ 0   S   2   +A   2 σ 1   S   1   =A   2 ω 1 .  (23)  
         [0055]    When t=3:  
           A   3   =S   2 S 4 S 6 +S 3 S 4 S 5 +S 3 S 4 S 5 +S 4 S 4 S 4 +S 3 S 3 S 6 +S 2 S 5 S 5 ;   (24)  
         Φ 0   =A   3 σ 0 , Φ 1   =A   3 σ 1 , Φ 2   =A   3 σ 2 Φ 3 =A 3 ;  (25)  
         Ω 0   =A   3 σ 0   S   1   =A   3 ω 0 , Ω 1   =A   3 σ 0   S   2   +A   3 σ 1   S   2   +A   3 σ 1   S   1   =A   3 ω 1 ; Ω 2   =A   3 σ 0   S   3   +A   3 σ 1   S   2   +A   3 σ 2 S 1   =A   3 ω 2 .  (26)  
         [0056]    In comparison with the conventional PGZ algorithm for computing σ for t=3, the invention greatly simplifies the PGZ algorithm so that the FFI operation is not needed when computing Φ for t=3. The RTL hardware of the simplified PGZ algorithm that does not need FFI operations for t=3 is shown in FIG. 7, which only requires:  
           FFA× 12 ; FFM× 24 ; FFI× 0  
         [0057]    However, the conventional PGZ architecture utilizes the redundant hardware circuits to achieve different error-correcting abilities (t≦3), as shown in FIG. 2. An objective of the invention is to use a single hardware circuit to achieve all theses error-correcting abilities (t=0, 1, 2, 3), as shown in FIG. 3.  
         [0058]    Furthermore, for the conventional PGZ algorithm, the PGZ decoding circuit for t=3 cannot correctly solve the t=1, 2 error(s). This is because when t is less than 3, divided-by-zero problems occur. For t=3, the equation to be solved is:  
                 [           S   2           S   3           S   4               S   3           S   4           S   5               S   4           S   5           S   6           ]          [           σ   2               σ   1               σ   0           ]       =       [           -     S   1                 -     S   2                 -     S   3             ]     .             (   27   )                               
 
         [0059]    If the number of error is less than 3, the rows or columns in the matrix S 3×3  will be linearly dependent; that is  
           [           S   2               S   3               S   4           ]     =       α        [           S   3               S   4               S   5           ]       =     β        [           S   4               S   5               S   6           ]           ,                         
 
         [0060]    where α and β are constants.  
         [0061]    Accordingly, the denominator and the three numerators in Eq. (12) will be 0. In other words,  
           S   2   S   4   S   6   +S   4   S   4   S   4   +S   3   S   3   S   6   +S   2   S   5   S   5 =0  
           S   1   S   3   S   5   +S   1   S   4   S   4   +S   2   S   2   S   5   +S   3   S   3   S   3 =0  
           S   2   S   2   S   6   +S   1   S   4   S   5   +S   3   S   3   S   4   +S   2   S   4   S   4   +S   1   S   3   S   6   +S   2   S   3   S   5 =0  
           S   1   S   4   S   6   +S   2   S   4   S   5   +S   3   S   3   S   5   +S   1   S   5   S   5   +S   2   S   3   S   6   +S   3   S   4   S   4 =0  (28)  
         [0062]    Similarly, if the number of errors is less than 2, the two sets of denominators and numerators in Eq. (10) will be 0 too. That is,  
           S   2   S   4   +S   3 S 3 =0  
           S   1   S   3   +S   2   S   2 =0  
           S   1   S   4   +S   2   S   3 =0  (29)  
         [0063]    Once divided-by-zero problems occur when computing σ, the conventional PGZ algorithm cannot perform error corrections. To solve this problem, the prior art requires the use of the redundant duplicate hardware circuits, as shown in FIG. 2. A state machine that checks error states is employed to correct different numbers of errors.  
         [0064]    In order to correct different numbers of errors using a single hardware circuit, the invention extracts important information from Eqs. (28) and (29). Such information can be used to find out the number of errors. Explicitly,  
         [0065]    when t=0: S 2 =0;  
         [0066]    when t=0, 1: S 2 S 4 +S 3 S 3 =0;  
         [0067]    when t=0, 1, 2: S 2 S 4 S 6 +S 4 S 4 S 4 +S 3 S 3 S 6 +S 2 S 5 S 5 =0  
         [0068]    From Eq. (15), the following expressions are obtained:  
         [0069]    A 1 =S 2 ;  
         [0070]    A 2 =S 2 S 4 +S 3 S 3 ;  
         [0071]    A 3 =S 2 S 4 S 6 +S 4 S 4 S 4 +S 3 S 3 S 6 +S 2 S 5 S 5 .  
         [0072]    Therefore, using A 1 , A 2 , and A 3  can determine the number of errors. Multi-mode decoding procedure based on the simplified PGZ algorithm is shown in FIG. 8.  
         [0073]    The simplified t=3 PGZ algorithm shown in FIG. 7 implements the RTL hardware without FFI operations. A controller 107 is capable of obtaining the number of errors as shown in FIG. 8. The multi-mode PGZ decoder 100 accomplishes the goal of using one circuit to solve different errors (t≦3). FIG. 9 shows an RTL hardware embodiment of the multi-mode PGZ decoder  100  according to the present invention, which includes:  
           FFA× 15 ; FFM× 27 ; FFI× 0  
         [0074]    Based upon the simplified PGZ algorithm, the Reed-Solomon decoding procedure according to the present invention comprises the steps of: computing the syndrome of received data; solving a key equation; and evaluating error locations and error value, wherein the step for solving the key equation is based upon the simplified PGZ algorithm. For t=3 PGZ algorithm, one first computes the common term of σ(x) in the error location polynomial ( 12 ) to reduce the number of the required FFA and FFM. Then perform a solving procedure without requiring FFI operations. This greatly reduces the calculation complexity and the occupied die area. In the invention, a multi-mode decoding method uses the determinant A, to determine the number of errors for implementing the multi-mode Reed-Solomon decoding procedure.  
         [0075]    In another embodiment of the invention, the multi-mode Reed-Solomon decoder comprising: a syndrome calculator  101  to calculate syndromes of received data; a key equation solver  102  to receive a syndrome equation output from the syndrome calculator  101 ; and an error location and error value evaluator  103  to obtain the error locations and error value. The key equation solver uses a simplified PGZ decoder as the basis thereof. The improved PGZ decoder comprises FFA  104  and FFM  105  without requiring any FFI  106 . The PGZ decoder contains a multi-mode decoding controller  107 , which determines the number or errors from the determinant value A t  so that the improved PGZ decoder can simultaneously perform t=0, 1, 2, 3 error corrections. Thus, the invention discloses a multi-mode PGZ decoder  100  to implement the key equation solver  102 .  
       EFFECTS OF THE INVENTION  
       [0076]    In accordance with the invention, the multi-mode Reed-Solomon decoder and method are based upon a simplified PGZ algorithm to solve key equations. The key equation solver is a multi-mode PGZ decoder that includes FFA and FFM without the need of any FFI. The multi-mode PGZ decoder further comprises a multi-mode decoding controller, which determines the number of errors using the determinant value A t , so that the improved PGZ decoder can perform error corrections with t=0, 1, 2, 3. Therefore, the disclosed Reed-Solomon decoder lowers the cost and reduces the die size. The simplified PGZ algorithm also greatly reduces the calculation complexity, to enhance the operation speed of the key equation solver.  
         [0077]    While the invention has been described by way of example and in terms of the preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, it is intended to cover various modifications and similar arrangements as would be apparent to those skilled in the art. Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.