Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-08-13
2001-03-27
Baker, Stephen M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06209115
ABSTRACT:
FIELD OF INVENTION
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Reed-Solomon encoding is particularly well suited for correcting burst errors, wherein a plurality of consecutive bits become corrupted.
Cheng T. C.
Fu Shen-Li
Truong T. K.
Baker Stephen M.
Christie Parker & Hale LLP
LandOfFree
Reed-Solomon decoder and VLSI implementation thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reed-Solomon decoder and VLSI implementation thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-Solomon decoder and VLSI implementation thereof will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2519462