Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-12-08
2001-08-21
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06279137
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains generally to error detection/correction and more particularly to systems and methods used in Reed-Solomon (RS) coding and decoding for error correction.
2. Description of Related Art
Digital processing has become pervasive in modern society. For example, digital processing circuitry is commonly employed in many modern products, including personal computers, automobiles, communications equipment, and common household devices. One advantage of digital processing circuitry is that it can perform complex operations at rapid speeds, which has allowed activities previously considered impractical to be readily implemented. A familiar example of a digital processing system is a compact disc system reading digital data from a digital compact disc.
The communication of digital data is often a crucial component of digital processing systems. Typically, data is read from or written to local or remote data storage locations in successive read and write operations across a communications link. In such data storage locations, data is preferably stored as binary digits called “bits”. In the example of a compact disc system, bit data is generally read from the compact disc and communicated among internal or external components, such as a microprocessor or a digital sound card in a personal computer.
FIG. 1A
illustrates an overview of a digital processing system including an RS encoder
150
, a communication channel or storage medium
152
, and an RS decoder
154
. An original data message is received from a data source
158
, encoded by the RS encoder
150
and transferred over a communication channel
152
or stored in storage medium
152
. The RS decoder
154
receives or reads the transferred data and decodes it to extract the original data message before sending the original data message to the data receiver
160
. As shown in
FIG. 1A
, errors
156
are sometimes introduced during the transfer of the data bits as a result of, for example, channel distortion or noise. Errors
156
can also be introduced by defects of the data storage locations at which the data is stored. Such errors are typically rare in relation to the total amount of data transferred correctly. In some systems, however, a particular kind of data error, called a “burst error”, occurs in consecutive data bits. Burst errors are often caused on compact discs, for example, by scratches, fingerprints, or other physical defects on the disc.
Consequently, to ensure data integrity within the system (i.e., to produce correct results), data errors must be detected and corrected. To facilitate error detection and correction of the data, encoding techniques are often used to encode the data prior to its transfer or storage. By encoding the data, redundancies are introduced upon the data. Typically, encoding is accomplished by dividing the message data word by a generating polynomial and appending the remainder to the message data. Such redundancies increase the likelihood that the data can be recovered even if errors are introduced into the data during its transfer. Once transferred, the encoded data is thereafter decoded to recreate the original (i.e., pre-encoding and transfer) data values.
Various coding schemes have been developed and are commonly used in digital processing and communication devices. Industry-wide standards have been set forth for coding and error correction schemes to provide intercompatibility of products and devices constructed by different manufacturers. Standards have been set forth, for instance, for the encoding of data stored on optical storage devices, such as CD-ROM storage devices.
Reed-Solomon (RS) coding is exemplary of a coding scheme typically utilized to encode digital data. Error-correction operations, however, are computationally intensive, and as products and systems emerge in which data is transferred at quicker rates, the rates at which error-correction operations must be performed must be increased correspondingly. Likewise, higher density semiconductor technologies and the faster transfer rates increase the possibility of errors and, therefore, necessitate more robust error detection and correction. When more powerful RS codes are employed (e.g., those capable of correcting three or more burst errors), the decoding algorithm becomes difficult to solve using only algebraic methods. The first part of a standard decoding algorithm, for example, calculates the partial syndromes of a codeword and converts them into the coefficients (i.e., &Lgr;
n
) of an error-locator polynomial &Lgr;(x), which has the property that its roots correspond directly to the location of the errors in the codeword. A partial syndrome is calculated by dividing a polynomial representing the received codeword by a factor of the generating polynomial. The remainder of this division operation is a partial syndrome. The second part of a decoding algorithm is to determine the roots of the error locator polynomial. For error-locator polynomials of small degree, the roots can be reasonably calculated algebraically. For error locator polynomials of high degree, however, a brute force method is preferably employed to evaluate the polynomial with every possible root value and determine which roots produce a zero result (where a zero result indicates a error location).
For these more powerful codes, a decoding algorithm may employ a method known as a Chien Search. Because the Chien Search must test every possible value, it is often the most time consuming and computationally intensive part of the decoding algorithm. Therefore, it is advantageous to perform the Chien Search in parallel to reduce the execution time for error correction. In prior designs, this parallelism was achieved by merely replicating serial Chien Search logic and parceling out portions of the search to each parallel module. The technique, however, is costly because the replication requires a significant number of logic gates. As such, need exists for a less costly design for implementing a parallel Chien Search.
SUMMARY OF THE INVENTION
A system and method in accordance with the present invention is capable of determining a root of a polynomial, where possible roots are elements of a Galois Field. An embodiment of the present invention can, for example, be utilized to find the roots of an error-locator polynomial to determine the location of an error in a codeword. In accordance with the present invention, the amount of storage required to determine the roots of the polynomial may be minimized by coupling parallel multiplier ranks to receive operands from a single rank of data storage units.
It is therefore an advantage of an embodiment of the present invention that logic gates are minimized in a Chien Search circuit.
It is another advantage of an embodiment of the present invention that memory requirements are minimized in a Chien Search program.
Another advantage of an embodiment of the present invention is that the Chien Search performance may be improved by increasing the parallelism of the implementation without requiring a proportionate increase in storage required.
Additional objects, advantages, and novel features of the invention are set forth in the description which follows and will become more apparent to those skilled in the art when taken in conjunction with the accompanying drawings. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and accommodations particularly pointed out in the appended claims.
To achieve the foregoing and other objects, in accordance with the purposes of the present invention, as embodied and broadly described herein, a system for a storage-efficient Chien Search in accordance with the present invention comprises a plurality of data storage units for storing a corresponding plurality of stored values; a base rank including a base summer and a plurality of base multipliers for producing a plurality of base product values, each base multiplier corresponding to one of the data storage
Poeppelman Alan D.
Rutherford Mark D.
De'cady Albert
Lamarre Guy
LSI Logic Corporation
LandOfFree
System and method for a storage-efficient parallel Chien Search does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for a storage-efficient parallel Chien Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for a storage-efficient parallel Chien Search will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2508676