Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-01-27
2001-04-24
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S701000
Reexamination Certificate
active
06223322
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods and apparatus for processing product (rectangular) error correction-coded (ECC) data arrays, and more particularly to increasing the effective data rate as data is moved among memory and correction circuitry.
DESCRIPTION OF RELATED ART
In the prior art, digital versatile disk or alternatively digital videodisc (DVD) optical storage technology has received significant attention. In this regard, DVD is similar to that of a CD-ROM. However, it possesses a substantially greater storage capacity. Structurally, a DVD uses a single spiral track on a reflective metal surface packaged in plastic. The spiral track contains pits that are read by a drive laser as values of one or zero bits. DVD increases the data capacity of the disk by increasing the pit density and the number of tracks. As the pits become smaller and more densely packed, a smaller laser is required to read the disk. DVD uses a 635-nanometer laser compared with the 780-nanometer laser on the standard CD-ROM. Current laser support doubles the pits per track and double the tracks per surface area available on a CD-ROM. DVD further increases capacity by using a more efficient sector format. The base capacity of current DVD disks is 4.7 GB (single side/single layer), while the capacity of the CD-ROM use is in the order of 650 MB.
It is also well known in the prior art to use finite field, algebraic, block, or cyclic codes for detecting and correcting multiple bytes in error in long byte strings read back from a cyclic, concentric, tracked storage medium such as a magnetic disk storage subsystem or the like. Typically, each byte string of predetermined length is treated as if it were an algebraic polynomial and subject to modulo division by an encoding polynomial. If the code is denominated as being “systematic”, then redundant bytes derived from the data are appended to the data string which otherwise remains intact. In the case of the linear block codes, the remainder is appended to the end of the data byte string. Each data byte string plus the appended remainder is then recorded on a storage medium or transmitted. Subsequently, when the data is accessed and played back from the medium, a remainder is in principle recalculated from the datastream as it is extracted and compared with the recorded remainder. If the remainder values comparison match, the difference result is zero. If the results do not match (nonzero difference), then this is indicative or error or erasure. The codes are quite advanced such that the remainders are processed not only for identifying the presence of error, but also for pinpointing its location and determining the correction values to be applied to the datastream. This is termed syndrome processing. Codes useful for error detection and correction are called “ECC” codes.
A Reed-Solomon (RS) code exemplifies linear cyclic ECC codes used extensively in magnetic recording and communications. One advantage of RS codes is that they maintain maximum distance among codewords for any given length of data. This “spacing” between permissible codewords renders them useful for detecting and correcting randomly occurring byte errors as well as burst errors over a run of contiguous bytes. Reference should be made to copending application Ser. No. 08/838,375, now is U.S. Pat. No. 5,942,005 “Method and Means for Computationally Efficient Error and Erasure Correction in Linear Cyclic Codes”, filed Apr. 8, 1997, for a detailed description of a high-performance ECC detection and correction method and apparatus embedded in the recording channel path of a magnetic disk storage subsystem.
The RS code among other ECC codes is one dimensional in that it is defined over a data byte string of predetermined length. Such encoding is adequate for one dimensional data recording or transmission such as is found on concentric tracked magnetic disk storage. However, optical recorded images are recorded as data arrays. In this mode, so-called product or rectangular codes suitable for protecting data arrays have been extant for some time.
A product-coded data array as defined in Lin et al., “Error Control Coding: Fundamentals and Applications”,
Prentice-Hall, Inc.,
copyright 1983, at pp. 274-278, comprises a data array or rectangle of data bytes in which K
1
, rows and K
2
columns formed. Then, a horizontal ECC code of PI bytes is appended to each row and a vertical ECC code of PO bytes is appended to each column. This results in an array of dimensions (K
1
+PI)×(K
2
+PO). The rate (k
) of the rectangular code is:
k
=
(
K
1
×K
2
)/(
K+PI
)(
K
2
+PO).
When the data is read from any storage system, the data bytes are subject to error and erasure from random, intermittent, recurrent sources. These may be due to media defects, signal coupling between tracks, extraneous signals induced in the readback path, etc. In the case of a one-dimensional data array such as a row vector, error patterns may occur as random bytes in error or clustered together as a run of contiguous bytes in error. One related consequence is the fact that as the number of errors in any given row increase, then the likelihood of miscorrection by the ECC decoder increases. As Lin et al. point out at page 275, in a product-coded, two-dimensional array, one process of error detection and correction involves first error decoding the rows and then error decoding the columns. If the density of errors is relatively low, then row correction might be sufficient. However, if the density in some portions of some rows is high, then row error decoding might result in the old errors being cured and new errors being created.
It is generally desired to correct the errors in place. This means that an array is read from the medium and written into a sufficiently sized buffer or RAM and local to the storage subsystem. One processing problem is that the local buffer or RAM must be repeatedly referenced in the column as well as row directions, the data extracted and moved through the ECC processor, and the corrected data returned to the local buffer or RAM. This substantially increases both decoding time and complexity in the processing of errors and erasures.
SUMMARY OF THE INVENTION
It is an object of this invention to devise a method and apparatus for enhancing the transfer data rate among logical and memory elements processing errors and erasures in product-coded data arrays.
It is a related object to devise a method and apparatus for enhancing the transfer data rate among logical and memory elements processing errors and erasures in systematic ECC product-coded data arrays as used in DVD or other optically readable data recording subsystems.
It is yet another object that such method and apparatus efficiently effectuate an enhanced transfer data rate such that corrected data may be written back in place in the ECC product-coded data array as imaged from a storage or communications source into a buffer or RAM local to said storage or communications source.
It is still another object that such method and apparatus use an improved memory interleave arrangement for mapping the coded data into the local or working memory, increasing use efficiency without decreasing access speed of the local or working memory.
The above objects are believed satisfied by a machine-implementable method for enhancing the data transfer rate in an arrangement formed by an ECC processor coupling a local memory. The arrangement detects and corrects errors and erasures responsive to a source of error correction-coded (ECC) product data arrays. Each product-coded array has a first predetermined number of rows of Y bytes per row and a second predetermined number of columns. The arrangement writes each data array into the local memory, transfers data from the array in the local memory to the ECC processor, transfers corrected data from the ECC processor, and writes the transferred corrected data back into the local memory.
The method of the invention transfers each row of the data array from the source in row major
Michigami Toru
Tanaka Keisuke
International Business Machines - Corporation
R. Bruce Brodie
Tu Christine T.
LandOfFree
Method and apparatus for enhancing data rate in processing... 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 apparatus for enhancing data rate in processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for enhancing data rate in processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549494