Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-01-29
2002-09-24
Sheikh, Ayaz (Department: 2155)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S052000, C714S752000, C714S755000, C714S756000, C714S762000, C714S763000, C714S769000, C714S774000, C714S784000, C714S793000, C369S032010, C369S053130, C369S116000
Reexamination Certificate
active
06457156
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to error correction techniques, and more particularly to improved methods for correcting errors in data that is read from a physical medium.
2. Description of the Related Art
To maintain an acceptable level of data integrity, many types of error correction codes are commonly used. Generally, data that is stored on a physical media is encoded with data patterns that enable decoding systems to identify and correct errors that may be introduced during a reading, processing or transferring operation. In optical storage media applications, there are many factors that contribute to the introduction of errors. Some factors include media defects (i.e., such as damaged compact disc surfaces), electronic noise, component failures, poor electrical connections, and deterioration due to age. Because errors are so common, there is an ever increasing need for error correction systems that are powerful enough to correct complex error combinations, and fast enough to meet the performance demands of today's computer systems.
In optical data storage media, error correction techniques and systems are typically performed on a “per-fame” basis, where each frame has its data arranged in an array format. For ease of discussion,
FIG. 1A
shows a data frame
100
having a plurality of data bytes
104
a
and associated check bytes
104
b.
The data bytes
104
a
are arranged in Q code words
110
a
,
110
b
, and
110
c
, which are aligned in a vertical dimension along the data frame
100
. In a similar manner, P code words
112
a
and
112
b
are aligned in a horizontal dimension along the data frame
100
. When an error data byte
106
is detected in the data frame
100
after performing an error correction code (ECC) operation, the check bytes
104
b
will reflect a non-zero syndrome
108
, which indicates the presence of an error.
For example, when the error data byte
106
is detected after performing the ECC operation, non-zero syndromes
108
will be detected along both a Q code word
110
a
and a P code word
112
b.
In a similar manner, when error data bytes
116
a
and
116
b
are detected in the data frame
100
after performing an ECC operation, respective non-zero syndromes
108
will be detected in the check bytes in both the Q code words
110
b
and
110
c
, and the P code word
112
a.
As should be familiar to those skilled in the art of error correction techniques, the above described ECC operations implement well known two-dimensional (i.e., Q and P dimensions) product code to protect the data that is stored on the media. For more information on product code, reference may be made to a book entitled “Error-Correcting Codes” by W. Wesley Peterson and E. J. Weldon, Jr. (1972), and a book entitled “Practical Error Correction Design for Engineers” by Neal Glover and Trent Dudly, p. 271 (1991). These books are herein incorporated by reference in their entirety.
When product code with two check bytes is used, there are four commonly used tools that may be implemented in the correction of detected error data bytes. For example, there is single error correction (SEC) system where the location and pattern are not known, that may be used for the P dimension (i.e., SEC P) and the Q dimension (i.e., SEC Q). There is also what is known as an erasure correction (EC) system where the location is known, but the pattern is not, which is also implemented in the P dimension (i.e., EC P) and in the Q dimension (i.e., EC Q).
In general, one or more of the four error correction systems may be used in correcting errors. However, an error correction system is generally best selected depending on the number of errors that are detected along a particular code word. For example, the single error correction (SEC) system is optimized to correct only one error data byte at a time along a particular code word. This is true because single error correction systems are only required to solve simple syndrome equations.
On the other hand, when there is more than one error data byte along a particular code word, the simple syndrome equations may not work, and in some cases, additional errors may be introduced. To remedy this, erasure correction (EC) systems that implement more complex syndrome equations are used. In EC correction systems, the syndrome equations are solved by plugging in the location (L) values for each of the code words in which the error data bytes are detected. By way of example, in
FIG. 1A
two error data bytes
116
a
and
116
b
lie along the P code word
112
a.
When the locations L for the Q code words
110
b
and
110
c
are plugged into the syndrome equations of
FIG. 1B
, the error data bytes can be corrected.
Single error correction (SEC) systems are therefore best used in cases where there is only one error data byte along a particular code word, and when there is more than one error data byte along a particular code word, the erasure correction (EC) systems should be used. Unfortunately, conventional correction schemes are not configured to use the best correction system to process each unique error pattern, and therefore, often fail to produce an acceptable level of correction. In fact, most hardware error correction implementations are programmed to correct a given data frame
100
with only one or two error correction systems, without first examining which scheme is best suited for the detected errors. As a result, many correctable errors will necessarily be marked as un-correctable because only a subset of all possible correction systems will be performed.
Although software-only error correction can be used to increase the number of error correction systems used in correcting a given data frame
100
, software error correction is very computationally intensive. As a result, software-only error correction has the known detrimental effect of further burdening a computer's microprocessor. In addition, most optical drive applications will also require an additional microprocessor, microcontroller, or digital signal processor to perform some of the correction operations. Consequently, software-only implementations have been less than adequate for commercial use.
In view of the foregoing, what is needed is an error correction system that is implemented in hardware, yet provides the flexibility of using custom correction systems that are optimally suited to correct the errors detected in a particular data frame.
SUMMARY OF THE INVENTION
Broadly speaking, the present invention fills these needs by providing a method and apparatus for performing intelligent error correction. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium. Several inventive embodiments of the present invention are described below.
In one embodiment, a method for error code correction using product code is disclosed. The method includes: (a) reading a data frame and associated check bytes from a media; (b) generating an error correction model for the data frame and associated check bytes, where the error correction model is defined by non-zero syndromes in the check bytes of Q dimension code words and P dimension code words of the data frame; (c) examining the generated error correction model; and (d) correcting the data frame using a combination of error correction systems that are selected based on the examining of the generated error correction model.
In another embodiment, an apparatus for performing error correction using product code stored on a physical medium is disclosed. The apparatus includes an error correction code sequencer, and a memory block that is integrated with the error correction code sequencer. The memory block is configured to store a plurality of combinations of error correction systems. The apparatus further includes a decoder processor that is in communication with the physical medium, and a digital signal processor that is in communication with a programmable memory devi
Adaptec, Inc.
Jean Frantz B.
Martine & Penilla LLP
Sheikh Ayaz
LandOfFree
Error correction method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error correction method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823642