Abstract:
A circuit for calculating an error position polynomial at high speed. The error position polynomial is calculated by using the Berlekamp-Massey iterative algorithm of a serial structure to simplify calculation and obtain a high-speed operation. To correct a Reed-Solomon code, a syndrome calculator calculates a syndrome from a received word. An error position polynomial is then calculated from the syndrome by an error position polynomial calculator. An error position is retrieved from the error position polynomial and an error value of the retrieved error position is calculated by a error position retrieval and error value calculator. The error is corrected by adding an error position symbol to the error value via an error corrector, thereby generating the corrected code word.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a circuit for calculating an error position polynomial in an error correcting system using a Reed-Solomon code, and more particularly, to a circuit which can rapidly calculate an error position polynomial by using the Berlekamp-Massey iterative algorithm. 
     2. Description of the Related Art 
     In digital communication and storage systems, a Reed-Solomon (hereinafter, referred to as the RS) code for controlling an error has widely been used. In data coded to the RS code, an error is frequently generated during data transmission or reproduction. Since incorrect data is received due to this error, the data coded into the RS code needs to be error-corrected by RS decoding. In this RS decoding process, it is necessary to calculate an error position polynomial having an error position as a root. Examples of such error position polynomial calculation are described in papers, R. E. Blahut, “Theory and Practice of Error Control Code”, Addison-Wesley, 1983, and J. L. Massey, “Shift Register Synthesis and BCH Decoding” IEEE Transactions on Information Theory, Vol. IT-15, pp. 122-127, January, 1969. As a circuit using the Berlekamp-Massey algorithm (BMA) to calculate the error position, there is an example using a linear feedback shift register (LFSR) published by Massey, 1965. A discrepancy is calculated from a syndrome and an error position polynomial. If the discrepancy is 0, the previous error position polynomial is used. If it is not 0, the error position polynomial is again calculated. In order to again calculate the error position polynomial, a correction polynomial is given. That is, a new error position polynomial is calculated by using the correcting polynomial and the discrepancy. However, since such a circuit has a parallel structure, many multipliers are required to calculate the error position polynomial, and thus, the size of the circuit is increased. Moreover, since there is a long delay time in a circuit for calculating the discrepancy and a circuit for calculating the error position polynomial using the discrepancy, it is difficult to apply such a conventional circuit to a digital communication system which pursues a high-speed operation or to a storage system which has high storage capacity and requires high-speed access. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a circuit for calculating an error position polynomial which has a small circuit size and can rapidly calculate an error position polynomial. 
     To achieve the foregoing and other objects, the error position polynomial is calculated by using the Berlekamp-Massey iterative algorithm of a serial structure to simplify calculation and obtain a high-speed operation. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and other objects, features and advantages of the present invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings in which: 
     FIG. 1 is a block diagram of an RS code error correcting system according to a preferred embodiment of the present invention; and 
     FIG. 2 is a detailed block diagram of an error position polynomial calculator shown in FIG.  1 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In the following description, well known functions and constructions which may obscure the subject matter of the present invention are not described in detail. The following terms are defined in consideration of the function in the present invention and may be varied according to intentions or customs of users and chip designers. Therefore, definitions should be based on the whole contents of the specification. 
     Referring to FIG. 1, a syndrome calculator  101  calculates a syndrome from a received word. An error position polynomial calculator  103  calculates an error position polynomial from the syndrome calculated by the syndrome calculator  101 . An error position retrieval and error value calculator  105  retrieves an error position from the error position polynomial calculated by the error position polynomial calculator  103  and calculates an error value of the retrieved error position. An error corrector  107  corrects an error by adding a symbol of the error position retrieved from the error position retrieval and error value calculator  105  to an error value. A calculation controller  108  generates a control signal by a signal generated from the syndrome calculator  101  so that the error position polynomial calculator  103  can calculate the error position polynomial. 
     FIG. 2 is a detailed block diagram of the error position polynomial calculator  103  shown in FIG. 1. A first shift register  201  stores a correction polynomial B(x). A second shift register  203  stores an error position polynomial Λ(x). A third shift register  205  stores a syndrome polynomial S(x). A fourth multiplexer  206  selects one of syndrome symbols generated from the third shift register  205  according to a signal of a syndrome select terminal  317  of the calculation controller  108 . A delay  217  delays a symbol byte of the correction polynomial of the first shift register  201 . A first operation cell  215  operates a symbol of the error position polynomial of the second shift register  203 , a symbol of the syndrome polynomial of the fourth multiplexer  206  and a next discrepancy in a Galois field GF(2 m ). A second multiplexer  209  selects one of the output of the first operation cell  215  and the output of the fourth multiplexer  206  according to a signal of an intermediate value storage select terminal  313  of the calculation controller  108 . 
     A next discrepancy storage unit  221  stores an intermediate value in order to calculate the next discrepancy from the output of the second multiplexer  209 . A third multiplexer  211  selects one of the output of the first operation cell  215  and a signal of a syndrome coefficient terminal S 0  according to a signal of a current discrepancy input select terminal  315  of the calculation controller  108 . A current discrepancy storage unit  223  stores a current discrepancy according to the output of the third multiplexer  211 . A coefficient signal storage unit  227  stores a coefficient signal from the output of the second shift register  203 . A second operation cell  213  performs an operation in the Galois field GF(2 m ) by multiplying the output of the first shift register  201  and the output of the current discrepancy storage unit  223  and then adding the multiplied value to the output of the second shift register  203 . A third operation cell  219  performs an operation in the Galois field GF(2 m ) by dividing the output of the coefficient signal storage unit  227  by the output of the current discrepancy storage unit  223 . A first multiplexer  207  selects one of the output of the third operation cell  219  and the output of the delay  217  according to a signal of a condition select terminal  311  of the calculation controller  108  and supplies the selected signal to the first shift register  201 . 
     In RS(N, K, d) representing the RS code, N is a code word length, K is a data word length, and d is a minimum Hamming distance. One of the features of the RS code is that d=N−K+1. N−K designates the number of parities. Assuming that N−K is R, R=d−1. If the number of symbols which can be corrected by this RS code is t, then t=(d−1)/2. 
     A process of correcting the RS code is as follows. The syndrome is calculated from the received word by the syndrome calculator  101 . The error position polynomial is calculated from the syndrome by the error position polynomial calculator  103 . The error position is retrieved from the error position polynomial and the error value of the retrieved error position is calculated by the error position retrieval and error value calculator  105 . The error is corrected by adding the error position symbol to the error value by the error corrector  107 , thereby generating the corrected code word. 
     Assuming that the syndrome polynomial S(x)=S d−1 x d−2 +S d−2 x d−3 +. . . +S 0  and the error position polynomial is represented by:               (   X   )       =         ∏     i   =   0     v                     (     1   +       X   i        x       )       =          v            X     v   -   1       +   …   +             0                                
     (where Λ 0 =1 and the highest degree of the error position polynomial is less than or equal to t), and assuming that Λ(x)=1, B(x)=1 and γ=0, the Berlekamp-Massey algorithm for calculating the error position polynomial is executed by the following steps. 
     (a). Calculate a discrepancy Δ γ from the syndrome by the following equation (1):                Δ   γ     =       S   γ     +       ∑     j   =   1     t            ∫     j   =   1     γ            S     γ   -   j            (     =       ∑     γ   =   1     t               j          S     γ   -   j             )                     (   1   )                                
     (b). Calculate the error position polynomial, as represented by: 
     
       
         Λ(γ+1)( x )=Λ (γ) ( x )+Δ γ   xB   (γ) ( x )  (2) 
       
     
     (c). If Δ γ ≠0 and deg(B(x))≧deg(Λ(x)), then the correction polynomial B(x)=Δ γ   −1 Λ(x) and go to the following step (e). 
     (d). If Δ γ =0 or deg(B(x))≦degΛ(x), then B(x)=xB(x). 
     (e). Increase γ by 1 (that is, γ=γ+1), and if γ=d−1, complete the algorithm and if not, return to step (a). 
     The more detailed description will be given with reference to the above Berlekamp-Massey algorithm (BMA) and FIG.  2 . 
     The first, second and third shift registers  201 ,  203  and  205  store the correcting polynomial B(x), the error position polynomial Λ(x) and the syndrome polynomial S(x), respectively. The delay  217 , the next discrepancy storage unit  221  and the current discrepancy storage unit  223  consist of flip-flops for storing the symbol (usually, bytes). The delay  217  delays the output of the first shift register  201 . The next and current discrepancy storage units  221  and  223  store the next discrepancy and the current discrepancy, respectively. 
     The first, second and third operation cells  215 ,  213  and  219  are cells for the operation in the Galois field GF(2 m ). The first and second operation cells  215  and  213  of the same forms multiply two values through their multipliers M 2  and M 3  and add the multiplied results to another values through their adders A 2  and A 1 , respectively. The third operation cell  211  consisting of an inverse unit N 1  and a multiplier M 1  executes division by multiplying a reciprocal number of a received value by another value. The syndrome polynomial S(x) is applied to the third shift register  205 . The error position polynomial Λ(x) is applied to the second shift register  203 . A signal  411 , which is the output of the third operation cell  219 , is obtained by dividing the coefficient signal of the coefficient signal storage unit  227  by the current discrepancy of the current discrepancy storage unit  223 . A signal  414 , which is the output of the second operation cell  213 , is obtained by multiplying the current discrepancy of the current discrepancy storage unit  223  by a coefficient signal  413  generated from the first shift register  201  and then adding the multiplied value to a signal  417  generated from the second shift register  203 . 
     The first multiplexer  207  selects one of the inputs according to the signal of the condition select terminal  311  of the calculation controller  108 . That is, if the conditions of the step (c) of the above BMA are satisfied, the first multiplexer  207  selects the output signal  411  of the third operation cell  211 , and otherwise, it selects the output signal of the delay  217 . The second multiplexer  209  selects the input of the next discrepancy storage unit  221  for storing the intermediate value in order to calculate the discrepancy to be used for the next calculation according to the intermediate value storage select terminal  313  of the calculation controller  108 . At the first of a sub iterative period, the second multiplexer  209  selects the output of the fourth multiplexer  206 , and otherwise, it selects the output of the first operation cell  215 . The third multiplexer  211  selects the input of the current discrepancy storage unit  223  according to the signal of the current discrepancy input select terminal  315 . At the first of an iterative period, the third multiplexer  211  selects the signal of the syndrome coefficient terminal S( 0 ), and thereafter, it always selects the output of the first operation cell  215 . The fourth multiplexer  206  selects the syndrome signal to be sequentially input to the first operation cell  215  in order to calculate the discrepancy according to the signal of the syndrome select terminal  317  of the calculation control circuit  108 . The signal of the syndrome select terminal  317  is selected every main iterative period and fixed at the sub iterative period. At the first sub iterative period, the fourth multiplexer  206  selects syndromes S( 1 ) and S( 0 ), and at the second sub repeating period, it selects syndromes S( 2 ), S( 1 ) and S( 0 ). 
     In the error position polynomial calculator according to the present invention, the output of the delay  217  is initialized to 0, the first shift register  201  to  1  and the second shift register  203  to  1 . The calculation is iterated by 2t (main iterative period) and each main iterative period is iterated by t (sub-iterative period). At the first of the sub iterative period, the output of the delay  217  is always  0 , the output of the coefficient signal storage unit  227  is  1 , and the current discrepancy storage unit has the output of the first operation cell  215 . 
     Since t=2, it is assumed that there are 4 syndromes S( 3 ), S( 2 ), S( 1 ) and S( 0 ) in order to calculate the error position polynomial of the RS code which can correct a maximum of 2 errors. At the first of the main iterative period, the 4-bit ( 3 : 0 ) output of the third shift register  416  is S( 1 ), S( 2 ), S( 3 ) and S( 0 ); the 2-bit ( 1 : 0 ) output of the first shift register  201  is ( 0 ,  1 ); the output of the delay  217  is  0 ; the 3-bit ( 3 : 0 ) output of the second shift register  203  is ( 0 ,  0 ,  1 ); the output of the current discrepancy storage unit  223  is S( 0 ); and the output of the fourth multiplexer  206  is S( 1 ). If the current discrepancy S( 0 ) is 0, the first shift register  201  has its own value through the delay  217 . After the sub period, the first shift register  201  has a value obtained by multiplying the output of the first shift register  201  by x through the multiplier M 3  of the second operation cell  213 . The second shift register  203  maintains its own value. The third shift register  205  has the output of S( 3 ), S( 0 ), S( 1 ) and S( 2 ). 
     If the current discrepancy S( 0 ) is not 0, the first shift register  201  has a value obtained by dividing the value of the second shift register by the discrepancy. The second shift register  203  has a value obtained by multiplying the discrepancy by the value of the first shift register  201  and then adding the multiplied value to its own value. This has the effect of multiplying x by using the value of the second shift register  203  for the calculation. The third shift register  205  has the above result. The next calculation differs only in the process of calculating the discrepancy. A corresponding signal is selected in the first multiplexer  207  by the signal of the condition select terminal  311  of the calculation controller  108  depending on the conditions of the above step (c) or (d) of the BMA. The values of the first and second shift registers  201  and  203  are calculated as described above. 
     At the second main period, the fourth multiplexer  206  selects the syndrome S( 2 ). The discrepancy to be used for the next calculation is calculated by multiplying the syndrome S( 2 ) by the new coefficient of the second shift register  203  and then adding the multiplied value to the next discrepancy. At the first of this period, the current discrepancy storage unit  223  latches a discrepancy C( 0 )S( 1 )+C( 1 )S( 0 ) calculated in the first main period so as to be used for calculating the new error position polynomial. The next discrepancy calculated at the second main period is C( 0 )S( 2 )+C( 1 )S( 1 )+C( 2 )S( 0 ). The next discrepancy calculated at the third main period is C( 0 )S( 3 )+C( 1 )S( 2 )+C( 2 )S( 1 , and the current discrepancy is the discrepancy calculated at the second main period. Since the fourth main period is the last repeating process, there is no need to be concerned about the next discrepancy and the current discrepancy is the discrepancy calculated at the third main period. The error position polynomial is calculated after 8 (=4×2) clocks (4 main periods and 2 sub periods). 
     In FIG. 2, although the syndrome polynomial is loaded initially in parallel and outputted in parallel, it may be possible to serially load and serially output the syndrome polynomial as long as timing is permitted. 
     As described previously, the inventive circuit for calculating the discrepancy and calculating the error position polynomial using the discrepancy is small in circuit size and is rapidly operated by fast clocks (requiring 2t 2  clocks). 
     While the invention has been shown and described with reference to a certain preferred embodiment thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.