Differential cyclic redundancy check

• US 6,601,216 B1
• Filed: 03/31/2000
• Issued: 07/29/2003
• Est. Priority Date: 03/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Obata, Kenji C.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/539,372
• Time in Patent Office: 1,215 Days
• Field of Search: 714/807
• US Class Current: 714/807
• CPC Class Codes: H03M 13/093 CRC update after modification of the information word

Abstract

A method for generating error check bits in a digital system is suited for use in a system in which a previously stored data page is modified. The 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(Δ page),

where CRC(Δ page) is computed by taking advantage of the fact that Δ page (i.e., a page where all bits are 0 except for those bit positions where the data has been modified) is sparse.

Claims

1. A method for generating error check bits in a digital system, comprising:

storing a page of digital information (old page) and associated CRC check bits (CRC(old page));

receiving an indication that a new page has been created from the old page by modification of at least some of the bits making up the page of digital information;

forming a page of data (Δ

page) indicative of the changed bits; and

computing CRC check bits (CRC(new page)) for the new page based on CRC(old page) and CRC check bits for Δ

page CRC(Δ

page), wherein CRC(Δ

page) is obtained from a pre-computed lookup table containing CRC check bits for predefined error patterns.

2. A method as recited in claim 1, wherein each page is made up of a prescribed number of bits.

3. A method as recited in claim 2, wherein Δ

page is sparse.

4. A method as recited in claim 3, wherein the old page and new page are stored in a database system.

5. A method as recited in claim 3, wherein the old page and new page are stored in a file system.

6. A method as recited in claim 3, comprising the step of computing CRC(new page) in accordance with the equation,

9. A computer readable storage medium comprising code for instructing a computer in carrying out the steps recited in claim 1.

7. A method for generating error check bits in a digital system, comprising:

storing a page of digital information (old page) and associated CRC check bits (CRC(old page));

receiving an indication that a new page has been created from the old page by modification of at least some of the bits making up the page of digital information;

forming a page of data (Δ

page) indicative of the changed bits, wherein Δ

page is sparse; and

computing CRC check bits (CRC(new page)) for the new page based on CRC(old page) and Δ

page, wherein CRC(new page) is computed in accordance with the equation,

8. A method as recited in claim 7, further comprising, after receiving a change request:

finding intervals containing changed bits;

for each such interval, looking up a table entry and forming a CRC polynomial f(x) based on the table entry and a polynomial Δ

(x) based on Δ

page;

forming the product f(x)*Δ

(x);

computing CRC(Δ

page)=CRC(f(x)*Δ

(x)); and

computing CRC(new page)=CRC(old page) XOR CRC(Δ

page).

10. A computer readable storage medium comprising code for instructing a computer in carrying out the steps recited in claim 8.

11. A digital system, comprising:

a computer;

a computer readable storage medium operatively coupled to the computer; and

computer code executable by the computer for carrying a differential algorithm for generating error check bits, wherein said algorithm comprises;

i. storing in the storage medium a page of digital information (old page) and associated CRC check bits (CRC(old page));

ii. receiving an indication that a new page has been created from the old page by modification of at least some of the bits making up the page of digital information;

iii. forming a page of data (Δ

page) indicative of the changed bits; and

iv. computing CRC check bits (CRC(new page)) for the new page based on CRC(old page) and CRC check bits for Δ

page CRC(Δ

page), wherein CRC(Δ

page) is obtained from a pre-computed lookup table containing CRC check bits for predefined error patterns.

12. A system as recited in claim 11, wherein each page is made up of a prescribed number of bits.

13. A system as recited in claim 12, wherein Δ

page is sparse.

14. A system as recited in claim 13, wherein the old page and new page are stored in a database system.

15. A system as recited in claim 13, wherein the old page and new page are stored in a file system.

16. A system as recited in claim 13, wherein the algorithm further comprises computing CRC(new page) in accordance with the equation,

17. A digital system, comprising:

a computer;

a computer readable storage medium operatively coupled to the computer; and

computer code executable by the computer for carrying a differential algorithm for generating error check bits, wherein said algorithm comprises;

storing in the storage medium a page of digital information (old page) and associated CRC check bits (CRC(old page));

receiving an indication that a new page has been created from the old page by modification of at least some of the bits making up the page of digital information;

forming a page of data (Δ

page) indicative of the changed bits, wherein Δ

page is sparse; and

computing CRC check bits (CRC(new page)) for the new page based on CRC(old page) and Δ

page, wherein CRC(new page) is computed in accordance with the equation

18. A system as recited in claim 17, wherein the algorithm further comprises, after receiving a change request:

finding intervals containing changed bits;

for each such interval, looking up a table entry and forming a CRC polynomial f(x) based on the table entry and a polynomial Δ

(x) based on Δ

page;

forming the product f(x)*Δ

(x);

computing CRC(Δ

page)=CRC(f(x)*Δ

(x)); and

computing CRC(new page)=CRC(old page) XOR CRC(Δ

page).