Reed-Solomon decoder and VLSI implementation thereof

[0002] This patent application claims the benefit of the filing dates of U.S. Provisional patent application Ser. No. 60/055,275, filed on Aug. 13, 1997 and entitled SIMPLIFIED PROCEDURE FOR CORRECTING ERRORS OF REED-SOLOMON CODE USING AN INVERSIONLESS THE [SIC] BERLEKAMP-MASSEY ALGORITHM; and U.S. Provisional patent application Ser. No. 60/072,407, filed on Jan. 23, 1998 and entitled VLSI DESIGN OF A DECODER FOR CORRECTING ERRORS OF REED-SOLOMON CODES USING AN INVERSIONLESS BERLEKAMP-MASSEY ALGORITHM, the contents of both of which are hereby incorporated by reference.

[0003] The present invention relates generally to forward error correcting methodology. The present invention relates more particularly to a method for decoding Reed-Solomon encoded data so as to effect error correction in a manner which is computationally efficient and which is suited for very large scale integrated circuit (VLSI) implementation. The present invention further comprises a VLSI implementation of the Reed-Solomon decoding methodology.

[0004] As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. Such binary data, which comprises a string of bits, i.e., zeros and ones, must be correctly recognized so as to facilitate the proper interpretation of the information represented thereby. That is, each individual zero and one needs to be interpreted reliably, so as to facilitate the accurate reconstruction of the stored and/or transmitted data represented thereby.

[0005] Such increased storage densities and transmission rates place a heavy burden upon the hardware utilized to recognize the state of individual bits. In contemporary storage devices, high storage densities dictate that the individual data bits be stored very close to one another. Further, in some data storage systems, the difference between the manner in which a one and a zero is stored in the media is not great enough to make the reading thereof as reliable as desired.

[0006] High data transmission rates imply either that the time allocated for each bit is substantially reduced, or that a modulation scheme is utilized wherein small differences in amplitude, frequency, and/or phase indicate a distinct sequence of bits, e.g., such as in multi-bit modulation. In either instance, the ability of hardware devices to accurately and reliably interpret such transmitted data is substantially reduced.

[0007] Although modern data storage systems are generally capable of limiting read errors to approximately one bit in ten billion, the extremely high volume of data processing typically being performed in contemporary data processing systems makes even such a seemingly low error rate unacceptable. In many systems, such an error rate would result in at least one error per day.

[0008] It must be appreciated that the incorrect reading of even a single bit of data may have highly undesirable effects. For example, the incorrect reading of a single bit of a computer program may cause the program to lock up or otherwise function incorrectly. Also, the incorrect reading of a single bit of numeric data may cause a number to be misread, which may have serious consequences when dealing with financial data, for example.

[0009] As those skilled on the art will appreciate, increasing data storage density and/or increasing data transmission speed inherently increases the bit error rate, i.e., the percentage of error bits contained in a message. It is desirable to be able to identify and correct data errors which occur during data storage and/or transmission operations. By being able to identify and correct such data errors, data may be stored more densely and/or transmitted more rapidly.

[0010] Further, the ability to correct data errors facilitates the use of mechanical devices, e.g., record/read heads, which are manufactured according to reduced tolerances and which are therefore less expensive. That is, hardware may be utilized which is more prone to introducing data errors, but which costs less.

[0011] Moreover, the ability to correct errors facilitates storage and transmission of data in low signal to noise environments. Thus, since data errors can be corrected, more noise can be tolerated within a storage medium (or rather the data signal can be recorded at a lower level as compared to the noise level, thus facilitating higher storage densities). Similarly, more noise can also be tolerated in data transmission, thereby facilitating increased data transmission speed.

[0012] The ability to store and transmit data in low signal to noise environments provides substantial benefit in satellite/spacecraft communications, compact disc (CD) recording, high definition television (HDTV), digital versatile disc (DVD) recording, network communications, and the like. In satellite/spacecraft communications, a weak signal (low signal to noise ratio) inherently results from the use of low power transmitters necessitated by weight constraints. In compact disc (CD) and digital disc (DVD) recording, being able to record in low signal to noise environments facilitates increased storage densities. In high definition television (HDTV) and network communications, being able to operate in low signal to noise environments facilitates communication at increased data transmission rates.

[0013] Error detection and correction methodologies for determining the existence of errors in stored and/or transmitted data and for correcting those errors are well known. Among the simplest of these methodologies is the use of data redundancy, wherein the data is repeated several times when it is stored or transmitted. When the data is read, a particular data error is unlikely to affect more than one occurrence of the data, such that a majority vote results in the correct data being recognized.

[0014] For example, a data byte may be stored three times. A data error is likely to affect only one of these three stored data bytes. Thus, the two correctly stored data bytes constitute a majority with respect to the incorrectly stored data byte, thereby identifying the data error and assuring correct interpretation of the stored data. However, as those skilled in the art will appreciate, such a majority vote method is extremely inefficient, since the data must be stored or transmitted several, e.g., 3, times. It is preferable to utilize an error detection and correction methodology which requires as few added bits to the message data as possible. This tends to minimize storage requirements and maximize transmission speed.

[0015] In an effort to overcome the deficiencies associated with the inefficient methodology of the majority vote system, various means for providing data correction which add only a few extra bits to the data have evolved. For example, the well known use of parity bits provides a much mnore efficient scheme for indicating the presence of a data error, although the use of simple parity alone does not facilitate the correction of such errors. When only parity error detection is used, then incorrectly transmitted data must be re-transmitted. Thus, although corrupt data is readily identifiable, corrupt data which was only present in a storage medium, and thus is not available for re-transmission, may not be recoverable.

[0016] Since it does not facilitate error correction without retransmission, parity is not a forward error correction methodology. In forward error correction methodologies, sufficient information is added to the stored or transmitted data to facilitate the reliable correction of data errors without requiring such retransmission, as long as a mathematically determined error rate is not exceeded.

[0017] It is desirable to provide a methodology for correcting burst errors. Burst errors involve the corruption of a plurality of consecutive bits. Burst errors are common in data storage and data transmission.

[0018] Burst errors typically occur during data storage due to faulty media. For example, a scratch or other imperfection upon a magnetic or optical storage medium may result in the loss or corruption of many consecutive bits stored upon the medium.

[0019] Burst errors typically occur during data transmission due to noise or static within the transmission frequency band. Signal fading and cross-talk may also cause burst errors during data transmission.

[0020] The well known Reed-Solomon encoding methodology provides an efficient means of error detection which also facilitates forward error correction, wherein a comparatively large number of data errors in stored and/or transmitted data can be corrected.

[0021] Reed-Solomon encoding is particularly well suited for correcting burst errors, wherein a plurality of consecutive bits become corrupted. For example, the implementation of Reed-Solomon encoding currently used to store information upon compact discs (CDs) is capable of correcting error bursts containing as many as four thousand consecutive bits.

[0022] Reed-Solomon encoding is based upon the arithmetic of finite fields. A basic definition of Reed-Solomon encoding states that encoding is performed by mapping from a vector space of M over a finite field K into a vector space of higher dimension over the same field. Essentially, this means that with a given character set, redundant characters are utilized to represent the original data in a manner which facilitates reconstruction of the original data when a number of the characters have become corrupted.

[0023] This may be better understood by visualizing Reed-Solomon code as specifying a polynomial which defines a smooth curve containing a large number of points. The polynomial and its associated curve represent the message. That is, points upon the curve are analogous to data points. A corrupted bit is analogous to a point that is not on the curve, and therefore is easily recognized as bad. It can thus be appreciated that a large number of such bad points may be present in such a curve without preventing accurate reconstruction of the proper curve (that is, the desired message). Of course, for this to be true, the curve must be defined by a larger number of points than are mathematically required to define the curve, so as to provide the necessary redundancy.

[0024] If N is the number of elements in the character set of the Reed-Solomon code, then the Reed-Solomon encode is capable of correcting a maximum of t errors, as long as the message length is less than N-2t.

[0025] Although the use of Reed-Solomon encoding provides substantial benefits by enhancing the reliability with which data may be stored or transmitted, the use of Reed-Solomon encoding according to contemporary practice possesses inherent deficiencies. These deficiencies are associated with the decoding of Reed-Solomon encoded data. It should be noted that in many applications, the encoding process is less critical than the decoding process. For example, since CDs are encoded only once, during the mastering process, and subsequently decoded many times by users, the encoding process can use slower, more complex and expensive technology. However, decoding must be performed rapidly to facilitate real-time use of the data, e.g., music, programs, etc., and must use devices which are cost competitive in the consumer electronics market. Thus, it is desirable to provide a VLSI device for performing Reed-Solomon decoding, since such VLSI devices tend to be comparatively fast and inexpensive.

[0026] Decoding Reed-Solomon encoded data involves the calculation of an error locator polynomial and an error evaluator polynomial. One of two methods is typically utilized to decode Reed-Solomon encoded data. The Berlekamp-Massey algorithm is the best known technique for finding the error locator. The Berlekamp-Massey algorithm is capable of being implemented in a VLSI chip. However, the Berlekamp-Massey algorithm utilizes an inversion process which undesirably increases the complexity of such a VLSI design and which is computationally intensive, thereby undesirably decreasing the speed of decoding process.

[0027] Also well known is the use of Euclid's algorithm for the decoding of Reed-Solomon encoded data. However, Euclid's algorithm utilizes a polynomial division methodology which is computationally intensive and which is difficult to implement in VLSI.

[0028] In view of the foregoing, it is desirable to provide a method for decoding Reed-Solomon encoded data which is easily and economically implemented as a VLSI chip and which is computationally efficient so as to substantially enhance decoding speed.

[0029] The present invention specifically addresses and alleviates the above mentioned deficiencies associated with the prior art. More particularly, the present invention comprises a highly efficient Reed-Solomon decoding algorithm and a VLSI implementation thereof. The VLSI implementation of the algorithm is used to correct errors found in data which was encoded utilizing Reed-Solomon encoding and is particularly well suited for low cost, high speed applications. The algorithm of the present invention takes advantage of certain desirable features of Euclid's algorithm and of the Berlekamp-Massey algorithm.

[0030] According to the present invention, the error locator polynomial and the error evaluator polynomial are calculated simultaneously and there is no need to perform polynomial divisions within the reiteration process. Further, the need to compute the discrepancies and to perform the field element inversions, as required by the prior art, is eliminated. Thus, the complexity of the VLSI implementation is substantially reduced and the processing time is shortened. A software simulation of the decoding algorithm of the present invention shows that the decoding process is faster than that of the original Euclid's algorithm and faster than the Berlekamp-Massey algorithm.

[0031] As discussed above, two different methods, Euclid's algorithms and the Berlekamp-Massey algorithm, for decoding Reed-Solomon encoded data are well known. Euclid's algorithm offers the advantage of facilitating the simultaneous calculation of the error evaluator polynomial along with the error locator polynomial. However, Euclid's algorithm is less efficient in practice than the Berlekamp-Massey algorithm because Euclid's algorithm performs polynomial divisions within the iteration process thereof.

[0032] The Berlekamp-Massey algorithm is the most widely used technique for determining the error locator polynomial and error evaluator polynomial. Although the Berlekamp-Massey algorithm can be implemented in a VLSI chip, such implementation is made undesirably complex by the Berlekamp-Massey algorithm's iteration process and field element inversions. Thus, the error locator polynomial and the error evaluator polynomial can be calculated simultaneously when using the Berlekamp-Massey algorithm with inverses.

[0033] According to the present invention, desirable features of Euclid's algorithm and the Berlekamp-Massey algorithm are utilized to reduce the complexity of a VLSI implementation of the decoding algorithm and to reduce the processing time required for decoding. More particularly, the present invention utilizes an iteration process similar to that of Euclid's algorithm. According to the present invention, field element inversion computations are eliminated as well. According to the present invention, the error evaluator polynomial is computed simultaneously with the error locator polynomial. Further simplifying computation, polynomial swaps are avoided. Thus, the decoding algorithm of the present invention is substantially easier to implement in a VLSI design, as compared to contemporary algorithms such as Euclid's algorithm and the Berlekamp-Massey algorithm.

[0034] The method for correcting errors in Reed-Solomon encoded data of the present invention can be practiced using either a general purpose computer or dedicated circuits, e.g., a VLSI implementation. As used herein, the term dedicated circuit refers to a circuit which facilitates Reed-Solomon decoding and which is not used in general purpose computing.

[0035] These, as well as other advantages of the present invention will be more apparent from the following description and drawings. It is understood that changes in the specific structure shown and described may be made within the scope of the claims without departing from the spirit of the invention.

[0036] FIG. 1 is an overall block diagram of a pipeline (255, 223) Reed-Solomon domain decoder according to the present invention;

[0037] FIG. 2 is a systolic array for computing the modified Berlekamp-Massey algorithm according to the present invention;

[0038] FIG. 3 is a block diagram of a Chien search unit according to the present invention; and

[0039] FIG. 4 is a block diagram of the iteration circuit and the polynomial calculation circuit according to a VLSI implementation of the present invention.

[0040] The detailed description set forth below in connection with the appended drawings is intended as a description of the presently preferred embodiment of the invention, and is not intended to represent the only form in which the present invention may be constructed or utilized. The detailed description sets forth the functions of the invention, as well as the sequence of steps for constructing and operating the invention in connection with the illustrated embodiment. It is to be understood, however, that the same or equivalent functions may be accomplished by different embodiments that are also intended to be encompassed within the spirit and scope of the invention.

[0041] The present invention comprises a decoding method for correcting errors which occur in Reed-Solomon (RS) encoded data by using a modified, i.e., inversionless, Berlekamp-Massey algorithm. The modified Berlekamp-Massey algorithm of the present invention provides a method which is readily incorporated into a VLSI design and which is comparatively fast as compared to contemporary Reed-Solomon decoding algorithms. According to the present invention, the error locator polynomial and the error evaluator polynomial are obtained simultaneously. As a consequence, the decoder can be made more modular, simpler, and is suitable for both VLSI and software implementation. An exemplary software simulation result and an example illustrating the pipeline and systolic array aspects of this decoder structure is given for a (225,223) Reed-Solomon code.

[0042] According to the present invention, the modified Berlekamp-Massey algorithm is improved such that it finds the error locator polynomial and the error evaluator polynomial simultaneously. In other words, the error locator polynomial and the error evaluator polynomial are computed directly by using the modified Berlekamp-Massey algorithm with no inverses. Thus, according to the present invention, the computation of inverse field elements is completely avoided in Berlekamp's key equation.

[0043] The modified Berlekamp-Massey algorithm is used to reduce the hardware complexity for the time domain decoder of Reed-Solomon codes of the present invention. As a consequence, an efficient VLSI implementation of time domain Reed-Solomon decoder is provided.

[0044] Time Domain Decoder for Reed-Solomon Codes

[0045] The algorithm for decoding Reed-Solomon encoded data according to the present invention is provided below. As discussed above, this algorithm avoids the need to perform inverses (as required by contemporary decoding algorithms). According to the present invention, the error evaluator polynomial and the error locator polynomial are computed simultaneously. This simplification of the decoding process makes the algorithm of the present invention suited for implementation in very large scale integrated circuit (VLSI) design.

[0046] The conventional decoder methodology is now explained in more detail. Let n be the block length of an (n, k) RS code in GF(2^m), where k is the number of m-bit message symbols. Also, let d be the minimum distance of the code, where d−1 denotes the number of parity symbols. Thus, k=n−(d−1). Finally, let the code vector be ^c=(c₀,c₁,c₂. . . ,c_n−1). Also, let the error vector be ^e=(e₀,e₁,e₂. . . , e_n−1). The received vector at the input of the RS decoder is r=c+e=(r₀, r₁,r₂. . . , r_n−1). Suppose that ^verrors occur in the received vector ^rand assume that 2v≦d−1. Then, the maximum number of errors in RS codes which can be corrected is

[0047] t=└(d−1)/2┘  (1)

[0048] where └x┘ denotes the greatest integer less than or equal to ^x.

[0049] It is well known that the syndromes are defined by $\begin{array}{cc}{S}_k=\sum _{i=0}^{n-1}{r}_i{\alpha }^{\mathrm{ik}}=\sum _{i=0}^{n-1}{e}_i{\alpha }^{\mathrm{ik}}+\sum _{i=0}^{n-1}{c}_i{\alpha }^{\mathrm{ik}}\mathrm{for}1\le k\le d-1& \left(2\right)\end{array}$

[0050] where ^α is a primitive element in GF(₂m)and S_k, is known for 1≦k≦d−1. But c₀+c₁α^k+c₂α^2k. . . +c_n−1α^(n−1)k=0, for 1≦k≦d−1. Then, (2) becomes $\begin{array}{cc}{S}_k=\sum _{i=1}^v{Y}_i{X}_i^k\mathrm{for}1\le k\le d-1& \left(3\right)\end{array}$

[0051] where X_iand Y_iare the _i^therror amplitude and the _i^therror location, respectively.

[0052] Define the syndrome polynomial as $\begin{array}{cc}S\left(x\right)=\sum _{k=1}^{d-1}{S}_k{x}^k.& \left(4\right)\end{array}$

[0053] A substitution of (3) into (4) yields $\begin{array}{cc}S\left(x\right)=\sum _{k=1}^{d-1}\left(\sum _{i=1}^v{Y}_i{X}_i^k\right)x^k=\sum _{i=1}^v{Y}_i\left(\sum _{k=1}^{d-1}{\left(X_{i}x\right)}^k\right).& \left(5\right)\end{array}$

[0054] But $\sum _{k=1}^{d-1}{\left(X_{i}x\right)}^k=\frac{X_{i}x+{\left(X_{i}x\right)}^d}{1+X_{i}x}.$

[0055] Thus (5) becomes $\begin{array}{cc}S\left(x\right)=\sum _{i=1}^v{Y}_i\frac{X_{i}x+{\left(X_{i}x\right)}^d}{1+X_{i}x}\equiv \sum _{i=1}^v{Y}_i\frac{X_{i}x}{1-X_{i}x}\mathrm{mod}{x}^d.& \left(6\right)\end{array}$

[0056] Now, let the error locator polynomial be defined by $\begin{array}{cc}\sigma \left(x\right)=\prod _{j=1}^v\left(1+X_{j}x\right)=\sum _{j=0}^v{\sigma }_j{x}^j& \left(7\right)\end{array}$

[0057] where σ(x) is the polynomial with zeros at the inverse error locations with σ₀=1 and deg{σ(x)}=^ν. Finally, let the error evaluator polynomial be defined by $\begin{array}{cc}P\left(x\right)=\sum _{i=1}^v{Y}_i{X}_{i}x\prod _{l\ne i}\left(1+X_{l}x\right)& \left(8\right)\end{array}$

[0058] where deg{P(x)}=^ν and P(O)=0. Hence (6) becomes $\begin{array}{cc}S\left(x\right)\equiv \frac{P\left(x\right)}{\sigma \left(x\right)}\mathrm{mod}{x}^d.& \left(9\right)\end{array}$

[0059] Thus, by (9), Berlekamp's key equation is given by

[0060] (1+S(x))σ(x)≡Ω(x) mod x^d  (10)

[0061] where Ω(x)=σ(x)+P(x) with Ω(0)=1 and deg{Ω(x)}=^ν.

[0062] Thus, the error evaluator polynomial is given by

[0063] P(x)≡Ω(x)+σ(x).  (11)

[0064] It is well known that the Berlekamp-Massey algorithm can be used to find σ(x) and Ω(x) in (10). For a given these known polynomials, the error evaluator polynomial can be obtained by (11). Note that P(X_i⁻¹)=Ω(X_i⁻¹)+σ(X_i⁻¹)=Ω(X_i⁻¹), where X_i⁻¹is the reciprocal root of σ(x) for 1≦i≦ν.

[0065] The following algorithm is the iterative procedure developed by Berlekamp and Massey to find σ(x) and Ω(x) that satisfies (10).

[0066] 1. Initially define C⁽⁰⁾(x)=1, D⁽⁰⁾(x)=1, A⁽⁰⁾(x)=1, B⁽⁰⁾(x)=0, l⁽⁰⁾=1 and k=0.

[0067] 2. Set k=k+1 if S_kis unknown stop. Otherwise define $\begin{array}{cc}{\Delta }^k=\sum _{j=0}^{l^{\left(k-1\right)}}{c}_j^{\left(k-1\right)}{s}_{k-j}\mathrm{and}\mathrm{let}& \left(12\right)\\ C^{\left(k\right)}\left(x\right)=D^{\left(k-1\right)}\left(x\right)-{\Delta }^{\left(k\right)}{B}^{\left(k-1\right)}\left(x\right)·x& \left(13\right)\\ D^{\left(k\right)}\left(x\right)=D^{\left(k-1\right)}\left(x\right)-{\Delta }^{\left(k\right)}{B}^{\left(k-1\right)}\left(x\right)·x& \left(14\right)\\ A^{\left(k\right)}\left(x\right)=\{\begin{array}{c}x·A^{\left(k-1\right)}\left(x\right),\mathrm{if}{\Delta }^{\left(k\right)}=0\mathrm{or}\mathrm{if}2l^{\left(k-1\right)}>k-1\\ C^{\left(k-1\right)}\left(x\right)/{\Delta }^{\left(k\right)},\mathrm{if}{\Delta }^{\left(k\right)}\ne 0\mathrm{and}2l^{\left(k-1\right)}\le k-1\end{array}& \underset{\left(16\right)}{\underset{}{\stackrel{}{\left(15\right)}}}\\ B^{\left(k\right)}\left(x\right)=\{\begin{array}{c}x·B^{\left(k-1\right)}\left(x\right),\mathrm{if}{\Delta }^{\left(k\right)}=0\mathrm{or}\mathrm{if}2l^{\left(k-1\right)}>k-1\\ D^{\left(k-1\right)}\left(x\right)/{\Delta }^{\left(k\right)},\mathrm{if}{\Delta }^{\left(k\right)}\ne 0\mathrm{and}2l^{\left(k-1\right)}\le k-1\end{array}\mathrm{and}& \underset{\underset{\left(18\right)}{}}{\stackrel{}{\left(17\right)}}\\ l^{\left(k\right)}\left(x\right)=\{\begin{array}{cccc}{l}^{\left(k-1\right)},& \mathrm{if}{\Delta }^{\left(k\right)}=0& \mathrm{or}\mathrm{if}& 2l^{\left(k-1\right)}>k-1\\ k-l^{\left(k-1\right)}\left(x\right),& \mathrm{if}{\Delta }^{\left(k\right)}\ne 0& \mathrm{and}& 2l^{\left(k-1\right)}\le k-1\end{array}& \underset{\underset{\left(20\right)}{}}{\stackrel{}{\left(19\right)}}\end{array}$

[0068] 3. Return to step 2.

[0069] In this iterative procedure,

[0070] σ(x)=C^(d−1)(x)  (21)

[0071] and

[0072] Ω(x)=D^(d−1)(x).  (22)

[0073] The errors are located by finding the reciprocal root of the polynomial σ(x) in (21). These roots are usually found by a Chien-search procedure. Note that in (16) and (18) there are only two places in the algorithm where the inversion of the element Δ^(k)is required. It is well known that inversion takes many operations or special hardware. The modified Berlekamp Massey algorithm is developed for finding the error locator polynomial and the error evaluator polynomial that satisfies (10). The following algorithm is the modified Berlekamp-Massey algorithm which eliminates the requirement for inversion.

[0074] 1. Initially define {overscore (C)}⁽⁰⁾(x)=1, {overscore (D)}⁽⁰⁾(x)=1, {overscore (A)}⁽⁰⁾(x)=1, {overscore (B)}⁽⁰⁾(x)=0, {overscore (l)}⁽⁰⁾=0, γ^(k)=1 if k≦0.

[0075] 2. Set k=k+1 if k=d−1, stop. Otherwise, define $\begin{array}{cc}{\stackrel{\_}{\Delta }}^{\left(k\right)}=\sum _{j=0}^{{\stackrel{\_}{l}}^{\left(k-1\right)}}{\stackrel{\_}{c}}_j^{\left(k-1\right)}{s}_{k-j}\mathrm{and}\mathrm{let}& \left(23\right)\\ {\stackrel{\_}{C}}^{\left(k\right)}\left(x\right)={\gamma }^{\left(k-1\right)}{\stackrel{\_}{C}}^{\left(k-1\right)}\left(x\right)-{\stackrel{\_}{\Delta }}^{\left(k\right)}{\stackrel{\_}{A}}^{\left(k-1\right)}\left(x\right)·x& \left(24\right)\\ {\stackrel{\_}{D}}^{\left(k\right)}\left(x\right)={\gamma }^{\left(k-1\right)}{\stackrel{\_}{D}}^{\left(k-1\right)}\left(x\right)-{\stackrel{\_}{\Delta }}^{\left(k\right)}{\stackrel{\_}{B}}^{\left(k-1\right)}\left(x\right)·x& \left(25\right)\\ {\stackrel{\_}{A}}^{\left(k\right)}\left(x\right)=\{\begin{array}{cccc}x·{\stackrel{\_}{A}}^{\left(k-1\right)}\left(x\right),& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}=0& \mathrm{or}\mathrm{if}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}>k-1\\ {\stackrel{\_}{C}}^{\left(k-1\right)}\left(x\right),& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}\ne 0& \mathrm{and}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}\le k-1\end{array}& \underset{\underset{\left(27\right)}{}}{\stackrel{}{\left(26\right)}}\\ {\stackrel{\_}{B}}^{\left(k\right)}\left(x\right)=\{\begin{array}{cccc}x·{\stackrel{\_}{B}}^{\left(k-1\right)}\left(x\right),& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}=0& \mathrm{or}\mathrm{if}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}>k-1\\ {\stackrel{\_}{D}}^{\left(k-1\right)}\left(x\right),& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}\ne 0& \mathrm{and}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}\le k-1\end{array}& \underset{\underset{\left(29\right)}{}}{\stackrel{}{\left(28\right)}}\\ {\stackrel{\_}{l}}^{\left(k\right)}\left(x\right)=\{\begin{array}{cccc}{\stackrel{\_}{l}}^{\left(k-1\right)},& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}=0& \mathrm{or}\mathrm{if}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}>k-1\\ k-{\stackrel{\_}{l}}^{\left(k-1\right)}\left(x\right),& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}\ne 0& \mathrm{and}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}\le k-1\end{array}& \underset{\underset{\left(31\right)}{}}{\stackrel{}{\left(30\right)}}\\ {\gamma }^{\left(k\right)}=\{\begin{array}{cccc}{\gamma }^{\left(k-1\right)},& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}=0& \mathrm{or}\mathrm{if}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}>k-1\\ {\stackrel{\_}{\Delta }}^{\left(k\right)},& \mathrm{if}{\stackrel{\_}{\Delta }}^{\left(k\right)}\ne 0& \mathrm{and}& 2{\stackrel{\_}{l}}^{\left(k-1\right)}\le k-1\end{array}& \underset{\underset{\left(33\right)}{}}{\stackrel{}{\left(32\right)}}\end{array}$

[0076] 3. Return to step 2.

[0077] The following theorem illustrates the principal relations of these two algorithms.

[0078] Theorem 1. For 0≦n≦d−1, $\begin{array}{cc}{\stackrel{\_}{C}}^{\left(n\right)}\left(x\right)=\prod _{i=-1}^{n-1}{\gamma }^{\left(i\right)}{C}^{\left(n\right)}\left(x\right)& \left(34\right)\\ {\stackrel{\_}{D}}^{\left(n\right)}\left(x\right)=\prod _{i=-1}^{n-1}{\gamma }^{\left(i\right)}{D}^{\left(n\right)}\left(x\right)& \left(35\right)\\ {\stackrel{\_}{A}}^{\left(n\right)}\left(x\right)={\gamma }^{\left(n\right)}{A}^{\left(n\right)}\left(x\right)& \left(36\right)\\ {\stackrel{\_}{B}}^{\left(n\right)}\left(x\right)={\gamma }^{\left(n\right)}{A}^{\left(n\right)}\left(x\right)\mathrm{and}& \left(37\right)\\ {\stackrel{\_}{l}}^{\left(n\right)}=l^{\left(n\right)}& \left(38\right)\end{array}$

[0079] where C^(k)(x), D^(k)(x), A^(k)(x), B^(k)(x) and l^(k)are defined in (13)-(20), for n=k.

[0080] Proof. Theorem 1 can be proved by induction. By definition, the relations in (34)-(38) hold for n=0. Assume (34)-(38) hold for n=k−1. For n=k, a substitution of (34) for n=k−1 into (23) yields $\begin{array}{cc}\begin{array}{c}{\stackrel{\_}{\Delta }}_k=\sum _{j=0}^{{\stackrel{\_}{l}}^{\left(k-1\right)}}\left(\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}{c}^{\left(k-1\right)}\right)s_{k-j}\\ =\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}\sum _{j=0}^{{\stackrel{\_}{l}}^{\left(k-1\right)}}{c}_j^{\left(k-1\right)}{s}_{k-j}=\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}{\Delta }^{\left(k\right)}\end{array}& \left(39\right)\end{array}$

[0081] where γ⁽ⁱ⁾=1 for i=0 or −1. A substitution of (34) for n=k−1, (36) for n=k−1 and (39) into (24) yields $\begin{array}{cc}\begin{array}{c}{\stackrel{\_}{C}}^{\left(k\right)}\left(x\right)={\gamma }^{\left(k-1\right)}\left(\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}{C}^{\left(k-1\right)}\left(x\right)\right)-\left(\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}{\Delta }^{\left(k\right)}\right)·\\ \left({\gamma }^{\left(k-1\right)}{A}^{\left(k-1\right)}\left(x\right)\right)x\\ ={\gamma }^{\left(k-1\right)}\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}\left(C^{\left(k-1\right)}\left(x\right)-{\Delta }^{\left(k\right)}{A}^{\left(k-1\right)}\left(x\right)x\right)\end{array}& \left(40\right)\end{array}$

[0082] By (13), (40) becomes $\begin{array}{cc}{\stackrel{\_}{C}}^{\left(k\right)}\left(x\right)={\gamma }^{\left(k-1\right)}\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}{C}^{\left(k\right)}\left(x\right)=\prod _{i=-1}^{k-1}{\gamma }^{\left(i\right)}{C}^{\left(k\right)}\left(x\right)& \left(41\right)\end{array}$

[0083] Thus, (34) is proved.

[0084] Using a technique similar to that used for derivation of (39), once can derive (35).

[0085] Note by (39) that {overscore (Δ)}^(k)=0 if Δ^(k)=0 and {overscore (Δ)}^(k)≠0 if Δ^(k)≠0 because γ⁽ⁱ⁾≠0 for −1<i≦k−2. Hence, if {overscore (Δ)}^(k)=Δ^(k)=0 or if 2{overscore (l)}^(k−1)=2l^(k−1)>k−1, then, by (26) and (36) for n=k−1, one has

[0086] {overscore (A)}^(k)(x)=x·{overscore (A)}^(k−1)(x)=x·γ^(k−1)A^(k−1)(x).  (42)

[0087] But γ^(k)=γ^(k−1)in (32) and A^(k)(x)=x·A^(k−1)(x) in (15). Thus, (42) becomes A^(k)(x)=γ^(k)A^(k)(x). If {overscore (Δ)}^(k)=Δ^(k)≠0 and 2{overscore (l)}^(k−1)=2l^(k−1)≦k−1, then, by (27), (34) for n=k−1 and (39), one has $\begin{array}{cc}\begin{array}{c}{\stackrel{\_}{A}}^{\left(k\right)}\left(x\right)={\stackrel{\_}{C}}^{\left(k-1\right)}\left(x\right)=\prod _{i=-1}^{k-2}{\gamma }^{\left(i\right)}{C}^{\left(k-1\right)}\left(x\right)\\ =\left(\frac{{\stackrel{\_}{\Delta }}^{\left(k\right)}}{{\Delta }^{\left(k\right)}}\right)C^{\left(k-1\right)}\left(x\right)={\stackrel{\_}{\Delta }}^{\left(k\right)}\left(\frac{C^{\left(k-1\right)}\left(x\right)}{{\Delta }^{\left(k\right)}}\right)\end{array}& \left(43\right)\end{array}$

[0088] But, by (16) and (33), (43) becomes {overscore (A)}^(k)(x)=γ^(k)A^(k)(x). Thus (36) is proved. Using a technique similar to that used for derivation of (36), one can derived (37). If {overscore (Δ)}^(k)=Δ^(k)=0 or if 2{overscore (l)}^(k−1)>k−1, then {overscore (l)}^(k)={overscore (l)}^(k−1)=l^(k−1)=l^(k). If {overscore (Δ)}^(k)=Δ^(k)≠0 or if 2{overscore (l)}^(k−1)=2l^(k−1)≦k−1, then {overscore (l)}^(k)=k−{overscore (l)}^(k−1)=k−l^(k−1)=l^(k). Thus, (38) is proved. Hence, the theorem is proved.

[0089] From (38) and (35), the modified error locator polynomial and error evaluator polynomial are given by. $\begin{array}{cc}{\stackrel{\_}{C}}^{\left(d-1\right)}\left(x\right)=\beta ·C^{\left(d-1\right)}\left(x\right)=\beta ·\sigma \left(x\right)=\left({\mathrm{\beta \sigma }}_0,{\mathrm{\beta \sigma }}_1,{\mathrm{\dots \beta \sigma }}_{d-1}\right)& \left(44\right)\\ \mathrm{and}& \\ {\stackrel{\_}{D}}^{\left(d-1\right)}\left(x\right)=\beta ·D^{\left(d-1\right)}\left(x\right)=\beta ·\Omega \left(x\right)=\left(\beta ·{\Omega }_0,\beta ·{\Omega }_1,\mathrm{\dots \beta }·{\Omega }_{d-1}\right)\mathrm{where}& \left(45\right)\\ \beta =\prod _{i=-1}^{d-2}{\gamma }^{\left(i\right)}={\stackrel{\_}{C}}^{\left(d-1\right)}\left(0\right)={\stackrel{\_}{D}}^{\left(d-1\right)}\left(0\right)& \left(46\right)\end{array}$

[0090] is a field element in GF(2^m).

[0091] Therefore, by (44) and (45), the error locator polynomial and the error evaluator polynomial are obtained by $\begin{array}{cc}\sigma \left(x\right)=\frac{{\stackrel{\_}{C}}^{\left(d-1\right)}\left(x\right)}{\beta }& \left(47\right)\\ \mathrm{and}& \\ P\left(x\right)=\Omega \left(x\right)-\sigma \left(x\right)=\frac{{\stackrel{\_}{D}}^{\left(d-1\right)}\left(x\right)}{\beta }-\sigma \left(x\right).& \left(48\right)\end{array}$

[0092] The errors are located by finding the reciprocal root of the polynomialσ(x) in (47) or {overscore (C)}^(d−1)(x) in (44). The Forney algorithm can be used to find the error magnitudes from P(x) given in (8). This algorithm is illustrated as follows:

[0093] By [14], evaluating (8) and (11) at X_j⁻¹yields $\begin{array}{cc}P\left(X_j^{-1}\right)=\Omega \left(X_j^{-1}\right)=Y_j\prod _{l\ne j}\left(1-X_l{X}_j^{-1}\right).& \left(49\right)\end{array}$

[0094] By (47) and (49), the error magnitudes are given by $\begin{array}{cc}{Y}_j=\frac{\Omega \left(X_j^{-1}\right)}{\prod _{l\ne j}\left(1-X_l{X}_j^{-1}\right)}=\frac{\Omega \left(X_j^{-1}\right)}{X_j^{-1}{\sigma }^1\left(X_j^{-1}\right)}=\frac{{\stackrel{\_}{D}}^{\left(d-1\right)}\left(X_j^{-1}\right)}{X_j^{-1}{\stackrel{\_}{C}}^{\left(d-1\right)\prime }\left(X_j^{-1}\right)}& \left(50\right)\\ \mathrm{where}& \\ {\sigma }^{\prime }\left(X_j^{-1}\right)=X_j\prod _{l\ne j}\left(1-X_l{X}_j^{-1}\right)& \\ \mathrm{and}& \\ {\stackrel{\_}{C}}^{\left(d-1\right)\prime }\left(X_j^{-1}\right)=\beta ·{\sigma }^{\prime }\left(X_j^{-1}\right)& \end{array}$

[0095] are the derivative with respect to ^x of σ(x) given in(7) and {overscore (C)}^(d−1)′(x) given in (44) evaluated at ^x=X_j⁻¹, respectively.

[0096] Let us recapitulate the decoding of RS codes for errors using the modified Berlekamp-Massey algorithm which eliminates the requirement for inversion. This procedures is composed of the following four steps:

[0097] Step 1. If ν>t, the best policy is not to decode the message. Otherwise, compute the syndrome values S₁,S₂, . . . S_d−1from (2). If S_k=0 for 1≦k≦d−1, the received word is a codeword and no further processing is needed.

[0098] Step 2. Use an inversionless Berlekamp-Massey algorithm to determine the modified error locator polynomial β·σ(x) and the modified error evaluator polynomial β·Ω(x) from the known S_kfor 1≦k≦d−1.

[0099] Step 3. Compute the roots of β·σ(x) using the Chien search. The roots of β·σ(x) are the inverse locations of the ^ν errors.

[0100] Step 4. Compute the error values from (50).

[0101] To illustrate the time domain decoder for correcting errors a (15,9) Reed-Solomon triple-error correcting code over GF(2⁴) is now presented, The representation of the filed GF(2⁴) generated by the primitive irreducible polynomial p(x)=x⁴+x+1 is given in Table 1 as follows:

[0102] For example, consider a (15,9) Reed-Solomon code over GF (2⁴) with a minimum distance d=7 In this code, ^ν errors under the condition 2^ν≦6 can be corrected. Thus, the generator polynomial of such a (15,9) Reed-Solomon code is defined by $g\left(x\right)=\prod _{i=1}^6\left(x-{\alpha }^i\right)=x^6+{\alpha }^{10}{x}^5+{\alpha }^{14}{x}^4+{\alpha }^4{x}^3+{\alpha }^6{x}^2+{\alpha }^{9}x+{\alpha }^6.$

[0103] Assume the message symbols are all zeros. The encoded code word, which is a multiple of g(x), is C(x)=0. Written as a vector, the code word is ^c=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0) Assume the error vector is ^e=(0,0,α¹¹,0,0,α⁵,0,α,0,0,0,0,0,0,0). Thus, the received vector is r=c+e. By (2), the syndromes S_kfor ^rare $S_k=\sum _{n=0}^{14}{r}_n{\alpha }^{\mathrm{nk}}={{\alpha }^{11}\left({\alpha }^2\right)}^k+{{\alpha }^5\left({\alpha }^5\right)}^k+{\alpha \left({\alpha }^7\right)}^k\mathrm{for}1\le k\le 6.$

[0104] This yields S₁=α¹²,S₂=1, S₃=α¹⁴,S₄=α¹³, S₅=1 and S₆=α¹¹Thus, the syndrome polynomial is

[0105] S(x)=α¹²x+x²+α¹⁴x³+α¹³x⁴+x⁵+α¹¹x⁶.  (51)

[0106] In this example, by (1), the maximum error correcting capability is t=└(d−1)/2┘=6/2=3.

[0107] The modified Berlekamp-Massey algorithm is applied next to S(^x) given in (51). By this means, the modified error locator polynomial and the modified error evaluator polynomial are determined by a use of the modified Berlekamp-Massey algorithm. These are accomplished by the recursive formula (24) and (25), given in Table 2 . From Table 2, one can observe that the computation terminates at k=6 and the modified error locator polynomial {overscore (C)}⁽⁶⁾(x) is obtained.

[0108] That is,

[0109] {overscore (C)}⁽⁶⁾(x)=α⁵+α⁴x+αx²+α⁴x³  (52)

[0110] where deg{{overscore (C)}⁽⁶⁾(x)}=3 and β={overscore (C)}⁽⁶⁾(0)=α⁵.

[0111] By (47), the error locator polynomial is σ(x)={overscore (C)}⁽⁶⁾(x)/β=1+α¹⁴x+α¹¹x²+α¹⁴x³. By the derivative with respect to ^x of in (52), one obtains

[0112] {overscore (C)}⁽⁶⁾′(x)=α⁴+α⁴x².  (53)

[0113] Using the Chien search, the root of {overscore (C)}⁽⁶⁾(x) constitute the set {α⁻²,α⁻⁵,α⁻⁷}. Also from Table 2, the modified error evaluate polynomial is obtained. That is,

[0114] {overscore (D)}⁶(x)=(α⁵+α¹⁰x+α⁵x²+α¹¹x³).  (54)

[0115] Thus, by (50), the error values are $Y_1=\frac{{\stackrel{\_}{D}}^{\left(6\right)}\left({\alpha }^{-2}\right)}{{\alpha }^{-2}{\stackrel{\_}{C}}^{\left(6\right)\prime }\left({\alpha }^{-2}\right)}=\frac{{\alpha }^5+{\alpha }^{10}\left({\alpha }^{-2}\right)+{{\alpha }^5\left({\alpha }^{-2}\right)}^2+{{\alpha }^{11}\left({\alpha }^{-2}\right)}^3}{{\alpha }^{-2}\left({\alpha }^4+{{\alpha }^4\left({\alpha }^{-2}\right)}^2\right)}={\alpha }^{11}$ $\mathrm{Similarly},\mathrm{one}\mathrm{obtains}$ $Y_2=\frac{{\stackrel{\_}{D}}^{\left(6\right)}\left({\alpha }^{-5}\right)}{{\alpha }^{-5}{\stackrel{\_}{C}}^{\left(6\right)\prime }\left({\alpha }^{-5}\right)}=\frac{{\alpha }^5+{\alpha }^{10}\left({\alpha }^{-5}\right)+{{\alpha }^5\left({\alpha }^{-5}\right)}^2+{{\alpha }^{11}\left({\alpha }^{-5}\right)}^3}{{\alpha }^{-5}\left({\alpha }^4+{{\alpha }^4\left({\alpha }^{-5}\right)}^2\right)}={\alpha }^5$ $\mathrm{and}$ $Y_3=\frac{{\stackrel{\_}{D}}^{\left(6\right)}\left({\alpha }^{-7}\right)}{{\alpha }^{-7}{\stackrel{\_}{C}}^{\left(6\right)\prime }\left({\alpha }^{-7}\right)}=\frac{{\alpha }^5+{\alpha }^{10}\left({\alpha }^{-7}\right)+{{\alpha }^5\left({\alpha }^{-7}\right)}^2+{{\alpha }^{11}\left({\alpha }^{-7}\right)}^3}{{\alpha }^{-7}\left({\alpha }^4+{{\alpha }^4\left({\alpha }^{-7}\right)}^2\right)}=\alpha$

[0116] Table 2 below is an example of the modified Berlekamp-Massey algorithm used to find the modified polynomials βxσ(x) and βxΩ(x).

[0117] Program Implementation and Simulation Results

[0118] The new Reed-Solomon decoding procedure described in the previous section has been verified using a C++ program. The program is implemented to correct ν errors for general (n, k) Reed-Solomon codes, where n is of the form n=2^m−1, 1≦k≦n−1, and 0≦ν≦└(n−k)/2┘. The error patterns are randomly generated over the positions and magnitudes. An example of simulation results for a (255,223) Reed-Solomon code correcting ν errors, where ν≦16, is given in Table 3. For each ν, the computation times are in second, which is averaged from the computations of correcting 100 different error patterns. The computation times tend to decrease when the number of errors occurred decrease. This is because of the quantity {overscore (Δ)}^(k)in Eqs. (24)-(33) is zero.

[0119] A VLSI Design of the Time Domain Reed-Solomon Decoder

[0120] Referring now to FIG. 1, the block diagram of a (255,223) Reed-Solomon time domain decoder is shown. The major functional units in this decoder are the syndrome computation unit 12, the modified Berlekamp-Massey algorithm unit 14, the polynomial evaluation unit 16, and the Chien search unit 18. Also, included is a delay register 10, which facilitates synchronization of the decoded message output.

[0121] The syndrome computation unit 12 accepts the received sequence of received messages r₀,r₁, . . . , r₂₅₄and computes their syndromes.

[0122] The sequence of syndromes S₃₂, . . . , S₂,S₁is shifted serially to the modified Berlekamp-Massey algorithm unit 14. The output of this unit is the modified error locator polynomial {overscore (C)}⁽¹⁶⁾(x)=β·σ(x) and the modified error evaluator polynomial {overscore (D)}⁽¹⁶⁾(x)=β·Ω(x), where β={overscore (C)}⁽¹⁶⁾(0). The processing of these polynomials is performed by the Chien search unit 18 and the polynomila evaluation unit 16, as discussed below.

[0123] Referring now to FIG. 2, the VLSI implementation of this modified Berlekamp-Massey algorithm of the present invention is shown. The only input is the sequence of syndromes S₃₂, . . .S₂,S₁. The maximum order of either polynomial {overscore (C)}(x) or {overscore (D)}(x) is t=32/2=16. Thus, one needs only t+1=17 sub-registers to store syndromes for calculating {overscore (Δ)}^(k). A register 30 comprises sub-registers F₀,F₁, . . . ,F₁₆. That is, F=(F₀,F₁, . . . , F₁₆). Similarly, the registers {overscore (C)}=({overscore (C)}₀,{overscore (C)}₁, . . . ,{overscore (C)}₁₆) and {overscore (D)}=({overscore (D)}₀,{overscore (D)}₁, . . . ,{overscore (D)}₁₆) are used to store the coefficients of {overscore (C)}(^x) and {overscore (D)}(^x) given in (24) and (25), respectively. Also, C=(C₀,C₁, . . . ,C₁₆) and D=(D₀,D₁, . . . ,D₁₆) are the temporary storage of register C and D, respectively. The register {overscore (A)}=({overscore (A)}₀, {overscore (A)}₁, . . . ,{overscore (A)}₁₆) and {overscore (B)}=({overscore (B)}₀,{overscore (B)}₁, . . . ,{overscore (B)}₁₆) are used to store the coefficients of {overscore (A)}(^x) and {overscore (B)}(^x) given in (28) and (29), respectively. The registers γ and L are used to store the values of γ and {overscore (l)} respectively. Also, there is a decision circuit which generates a control signal δ to control the switches, and a count K is used to store the updated value of k. The outputs are two sequences out of the contents of registers {overscore (C)} and {overscore (D)} following the operations of this structure. The operations of this VLSI structure are described below.

[0124] At the initial state, all switches are at position 1. Assume initially in registers that F=0, C=0, D=0, {overscore (C)}=1, {overscore (D)}=1, {overscore (A)}=1 and {overscore (B)}=0. Also, assume the contents in registers γ, L and K are 1, 0 and 0 respectively. During k^thiteration, the contents of counter K is increased by one. Next, the new syndrome is shifted into sub-register F_land simultaneously the contents in sub-registers F_iare shifted right into subsequent sub-registers F_i+lfor i=0,1,2, . . . ,15 so that the contents of register F will be timed properly for multiplication with the contents of register {overscore (C)} for generating Δ^(k). Simultaneously, the contents of registers C and D are loaded into {overscore (C)} and {overscore (D)} registers, respectively. Then, the upper logic is activated to compute {overscore (Δ)}^(k)given in (23) and simultaneously registers {overscore (A)} and {overscore (B)} are shifted right by one position to perform x·{overscore (A)}^(k−1)(^x) and x·{overscore (B)}^(k−1)(^x) respectively. From the known {overscore (Δ)}^(k), x·{overscore (A)}^(k−1)and x·{overscore (B)}^(k−1),the lower logic is activated to compute {overscore (C)}^(k)(^x) and {overscore (D)}^(k)(^x) signal stored in registers C and D, respectively. At the same time, the controls signal δ is calculated. If Δ^(l)=0 or 2{overscore (l)}^(k−1)>k−1, i.e., δ=0, switches are still remain at position 1. Thus, γ^(k)and {overscore (l)}^(k)in (32) and (38) can be realized and the new updated data of γ^(k)and {overscore (l)}^(k),i.e., γ^(k)=γ^(k−1)and {overscore (l)}^(k)={overscore (l)}^(k−1)are stored in registers γ and L, respectively. If Δ^(k)≠0 and 2{overscore (l)}^(k−1)≦k−1, i.e. δ=1, one moves switches to position 2 so that one replaces the contents of registers {overscore (A)} and {overscore (B)} by the contents of registers {overscore (C)} and {overscore (D)}, respectively. Also, the contents of registers γ and L are replaced by Δ^(k)and k−{overscore (l)}^(k−1), respectively. Then, the same procedure is received repeatedly. This sequence of operations stops when the content of register K equals d−1=32. Finally, the modified error location polynomial and the modified error evaluation polynomial stored in registers {overscore (C)} and {overscore (D)}, respectively are obtained.

[0125] The register transfer language (RTL) of this inverse-free Berlekamp-Massey algorithm is described as follows:

[0126] T₀: F←0, C←0, D←0, {overscore (C)}←1, {overscore (D)}←1, {overscore (A)}←1, B←0,γ←1, L←0, K←0 and all switches are at position 1.

[0127] T₁: k←k+1 if k>d−1=32 stop. Otherwise, F₀←S₀and simultaneously F_i+l←F_ifor i=1,2, . . . , 15, {overscore (C)}←C={overscore (C)}^(k−1)(^x) and {overscore (D)}←D={overscore (D)}^(K−1)(^x) $T_2:\mathrm{Compute}{\stackrel{\_}{\Delta }}^{\left(k\right)}=\sum _{i=0}^{{\stackrel{\_}{l}}^{\left(k\right)}}{\stackrel{\_}{c}}_j^{\left(k-1\right)}{S}_{k-j},\stackrel{\_}{A}\leftarrow x·{\stackrel{\_}{A}}^{\left(k-1\right)}\mathrm{and}\stackrel{\_}{B}\leftarrow x·{\stackrel{\_}{B}}^{\left(k-1\right)}$

[0128] T₃: C←{overscore (C)}^(k)(x)=γ^(k−1){overscore (C)}−{overscore (Δ)}^(k){overscore (A)}, and D←{overscore (B)}^(k)(x)=γ^(k−1){overscore (B)}−Δ^(k){overscore (D)}

[0129] T₄: If δ=0, go to T₁. Otherwise, move all switches to position 2 so that {overscore (A)}←{overscore (C)}=C^(k−1)(x), {overscore (B)}←{overscore (D)}=D^(k−1)(^x), γ←{overscore (Δ)}^(k)and L←k−{overscore (l)}^(k−1). Then, move all switch to position 1 and go to T₁.

[0130] One output of the modified Berlekamp-Massey algorithm unit, the modified error locator polynomial {overscore (C)}¹⁶(x)=β·σ(x) is sent to a Chien search unit for generating a binary sequence of error locations and computing a sequence of β·σ′(α⁻²⁵⁵)·α⁻²⁵⁵, . . . , β·σ′(α⁻¹)·α⁻¹simultaneously. In the Chien search method, by [2],one has $\begin{array}{cc}{\stackrel{\_}{C}}^{16}\left({\alpha }^{-i}\right)=\beta ·\sigma \left({\alpha }^{-i}\right)=\sum _{j=0}^{16}\beta ·{\sigma }_j{\alpha }^{-\mathrm{ij}}=\sum _{j=0}^{16}\beta ·{\sigma }_j{\alpha }^{-\left(i-1\right)j}{\alpha }^{-j}\mathrm{for}1\le i\le 255& \left(54\right)\end{array}$

[0131] By (54), if one multiplies the j^thterm of β·σ(α^−(i−l)) by α^jfor 0≦j≦16, then one obtains the corresponding term of β·σ(α⁻ⁱ). Thus, one only needs a constant multiplier and a register for computing each term of β·σ(α^−(i−l)). In order to facilitate the implementation of the Forney algorithm, β·σ(α⁻ⁱ) in (54) can be separated into the odd and even terms. That is,

[0132] {overscore (C)}⁽¹⁶⁾(α⁻ⁱ)=β·σ(α⁻ⁱ)=Δ_e(α⁻ⁱ)+Δ₀(α⁻ⁱ) for 1≦j≦255  (55)

[0133] where $\begin{array}{cc}{\Delta }_e\left({\alpha }^{-i}\right)=\sum _{j=0,2,\dots }^{16}\beta ·{\sigma }_j{\alpha }^{-\left(i-1\right)j}{\alpha }^{-j}& \left(56\right)\end{array}$

[0134] is the summation of even coefficients and $\begin{array}{cc}{\Delta }_0\left({\alpha }^{-i}\right)=\sum _{j=1,3,\dots }^{16}\beta ·{\sigma }_j{\alpha }^{-\left(i-1\right)j}{\alpha }^{-j}& \left(57\right)\end{array}$

[0135] is the summation of odd coefficients.

[0136] The summation of odd coefficients of β·σ(α⁻ⁱ), i.e., Δ₀(α⁻ⁱ) in (57) is equal to β·σ(α⁻ⁱ)α^−j. That is,

[0137] Δ₀(α⁻ⁱ)=β·σ′(α⁻ⁱ)α⁻ⁱ={overscore (C)}^(16)′(α⁻ⁱ)α⁻ⁱfor 1≦i≦255

[0138] Referring you to FIG. 3, the architecture of the Chien search method unit is shown. As shown, the odd and even number terms are summed separately. The architecture of this unit is similar to that of a contemporary Chien search unit, except there are only 17 error locator sub-cells in this (255,223) Reed-Solomon decoder and a zero detector at the end. The zero detector is converted the sequence {overscore (C)}⁽¹⁶⁾(α⁻ⁱ)'s into a sequence of 1's and 0's , where 1 and 0 indicate the occurrence, i.e., {overscore (C)}⁽¹⁶⁾(α^−l)=β·σ(α^−l)=0, or nonoccurrence, i.e., {overscore (C)}₀⁽¹⁶⁾(α^−l)=β·σ(α^−l)≠0, respectively, of and error at a specific inverse location. α^−l.

[0139] The other output of the modified Berlekamnp-Massey algorithm unit, a sequence of the modified error evaluator polynomial β·Ω(x) is sent to the polynomial evaluation unit to perform the evaluation of β·Ω(x). The output of the polynomial evaluation unit β·Ω(α⁻ⁱ)'s and one output of the Chien search unit, a sequence of β·σ′(α⁻²⁵⁵)α⁻²⁵⁵, . . . ,β·σ′(α⁻¹)α⁻¹,are shifted to a finite field divider for computing the sequence of Ω(α⁻²⁵⁵)/α⁻²⁵⁵·σ′(α⁻²⁵⁵), . . . , Ω(α⁻¹)/α⁻¹·σ′(α⁻¹). The product of the Ω(α⁻ⁱ)/α⁻ⁱ·σ′(α⁻ⁱ)'s and the other output of the Chien search unit, the binary sequence of error locations forms the sequence of the estimated error patterns, i.e., e₀, e₁, . . . ,e₂₅₄. Finally, the estimated code vector is obtained by subtracting the error vector e from the received vector r.

[0140] Refering now to FIG. 4, a very large scale integrated circuit (VLSI) implementation of the present invention is shown. The VLSI implementation comprises an integrated circuit 40 comprising an iteration circuit 42 which performs iteration according to the modified Berlekamp-Massey algorithm of the present invention and a polynomial calculator circuit 44 which defines the modified error locator polynomial according to equation 44 and also defines a modified error evaluator polynomial according to equation 45.

[0141] It is understood that the exemplary algorithm described herein and shown in the drawings represents only a presently preferred embodiment of the invention. Indeed, various modifications and additions may be made to such embodiment without departing from the spirit and scope of the invention. For example, those skilled in the art will appreciate that the algorithm of the present invention is applicable to Reed-Solomon codes having various different sizes. Thus, the description herein of a (225,223) Reed-Solomon code is by way of illustration only, and not by way of limitation. Further, those skilled in the art will appreciate that various different VLSI implementations of the present invention are contemplated. Thus, these and other modifications and additions may be obvious to those skilled in the art and may be implemented to adapt the present invention for use in a variety of different applications.

[0142] The following is a C++ program listing of the computer simulation of the algorithm for decoding Reed-Solomon encoded data according to the present invention.