Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-05-07
2002-08-13
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S799000
Reexamination Certificate
active
06434719
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention pertains to the correction of errors in a data stream such as that acquired from a storage medium, particularly when an estimate of reliability of the data is provided.
2. Related Art and Other Considerations
It is important that data be accurately transmissible from a source to a destination, since many operations depend upon the integrity of the data obtained from the source. Often the source of data utilized for a particular operation is a data storage medium and the destination is a computer or the like. The data storage medium can take various forms, such as a magnetic disk transduced by a magnetic disk drive or an optical disk transduced by an optical disk drive, for example.
On occasion the data may not be correctly read from the data storage medium or not correctly transmitted along a read channel of the drive to the destination. Fortunately, some apparatus that read or transmit data from a source to a destination, e.g., disk drives, have capabilities for attempting to detect and/or correct errors in the data stream from the source.
There is a substantial body of prior art directed to various techniques for error correction of data. Included in this body of prior art are numerous employments of “product codes” or two-dimensional codes. As used herein, “product codes” typically operate upon a matrix of data, with a first parity or code operation being performed upon a row of the matrix (horizontal) and a second parity or code operation being performed upon a column of the matrix (vertical). The horizontal and vertical codes may be employed in alternating sequence for resolving errors in the matrix.
It is known that some types of read channels are particular prone to suffer the prevalence of certain types of errors (e.g., single bits, tribits, etc.). In addition, various techniques have been introduced for obtaining a reliability estimate of data transmitted from a source to a destination. One such technique is referred to as the soft output Viterbi algorithm (SOVA), and is documented, e.g., by Hagenauer and Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and Its Applications”, Conference Record, IEEE Global Telecommunications Conference & Exhibition, Dallas, Tex., Nov. 27-30, 1989, Vol. 3, pp. 1680-1686. The SOVA technique assigns a reliability value to each bit in the data stream. Other techniques for obtaining reliability estimates also exist, such as that referenced as the “BCJR” algorithm [L. R. Bahl et al., “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”,
IEEE Tranactions On Information Theory,
March 1974, pp. 284-287].
What is needed, and thus an object of the present invention, is an effective way to use reliability information in error detection/location schemes which operate upon a matrix.
BRIEF SUMMARY OF THE INVENTION
In accordance with method and apparatus of the present invention, data obtained from a transmission channel is conceptualized as a matrix. Erroneous column(s) in the matrix are first determined on the basis of column parity violation. An error instance in the matrix is next ascertained by matching the erroneous column(s) with an error event characteristic of the transmission channel. A candidate error row is then located in the matrix with respect to the error instance. Lastly, positions in the matrix specified by an intersection of the candidate error row and the erroneous column(s) of the error instance are corrected.
Data reliability values assigned to positions of the matrix are used to determine the candidate error row. In particular, with respect to the erroneous column(s) of the error instance, and for each of plural rows of the matrix, factors related to reliability values assigned to positions of the matrix are summed to determine a least reliable row as the candidate error row. In an illustrated embodiment, squares of the reliability values are summed to determine a least reliable row, the least reliable row having an extreme (e.g., smallest) sum.
In correcting the row of a matrix, the invention is careful not to correct in isolation an odd weight error instance (e.g., an error instance involving an odd number of columns), lest row parity be violated. To this end, when a candidate error row has been selected for an odd weight error instance, the invention presumes that another odd weight error instance also resides in the same row. The correction of two odd weight error instances in the same row therefore does not violate row parity.
Preferably the transmission channel is included in a disk drive, and is one of an EPR4 and E
2
PR4 read channel. In the case of an EPR4 read channel, the error event characteristic of the transmission channel is one of (1) a di-bit error; (2) a tri-bit error, followed by one or more bits of no error, followed by a single bit error; (3) a single bit error; (4) a tri-bit error; and (5) a quad-bit error.
The operation of the invention is preferably preceded by a row error detection/correction operation which corrects single bit and tri-bit row errors in the matrix.
REFERENCES:
patent: 4653051 (1987-03-01), Sugimura et al.
patent: 5170400 (1992-12-01), Dotson
patent: 5291499 (1994-03-01), Behrens et al.
patent: 5666371 (1997-09-01), Purdham
patent: 6005727 (1999-12-01), Behrens et al.
Hagenauer and Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and Its Applications”, Conference, Record, IEEE Global Telecommunications Conference & Exhibition, Dallas, Texas, Nov. 27-30, 1989, vol. 3, pp. 1680-1686.
L.R. Bahl et al., “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”,IEEE Transactions On Information Theory, Mar. 1974, pp. 284-287.
Cirrus Logic Inc.
Nixon & Vanderhye P.C.
Ton David
LandOfFree
Error correction using reliability values for data matrix 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 using reliability values for data matrix, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction using reliability values for data matrix will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2939887