Abstract:
Forward error correction apparatus and methods are described. A forward errro correction method includes: (a) computing syndromes values; (b) computing an erasure location polynomial based upon one or more erasure locations; (c) computing modified syndromes based upon the computed erasure location polynomial and the computed syndrome values; (d) computing coefficients of an error location polynomial based upon the computed modified syndromes; (e) computing a composite error location polynomial based upon the computed coefficients of the error location polynomial; (f) computing a Chien polynomial based upon the computed composite error location polynomial; (g) performing a redundant Chien search on the computed composite error location polynomial to obtain error location values; and (h) evaluating the computed Chien polynomial based upon the error location values to obtain error and erasure values. A forward errro correction system includes: first and second simultaneously accessible memory locations; first, second and third register banks; and a micro-sequencer configured to choreograph a method of correcting errors and erases by coordinating the flow of data into the first and second memory locations and the first, second and third register banks.

Description:
[0001]    This is a divisional of U.S. Ser. No. 09/393,388, filed Sep. 10, 1999. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    This invention relates to apparatus and methods of forward error correction.  
           [0003]    Forward error correction techniques typically are used in digital communication systems (e.g., a system for reading information from a storage medium, such as an optical disk) to increase the rate at which reliable information may be transferred and to reduce the rate at which errors occur. Various errors may occur as data is being read from a storage medium, including data errors and erasures. Many forward error correction techniques use an error correction code to encode the information and to pad the information with redundancy (or check) symbols. Encoded information read from a storage medium may be processed to correct errors and erasures.  
           [0004]    Reed-Solomon (RS) encoding is a common error correction coding technique used to encode digital information which is stored on storage media. A RS (n, k) code is a cyclic symbol error correcting code with k symbols of original data that have been encoded. An (n-k)-symbol redundancy block is appended to the data The RS code represents a block sequence of a Galois field GF(2 m ) of 2 m  binary symbols, where m is the number of bits in each symbol. Constructing the Galois field GF(2 m ) requires a primitive polynomial p(x) of degree m and a primitive element β, which is a root of p(x). The powers of β generate all non-zero elements of GF(2 m ). There also is a generator polynomial g(x) which defines the particular method of encoding. A RS decoder performs Galois arithmetic to decode the encoded data. In general, RS decoding involves generating syndrome symbols, computing (e.g., using a Berlakamp computation process) the coefficients σ i  of an error location polynomial σ(x), using a Chien search process to determine the error locations based upon the roots of σ(x), and determining the value of the errors and erasures. After the error locations have been identified and the values of the errors and erasures have been determined, the original data that was read from the storage medium may be corrected, and the corrected information may be transmitted for use by an application (e.g., a video display or an audio transducer).  
         SUMMARY OF THE INVENTION  
         [0005]    In one aspect, the invention features a method of correcting errors and erasures, comprising: (a) computing syndromes values; (b) computing an erasure location polynomial based upon one or more erasure locations; (c) computing modified syndromes based upon the computed erasure location polynomial and the computed syndrome values; (d) computing coefficients of an error location polynomial based upon the computed modified syndromes; (e) computing a composite error location polynomial based upon the computed coefficients of the error location polynomial; (f) computing a Chien polynomial based upon the computed composite error location polynomial; (g) performing a redundant Chien search on the computed composite error location polynomial to obtain error location values; and (h) evaluating the computed Chien polynomial based upon the error location values to obtain error and erasure values.  
           [0006]    In another aspect, the invention features a system of correcting errors and erasures, comprising: first and second simultaneously accessible memory locations; first, second and third register banks; and a micro-sequencer configured to choreograph a method of correcting errors and erasures by coordinating the flow of data into the first and second memory locations and the first, second and third register banks.  
           [0007]    Embodiments may include one or more of the following features.  
           [0008]    The coefficients of the error location polynomial preferably are computed based upon a Berlakamp error correction algorithm.  
           [0009]    In one embodiment, the computed syndrome values are stored in RAM memory. The computed erasure location polynomial is stored in a first register bank. The modified syndromes are stored in RAM memory. The computed coefficients of the error location polynomial are stored in a second register bank. The computed composite error location polynomial is stored in the first register bank. The computed Chien polynomial is stored in a third register bank. The computed error location values are stored in RAM memory.  
           [0010]    Among the advantages of the invention are the following.  
           [0011]    The invention provides a scheme in which rate at which signals are decoded may be increased by storing the results of the above-described algorithms in registers rather than in memory. In one implementation, only sixteen registers are needed for performing the Chien search, and only eighteen registers are needed to implement Berlakamp&#39;s error correction algorithm. The invention provides hardware support that significantly increases the rate at which error and erasure polynomials may be computed using a relatively small number of hardware components. The invention therefore enables forward error correction techniques to be implemented in a high speed digital signal processing chip. The invention provides a relatively simple micro-sequencer-based forward error corrector design that may be implemented with a relatively small number of circuit components, and provides improved programming functionality.  
           [0012]    Other features and advantages will become apparent from the following description, including the drawings and the claims. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]    [0013]FIG. 1 is a block diagram of a system for reading encoded information from a storage disk.  
         [0014]    [0014]FIG. 2A is a block diagram of an error correction digital signal processor (DSP).  
         [0015]    [0015]FIG. 2B is a flow diagram of a cyclic three-buffer process for managing memory space in a method of correcting errors and erasures in an encoded block of data  
         [0016]    [0016]FIG. 3 is a diagrammatic view of an error correction code (ECC) block.  
         [0017]    [0017]FIG. 4 is a flow diagram of a method of identifying error locations and determining error and erasure values.  
         [0018]    [0018]FIG. 5 is a block diagram of a three-buffer method of computing an error location polynomial using the Berlakamp error correction algorithm.  
         [0019]    FIGS.  6 A- 6 C are block diagrams of a two-buffer method of computing an error location polynomial using the Berlakamp error correction algorithm.  
         [0020]    [0020]FIG. 7 is a flow diagram of a method of updating intermediate values required to implement the Berlakamp error correction algorithm.  
         [0021]    [0021]FIG. 8A is a block diagram of a multiplier for computing an erasure location polynomial.  
         [0022]    [0022]FIG. 8B is a block diagram of another multiplier for computing an erasure location polynomial.  
         [0023]    [0023]FIG. 9 is an apparatus for searching for the roots of a composite error location polynomial.  
         [0024]    FIGS.  10 A- 10 D are block diagrams of a method of computing errors and erasures. 
     
    
     DETAILED DESCRIPTION  
       [0025]    Referring to FIG. 1, a system  10  for reading encoded information from a storage disk  12  (e.g., a magnetic memory disk, a compact disk (CD), or a digital video disk (DVD)) includes a read head  14 , a demodulator  16 , an error correction digital signal processor (EC DSP)  18 , and an audio-video (AV) decoder  20 . In operation, read head  14  scans the surface of storage disk  12  and reads data stored on storage disk  12  with a magnetic transducer or an optical transducer. The data preferably is encoded with a RS cyclic redundancy code. Demodulator  16  extracts digital information from the signal produced by read head  14 . EC DSP  18  synchronizes to the extracted digital information, performs a 16-bit to 8-bit conversion and, as explained in detail below, corrects the extracted information based upon the redundant information encoded into the information stored on storage disk  12 . In particular, EC DSP  18  identifies error locations and determines the values of errors and erasures to correct the information read from storage disk  12 . AV decoder  20  generates audio and video data signals from the corrected data signal received from EC DSP  18 . The audio and video data signals may be transmitted to an application unit (e.g., a television or a computer) to present the audio and video signals to a user.  
         [0026]    As shown in FIG. 2A, data that is read from storage disk  12  enters EC DSP  18  as a RZ signal with sample clock or as an NRZ signal without a sample clock. The NRZ signal passes through a bit clock regenerator  22  which performs a clock recovery operation on the signal. EC DSP includes a multiplexor  24 , a first stage processor  26 , a subcode/ID processor  28 , a memory interface  30 , and an error corrector  32 . Multiplexor  24  transmits the data signal to first stage processor  26  that performs the processes of synchronization, demodulation, and deinterleaving. After these processes have been performed, first stage processor  26  loads one error correction code (ECC) block into memory (see FIG. 3). Memory interface  30  reads the ECC block from memory and calculates syndromes, which are passed to error corrector  32 . Error corrector  32  computes error locations and values and passes this information to memory interface  30 , which writes this information back into the memory locations from which memory interface  30  originally retrieved the erroneous data. Memory interface  30  descrambles the corrected data, checks the data for errors, and places the corrected data into a track buffer from which AV decoder  20  will receive the corrected data.  
         [0027]    Referring to FIG. 2B, memory interface  30  facilitates decoding in real time by cycling through three separate buffer locations as follows. At time T 0 , first stage processor  26  that performs the processes of synchronization, demodulation, and deinterleaving, and a first ECC block is stored in buffer  1  (step  40 ). At time T 1 :  
         [0028]    memory interface  30  reads the ECC block from buffer  1 , calculates syndromes and passes the syndromes to error corrector  32  (step  42 );  
         [0029]    memory interface  30  writes the corrected error information to the corresponding memory locations in buffer  1  (step  44 ); and  
         [0030]    a second ECC block is stored in buffer  2  (step  45 ).  
         [0031]    At time T 2 :  
         [0032]    memory interface  30  reads the ECC block from buffer  2 , calculates syndromes and passes the syndromes to error corrector  32  (step  46 );  
         [0033]    memory interface  30  writes the corrected error information to the corresponding memory locations in buffer  2  (step  48 );  
         [0034]    memory interface  30  descrambles the corrected data in buffer  1 , checks the data for errors, and places the corrected data into a track buffer from which AV decoder  20  will receive the connected data (step  50 ); and  
         [0035]    a third ECC block is stored in buffer  3  (step  51 ).  
         [0036]    At time T 3 :  
         [0037]    memory interface  30  reads the ECC block from buffer  3 , calculates syndromes and passes the syndromes to error corrector  32  (step  52 );  
         [0038]    memory interface  30  writes the corrected error information to the corresponding memory locations in buffer  3  (step  54 );  
         [0039]    memory interface  30  descrambles the corrected data in buffer  2 , checks the data for errors, and places the corrected data into a track buffer from which AV decoder  20  will receive the corrected data (step  56 ); and  
         [0040]    a third ECC block is stored in buffer  1  (step  57 ).  
         [0041]    At time T 4 :  
         [0042]    memory interface  30  reads the ECC block from buffer  1 , calculates syndromes and passes the syndromes to error corrector  32  (step  58 );  
         [0043]    memory interface  30  writes the corrected error information to the corresponding memory locations in buffer  1  (step  60 );  
         [0044]    memory interface  30  descrambles the corrected data in buffer  3 , checks the data for errors, and places the corrected data into a track buffer from which AV decoder  20  will receive the corrected data (step  62 ); and  
         [0045]    a third ECC block is stored in buffer  2  (step  63 ).  
         [0046]    The decoding of subsequent ECC blocks continues by cycling through the process steps of times T 2 , T 3  and T 4  (step  64 ).  
         [0047]    Referring to FIG. 3, the ECC block loaded into memory by first stage processor  26  includes a data block  70 , an RS PO block  72 , and an RS PI block  74 . Data block  70  consists of 192 rows of data, each containing 172 bytes (B ij ). RS PO block  72  consists of 16 bytes of parity added to each of the 172 columns of data block  70 . The parity was generated using a ( 208 ,  192 ) RS code and a generator polynomial given by  
           G   PO          (   x   )       =       ∏     i   =   0     15                     (     x   +     α   i       )                             
 
         [0048]    RS PI block  74  consists of 10 bytes of parity added to each of the  208  rows forming data block  70  and RS PO block  72 . The parity was generated using a ( 182 ,  172 ) RS code and a generator polynomial given by  
           G   PI          (   x   )       =       ∏     i   =   0     9                     (     x   +     α   i       )                             
 
         [0049]    For both the ( 208 ,  192 ) and ( 182 ,  172 ) RS codes, the primitive polynomial is given by P(x)=x 8 +x 4 +x 3 +x 2 +1. The resultant ECC block contains 37,856 bytes.  
         [0050]    Referring to FIG. 4, in one embodiment, error corrector  32  identifies error locations and determines values for errors and erasures as follows. Syndromes S i  are generated by memory interface  30  by evaluating the received data at α i  (step  80 ). If there are erasures present (step  82 ), an erasure location polynomial σ′(x) is computed, and a set of modified syndromes T i  is computed (step  84 ). Error location polynomial σ(x) is computed using Berlakamp&#39;s method (step  86 ). Error locations X L  are identified using a Chien search (step  88 ). Finally, Forney&#39;s method is used to identify error and erasure values Y L  (step  90 ).  
         [0051]    Each of the steps  80 - 90  is described in detail below.  
         [0052]    Generating Syndromes (Step  80 )  
         [0053]    Assuming that the transmitted code vector is v(x)=Σv j x j  (where j=0 to n−1) and that the read channel introduces the error vector e(x)=Σe j x j  (where j=0 to n−1), the vector received by error corrector  32  is given by r(x)=v(x)+e(x). The i th  syndrome is defined as S i =r(α i ). Accordingly, by evaluating the received signal r(x) at α i , each of the syndromes S i  may be generated  
         [0054]    No Erasures are Present (Step  82 )  
         [0055]    If no erasures are present (step  82 ; FIG. 4), error locations and error values may be determined as follows.  
         [0056]    Computing Error Location Polynomial (Berlakamp&#39;s Method) (Step  86 )  
         [0057]    The error location polynomial is given by σ(x)=Π(1+xX j )=Σσ j x j +1, where j=1 to t and X j  correspond to the error locations. Thus, the error locations X L  may be determined by identifying the roots of σ(x).  
         [0058]    Berlakamp&#39;s method is used to compute the coefficients σ i  of σ(x) based upon the generated syndrome values S i . In accordance with this approach, the following table is created with the values for the first rows entered as shown:  
                                     TABLE 1                           Berlakamp&#39;s Method            μ   σ μ (x)   d μ     I μ     μ − 1 μ                 −1   1   1   0   −1         0   1   S 0     0    0         1         2       . . .       2t                  
 
         [0059]    The remaining entries are computed iteratively one row at a time. The (u+1) th  is computed from the prior completed rows as follows:  
         [0060]    if d μ =0, then σ μ+1 (x)=σ μ (x) and l μ+1 =l μ ;  
         [0061]    if d μ ≠0, identify another row p which is prior to the μ th  row such that d p ≠0 and the number p−l p  (last column of Table 1) has the largest value, and compute the following:  
         [0062]    σ μ+1 (x)=σ μ (x)+d μ d p   −1 x μ−p σ p (x);  
         [0063]    l μ+1 =max(l μ , l p +μ−p);  
         [0064]    d μ+1 =S μ+1 +σ 1   μ+1 (x)S μ +σ 2   μ+1 (x)S μ−1 + . . . +σ 1μ+1   μ+1 (x)S μ−1−1μ+1    
         [0065]    The method is initialized with μ=0 and p=−1. The coefficients σ i  of σ(x) are computed by the time the bottom row of Table 1 has been completed because σ(x)=σ 2t (x).  
         [0066]    The above method may be implemented by maintaining σ μ+1 (x), σ μ (x), and σ p (x) in three registers, computing σ μ+1 (x) with one cycle updates, and computing d μ+1  with one hardware instruction.  
         [0067]    Referring to FIG. 5, in one embodiment, σ μ+1 (x), σ μ (x), and σ p (x) are maintained in three polynomial buffers  100 ,  102 ,  104  (8-bit wide registers). At time k, σ μ+1 (x) is stored in buffer  1 , σ μ (x) is stored in buffer  2 , and σ p (x) is stored in buffer  3 . At time k+1, σ μ+1 (x) is stored in buffer  2 , σ μ (x) is stored in buffer  1 , and σ p (x) is stored in buffer  3 . At the end of each iteration, the pointers for σ μ+1 (x), σ μ (x), and σ p (x) are updated to reflect the buffers in which the respective polynomials are stored. In this embodiment, the column values for d μ , l μ , and μ−l μ  are stored in RAM.  
         [0068]    Referring to FIG. 6A- 6 C, in another embodiment, σ μ+1 (x), σ μ (x), and σ p (x) are maintained in two registers  106 ,  108 ; the column values for d μ , l μ , and μ−l μ  are stored in RAM. With a software-controlled bank switch option, a customized hardware instruction may be used to update σ μ+1 (x) from σ μ (x) using registers  106 ,  108  as follows:  
         [0069]    (1) At time k, if d μ =0 and p−l p ≧μ−l μ , then σ μ+1 (x)=σ μ (x) and σ p (x) does not change. At time k+1, σ μ+1 (x) and σ μ (x) remain in their current buffers and d μ+1  is recomputed and saved to memory along with the value of (μ+1−l μ+1 ).  
         [0070]    (2) At time k, if d μ =0 and p−l p &lt;μ−l μ , then σ μ+1 (x)=σ μ (x) and σ p (x)=σ μ (x). At time k+1, the buffer containing σ p (x) at time k is updated with σ μ (x), d μ+1  is recomputed and saved to memory along with the value of (μ+1−l μ+1 ), and d p , l p , and p−l p  are updated in RAM (FIG. 6A)  
         [0071]    (3) At time k, if d μ ≠0 and p−l p l≧μ−l μ , then σ μ+1 (x)=σ μ (x)+d μ  d p   −1 x μ−p  σ p (x) and σ p (x)=σ p (x). At time k+1, the buffer containing σ μ (x) at time k is updated with σ μ (x)+d μ  d p   −1 x μ−p σ p (x) by updating the x 8  term in σ p (x) and progressing to x 0  (FIG. 6B). If the degree of x μ−p σ p (x)&gt;8, then an uncorrectable bit is set in a register.  
         [0072]    (4) At time k, if d μ ≠0 and p−l p &lt;μ−l μ , then σ μ+1 (x)=σ μ (x)+d μ  d p   −1 x μ−p σ p (x) and σ p (x)=σ μ (x). At time k+1, the buffer containing σ p (x) at time k is updated with σ μ (x)+d μ  d p   −1 x μ−p  σ p (x). Software triggers a bank swap  109  between the two buffers, whereby the physical meaning of the two buffers is swapped. This allows the buffers to be updated simultaneously without any intermediary storage space. The updating begins with the x 8  term in σ p (x) and progressing to x 0 . If the degree of x μ−p σ p (x)&gt;8, then an uncorrectable bit is set in a register (FIG. 6C).  
         [0073]    Referring to FIG. 7, d μ+1  is computed with a customized hardware instruction as follows. A register R 1  is initialized to l μ+1 (step  110 ). A register dmu_p 1  is initialized to S μ+1 (step  112 ). A pointer tmp_synd_addrs is initialized to point to the address of S μ (step  114 ). The value at the memory address identified in register tmp_synd_addrs is multiplied by the contents of X i  stored in the buffer which contains σ μ (step  116 ). The contents of register dmu_p 1  are added to the product of the result obtained in step  116  (step  118 ). The content of the register identified by the pointer tmp_synd_addrs is decremented (step  120 ). The value of I is incremented by 1 (step  122 ). The l μ+1  register is decremented by 1 (step  124 ). If the value contained in the l μ+1  register is zero (step  126 ), the process is terminated (step  128 ); otherwise, the value stored in register tmp_synd_addrs is multiplied by the contents of X i  stored in the buffer which contains σ μ (step  116 ) and the process steps  118 - 126  are repeated.  
         [0074]    At the end of the above-described process (step  86 ), row 2t of Table 1 contains the coefficients σ i  of the error location polynomial σ(x) (i.e., σ(x)=σ 2t (x)).  
         [0075]    Identifying Error Locations (Chien Search) (Step  88 )  
         [0076]    Once the coefficients σ i  of the error location polynomial σ(x) have been computed, the error locations X L  are determined by searching for the roots of σ(x) using conventional Chien searching techniques.  
         [0077]    Determining Error Values (Forney&#39;s Method) (Step  90 )  
         [0078]    Error values Y L  are computed from the error locations X L  and the syndromes S i  as follows:  
           Y   i     =       Ω        (     X   i     -   1       )           ∏     j   ≠   i                       (     1   +       X   j       X   i         )           ,                         
 
         [0079]    where Ω(x)=S(x)σ(x)(mod x 2t ) and  
         S        (   x   )       =       ∑     k   =   1       2      t              S     k   -   1              x     k   -   1       .                               
 
         [0080]    Erasures are Present (Step  82 )  
         [0081]    If erasures are present (step  82 ; FIG. 4), error locations and error and erasure values may be determined as follows.  
         [0082]    Computing Erasure Location Polynomial (Step  83 )  
         [0083]    An erasure location polynomial is defined as follows: 
         σ′( z )=Π( z+Z   j )=Σσ′ s−j   z   j +σ′ s ( j =1 to  s ), 
         [0084]    where s is the number of erasures present and Z i  are the known locations of the erasures. This expression may be rewritten as follows:  
                 σ   l          (   z   )       =                  (       z     s   -   1       +       Q     s   -   2            z     s   -   2         +     …                   Q   1        z     +     Q   0       )     ×     (     z   +     Z   s       )                   =                  z   s     +       (       Z   s     +     Q     s   -   2         )          z     s   -   1         +       (         Q     s   -   2            Z   s       +     Q     s   -   3         )          z     s   -   2         +   …                                  (         Q   1          Z   s       +     Q   0       )        z     +       Q   0          Z   s                                     
 
         [0085]    Referring to FIG. 8A, in one embodiment, this expression for the erasure location polynomial σ′(x) is computed recursively with s 8-bit wide registers  130 . In operation, the following steps are performed: (a) an erasure location and the output of a given register in a series of k registers are multiplied to produce a product; (b) if there is a register immediately preceding the given register in the series of registers, the product is added to the output of the preceding register to produce a sum; (c) the sum (or the product, if a sum was not produced) is applied to the input of the given register; (d) steps (a)-(c) are repeated for each of the registers in the series; (e) each of the registers in the series is clocked to transmit register input values to register outputs; and (f) steps (a)-(e) are repeated for each of the erasure locations. The output of a first register is initialized to 1, and the outputs of the remaining registers is initialized to 0.  
         [0086]    Referring to FIG. 8B, in another multiplier embodiment, a customized hardware instruction may be used to compute σ′(x) using one multiplier  132  and one adder  134 . In operation, the following steps are performed: (a) an erasure location is applied to an input of a input register; (b) an output of a given register in a series of registers and an output of the input register are multiplied to produce a product; (c) the product and an output of the dummy register are added to produce a sum; (d) the sum is applied to an input of a subsequent register immediately following the given register; (e) the subsequent register is treated as the given register and steps (a)-(d) are repeated for each of the erasure locations. For example, the multiplier may be cycled as follows:  
         [0087]    cycle 1: initialize all registers to 1 and dummy register  136  to 0; set D 0 =Z 1  and sel=0;  
         [0088]    cycle 2: set Q 0 =Z 1 ; set D=Z 2 ;  
         [0089]    cycle 3: set Z 5 =Z 2  and D=Z 3 ;  
         [0090]    cycle 4: set Q i−1 =Q 0 , Q 0 =D 0 , and sel=1;  
         [0091]    cycle 5: set Q 1 =D 1 , sel=0, Z 5 =Z 3 , and D=Z 4 .  
         [0092]    The performance of cycles 1-5 results in the computation of two erasure multiplications. Q 2 , Q 1  and Q 0  now hold the second degree erasure polynomial whose roots are Z 1  and Z 2 . Additional multiplications may be computed by continuing the sequence of cycles.  
         [0093]    The erasure location polynomial σ′(x) is used to compute modified syndrome values T i  as follows.  
         [0094]    Computing Modified Syndromes (step  84 )  
         [0095]    The modified syndromes T i  are defined as follows:  
         T   i     =         ∑     j   =   0     s            σ   j   l          S     i   +   s   -   j                     for                 0       ≤   i   ≤       2      t     -   s   -   1                             
 
         [0096]    Software running on the micro-sequencer may load σ j ′, S i+s−j  from memory and perform the multiplication and accumulation. Th expression for T i  may be rewritten as:  
           T   i     =       ∑     m   =   1     α            E   m          X   m   i           ,       for                 0     ≤   i   ≤       2      t     -   s   -   1                             
 
         [0097]    where E m =Y m σ′(X m ), α corresponds to the number of errors, the values X m  correspond to the unknown error locations, and the values Y m  corresponds to the unknown error and erasure values.  
         [0098]    The modified syndrome values T i  may be used to compute the coefficients σ i  of the error location polynomial σ(x).  
         [0099]    Computing Error Location Polynomial (Berlakamp&#39;s Method) (Step  86 )  
         [0100]    Because the modified syndromes represent a system of equations that are linear in E i  and nonlinear in X i , Berlakamp&#39;s method (described above; step  86 ) may be used to compute the coefficients σ i  of the error location polynomial σ(x) from the modified syndromes T i  based upon the substitution of the modified syndrome values T i  for the syndrome values S i .  
         [0101]    At the end of the process (step  86 ), Table 1contains the coefficients σ i  of the error location polynomial σ(x).  
         [0102]    Identifying Error Locations (Chien Search) (Step  88 )  
         [0103]    Once the coefficients σ i  of the error location polynomial σ(x) have been computed, the error locations X L  may be determined by searching for the roots of σ(x) using conventional Chien searching techniques.  
         [0104]    In an alternative embodiment, the error locations X L  are determined by searching for the roots of a composite error location polynomial σ″(x)=x 5 σ′(x −1 )σ(x) using conventional Chien searching methods. This approach simplifies the hardware implementation needed to compute the error and erasure values.  
         [0105]    During the Chien search, the following expressions are evaluated and tested for zero: 
         σ″(α −0 )=σ″(1)=σ″ 16 +σ″ 15 + . . . +σ″ 1 +σ″ 0   
         σ″(α −1 )=σ″(α 254 )=σ″ 16 α 254x16 +σ″ 15 α 254x15 + . . . +σ″ 1 α 254x1 +σ″ 0   
         σ″(α −2 )=σ″(α 253 )=σ″ 16 α 253x16 +σ″ 15 α 253x15 + . . . +σ″ 1 α 253x1 +σ″ 0   
         σ″(α −207 )=σ″(α 48 )=σ″ 16 α 48x16 +σ″ 15 α 48x15 + . . . +σ″ 1 α 48x1 +σ″ 0   
         [0106]    Referring to FIG. 9, a circuit  140  may be used to evaluate the above expression. Circuit  140  is initialized to σ″ 16 , σ″ 15 , . . . , σ″ 0 . In one operation, σ″(1) is obtained. During the first 47 clocking cycles a root counter  144  is monitored for new roots and, when a new root is detected, a bit flag is set to high, indicating that an uncorrectable error has occurred. Each clock cycle from clock number  48  through clock number  254  generates σ″( 48 ) through σ″( 254 ). After the 254 th  cycle, firmware identified a data block as uncorrectable if: (1) the bit flag is set to high; or (2) value of root counter  144  does not equal v+s, where v is the power of σ″(x) and s is the number of erasures.  
         [0107]    In an alternative embodiment, the σ″ 0  register is not included and, instead of testing against zero, the sum of the remaining registers is tested against 1.  
         [0108]    At the end of the above-described process (step  88 ), the error locations X L  have been identified. By performing a redundant Chien search on the composite error location polynomial σ″(x), computation time and implementation complexity may be reduced relative to an approach that performs a Chien search on the error location polynomial σ(x) because this redundant Chien search provides (through the “to Forney” signal) the value of the denominator σ″ 0 (X L   −1 ) for the error and erasure values Y L , as described in the following section.  
         [0109]    Determining Error and Erasure Values (Forney&#39;s Method) (Step  90 )  
         [0110]    The error and erasure values Y L  are computed from the error locations X L , the syndromes S i  and a composite error location polynomial σ″(x) as follows:  
           Y   i     =       Ω        (     X   i     -   1       )           ∏     j   ≠   i                       (     1   +       X   j       X   i         )           ,                         
 
         [0111]    where Ω(x)=S(x)σ″(x) (mod x 2t ), S(x)=ΣS k−1 x k−1 , and σ″(x)=x s σ′(x −1 )σ(x). This expression may be rewritten as follows. Assuming τ=v+s, σ″(x) may be rewritten as:  
           σ   ll          (   x   )       =           σ   τ          x   τ       +       σ     τ   -   1            x     τ   -   1         +   …   +       σ   1          x   1       +     σ   0       =       ∏     j   =   1     τ                     (     1   +       X   j        x       )                               
 
         [0112]    Based upon this result, the erasure value polynomial evaluated at σ″(x) and σ″(X L   −1 ) (i.e., D x (σ″(x)) and D x (σ″(X L   −1 ))) may be given by:  
           D   x          (       σ   ll          (   x   )       )       =         ∑     L   =   1     τ            ∏     j   ≠   L                           X   L          (     1   +       X   j        x       )                     and                     D   x          (       σ   ll          (     X   L     -   1       )       )             =       X   L            ∏     j   ≠   L            (     1   +       X   j       X   L         )                                 
 
         [0113]    The erasure location polynomial σ″(x) may be rewritten in terms of its odd σ o ″ and even σ e ″ components: σ″(x)=σ o ″(x)+σ e ″(x), where σ o ″(x)=σ 1 ″x+σ 3 ″x 3 + . . . and σ o (x)=σ 0 ″+σ 2 ″x 2 + . . . Now, since the erasure value polynomial evaluated at σ″(x) may be rewritten as: D x (σ″(x))=σ″ 1 +σ″ 3 x 2 +σ″ 5 x 4 + . . . , the following expression is true: 
           X   L   −1   D   x (σ″( X   L   −1 ))=σ″ 1   X   L   −1 +σ 3   ″X   L   −3 +σ 5   ″X   L   −5 + . . . =σ o ″( X   L   −1 ) 
         [0114]    Accordingly,  
           σ   o   ″          (     X   L     -   1       )       =       ∏     j   ≠   L              (     1   +       X   j       X   L         )     .                             
 
         [0115]    Thus, the error and erasure values Y L  may be given by:  
         Y   L     =       Ω                   (     X   L     -   1       )           σ   o   ″          (     X   L     -   1       )                               
 
         [0116]    The denominator of the above expression is obtained from the “to Forney” signal of FIG. 9. The numerator may be computed by initializing the flip flops  142  in FIG. 9 with the values of Ω i  rather than the values of σ i ; the values of Ω i  may be computed by software running on the micro-sequencer.  
         [0117]    Memory Management  
         [0118]    The rate at which signals are decoded may be increased by storing the results of the above-described algorithms in registers rather than in memory. In the following implementation, only sixteen registers are needed for performing the Chien search, and only eighteen registers are needed to implement Berlakamp&#39;s method (described above) for computing the coefficients σ i  of the error location polynomial σ(x) from the modified syndromes T i . In this implementation, a micro-sequencer issues instructions that execute the decoding process and coordinate the flow of data into the registers and memory locations.  
         [0119]    Referring to FIGS.  10 A- 10 D, in one embodiment, errors and erasures may be computed by error corrector  32  implementing one or more of the above-described methods as follows. The following description assumes that errors and erasures are present in the received EC data block. In accordance with this method, error corrector  32  performs the following tasks serially: (1) compute the erasure location polynomial σ′(x) for erasures; (2) compute the modified syndromes T i ; (3) perform Berlakamp&#39;s method to obtain the coefficients σ i  of the error location polynomial σ(x); (4) compute the composite error location polynomial σ″(x); (5) compute the Chien polynomial Ω(x); (6) perform a redundant Chien search on σ″(x) to obtain the error locations X L ; and (7) evaluate Ω(X L   −1 ) to obtain the error and erasure values Y L .  
         [0120]    As shown in FIG. 10A, based upon the predetermined erasure locations, which are stored in RAM memory  200 , the coefficients  201  of the erasure location polynomial σ′(x) are computed and stored in register bank  202  (step  204 ). The modified syndromes T i  are computed based upon the coefficients of σ′(x) and the syndrome values  205  (S i ) which are stored in RAM memory  206  (step  208 ); the modified syndromes T i  are stored in RAM memory  210 . The modified syndromes T i  are used to compute the coefficients  211  of error location polynomial σ(x) (step  212 ); these coefficients are stored in register bank  214  and in RAM memory  216 .  
         [0121]    Referring to FIG. 10B, composite error location polynomial σ″(x) (=x s σ′(x −1 )σ(x)) is computed based upon the stored coefficients  211  of the error location polynomial σ(x) and the stored coefficients  201  of the erasure location polynomial σ′(x) (step  218 ). The coefficients of σ″(x) are computed in software and are stored in RAM memory  216  and in register bank  202 . The Chien polynomial Ω(x) (=S(x)σ″(x)) is computed based upon the stored coefficients  220  of σ″(x) and the stored syndrome values  205  (S i ) (step  222 ). The computed coefficient values  224  of Ω(x) are stored in register bank  226 .  
         [0122]    As shown in FIG. 10C, a Chien search is performed (step  228 ). During the Chien search, the values  232 ,  234  of log α (X L   −1 ) (Chien locations) and σ o ″(X L   −1 ) are computed, respectively. The values  232  log α (X L   −1 )) are written to RAM memory location  200 . The inverses of values  234  (σ o ″(X L   −1 )) are computed and stored in memory location  216  (step  236 ).  
         [0123]    Referring to FIG. 10D, the coefficient values  224  of Ω(x) are written from register bank  226  to register bank  202 . The values  238  (log α (X L+1 /X L )) are clocked into register bank  202  (step  240 ). The errors and erasures values Y L  are computed by multiplying the inverse of the composite error location polynomial evaluated at error location X L  and the Chien polynomial values evaluated at X L  (step  242 ):  
         Y   L     =       Ω                   (     X   L     -   1       )           σ   o   ″                     (     X   L     -   1       )                               
 
         [0124]    The computed error and erasure values Y L  are stored in RAM memory  210 .  
         [0125]    Other embodiments are within the scope of the claims