Abstract:
A Reed-Solomon decoder includes an inversionless Berlekamp-Massey algorithm (iBMA) circuit with a pipelined feedback loop. A first polynomial generator generates error locator polynomial values. A discrepancy generator generates discrepancy values based on the error locator polynomial values and the scratch polynomial values. Arithmetic units are used to generate the discrepancy values are also used to generate the error locator polynomial to reduce circuit area. A first delay circuit delays the discrepancy values. A feedback loop feeds back the delayed discrepancy values to the error locator polynomial generator. An error location finder circuit communicates with the iBMA circuit and identifies error locations. An error value computation circuit communicates with at least one of the error location finder circuit and the iBMA circuit and generates error values.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application is a continuation of U.S. patent application Ser. No. 10/305,091 filed on Nov. 26, 2002 now U.S. Pat. No. 7,051,267, which application claims the benefit of U.S. Provisional Application No. 60/370,644, filed on Apr. 8, 2002. The disclosures of the above applications are incorporated herein by reference. 

   FIELD OF THE INVENTION 
   The present invention relates to forward error correction, and more particularly to Reed-Solomon decoders. 
   BACKGROUND OF THE INVENTION 
   As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. To ensure data integrity, an error correcting Reed-Solomon (RS) code is often used. Many communications systems perform forward error correction (FEC) to improve data transmission accuracy and to ensure data integrity. FEC helps reduce bit error rates (BER) in applications such as data storage, digital video broadcasts, and wireless communications. Reed-Solomon (RS) error-correcting codes are commonly used for FEC. 
   Referring now to  FIG. 1 , a first device  10 - 1  communicates with a second device  10 - 2  over a communications channel  12 . The communications channel can be hardwired or wireless. For example, the communications channel  12  can be an Ethernet network, a wireless local area network, a bus for a hard drive, etc. The first device  10 - 1  includes components  14 - 1  that output signals to a RS encoder  16 - 1  and that receive signals from a RS decoder  18 - 1 . Likewise, the device  10 - 2  includes components  14 - 2  that output signals to a RS encoder  16 - 2  and that receive signals from a RS decoder  18 - 2 . The components  14 - 1  of the first device  10 - 1  may be similar to or different than the components  14 - 2  of the second device  10 - 2 . The encoders  16  encode the data before the data is output onto the communications channel  12 . The encoders  16  insert redundant bits into the data stream. The decoders  18  use the redundant bits to detect and, when possible, to correct errors in the received data. 
   Referring now to  FIG. 2A , steps that are performed by a RS decoder are shown generally at  20 . In step  22 , the RS decoder computes syndrome values. In step  24 , the RS decoder computes an error locator polynomial. The error locator polynomial can be calculated using a Berlekamp-Massey algorithm (BMA), inversionless BMA (iBMA), Euclidean algorithm, or other suitable algorithms. In step  26 , the Reed-Solomon decoder calculates an error evaluator polynomial, which is typically based on the syndrome values and the error locator polynomial. 
   In step  28 , the RS decoder finds error locations. For example, Chien&#39;s search algorithm, which will be described below, can be used. In step  30 , error values are found. For example, Forney&#39;s algorithm, which will be described below, is often used to find the error values. Steps  28  and  30  may be performed in parallel in hardware implementations. 
   Referring now to  FIG. 2B , a RS decoder  32  typically includes a syndrome calculator  34  and an error locator polynomial generator  36 , which employs Euclidean, Berlekamp-Massey or other algorithms. The RS decoder  32  also includes an error evaluator polynomial generator  38 , an error location finder  40  and a error value finder  42 . Control devices  44  and storage devices  46  may also be used to control decoding and to store data values for use by the RS decoder  32 . The RS decoder  32  can be implemented using register-based VLSI, software and a processor, an application specific integrated circuit (ASIC) or in any other suitable manner. 
   The error location search can be performed using Chien&#39;s search, which is disclosed in R. T. Chien, “Cyclic Decoding Procedure for the Bose-Chandhuri-Hocquenghem Codes”, I.E.E.E. Transactions on Information Theory, Vol. IT-10, pp. 357-363, October 1964, which is hereby incorporated by reference in its entirety. The error value computation can be performed using Forney&#39;s algorithm disclosed in G. D. Forney, “On Decoding BCH Codes”, I.E.E.E Transactions on Information Theory, Vol. IT-11, pp. 549-557, October 1965, which is hereby incorporated by reference in its entirety. 
   While a data storage system will be used below to illustrate the operation of a Reed-Solomon decoder, skilled artisans will appreciate that there are may other uses for Reed-Solomon decoders. In the data storage system illustrated in  FIG. 3 , the Reed-Solomon decoder  32  receives sequential sectors or codewords  50 - 1 ,  50 - 2 ,  50 - 3  . . . , and  50 - n . While the first codeword  50 - 1  is received, the Reed-Solomon decoder  32  computes the syndrome values for the first codeword  50 - 1  as shown at  52 . While the second codeword  50 - 2  is received, the Reed-Solomon decoder  32  computes the error locator polynomial and then performs error location search and error value computations for the first codeword  50 - 1  as shown at  54 . While the second codeword  50 - 2  is received, the Reed-Solomon decoder  32  also computes the syndrome values for the second codeword  50 - 2  as shown at  55 . Operation continues in this manner for subsequent codewords. 
   The syndrome computation for an n th  codeword must be completed by the end of the n th  codeword. The error location search and error value computations for the n th  codeword must be completed by the end of the (n+1) th  codeword. The syndrome computation operates under the symbol clock f symbol . The error location search and error value computations operate under a system clock f system . 
   The Reed-Solomon decoder  32  operates based on finite fields GF(2 m ) where each symbol is an m-bit binary symbol εGF(2 m ). A Reed-Solomon code with correcting power t has a generator polynomial G(x) over GF(2 m ) with 2t roots:
 
 G ( x )=( x+a   b ) . . . ( x+a   b+2t−2 )( x+a   b+2t−1 )
 
 G ( x )= x   2t   +g   2t−1   x   2t−1   + . . . +g   1   x   1   +g   0   x   0 .
 
where g i εGF(2 m ). A Reed-Solomon code word can be represented using polynomial C(x):
 
 C ( x )= c   n−1   x   n−1   + . . . +c   1   x   1   +c   0   x   0  
 
 C ( x )= x   2t ( d   k−1   x   k−1   + . . . +d   0   x   0 )+( r   2t−1   x   2t−1   + . . . . +r   0   x   0 )
 
 C ( x )= x   2t   D ( x )+ R ( x ).
 
where D(x) represents the data symbols to be encoded and R(x) represents the Reed-Solomon parity symbols. The received code word can be represented using polynomial V(x):
 
 V ( x )= v   n−1   x   n−1   + . . . +v   1   x   1   +v   0   x   0  
 
 V ( x )=( c   n−1   x   n−1   + . . . +c   0   x   0 )+( e   n−1   x   n−1   + . . . +e   0   x   0 )
 
 V ( x )= C ( x )+ E ( x ).
 
where C(x) is the polynomial representing the Reed-Solomon codeword and E(x) is a polynomial representing the error vector.
 
   During the decoding of a Reed-Solomon code, a set of 2t syndromes S 0 , S 1 , . . . , S 2t−1  is first computed as shown in step  22  of  FIG. 2A  by evaluating V(x) at α i : 
             S   j     =         ∑     i   =   0       n   -   1       ⁢     V   ⁡     (     α     i   ⁡     (     b   +   j     )         )         =       ∑     i   =   0       n   -   1       ⁢       v   i     ⁢       α     i   ⁡     (     b   +   j     )         .                 
Next, in step  24  of  FIG. 2A , an error locator polynomial Λ(x) of degree t is computed from the syndromes S 0 , S 1 , . . . , S 2t−1 . For example, an inversion-less Berlekamp-Massey algorithm (iBMA) is typically employed, although other algorithms can be used. Further details concerning the iBMA approach can be found in “Inversionless Decoding of Both Errors and Erasures of Reed-Solomon Code”, I.E.E.E. Transactions on Communications, Vol. 46, No. 8, August 1998), which is hereby incorporated by reference in its entirety. A scratch polynomial B(x) of degree 2t is also used in the iBMA computation.
 
   Referring now to  FIG. 4 , steps of the iBMA algorithm are shown. In step  56 , initialization of the error locator polynomial (Λ(x)=1), the scratch polynomial (B(x)=1), indexes (r=0, L=0) and previous discrepancy (Δ B =1) is performed. If r=2t, as determined in step  57 , control ends in step  58 . Otherwise the discrepancy Δ is computed in step  60 : 
           Δ   =       ∑     i   =   0     L     ⁢       Λ   i     ⁢     S     r   -   i                 
Next, Λ(x), B(x), L and Δ B  are updated according to rules in box  62 . If Δ≠0 as determined in step  64 , Λ(x) is set equal to Δ B Λ(x)+Δ x B(x) in step  66 . Otherwise, Λ(x) is set equal to Λ(x) in step  68 . If Δ≠0 and 2L≦r as determined in step  72 , B(x) is set equal to Λ(x), L is set equal to r+1−L, and Δ B  is set equal to Δ in step  74 . Otherwise, B(x) is set equal to xB(x) in step  76 . In step  80 , r is incremented. Control loops from step  80  to step  57 .
 
   To find the error locations, a search algorithm such as Chien&#39;s search is used to evaluate Λ(x) at 1, α −1 , α −2 , . . . , α −(n−1) , where Λ(a −i )=0 implies v i  is a symbol with error. For error value computation, Forney&#39;s algorithm is typically used to compute error values at α −i , where Λ(a −i )=0. An error evaluator polynomial is defined by Ω(x)=Λ(x)S(x)modx 2t , where S(x) is the syndrome polynomial. Then, the error value at location α −i  is given by: 
               x   b     ⁢     Ω   ⁡     (   x   )           x   ⁢           ⁢       Λ   ′     ⁡     (   x   )               
wherein Λ′(x) is a formal derivative of Λ(x).
 
   A parallel architecture can be used for the iBMA algorithm implementation. Referring now to  FIG. 5A , an iBMA circuit  100  for implementing the iBMA with t=3 is shown. As can be appreciated, t can have higher or lower values. The iBMA circuit  100  includes delay devices  102  (such as registers), finite field adders  104 , and finite field multipliers  106 . 
   The discrepancy value A is computed by multiplying syndromes S 0 , S 1 , . . . , S 5  with the error locator polynomial coefficients Λ 0 , Λ 1 , Λ 2 , and Λ 3 , respectively, using multipliers S m0 , S m1 , S m2 , and S m3 , respectively. Outputs of multipliers S m0  and S m2  are summed by adder  110  to provide an even portion of Δ even  discrepancy Δ. Outputs of multipliers S m1  and S m3  are summed by adder  112  to provide an odd portion of Δ odd  discrepancy Δ. (Such a separation of Δ even  and Δ odd  is because of the hardware reuse of iBMA and error evaluation circuit. Δ odd  is used in the evaluation of xΛ′(x) in the Feng or Forney method.) Δ even  and Δ odd  are summed by adder  114  to provide discrepancy Δ, which is fed back to multipliers B m0 , B m1 , B m2 , and B m3 . 
   Discrepancy Δ is also fed back through delay device  116  to conditionally update the value of the previous discrepancy Δ B . Δ B  is fed to the inputs of multipliers Δ m0 , Δ m1 , Δ m2 , and Δ m3 . Multipliers B m0 , . . . , B m3  and Δ m0 , . . . , Λ m3  are used in the computation of the updated value of Λ(x) according to  FIG. 4 , step  66 . A condition circuit  116  tracks index variables L, r and the discrepancy value Δ to determine the updated Λ(x) and B(x) values according to  FIG. 4  steps  64  and  72 . 
     FIG. 5B  shows the computation schedule of the iBMA of the iBMA algorithm using the circuit in  FIG. 5A , where each iBMA iteration is finished within one clock cycle. In a first half of the clock cycle of a first iteration, syndrome values are calculated. In a second half of the clock cycle of the first iteration, the syndrome values are used to generate error locations and to compute error values. The critical path is the feedback loop within the iBMA iterations. In each iBMA iteration, the critical path involves the computation of the discrepancy value Δ followed by the computation of Λ(x) and B(x). As the clock speed increases, it has become more difficult to complete one iBMA iteration within one clock cycle. 
   SUMMARY OF THE INVENTION 
   A Reed-Solomon decoder includes an inversionless Berlekamp-Massey algorithm (iBMA) circuit with a first polynomial generator that generates an error locator polynomial. A discrepancy generator generates discrepancy values based on the error locator polynomial. Arithmetic units used by the error locator polynomial generator are also used by the discrepancy generator of the iBMA circuit to reduce circuit area. 
   In other features, a syndrome calculating circuit generates syndromes that are output to the iBMA circuit. An error location finder circuit communicates with the iBMA circuit and that identifies error locations. The error location finder circuit can implement Chien&#39;s search. 
   In other features, an error value computation circuit communicates with the iBMA circuit and that generates error values. The error value computation circuit implements one of Forney&#39;s and Feng&#39;s algorithm. The iBMA circuit completes one iteration every two clock cycles. 
   In still other features, a second delay circuit communicates with an output of a scratch polynomial generator that generates a scratch polynomial. The discrepancy generator calculates discrepancy values over two clock cycles. 
   In still other features, a first delay circuit delays the discrepancy values. A feedback loop feeds back the delayed discrepancy values to the error locator polynomial generator and the scratch polynomial generator. The iBMA circuit is integrated with at least one of the error location finder circuit and the error value computation circuit. 
   Further areas of applicability of the present invention will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will become more fully understood from the detailed description and the accompanying drawings, wherein: 
       FIG. 1  is a functional block diagram of first and second devices that include RS encoders/decoders according to the prior art; 
       FIG. 2A  illustrates steps for RS decoding according to the prior art; 
       FIG. 2B  is a functional block diagram of a RS decoder according to the prior art; 
       FIG. 3  illustrates pipelining of the Reed-Solomon decoder according to the prior art; 
       FIG. 4  illustrates steps of an inversionless Berlekamp-Massey algorithm (iBMA) according to the prior art; 
       FIG. 5A  is an electrical schematic of an iBMA circuit for a Reed-Solomon decoder according to the prior art; 
       FIG. 5B  illustrates the timing of the iBMA circuit of  FIG. 5A ; 
       FIG. 6A  is an electrical schematic of an iBMA circuit for a Reed-Solomon decoder according to the present invention with a pipelined feedback loop; 
       FIG. 6B  illustrates the timing of the iBMA circuit of  FIG. 6A ; 
       FIG. 7  is an electrical schematic of an iBMA circuit for a Reed-Solomon decoder according to the present invention with additional pipelining of the feedback loop; 
       FIG. 8  is an electrical schematic of an iBMA circuit for a Reed-Solomon decoder according to the present invention with shared circuit elements such as multipliers; 
       FIG. 9  is an electrical schematic of the shared circuit of an iBMA algorithm, an error location finder and an error value calculation circuit (Feng) for a Reed-Solomon decoder according to the present invention; and 
       FIG. 10  is an electrical schematic of the shared circuit of an iBMA algorithm, an error location finder and an error value calculation circuit (Forney) for a Reed-Solomon decoder according to the present invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The following description of the preferred embodiment(s) is merely exemplary in nature and is in no way intended to limit the invention, its application, or uses. For purposes of clarity, the same reference numbers will be used in the drawings to identify similar elements. 
   The present invention provides an efficient and high-speed Reed-Solomon decoder. Higher speeds are achieved by pipelining the feedback loop in the BMA circuit one or more times. Circuit area is reduced by hardware sharing between the iBMA pipelines and hardware sharing between the iBMA, the error location finder and the error value computation circuit. 
   Referring now to  FIG. 6A , an improved iBMA circuit  150  is shown. Normally, a critical path in a feedback loop cannot be reduced using pipelining. For the iBMA circuit  150 , however, the input signals to the circuit  150  (the syndromes S 0 , . . . , S 5 ) are only taken as the initial value of the iBMA algorithm. Once the iBMA iteration starts, the iBMA circuit  150  no longer depends on outside input values. The iBMA circuit  150  according to the present invention includes a pipelined feedback loop. In other words, one or more delay devices such as registers or SR latches are inserted in the feedback loop. 
   In the exemplary implementation, a register  152  is positioned at the output of the adder  114 . The register  152  outputs Δ d , which is a delayed discrepancy value. Instead of completing one iBMA iteration per clock cycle, two clock cycles are required for each iBMA iteration. 
   Referring now to  FIGS. 6A and 6B , for each iBMA iteration, the discrepancy Δ is calculated during a first clock cycle. The register  152  changes value at the end of the first clock cycle. During the second clock cycle, Λ(x) and B(x) are calculated and updated. The discrepancy Δ maintains the same value during the second clock cycle. In other words, two clock cycles are required for each iBMA iteration. However, the critical path in the feedback loop is reduced, which allows the iBMA circuit  150  to run at faster clock speeds. The pipeline position is not limited to the output of the adder  114 . Other suitable locations to pipeline the feedback loop include any position between the outputs of the multipliers S m0 , . . . , S m3  and the output of the adder  114 . 
   Additional increases in clock speeds can be achieved by further pipelining the feedback loop. For example, the discrepancy Δ computation can be broken into two steps and three clock cycles can be used to complete each iBMA iteration.  FIG. 7  illustrates an iBMA circuit  158  with additional pipelining. The iBMA circuit  158  includes additional delay devices  160 ,  162 ,  164 , and  166  (such as registers) that are inserted between multipliers S m0 , S m1 , S m2  and S m3  and adders  110  and  112 . The positions of the registers  160 ,  162 ,  164  and  166  can be moved between the output of the adder  114  and the outputs of the multipliers S m0 , S m1 , S m2  and S m3  according to the actual speed requirement. 
   After pipelining the feedback loop as taught in  FIGS. 6A ,  6 B, and  7 , some hardware resources are used in one clock cycle within one iBMA iteration and not other clock cycles. In  FIG. 6A , the multipliers S m0 , S m1 , S m2  and S m3  are used during the first clock cycle. Multipliers Λ m0 , Λ m1 , Λ m2 , and Λ m3  and B m0 , B m1 , and B m2  are idle during the first clock cycle. Resource sharing can be used to reduce the circuit area of the iBMA circuits  150  and  158 . S m0 , S m1 , S m2  and S m3  can be shared with multipliers Λ m0 , Λ m1 , Λ m2 , and Λ m3  as shown in an iBMA circuit  170  in  FIG. 8 . As can be appreciated, similar techniques can be applied to the iBMA circuit  158  shown in  FIG. 7 . 
   After the 2t iterations of the iBMA, the Λ(x) coefficients values are ready to be used in Chien&#39;s search to find error locations. At the same time, error values can be computed using Forney&#39;s algorithm. The error values can also be computed using “Error Evaluator for Inversionless Berlekamp-Massey Algorithm In Reed-Solomon Decoders”, Feng et al. Ser. No. 10/304,511, filed Nov. 26, 2002 which was based on U.S. Provisional Application No. 60/371,898, filed Apr. 11, 2002 and which are both hereby incorporated by reference in their entirety. When there is no erasure, Feng&#39;s evaluation can be used to simplify the computation. In other words, the error evaluator polynomial generator  38  in  FIG. 2B  and step  26  in  FIG. 2A  can be omitted. This method avoids calculating the traditional error evaluator polynomial Ω(x). 
               Λ   0     ⁢     Δ   B     ⁢     x     b   +     2   ⁢   t     -   1             xB   ⁡     (   x   )       ⁢       Λ   ′     ⁡     (   x   )               
Both equations are evaluated at α −1  for the error value, where Λ′(x) is the formal derivative of Λ(x), and B(x) is the scratch polynomial used in the iBMA algorithm.
 
   To reduce circuit area, the pipelined iBMA algorithm, Chien&#39;s search and the error value computation can share the same circuitry. Referring to  FIG. 9 , a shared circuit  180  using the algorithm disclosed in Feng et al. as the error value calculation method is shown. 
   After the 2t iBMA iterations, the Λ(x) coefficients values are stored in registers Λ 0 , Λ 1 , Λ 2 , and Λ 3 . To evaluate Λ(x) at 1, α −1 , α −2 , . . . , α −(n−1) , the multipliers S m0 , . . . , S m3  and adders A 0 , . . . , A 3  in  FIG. 9  are used. In this mode, the multipliers S m0 , . . . , S m3  inputs are switched to 1, α −1 , α −2 , . . . , α −2 , . . . and the adders A 0 , . . . , A 3  inputs are switched to zero. The signal Δ is the evaluation of Λ(x) at 1, α −1 , α −2 , . . . , α −(n−1) . The signal Δ odd  is the evaluation of xΛ′(x) at 1, α −1 , α −2 , . . . , α −(n−1) . Similarly, the value of B(x) evaluated at 1, α −1 , α −2 , . . . , α −(n−1)  are output at B. The evaluation of the error values is provided at E. 
   Alternately, if Forney&#39;s algorithm is used, the Ω(x) coefficients can be computed by Ω(x)=Λ(x)S(x)modx 2t  by using the multipliers Λ m0 , Λ m1 , Λ m2 , and Δ m3  and the adders  110 ,  112  and  114 . The B(x) registers are used to store the Ω(x) coefficients values. The iBMA and error value calculation algorithms share the hardware, as shown in  FIG. 10 . 
   Those skilled in the art can now appreciate from the foregoing description that the broad teachings of the present invention can be implemented in a variety of forms. Therefore, while this invention has been described in connection with particular examples thereof, the true scope of the invention should not be so limited since other modifications will become apparent to the skilled practitioner upon a study of the drawings, the specification and the following claims.