Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-02-25
2003-12-09
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06662334
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to computer storage devices, and more particularly to devices for detecting and correcting errors in data that are read in from storage device media.
2. Description of the Related Art
Modem computer systems typically include one or more storage devices (e.g., hard disk drives, CD-ROM drives, DVD-ROM drives, etc.) to store large amount of data and programs. These mass storage devices can provide information to the processors in the computer systems through random access memory (RAM) circuitry such as dynamic random access memory (DRAM), static random access memory (SRAM), etc. For most computer systems, storing information in a mass storage device and retrieving the information as needed in a hierarchical structure is generally far more economical than using exclusively a RAM circuitry. As used herein, the term “storage device” refers to any suitable mass storage devices that store and access data to and from a circular disk such as hard disk drives, CD-ROM and CD-RAM drives, DVD-ROM and DVD-RAM drives, removable disk drives, and the like.
Mass storage devices typically store information in sectors by using magnetic or optical technology. Like most recording technology, reading data bits from the sectors often generates errors due to noise, manufacturing imperfections of the physical medium, dust, etc. To detect and correct such errors, mass storage devices typically implement an error correction code (ECC) scheme in writing to and reading from hard disk drives. The implementation of ECC schemes allows encoding of user data for reliable recovery of the original data.
Conventional ECC schemes often implement well known Reed-Solomon codes for detecting and correcting errors in data that have been read in from the devices. The Reed-Solomon codes are defined by a generator polynomial, which has 2t consecutive powers of &agr; as roots, where a is a primitive element in an extension field GF(2
m
). In this case, each codeword polynomial c(x) will have the same sequence of roots, or c(&agr;
i
)=0, where i=1, 2, 3, . . . , 2t−1. Thus, the codeword polynomial c(x) may be evaluated at each power of a to yield a set of simultaneous equations.
In this scenario, a single received word represented as a polynomial r(x) can be evaluated as the sum of the transmitted codeword polynomial c(x) and the error polynomial e(x): r(x)=c(x)+e(x). Then, the polynomial r(x) can be evaluated for each of the roots &agr;, &agr;
2
, &agr;
3
, . . . , &agr;
2t−1
to yield r(&agr;
k
)=c(&agr;
k
)+e(&agr;
k
), where k=1, 2, . . . , 2t−1. Since c(&agr;k) is equal to zero for k=1, 3, . . . , 2t−1, the equation is simplified to: r(&agr;
k
)=e(&agr;
k
). The values produced by this equation are called syndrome values and are typically denoted as s
k
=r(&agr;
k
)=e(&agr;
k
), which is equivalent to the following: e
0
(&agr;
k
)
0
+e
1
(&agr;
k
)
1
+e
2
(&agr;
k
)
2
+ . . . +e
n−1
(&agr;
k
)
n−1
.
Since the coefficient ei will either be 0 or 1, the syndrome value may be expressed as a sum of the terms having nonzero coefficients only. By reversing the order of exponents, the syndrome value can be derived in accordance with the following equation:
S
k
=
∑
e
i
≠
0
(
α
i
)
k
,
k
=
1
,
3
,
…
,
2
t
-
1
(
1
)
Equation (1) thus defines a system of equations that can be solved for the nonzero coefficients e
i
based on the syndrome values s
k
. The Reed-Solomon codes for encoding and decoding error correction codes are well known in the art and are described in more detail in in Error Coding Cookbook (1996), by C. Britton Rorabaugh, ISBN 0-07-911720-1, and in Error Control Systems for Digital Communication and Storage by Stephen B. Wicker, ISBN 0-13-200809-2. These references are incorporated herein by reference.
In order to utilize the ECC scheme, data is first encoded into an ECC format for storage. For example, a conventional ECC scheme typically computes ECC checkbytes for a given block of user data such as a sector. Then, the computed ECC checkbytes are appended to the sector of user data to form ECC data sector and then recorded on a storage device medium. Thus, each ECC data sector typically contains user data (e.g., 512 bytes) and additional ECC check bytes appended to the user data bytes.
A Each of the ECC data sectors also includes a sync pattern or bytes for identifying the beginning of the sector. The sync pattern or bytes are thus used to delineate a sector boundary. When the recorded sectors of data are read from a storage device medium, the ECC scheme decodes the received sector data including the ECC bytes by generating syndromes for the received data in each of the sectors. Zero syndromes indicate that no error has been detected in the sector while non-zero syndromes indicate that one or more errors have been detected in the sector. For each of the sectors with non-zero syndromes, error locations and error patterns are determined and based on the error locations and patterns, the detected errors in the sector are corrected.
Hard disk drives implementing the ECC schemes are well known in the art and is described, for example, the following references: U.S. Pat. No. 6,192,499, by Honda Yang and entitled “Device and Method for Extending Error Correction Beyond One Sector Time” and U.S. Pat. No. 6,092,233, by Honda Yang and entitled “Pipelined Berlekamp-Massey Error Locator Polynomial Generating Apparatus and Method.” In addition, optical disk drives (e.g., CD-ROM, CD-RAM, DVD-ROM, DVD-RAM, etc.) implementing the ECC schemes are also well known in the art and are described, for example, in U.S. Pat. No. 6,457,156, by Ross J. Stenfort and entitled “Error Correction Method and Apparatus.” These references are incorporated herein by reference.
As the storage device density increases to store more data on a given storage medium, however, more errors will need to be detected and corrected when reading data off the medium. In addition, modern storage devices typically gain performance advantages by reading the data off the medium at a higher data rate. In both instances, more data are read and processed for a given time or more time is required to process the same amount of data. Even in the absence of these factors, it is often desirable to implement a higher correction power in the ECC schemes by increasing the number of errors detected and corrected.
Unfortunately, detecting and correcting more errors require more time to decode errors in ECC data sectors by determining error locations and patterns. For example, in order to detect more errors, more syndromes need to be generated for a given ECC data sector. The generation of more syndromes, in turn, requires more computing resources and/or time to determine the error locations and patterns.
Furthermore, modem ECC decoders typically strive to process error on-the-fly by computing the error patterns and locations for a received ECC data sector within the time to receive the next ECC data sector. In such a circumstance, the time to compute the error locations and patterns is further diminished. As a result, the ECC decoder may not be able to decode the errors for the received ECC data sector within the time to receive the next ECC data sector. In this case, an error event often called “correction overrun” is generated to suspend reading of the next ECC data sector from a storage medium until the ECC decoder generates the error locations and patterns. Then, the reading of the next ECC data sector resumes by waiting for the storage medium to make another revolution to the beginning of the interrupted sector. Such interruption of data flow thus causes undesirable delays and performance penalties.
One solution implements a very fast ECC decoder to ensure that the worst case buffer access latency is within the allotted time to receive the next ECC sector data. This approach, however, would
Adaptec, Inc.
Baker Stephen M.
Martine & Penilla LLP
LandOfFree
Method and device for performing error correction on ECC... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for performing error correction on ECC..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for performing error correction on ECC... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3106715