Decoder for error correcting block codes

[0002] This invention relates to error correcting code techniques.

[0003] Error correcting code techniques are used in digital systems to correct and detect errors in digital data. Such techniques are particularly employed with magnetic disks which typically have relatively high rates of error due to manufacturing defects and so forth. Several types of error correcting techniques are known. One type of error correcting technique uses so-called “block codes.” Two examples of block codes are the so called “Reed Solomon” (RS) code and “Bose-Chaudhuri-Hocquenghem” (BCH) code.

[0004] Block codes such as “Reed Solomon” and “Bose-Chaudhuri-Hocquenghem”, operate on data symbols. Data symbols are vectors of binary bits of data. Symbols are generated by grouping bits at a particular bit position for a group of words into a vector. When block codes are used in a disk drive, before a string of data symbols are recorded on a disk, the string is mathematically encoded producing error correcting code symbols that are appended to the data symbols to form code words. These code words i.e., data symbols and error correcting code symbols are stored on the disk. When the stored data is retrieved from the disk, the code words are mathematically decoded to form decoded code words.

[0005] In order to correct errors, the locations and magnitudes or values of the errors are needed. A conventional approach for determining the location of such errors uses a decoder including a syndrome generator to form error syndromes. The error syndromes are used to generate an error location polynomial and the error location polynomial is used to determine an error location. The conventional approach uses a single Chien search circuit to search for roots of the error location polynomial. The Chien search circuit evaluates the error location polynomial for all possible error locators by iteratively evaluating the error location polynomial “n” times, where n is the code length. This is a time consuming process when n is large and the code rate is high.

[0006] The roots of the error location polynomial (i.e., when the error location polynomial is zero) correspond to the location of the errors in the code word. An error evaluation polynomial is evaluated to determine error values based on the determined error locations. Once the error locations and the corresponding error values are known, the data can be corrected.

[0007] According to an aspect of the invention, a decoder for decoding block error correction codes includes a first search circuit to find roots of an error location polynomial corresponding to an error location and a second search circuit to find roots of an error location polynomial corresponding to an error location. A multiplexer is fed by the first search circuit and the second search circuit to produce an error location from the error location polynomial.

[0008] According to a further aspect of the invention, a decoder for decoding block codes includes a parallel error location polynomial search circuit. The parallel error location search circuit includes a first search circuit that finds roots of an error location polynomial that correspond to an error location. The circuit includes a first modulo adder circuit that adds odd terms of the error location polynomial to produce a derivative of the error location polynomial. The circuit also includes a second search circuit that finds roots of an error location polynomial that correspond to an error location. A second modulo adder circuit adds odd terms of the error location polynomial to produce a derivative of the error location polynomial. The circuit also includes a first multiplexer fed by error location outputs from the first search circuit and the second search circuit, a second multiplexer fed by derivatives of error location outputs from the first and the second modulo adders. The circuit also includes an error evaluation circuit that produces the error evaluator polynomial and a logic circuit including a divider circuit to divide the error evaluator polynomial by the output from the second multiplexer.

[0009] According to a still further aspect of the invention, a method of decoding an error correcting block code includes evaluating an error location polynomial produced from an error location polynomial generation circuit by applying the error location polynomial to a parallel root search circuit that searches for roots of the error location polynomial in a parallel manner.

[0010] One or more advantages are provided by the above aspects. The two-way parallel root search circuit searches for roots of the error location polynomial in a parallel manner. This saves substantial computation time to facilitate real time decoding of high rate Reed Solomon and BCH codes. For example, a two-way parallel root search circuit can use two duplicate root search circuits to reduce the search time to determine the roots of an error-locator polynomial by half. An additional advantage of the arrangement is that the parallel root search circuit can be modified to provide a term that can be used with an error evaluator without the need to compute a derivative of the error location polynomial.

[0011] FIG. 1 is a block diagram of a computer including a storage device.

[0012] FIG. 2 is a block diagram of an error correction apparatus for the storage device of FIG. 1.

[0013] FIG. 3 is a block diagram of an error correction detection circuit.

[0014] FIGS. 4 and 5 are block diagrams of parallel error search circuits.

[0015] FIGS. 6 and 7 are block diagrams of multi-way error search circuits.

[0016] FIGS. 8 and 9 are block diagrams of parallel search circuits and error evaluator circuits.

[0017] FIG. 10 is a detailed diagram of the error search and evaluator circuit of FIG. 8.

[0018] FIG. 11 is a block diagram of a generalized U-way error search and evaluator circuit.

[0019] FIG. 12 is a block diagram of an initializer circuit.

[0020] FIG. 13 is a block diagram of an error evaluator circuit.

[0021] Referring now to FIG. 1, a computer system 10 includes a processor 12, a main memory 14 and a magnetic storage subsystem 15, all coupled via a computer bus 16. The magnetic storage system 15 includes a bus adapter 18, a storage bus 19 and a storage device 20. A preferred example of the storage device 20 is a magnetic disk. Other examples include a magnetic tape drive and a solid state disk.

[0022] The storage device 20 includes an error correcting code symbol generator 22 and an error correction circuit 24, as well as, a disk drive 26.

[0023] Referring now to FIG. 2, a portion of the storage device 20 is shown including the error correcting code generator 22. The error correcting code generator 22 is fed input data from the bus adapter 18 and generates error correcting code symbols. During a write to disk operation, the error correcting code symbols are concatenated with data symbols and fed to a disk interface 23 for storage on the disk drive 26 (FIG. 1). During a read from disk operation, the data from the disk 26 are fed to the disk interface 23 and to an error correction circuit (EC) 24. The EC circuit 24 uses a parallel decoding technique in order to correct the errors. The EC circuit 24 corrects such errors providing they do not exceed the capability of the EC circuit 24.

[0024] Referring now to FIG. 3, details of the error correction circuit 24 are shown. A syndrome generator 30 produces error syndromes from results of “exclusive ORing” retrieved error correcting code symbols in a conventional manner. The syndromes are fed to an error location polynomial circuit 32 to produce an error locator polynomial σ. The roots of the error location polynomial are determined in a two-way, parallel root search circuit 34. The roots of the error location polynomial, if any, correspond to the error locations, if any, in the codewords. The evaluator circuit 36 evaluates the errors at the locations identified by the parallel root search circuit 34. As will be described below, optionally, the error evaluator and root search circuits can share circuits.

[0025] The two-way parallel root search circuit 34 searches for roots of the error location polynomial σ in a parallel manner. This saves substantial computation time to facilitate real time decoding of high rate Reed Solomon and BCH codes. The two-way parallel root search circuit 34 implements a variation of the so-called “Chien” search algorithm.

[0026] A Chien search algorithm evaluates an error location polynomial using Galois field (GF) arithmetic. Considering an m bit symbol of a Reed Solomon code of length 2^m−1, such a symbol can be considered to be an element “α” defined in the Galois field GF(2^m). If α is a primitive element of the Galois field GF(2^m) then the possible error locations in the multi-bit symbol are in the set of {1, α, . . . αⁿ⁻¹}. The value α is a primitive element if α can generate all of the values of the field except 0. If σ(x) is an error location polynomial that contains k error locations, namely, α^t1, α^t2, . . . α^tk−1and α^tkthen

[0027] σ(χ)=(α^t1χ−1)(α^t2χ−1) . . . (α^tk−1χ−1)(α^tkχ−1)=σ_kχ^k+σ_k−1χ^k−1+ . . . +σ₁χ+σ₀

[0028] The error locations α^αjare found from the given coefficients σ_i, i=0, . . . , k. The simplest way to find an error-location from σ(χ) is by trial and error, i.e., by evaluating σ(χ) for all possible values i.e., χε{1, α⁻¹, . . . , α⁻⁽ⁿ⁻¹⁾}, where σ(α⁻¹⁾⁼0, α⁻¹corresponds to an error location. The Chien search is an implementation of this trial and error method in an orderly manner.

[0029] Consider the evaluation of σ(χ) with α^−jfor j≧0. Every possible value of α^−jis evaluated as:

[0030] σ(α^−j)=σ_kα^−kj+σ_k−1α^−(k−1)j+ . . . +σ₁α^−j+σ₀

[0031] The order of trials can be either in ascending order or in descending order of j. For an ascending order search, the expression σ(α^−j) is evaluated to find error locations by iterating from 0 to n−1. Given a bank of registers reg_k(j) to reg₀(j), and denoting reg_i(j)=σ_iα^−ijprovides

[0032] σ(α^−j)=reg_k(j)+reg_k−1(j)+ . . . +reg₁(j)+reg₀(j)

[0033] where reg_i(j) can be considered as the i-th register value in registers reg_k(j) to reg₀(j) at iteration cycle j. Reg_i(j) can be obtained iteratively from the value of the same register in the previous iteration cycle, i.e.,

[0034] reg_i(j)=α⁻ⁱreg_i(j−1) for j≧1

[0035] The initial values of these registers are:

[0036] reg_i(0)=σ_ifor i=0, . . . k

[0037] A Chien search can also be performed in a descending order. For a descending order search the expression a is iteratively evaluated from n−1 to 0.

[0038] The error location polynomial evaluated from n−1 to 0 can be expressed as:

[0039] σ(α^{−(n−1−j)})=σ_kα^{−k(n−1−j)}+σ_k−1α^{−(k−1)(n−1−j)}+ . . . +σ₁α^{−n−1−j)}+σ₀

[0040] By defining

[0041] reg_i(j)=σ_iα^{−i(n−1−j)}=(αⁱ⁽¹⁻ⁿ⁾σ_i)α^ij

[0042] we have

[0043] σ(α^{−(n−1−j)})=reg_k(j)+reg_k−1(j)+ . . . +reg₁(j)+reg₀(j)

[0044] where the initial value of the register reg_iis

[0045] reg_i(0)=αⁱ⁽¹⁻ⁿ⁾σ_i

[0046] and the iterative relation is

[0047] reg_i(j)=αⁱreg_i(j−1) for j≧1

[0048] An “n” number of iterations are performed to evaluate the error location polynomial, where n is the code length. When n is large, the number of the iterations may be too large for real-time hardware decoding.

[0049] Referring now to FIG. 4, the two-way parallel root search circuit 34 is shown. The two-way parallel search circuit 34 includes a first search circuit 34acomprised of a series of multipliers 40 and a first bank of registers 42 that feed results on an iterative basis to a bank of “exclusive OR” gates 44. The banks of exclusive OR gates 44 and 45 are fed by register 0 REG (0) 47. The bank of exclusive or gates 44 “exclusive OR's” (i.e., adds modulo 2) the outputs of register 47 and the register bank 42.

[0050] The two-way parallel root search circuit 34 includes a second search circuit 34bcomprised of multipliers 41 and a second bank register 43 that also evaluate the error polynomial on an iterative basis. The outputs of the second bank of registers 43 are coupled to a second bank of exclusive OR gates 45 to evaluate the results from the second bank of registers 43.

[0051] The output of exclusive OR gate banks 44 and 45 are fed to a multiplexer 48 that is controlled by a select signal (not shown) that alternately selects one of the search circuits 34a, 34b, as an output each cycle of the decoder 34. When the multiplexer 48 outputs a logic zero, this corresponds to a root of the error location polynomial.

[0052] The two-way parallel root search circuit 34 reduces the number of search iterations and, as a consequence, the amount of search time, needed to find the roots of the error location polynomial. The two-way parallel search circuit uses a pair of chains each chain having different initial values and multiplier coefficients. The initial values for each chain are derived as follows:

[0053] Let v be any integer such that 0≦v≦n−1, then

[0054] v=2j+l

[0055] with l=0 or 1 and 0≦j≦(n−1)/2.

[0056] For a two-way parallel root search from 0 to n−1, σ(α^−v) the v^throot of the error location polynomial is given by: $\begin{array}{c}\sigma \left({\alpha }^{-v}\right)={\sigma }_k{\alpha }^{-k\left(2j+1\right)}+{\sigma }_{k-1}{\alpha }^{-\left(k-1\right)\left(2j+1\right)}+\dots +{\sigma }_1{\alpha }^{-\left(2j+1\right)+{\sigma }_0}\\ =\left({\alpha }^{-\mathrm{lk}}{\sigma }_k\right){\alpha }^{-2kj}+\left({\alpha }^{-l\left(k-1\right)}{\sigma }_{k-1}\right){\alpha }^{-2\left(k-1\right)j}+\dots +\\ \left({\alpha }^{-1}{\sigma }_1\right){\alpha }^{-2j}+{\sigma }_0\\ =\sum _{i=0}^k\left({\alpha }^{-\mathrm{il}}{\sigma }_i\right){\alpha }^{-2\mathrm{ij}}\end{array}$

[0057] by defining

[0058] reg_i⁽⁰⁾(j)=σ_iα^−(2i)jand reg_i⁽¹⁾(j)=(α⁻ⁱσ_i)α^−(2i)j

[0059] σ can be expressed in two different chains and is given, as in Equations 1 and 2:

[0060] σ(α^−(2j))=reg_k⁽⁰⁾(j)+reg_k−1⁽⁰⁾(j)+ . . . +reg₁⁽⁰⁾(j)+reg₀⁽⁰⁾(j)  (Equation 1)

[0061] and

[0062] σ(α^−(2j+1))=reg_k⁽¹⁾(j)+reg_k−1⁽¹⁾(j)+ . . . +reg₁⁽¹⁾(j)+reg₀⁽¹⁾(j)  (Equation 2)

[0063] for 0≦j≦(n−1)/2. Moreover, the values of the registers 42 (reg_i⁽⁰⁾) 42 and registers 43 (reg_i⁽¹⁾) have the same iterative relations for 0≦j≦(n−1)/2, as given in equations 3 and 4.

[0064] reg_i⁽⁰⁾(j)=α⁻²ⁱreg_i⁽⁰⁾(j−1)  (Equation 3)

[0065] reg_i⁽¹⁾(j)=α⁻²ⁱreg_i⁽¹⁾(j−1)  (Equation 4)

[0066] The initial values of these two banks 42, 43 of registers are:

[0067] register 42 reg_i⁽⁰⁾(0)=σ_iand

[0068] register 43 reg_i⁽¹⁾(0)=α⁻ⁱσ_i

[0069] The values of reg_i⁽⁰⁾(j) and reg_i⁽¹⁾(j) can be computed independently. The two-way parallel root search circuit 34 uses two duplicate root search circuits 34a, 34bwhich have different initial values in registers 42, 43. This parallel circuit 34 reduces the search time to determine the roots of the error-locator polynomial by half. The initial values of reg_i⁽⁰⁾registers 42 are provided by the error-locator polynomial coefficients σ_i, whereas an initializer 50 converts the initial values of reg_i⁽⁰⁾registers 43 to those of reg_i⁽¹⁾. The initializer 50 is described in conjunction with FIG. 12. The initial values for the registers are given in TABLE 1:

[0070] Referring now to FIG. 5, a parallel two-way root search circuit 34′ that searches from n−1 to 0 is illustrated. The circuit 34′ has a similar structure to circuit 34. Circuit 34′ therefore includes a first search circuit 34a′ including multipliers 40′, registers 42′, an “exclusive OR” bank 44, and a second search circuit 34b′ including multipliers 41′, registers 43′ and an “exclusive OR” bank 45′. The search circuit 34′ includes a register (0) 47′ and a multiplexer 48′. Multiplexer 48′ is controlled by a select signal (not shown) that alternately selects one of the search circuits 34a, 34b, as an output for each cycle of the decoder 34′. Circuit 34′ differs from circuit 34 (FIG. 4) in that the coefficients used to multiply the contents of registers are different and the initial values in registers 42′, 43′ are also different, as illustrated in the accompanying TABLE 2.

[0071] The two-way parallel root search 34′ from n−1 to 0 can be explained, as follows. For circuit 34′, the initial values of the two sets of registers 42′, 43′ reg_i⁽⁰⁾and reg_i⁽¹⁾are:

[0072] reg_i⁽⁰⁾(0)=α⁽¹⁻ⁿ⁾ⁱσ_iand reg_i⁽¹⁾(0)=α⁽²⁻ⁿ⁾ⁱσ_i

[0073] and the iteration relations are:

[0074] reg_i^(l)(j)=α²ⁱ

[0075] reg_i^(l)(j−1)

[0076] for 0≦j≦(n−1)/2. The error location polynomial σ is given by equation 5:

[0077] σ(α^{−(n−2j−l)})=reg_k^(l)(j)+reg_k−1^(l)(j)+ . . . +reg₁^(l)(j)+reg₀^(l)(j)  (Equation 5)

[0078] for 0≦j≦(n−1)/2, where l=0 and 1.

[0079] Referring now to FIGS. 6 and 7, generalized U-way parallel root search circuits 60 and 60′ are shown for search directions 0 to n−1 60 (FIG. 6) and for n−1 to 060′ (FIG. 7), respectively. As shown in FIG. 6, the U-way parallel search circuit 60 includes a plurality of (U number of) root search circuits 34₀-34_u−1, each evaluating one of the iterations for n and each comprising a plurality of registers/multiplier combinations. Each one of the search circuits 34a-34uincludes a bank of “exclusive OR” gates, as generally shown for bank 34aor 34a′, respectively. The outputs of the root search circuits 34₀-34_u−1are fed to a multiplexer 49 that is controlled by a select signal (not shown) that alternately selects one of the inputs as an output each cycle of the decoder. When the multiplexer 49 outputs a logic zero, this corresponds to a root of the error location polynomial.

[0080] The generalized U-way search circuit can be explained as follows: If u is a positive integer, then for any integer v where 0≦v≦n−1,

[0081] v=uj+l

[0082] with l ε{0,1, . . . , u−1} and 0≦j≦(n−1)/u. The error location polynomial is given by: $\begin{array}{c}\sigma \left({\alpha }^{-v}\right)={\sigma }_k{\alpha }^{-k\left(\mathrm{uj}+l\right)}+{\alpha }_{k-1}{\alpha }^{-\left(k-1\right)\left(\mathrm{uj}+l\right)}+\dots +{\sigma }_1{\alpha }^{-\left(\mathrm{uj}+l\right)}+{\sigma }_0\\ =\sum _{i=0}^k{\alpha }^{-\mathrm{il}}{\sigma }_i{\alpha }^{-\mathrm{iuj}}\end{array}$

[0083] A U-way parallel root search from 0 to n−1 also can be provided. For branches l=0, . . . , u−1, registers reg_i^(l)can be defined with the initial values, as given in equation 6.

[0084] reg_i^(l)(0)=α^−ilσ_i  (Equation 6)

[0085] The iterative relation for the registers is given by equation 7 as:

[0086] reg_i^(l)(j)=α^−iureg_i^(l)(j−1), 0≦j≦(n−1)/u  (Equation 7)

[0087] Thus, for branches l=0,1, . . . , u−1, the error location polynomial is given by equation 8 as:

[0088] σ(α^−(uj+l))=reg_k^(l)(j)+reg_k−1^(l)(j)+ . . . +reg₁^(l)(j)+reg₀^(l)(j)  (Equation 8)

[0089] with 0≦j≦(n−1)/u.

[0090] Referring now to FIG. 7, a u-way parallel Chien search from n−1 down to 0 can be provided based on the teachings set out above.

[0091] For the branches l=0, . . . , u−1, registers reg_i^(l)can be defined with the initial values, as given in equation 9.

[0092] reg_i^(l)(0)=α^(l+1−n)iσ_i  (Equation 9)

[0093] The iterative relation is thus given by equation 10 as:

[0094] reg_i^(l)(j)=α^iureg_i^(l)(j−1), 0≦j≦(n−1)/u.  (Equation 10)

[0095] Then, for branches l=0,1, . . . , u−1, the error location polynomial is given by equation 11 as:

[0096] σ(α^{−(n−uj−l)})=reg_k^(l)(j)+reg_k−1^(l)(j)+ . . . +reg₁^(l)(j)+reg₀^(l)(j)  (Equation 11)

[0097] with 0≦j≦(n−1)/2.

[0098] The u registers values reg_i⁽⁰⁾(j), reg_i^(l)(j), . . . , reg_i^(u−1)(j) can be updated in parallel. Therefore, at the same clock cycle, u results

[0099] σ(α^−uj), σ(α^−(uj+1)), . . . , σ(α^{−(uj+u−1)})

[0100] can be obtained. Based on equation 11, a u-way parallel root search circuit 60 can have u number of root search circuits 34₀-34_u−1having u different sets of initial values. This circuit 60 can search from 0 to n−1 (FIG. 6) and n−1 to 0 (FIG. 7) depending on the initial values and coefficients. As mentioned above, the initializer 20 is provided to convert the initial values σ_iof reg_i⁽⁰⁾to those of reg_i^(l)for l≦1.

[0101] Referring now to FIG. 8, a portion of a two-way parallel shared search and evaluator circuit 70 is shown. The two-way parallel search and evaluator circuit 70 includes a first root search circuit 74aSCF(0) and a second root search circuit 74bSCF(1) with associated multiplexers 75a-75b. From the outputs of the multiplexers 75a-75bare provided α^−jLσ(α^−j) and α^−j(L+1)σ′(α^−j). The term α^−j(L+1)σ′(α^−j) is one of the terms used to implement the Forney formula for error evaluation, as is described below. The value “L” is the leading exponent of consecutive roots of the Read-Solomon code.

[0102] The error location circuits 74aand 74binclude registers and multipliers and three banks 76a-76cof “exclusive or” gates. The derivative of the error evaluation polynomial is provided from bank 76cwhereas, the error location polynomial is provided from banks 76band 76aof “exclusive or” gates, as shown.

[0103] Each root search circuit 74a, 74bis a shared circuit that provides an error polynomial root search result and the derivative of the error-location polynomial. The derivative of the error location polynomial is provided by considering that an error-correction m-bit symbol RS code of length n can be generated by:

[0104] g(χ)=(χ−α^L)(χ−α^L+1) . . . (χ−α^L+2t−1)

[0105] If the redundancy symbols of the code are located in positions 0, 1, . . . 2t−1, then when a corrupt word r=r₀, . . . , r_n−1is received, the decoder 70 will first compute the syndromes by $S_i=\sum _{j=0}^{n-1}{r}_j{\alpha }^{\left(L+1\right)j,}i=0,\dots ,2t-1$

[0106] From these syndromes, an error-locator polynomial σ(χ) can be obtained by using a decoding algorithm, such as Berlekamp-Massey algorithm or Euclidean algorithm. The error evaluator polynomial ω(χ) can be computed by:

[0107] ω(χ)=σ(χ)S(χ)modχ^2t

[0108] where $S\left(\chi \right)=\sum _{i=0}^{2t-1}{S}_i{\chi }^i.$

[0109] After obtaining the error location j from the error-locator polynomial σ(χ) by the root search, the associated error values can be computed by the Forney formula $\begin{array}{cc}{e}_j=\frac{\omega \left({\alpha }^{-j}\right)}{{\alpha }^{-j\left(L+1\right)}{\sigma }^{\prime }\left({\alpha }^{-j}\right)}& \mathrm{Equation}12\end{array}$

[0110] where σ′(χ) is the derivative of σ(χ). Additional detail concerning the above discussion can be found in “Theory and Practice of Error Control Codes” by Blahert, Addison-Wesley Publishing Company, 1983.

[0111] To implement the Forney formula, two values are needed ω(α^−j) and α^−j(L+1)σ′(α^−j). The value α^−j(L+1)σ′(α^−j) can be produced from the root search circuits 74a, 74b.

[0112] Since ${\sigma }^{\prime }\left(\chi \right)=\sum _{i=0}^{k}i{\sigma }_i{\chi }^{i-1}$

[0113] and the code is over GF(2^m), we have $\begin{array}{c}{\alpha }^{-j\left(L+1\right)}{\sigma }^{\prime }\left({\alpha }^{-j}\right)={\alpha }^{\left(-j\left(L+1\right)\right)}\sum _{i\mathrm{is}\mathrm{odd}}{{\sigma }_i\left({\alpha }^{-j}\right)}^{i-1}\\ =\sum _{i\mathrm{is}\mathrm{odd}}{\sigma }_i{\alpha }^{-\left(L+i\right)j}\end{array}$

[0114] Recalling that the standard root (i.e., Chien) search technique is given by

[0115] reg_i(j)=σ_iα^−(L+i)j

[0116] for i=0,1, . . . , k and j=0,1, . . . , n−1.

[0117] The Chien search circuit can also be used to determine the derivative of the error location polynomial for use in an error evaluation circuit. The outputs from the root search circuit are given by Equation 13: $\begin{array}{cc}{\alpha }^{-\mathrm{jL}}\sigma \left({\alpha }^{-j}\right)=\sum _{i=0}^k{\mathrm{reg}}_i\left(j\right)& \mathrm{Equation}13\end{array}$

[0118] and equation 14 gives the outputs of the root search circuit that provide the term for the error evaluator $\begin{array}{cc}{\alpha }^{-j\left(L+1\right)}{\sigma }^{\prime }\left({\alpha }^{-j}\right)=\sum _{i\mathrm{is}\mathrm{odd}}{\mathrm{reg}}_i\left(j\right)& \mathrm{Equation}14\end{array}$

[0119] for 0≦j≦n−1. By initializing the register reg_ito reg_i(0)=σ_i, the register reg_ihas the following iterative relation

[0120] reg_i(j)=α^−(L+i)reg_i(j−1)

[0121] for 1≦j≦n−1. Since α^−jLσ(α^−j)=0 if and only if σ(α^−j)=0, χ^Lσ(χ) can also be used to find error-locations. Therefore, according to the above equations 13 and 14, by slightly modifying the root search circuits, the function of finding error-locations and calculation of α^−jL+1σ′(α^−j) can share the same circuit. The modification of the root search circuits involve generating a bank of exclusive OR gates to form the modulo sum terms corresponding to odd elements, to provide the derivative of the error location polynomial. Also, by initializing

[0122] reg_i(0)=α^(L+i)(1−n)σ_i

[0123] and defining the iteration relationship

[0124] reg_i(j)=α^(L+i)reg_i(j−1)

[0125] provides ${\alpha }^{-\left(n-1-j\right)L}\sigma \left({\alpha }^{-(n-l-j}\right)=\sum _{i=0}^k{\mathrm{reg}}_i\left(j\right)$

[0126] and ${\alpha }^{-\left(n-l-j\right)\left(L+1\right)}{\sigma }^{\prime }\left({\alpha }^{-(n-1-j}\right)=\sum _{i\mathrm{is}\mathrm{odd}}{\mathrm{reg}}_i\left(j\right)$

[0127] for 0≦j≦n−1. In addition, as shown in FIG. 9, a shared, parallel root search circuit 70′ can be provided in the descending order from n−1 to 0.

[0128] Referring now to FIG. 9, a portion of a two-way parallel shared search and evaluator circuit 70′ is shown. The two-way parallel search and evaluator circuit 70′ includes a first root search circuit 74a′ SCF(0) and a second root search circuit 74b′ SCF(1) with associated multiplexers 75a′-75b′. From the outputs of the multiplexers 75a-75bare provided α^{−L(n−1−j)}σ(α^−(n−j)) and α^{−(L+1)(n−1−j)}σ′(α^−(n−j)).

[0129] The error location circuits 74a′ and 74b′ include registers and multipliers and three banks 76a-76cof “exclusive or” gates and are similar to those described above for FIG. 8 except for different initial values. The derivative of the error evaluation polynomial is provided from bank 76c′ whereas, the error location polynomial is provided from banks 76b′ and 76a′ of “exclusive or” gates, as shown.

[0130] A U-way parallel root search that also computes α^{−(n−1−j)(L+1)}σ′(α⁻ⁱ) can be provided by the U-way parallel root search circuit and modifying the root circuit to have the root search circuit calculate the derivative of the error-locator polynomial in a similar manner, as shown above for the two way circuits 70, 70′ in FIGS. 8 and 9.

[0131] Let v=uj+1. Then

[0132] 1) Define reg_i^(l)(0)=α^−(L+i)lσ_iand the iterative relationship

[0133] reg_i^(l)(j)=α^−(L+i)ureg_i(j−1)

[0134] for l=0, . . . , u−1, we have ${\alpha }^{-\left(\mathrm{uj}+l\right)L}\sigma \left({\alpha }^{-(\mathrm{uj}+l}\right)=\stackrel{k}{\sum _{i=0}}{\mathrm{reg}}_i^l\left(j\right)\mathrm{and}$ ${\alpha }^{-\left(\mathrm{uj}\right)\left(L+1\right)}{\sigma }^{\prime }\left({\alpha }^{-(\mathrm{uj}+l}\right)=\sum _{i\mathrm{is}\mathrm{odd}}{\mathrm{reg}}_i^l\left(j\right)$

[0135] for 0≦j≦(n−1)/u. This U-way shared parallel circuit searches locations from 0 to n−1.

[0136] The U-way parallel, shared circuit can search locations from n−1 to 0. By defining reg_i^(l)(0)=α^{(L+i)(l+1−n)}σ_iand the iterative relationship

[0137] reg_i^(l)(j)=α^(L+i)ureg_i(j−1)

[0138] for l=0, . . . , u−1, provides ${\alpha }^{-\left(n-\mathrm{uj}-l\right)L}\sigma \left({\alpha }^{-(n-\mathrm{uj}-l}\right)=\stackrel{k}{\sum _{i=0}}{\mathrm{reg}}_i^l\left(j\right)\mathrm{and}$ ${\alpha }^{-\left(n-\mathrm{uj}-l\right)\left(L+1\right)}{\sigma }^{\prime }\left({\alpha }^{-(n-\mathrm{uj}-l}\right)=\sum _{i\mathrm{is}\mathrm{odd}}{\mathrm{reg}}_i^l\left(j\right)$

[0139] for 0≦j≦(n−1)/u.

[0140] Therefore, one of advantage of the arrangement of the shared circuits 70, 70′ for the two way case or for the U-way case is that the denominator of equation (12) is readily available from the root search circuit without the need to compute the derivative σ′(α^{−j) of the error location polynomial σ(α−j).}

[0141] Referring to FIG. 10, the parallel combined root search and error evaluator circuit 70 includes two-way parallel root search circuits 74a, 74bthat share circuitry with an error evaluator circuit 80. The circuit 70 includes a decoder 82 that uses the Berlekamp-Massey decoding algorithm or Euclidean algorithm to provide at decoder outputs both error-locator polynomial that is fed to the root search circuits 74a, 74b. $\sigma \left(\chi \right)=\sum _{l=0}^k{\sigma }_i{\chi }^i$

[0142] and error-value polynomial that is fed to the error evaluator circuit 80. $\omega \left(\chi \right)=\sum _{l=0}^k{\omega }_i{\chi }^i$

[0143] The error-locator polynomial σ(χ) fed to the two-way parallel combined root search circuit 74a, 74band provides the roots of the error location polynomial and the derivative calculation of σ(χ) which is carried out by the circuits 74a, 74bas shown. Since the initial values in the registers of sCF(1) are

[0144] σ₀, σ₁α, . . . , σ_kα^k

[0145] the coefficients of σ(χ) are provided from an initializer 50 (as will be described in FIG. 12). The initializer 50 accepts the coefficients of σ(χ) as input and outputs initial values σ₀, σ₁, . . . , σ_kfor the first root search circuit at the first cycle time, and outputs initial values σ₀, σ₁α, . . . , σ_kα^kfor the second root search circuit at the second cycle time. These two sets of outputs are used as initial values in the registers (FIG. 8) of the parallel shared search/evaluator circuits 74aand 74b. The output of circuits 74a, 74bwill be σ(α^−(2j+l))σ′(α^−(2j+l)) and location 2j+l, respectively for l=0 and 1.

[0146] While the processors 74a, 74bare running, the ω(χ) evaluator circuit 80 (FIG. 13) is also running. This evaluator 80 accepts the coefficients of ω(χ) from a Berlakamp-Massey decoder 82 as input, and outputs to an initializer 50 (FIG. 12) w_iα^−2ijfor i=0,1, . . . , k at every cycle time j. It is known that if 2j is an error location, then sCF(0) will output σ(α^−2j)=0, α^−2jσ′(α^−2j) and the location 2j. Thus, by directly dividing the output via a divider 84 α^−2jσ′(α^−2j) of sCF(0) by the summation of the output of the evaluator 80, the error value l_2jis obtained. If 2j+1 is an error-location, the values output from the evaluator 80 cannot be used directly. The initializer 50 is used to produce values ω_iα^−(2j+1)i, i=0,1, . . . , k from the evaluator 80 that can be used to evaluate the error evaluation polynomial ω(χ). Thus, the output of the evaluator 80 is sent to initializer 50. Initializer 50 outputs ω_iα^−2j, i=0,1, . . . , k at the first cycle time and ω_iα^−(2j+1), i=0,1, . . . , k at the second cycle time. Each of the sets of these two outputs are added together, respectively, by the “exclusive Or” gates 86. The output of the “exclusive Or” gates are ω(α^−2j) and ω(α^−2j−1), respectively.

[0147] The processors 74aand 74bare each comprised of gates that have two inputs a and b and output c such that c=b if a=0, and c=0 otherwise. Thus, when 2j+1 is an error location, the inputs to the divider 84 are

[0148] α^{−(L+1)(2j+l)}σ′(α^−(2j+l)) and ω(α^−(2j+l)),

[0149] where f=0 or 1. The divider 84 outputs the error values ${\hspace{0.17em}}^{e}2j+\mathrm{lL}=\frac{\omega \left({\alpha }^{-\left(2j+l\right)}\right)}{{\alpha }^{-\left(L+1\right)\left(2j+l\right)}{\sigma }^{\prime }\left({\alpha }^{-\left(2j+l\right)}\right)}.$

[0150] The other output of the decoder circuit 84 is the error location.

[0151] Referring now to FIG. 11, a general circuit 100 for a U-way parallel combined Chien search and Forney formula using a similar approach, as described in FIG. 10, is shown. The circuit 100 includes circuits 74a-74ucoupled to data selectors 89a, 89b. Multiplexer 89aprovides the error location and has as inputs the outputs of the circuits 74a-74u. Multiplexer 89bproduces the error value and has as inputs the output of dividers 84a-84u. Logic circuits 87a-87uare replicated for each input to the multiplexer 89b. The other elements are generally as in FIG. 10

[0152] It should be noted that the circuit for evaluating ω(χ) could be omitted to save gate counts. However, without the circuit for evaluating ω(χ) in parallel, all of the error locations would need to be stored and at the end of root search, additional cycles would be needed to compute the error values.

[0153] Therefore, a circuit for evaluating ω(χ) in parallel to the root search reduces the decoding delay while maintaining approximately the same gate counts. Also each value of ω(χ) can be provided instead of the initializer circuit 50. This may prove to be a more costly implementation.

[0154] Referring now to FIGS. 12 and 13 initializer circuit 50 and initializer circuit 20 are shown. These circuits use register 112, multiplier 114 and a multiplexer 116 to output constants for the multipliers in the search circuits described above. FIG. 12 shows a generalized initializer 50 for producing initial values for circuits of FIGS. 4 and 5 whereas, FIG. 13 shows a generalized circuit for producing initial values for the evaluator circuit 82 in FIGS. 10 and 11.

[0155] It is to be understood that while the invention has been described in conjunction with the detailed description thereof, the foregoing description is intended to illustrate and not limit the scope of the invention, which is defined by the scope of the appended claims. Other aspects, advantages, and modifications are within the scope of the following claims.