Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-08-16
2002-09-10
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000
Reexamination Certificate
active
06449746
ABSTRACT:
FIELD OF INVENTION
The present invention relates generally to forward error correcting (FEC) methodology. The present invention relates more particularly to a method for decoding Reed-Solomon (RS) encoded data for correcting erasures and errors in a manner which is computationally efficient and which is suited for very large scale integrated circuit (VLSI) implementation.
BACKGROUND OF THE INVENTION
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.
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.
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.
As those skilled in 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. Moreover, the ability to correct errors facilitates storage and transmission of data in environments with low signal to noise ratios. Thus, more noise can be tolerated within a storage and transmission medium.
Encoding is performed by an encoder before the data is transmitted (or stored). Once the transmitted data is received at the receiver end, a decoder decodes the data and corrects any correctable errors. Many encoders first break the message into a sequence of elementary blocks; next they substitute for each block a representative code, or signal, suitable for input to the channel. Such encoders are called block encoders. The operation of a block encoder may be described completely by a function or table showing, for each possible block, the code that represents it.
Error-correcting codes for binary channels that are constructed by algebraic techniques involving linear vector spaces or groups are called algebraic codes. Any binary code contains a number of code words which may be regarded as vectors C=(c
1
, c
2
, . . . , cn) of binary digits ci. The sum C+C′ of two vectors may be defined to be the vector (c
1
+c′
1
, . . . , cn+c′n) in which coordinates of C and C′ are added in modulo 2.
Thus, the vector sum of any two code words is also a code word. Because of that, these codes are linear vector spaces and groups under vector addition. Their code words also belong to the n-dimensional space consisting of all 2
n
vectors of n binary coordinates. Consequently, the coordinates ci must satisfy certain linear homogeneous equations. The sums in such equations are performed in modulo 2. In general, any r linearly independent parity check equations in c
1
, . . . , cn determine a linear subspace of dimension k=n−r. The 2
k
vectors in this subspace are the code words of a linear code.
The r parity checks may be transformed into a form which simplifies the encoding. This transformation consists of solving the original parity check equations for some r of the coordinates ci as expressions in which only the remaining n−r coordinates appear as independent variables. The k=n−r independent variables are called message digits because the 2
k
values of these coordinates may be used to represent the letters of the message alphabet. The r dependent coordinates, called check digits, are then easily computed by circuits which perform modulo 2 multiplications and additions.
At the receiver the decoder can also do modulo 2 multiplications and additions to test if the received digits still satisfy the parity check equations. The set of parity check equations that fail is called the “syndrome” because it contains the data that the decoder needs to diagnose the errors. The syndrome depends only on the error locations, not on which code word was sent. In general, a code can be used to correct e errors if each pair of distinct code words differ in at least 2e+1 of the n coordinates. For a linear code, that is equivalent to requiring the smallest number d of “ones” among the coordinates of any code word [excepting the zero word (0, 0, . . . , 0)] to be 2e+1 or more. Under these conditions each pattern of 0, 1, . . . , e−1, or e errors produces a distinct syndrome; the decoder can then compute the error locations from the syndrome. This computation may offer some difficulty, but at least, it involves only 2e binary variables, representing the syndrome, instead of all n coordinates.
The well known RS 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. RS encoding is particularly well suited for correcting burst errors, wherein a plurality of consecutive bits become corrupted. RS encoding is an algebraic block encoding and is based upon the arithmetic of finite fields. A basic definition of RS 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.
This may be better understood by visualizing RS 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. If N is the number of elements in the character set of the RS code, then the RS encode is capable of correcting a maximum of t errors, as long as the message length is equal to N−2t.
Although the use of RS encoding provides substantial benefits by enhancing the reliability with which data may be stored or transmitted, the use of RS encoding according to contemporary practice possesses inherent deficiencies. These deficiencies are associated with the decoding of RS 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
Cheng Tsen C.
Jeng Jyh H.
Truong Truieu K.
Christie Parker & Hale LLP
De'cady Albert
Torres Joseph D.
Truong T. K.
LandOfFree
Decoding method for correcting both erasures and errors of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding method for correcting both erasures and errors of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding method for correcting both erasures and errors of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2879915