Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2000-03-31
2003-07-29
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
Reexamination Certificate
active
06601216
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of error detection in digital systems. More particularly, the invention relates to an improved error detection algorithm that is particularly useful in, although not limited to, applications involving the detection of errors in database systems and file systems, which are characterized by relatively small modifications made to previously stored pages of data.
BACKGROUND OF THE INVENTION
Digital devices are often required to transmit or store data on unreliable media. For example, bits transmitted on a phone line via modem or written to a disk may not necessarily be identical to those received on the other end of the line or read from the disk at a later time due to electronic interference, physical damage, etc. Since many such devices, computers in particular, are highly sensitive to the accuracy of the data they process, it is desirable to have a mechanism for detecting errors in data storage and transmission. This gives the device an opportunity to deal with the erroneous data gracefully. For example, a program may ignore or attempt recovery of a corrupt page on a disk, or a modem may request a retransmission of a damaged chunk of a transmission.
Error detection is often accomplished by including some number of error check bits along with the content bits. The error check bits are some function of the content bits. The check bits are recomputed on the receiving end, and compared with the transmitted check bits. The relationship between the content and check bits is such that, if an error occurred during transmission, with high probability the computed check bits will be inconsistent with the transmitted check bits and the error will be detected.
One of these techniques, the cyclic redundancy check (CRC), is probably the most widely used error detection method in the world. For instance, a version is used in the U.S. communication standard ANSI X3.66 and the European CCITT X.25, as well as in countless software products. The X3.66 standard refers to the CRC algorithm as the Frame Check Sequence, or FCS, which is described in Appendix D of ANSI 3.66-1979.
Current methods for computing the CRC accept a sequential stream of input data, compute the CRC, and emit the CRC check bits. This arrangement is convenient for many applications. However, suppose that one wishes to maintain a CRC for each page of a database file (a page is some convenient chunk of storage; for example, a typical page size is 4192 bytes). Each time data on the page is modified, the CRC must be recomputed in order to be made consistent with the new data. Current methods for doing this require starting from scratch, i.e., doing a sequential rescan of the entire page.
What is needed is a more efficient method for computing the error check bits, so that the complete CRC process does not have to be performed when only a small portion of the original data is modified, as in a database or file system.
SUMMARY OF THE INVENTION
The present invention provides a method for generating error check bits in a digital system. The invention is especially suited for use in a system in which a previously stored data page is modified. The inventive method comprises retrieving a previously computed set of error check bits, which we denote CRC(old page), for a previously stored page of data; and then, upon receiving an indication that the “old page” has been modified, updating the error check bits by incrementally updating CRC(old page) in accordance with the equation,
CRC
(new page)=
CRC
(old page)
XOR CRC
(&Dgr; page),
where CRC(&Dgr; page) is computed by taking advantage of the fact that &Dgr; page (i.e., a page where all bits are
0
except for those bit positions where the data has been modified) is sparse.
Other aspects of the present invention are described below.
REFERENCES:
patent: 5479654 (1995-12-01), Squibb
patent: 5765173 (1998-06-01), Cane et al.
patent: 5850565 (1998-12-01), Wightman
patent: 5978805 (1999-11-01), Carson
patent: 6101507 (2000-08-01), Cane et al.
patent: 6269374 (2001-07-01), Chen et al.
patent: 6357030 (2002-03-01), Demura et al.
patent: 6374264 (2002-04-01), Bohannon et al.
patent: 6449688 (2002-09-01), Peters et al.
American National Standard Institute, Inc., “American National Standard for advanced data communication control procedures (ADCCP),” 1979, ANSI X3.66-1979, 1-109.
Baker Stephen M.
Woodcock & Washburn LLP
LandOfFree
Differential cyclic redundancy check does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Differential cyclic redundancy check, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Differential cyclic redundancy check will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3054360