US4564941A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error detection system
Assignee: Apple Inc
•
Filing: 1983-12-08
•
Granted: 1986-01-14
•
Expires: 2003-12-08
Abstract
Abstract The present invention provides methods and apparatus for improved error detection in a data processing system. The techniques of the present invention insure that there is a high probability that an error in a record of data (each record comprising a plurality of data bits) is detected. In the event of an error, the present invention applies a randomizing function to the error which modifies subsequent bits within the record and then propagates and further randomizes the error throughout the record to magnify its apparent size. The randomizing and propagation of the error significantly lowers the misdetection probability for random errors within a record, in that error detectability is no longer pattern sensitive. The use of both propagation and randomization functions significantly alters the data containing an error, such that a high probability of detection using check-sum techniques exists.
Inventors
- 👤 Richard N. Woolley
- 👤 Neal Glover
- 👤 Richard Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 21:19
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1866; H03M13/27
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
144 words
A method for storing and recovering data in a data processing system, said data being organized into a plurality (N) of sequential bytes, such that an error in a byte is propagated throughout each subsequent byte, comprising the steps of: performing an exclusive-OR operation between each byte (i) and the previous byte (i-1) in order to obtain a resultant value (R i ); storing each of said resultant values R i in a storage device; reading said resultant values R i from said storage device; recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte (i-1), such that: ##EQU1## where: "N"=number of bytes in said data, and "⊕" denotes an exclusive-OR operation; whereby an error in a byte is propagated throughout subsequent bytes, thereby increasing the detectability of said error.
Claim 2
Independent Claim
144 words
A method for storing and recovering data in a data processing system, said data being organized into a plurality (N) of sequential bytes, such that an error in a byte is propagated throughout each subsequent byte, comprising the steps of: performing an exclusive-OR operation between each byte (i) and the previous byte (i-1) in order to obtain a resultant value (R i ); storing each of said resultant values R i in a storage device; reading said resultant values R i from said storage device; recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte (i-1), such that: ##EQU1## where: "N"=number of bytes in said data, and "⊕" denotes an exclusive-OR operation; whereby an error in a byte is propagated throughout subsequent bytes, thereby increasing the detectability of said error.
Claim 3
Dependent Claim
40 words
The method as defined by claim 1, further including the step of calculating a first check-sum quantity for said data prior to said storage step and storing said first check-sum with said resultant values R i in said storage means.
Claim 4
Dependent Claim
21 words
The method as defined by claim 2, further including the step of calculating a second check-sum quantity for said recovered data.
Claim 5
Dependent Claim
22 words
The method as defined by claim 3, wherein an error is detected if said first and second check-sum quantities do not match.
Claim 6
Dependent Claim
40 words
The method as defined by claim 4, wherein said first and second check-sums are calculated by evaluating the expression: ##EQU2## where, byte i denotes a byte at position i (where i=0, 1, 2 . . . N-1) in said data.
Claim 7
Dependent Claim
36 words
The method as defined by claim 5, wherein a plurality of first and second check-sums are calculated for said data, each of said check-sums being calculated for a predetermined interleaved multiple of an initial specified byte.
Claim 8
Dependent Claim
148 words
An improved error detection system for data stored and recovered in a data processing system comprising: storage means for storing data as a plurality (N) of sequential bytes; processing means coupled to said memory means for performing logical operation on said data, said processing means including: writing means for performing an exclusive-OR operation between each byte (i) and the previous byte (i-1) of said data in order to obtain a resultant value (R i ), and storing said resultant value R i in said storage means; reading means for recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte (i-1), such that: ##EQU3## where: "N"=number of bytes in said data, and "⊕" denotes an exclusive-OR operation; whereby an error in a byte is propagated throughout subsequent bytes, thereby increasing the detectability of said error.
Claim 9
Dependent Claim
148 words
An improved error detection system for data stored and recovered in a data processing system comprising: storage means for storing data as a plurality (N) of sequential bytes; processing means coupled to said memory means for performing logical operation on said data, said processing means including: writing means for performing an exclusive-OR operation between each byte (i) and the previous byte (i-1) of said data in order to obtain a resultant value (R i ), and storing said resultant value R i in said storage means; reading means for recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte (i-1), such that: ##EQU3## where: "N"=number of bytes in said data, and "⊕" denotes an exclusive-OR operation; whereby an error in a byte is propagated throughout subsequent bytes, thereby increasing the detectability of said error.
Claim 10
Dependent Claim
40 words
The error detection system as defined by claim 7, wherein said processing means includes means for calculating a first check-sum quantity for said data and storing said first check-sum in said storage means with said resultant values R i .
Claim 11
Dependent Claim
25 words
The error detection system as defined by claim 8, wherein said processing means includes means for calculating a second check-sum quantity for said recovered data.
Claim 12
Dependent Claim
23 words
The error detection system as defined by claim 9, wherein an error is detected if said first and second check-sums do not match.
Claim 13
Dependent Claim
46 words
The error detection system as defined by claim 10, wherein said first and second check-sums are calculated by said processing means by evaluating the expression: ##EQU4## where, byte i denotes a byte at position i (where i=0, 1, 2 . . . N-1) in said data.
Claim 14
Dependent Claim
38 words
The error detection system as defined by claim 11, wherein a plurality of first and second check-sums are calculated for said data, each of said check-sums are calculated for a predetermined interleaved multiple of an initial specified byte.
Claim 15
Independent Claim
184 words
A method for storing and recovering data in a data processing system, said data being organized into a plurality (N) of sequential bytes, such that an error in a byte is distributed and propagated throughout each subsequent byte, comprising the steps of: performing an exclusive-OR operation between each byte (i) and the previous byte (i-1), said previous byte having been randomized by a predetermined function in order to obtain a resultant value (R i ); storing the value of each of said resultant values R i in a storage device; reading said resultant values R i from said storage device; recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte, said predetermined function having been applied to said previously recovered data byte (i-1) prior to said exclusive-OR operation such that: ##EQU5## where: "N"=number of sequential bytes in said data "⊕" denotes an exclusive-OR operation "'" represents said predetermined function; whereby an error in a byte is distributed and propagated throughout each subsequent byte, thereby increasing the detectability of said error.
Claim 16
Independent Claim
184 words
A method for storing and recovering data in a data processing system, said data being organized into a plurality (N) of sequential bytes, such that an error in a byte is distributed and propagated throughout each subsequent byte, comprising the steps of: performing an exclusive-OR operation between each byte (i) and the previous byte (i-1), said previous byte having been randomized by a predetermined function in order to obtain a resultant value (R i ); storing the value of each of said resultant values R i in a storage device; reading said resultant values R i from said storage device; recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte, said predetermined function having been applied to said previously recovered data byte (i-1) prior to said exclusive-OR operation such that: ##EQU5## where: "N"=number of sequential bytes in said data "⊕" denotes an exclusive-OR operation "'" represents said predetermined function; whereby an error in a byte is distributed and propagated throughout each subsequent byte, thereby increasing the detectability of said error.
Claim 17
Dependent Claim
40 words
The method as defined by claim 13, further including the step of calculating a first check-sum quantity for said data prior to said storage step and storing said first check-sum with said resultant values R i in said storage means.
Claim 18
Dependent Claim
21 words
The method as defined by claim 14, further including the step of calculating a second check-sum quantity for said recovered data.
Claim 19
Dependent Claim
22 words
The method as defined by claim 15, wherein an error is detected if said first and second check-sum quantities do not match.
Claim 20
Dependent Claim
40 words
The method as defined by claim 16, wherein said first and second check-sums are calculated by evaluating the expression: ##EQU6## where, byte i denotes a byte at position i (where i=0, 1, 2 . . . N-1) in said data.
Claim 21
Dependent Claim
36 words
The method as defined by claim 17, wherein a plurality of first and second check-sums are calculated for said data, each of said check-sums being calculated for a predetermined interleaved multiple of an initial specified byte.
Claim 22
Dependent Claim
14 words
The method as defined by claim 18, wherein said bytes are interleaved by 1.
Claim 23
Dependent Claim
14 words
The method as defined by claim 18, wherein said bytes are interleaved by 3.
Claim 24
Dependent Claim
26 words
The method as defined by claim 18, wherein said data is organized into records, each of said records comprising a plurality of bytes having 8 bits.
Claim 25
Dependent Claim
180 words
An improved error detection system for data stored and recovered in a data processing system, comprising: storage means for storing data as a plurality (N) of sequential bytes; processing means coupled to said memory means for performing logical operations on said data, said processing means including: writing means for performing an exclusive-OR operation between each byte (i) and the previous byte (i-1), said previous byte having been randomized by a predetermined function in order to obtain a resultant value (R i ) and storing said resultant value R i in said storage means; reading means for recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte, said predetermined function having been applied to said previously recovered data byte (i-1) prior to said exclusive-OR operation such that: ##EQU7## where: "N"=number of sequential bytes in said data "⊕" denotes an exclusive-OR operation "'" represents said predetermined function; whereby an error in a byte is distributed and propagated throughout each subsequent byte, thereby increasing the detectability of said error.
Claim 26
Dependent Claim
180 words
An improved error detection system for data stored and recovered in a data processing system, comprising: storage means for storing data as a plurality (N) of sequential bytes; processing means coupled to said memory means for performing logical operations on said data, said processing means including: writing means for performing an exclusive-OR operation between each byte (i) and the previous byte (i-1), said previous byte having been randomized by a predetermined function in order to obtain a resultant value (R i ) and storing said resultant value R i in said storage means; reading means for recovering said data bytes from said resultant values by performing an exclusive-OR operation between each value R i and the previously recovered data byte, said predetermined function having been applied to said previously recovered data byte (i-1) prior to said exclusive-OR operation such that: ##EQU7## where: "N"=number of sequential bytes in said data "⊕" denotes an exclusive-OR operation "'" represents said predetermined function; whereby an error in a byte is distributed and propagated throughout each subsequent byte, thereby increasing the detectability of said error.
Claim 27
Dependent Claim
40 words
The error detection system as defined by claim 22, wherein said processing means includes means for calculating a first check-sum quantity for said data and storing said first check-sum in said storage means with said resultant values R i .
Claim 28
Dependent Claim
25 words
The error detection system as defined by claim 23, wherein said processing means includes means for calculating a second check-sum quantity for said recovered data.
Claim 29
Dependent Claim
43 words
The error detection system as defined by claim 24, wherein said processing means includes means for calculating a plurality of said first and second check-sums for said data, each of said check-sums calculated for a predetermined interleaved multiple of an initial specified byte.
Claim 30
Dependent Claim
16 words
The error detection system as defined by claim 25, wherein said bytes are interleaved by one.
Claim 31
Dependent Claim
16 words
The error detection system as defined by claim 25, wherein said bytes are interleaved by three.
Claim 32
Independent Claim
99 words
A method for storing data in a data processing system, said data being organized into a plurality (N) of sequential interleaved bytes, comprising the steps of: defining first and second check-sums corresponding to interleaved bytes of said data; randomizing the contents of said second check-sum by a predetermined function; setting the contents of said first check-sum equal to the contents of said first check-sum plus the contents of said first byte; performing an exclusive-OR operation between the randomized contents of said second check-sum and said first byte; storing the resultant value of said exclusive-OR operation in a storage device.
Claim 33
Independent Claim
99 words
A method for storing data in a data processing system, said data being organized into a plurality (N) of sequential interleaved bytes, comprising the steps of: defining first and second check-sums corresponding to interleaved bytes of said data; randomizing the contents of said second check-sum by a predetermined function; setting the contents of said first check-sum equal to the contents of said first check-sum plus the contents of said first byte; performing an exclusive-OR operation between the randomized contents of said second check-sum and said first byte; storing the resultant value of said exclusive-OR operation in a storage device.
Claim 34
Dependent Claim
67 words
The method as defined by claim 28, further including the steps of: setting the contents of said second check-sum equal to the sum of the contents of said second check-sum plus the contents of said second byte; performing an exclusive-OR operation between the contents of said first check-sum and the contents of said second byte; storing the resultant value of said exclusive-OR operation in said storage device.
Claim 35
Dependent Claim
25 words
The method as defined by claim 29, further including the step of defining a third check-sum corresponding to bytes of said data interleaved by three.
Claim 36
Dependent Claim
22 words
The method as defined by claim 30, wherein said randomization function comprises a linear rotation of the contents of said second check-sum.
Claim 37
Dependent Claim
29 words
The method as defined by claim 31, wherein said method is applied to each of said sequential interleaved bytes, such that representations of each of said bytes are stored.
Claim 38
Dependent Claim
94 words
The method as defined by claim 28, further including a method for recovering said stored data, comprising steps of: setting the value of said first and second check-sums equal to zero; reading the first said stored resultant value obtained from said excusive-OR operation between said second check-sum and said first byte from said storage device; performing an exclusive-OR operation between said resultant value and said second check-sum, such that said first data byte is recovered; setting the contents of said first check-sum equal to the value of said first check-sum plus said first byte.
Claim 39
Dependent Claim
87 words
The method of recovery as defined by claim 33, further comprising the steps of: reading the second said stored resultant value obtained from said exclusive-OR operation between said first check-sum and the contents of said second byte; performing an exclusive-OR operation between said resultant value and said first check-sum, such that said second data byte is recovered; setting the contents of said second check-sum equal to the value of said second check-sum plus said second byte; randomizing the contents of said second check-sum by said predetermined function.
Claim 40
Dependent Claim
25 words
The method as defined by claim 34, further including the step of defining a third check-sum corresponding to bytes of said data interleaved by three.
Claim 41
Dependent Claim
27 words
The method as defined by claim 35, wherein said method is applied to each of said plurality (N) bytes to recover said data from said storage device.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-01-13 | 1989-07-15 | 1990-01-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-01-13 | 1993-07-15 | 1994-01-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-01-13 | 1997-07-15 | 1998-01-14 | $7700.00 | Window Closed / Lapsed |