US4849975A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error correction method and apparatus
Assignee: International Business Machines Corp
•
Filing: 1987-11-10
•
Granted: 1989-07-18
•
Expires: 2007-11-10
Abstract
Abstract A method and apparatus is disclosed for correcting up to two byte errors in encoded uncorrected data in records of a predetermined length. As illustrated, the records are subblocks of a block in a multi-level error correction code format. The data is read from a storage device and corrected by decoding and processing four syndromes of error (S 1 , S 2 , S 3 , S 0 ) that are generated by means disclosed in the prior art. These syndromes are decoded in response to uncorrected errors in any one record by computing vectors (P, Q, and R), which are functions of the four syndromes. Binary numbers (u and v) are then determined from these vectors by table look-up to enable calculation of one value (d) from the sum of said binary numbers for determining error locations. Another value (t), mathematically related to said one value, is then determined by table look-up and the error location values (y and z) are determined by calculating the offset of binary numbers (u,v) from the other value (t). Finally, error patterns (E y and E z ) are determined by table look-up.
Inventors
- 👤 Arvind M. Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 19:02
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1806; G11B20/1809; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
149 words
A method of correcting two errors in encoded uncorrected data in records of a predetermined length read from a storage device by decoding and processing four syndromes of error, said method comprising: providing an indication of the presence of two errors in any one record; responsive to said indication, decoding said syndromes by computing vectors which are functions of said four syndromes; calculating two binary numbers from said vectors by table look-up; calculating one value from the sum of said binary numbers for the purpose of determining the locations of said two errors; determining another value, having a specific mathematical relation to said one value, by table look-up; calculating values identifying the locations of said errors by calculating the offset of said binary numbers from said other value; computing the error patterns of said errors by table look-up; and correcting said errors at said locations using said error patterns.
Claim 2
Independent Claim
149 words
A method of correcting two errors in encoded uncorrected data in records of a predetermined length read from a storage device by decoding and processing four syndromes of error, said method comprising: providing an indication of the presence of two errors in any one record; responsive to said indication, decoding said syndromes by computing vectors which are functions of said four syndromes; calculating two binary numbers from said vectors by table look-up; calculating one value from the sum of said binary numbers for the purpose of determining the locations of said two errors; determining another value, having a specific mathematical relation to said one value, by table look-up; calculating values identifying the locations of said errors by calculating the offset of said binary numbers from said other value; computing the error patterns of said errors by table look-up; and correcting said errors at said locations using said error patterns.
Claim 3
Dependent Claim
24 words
The method of claim 1, including using log and antilog tables for computing said vectors from said four syndromes and computing said error patterns.
Claim 4
Dependent Claim
130 words
In a method of correcting two errors in encoded uncorrected data in records of a predetermined length read from a storage device by decoding and processing four syndromes of error (S 1 , S 2 , S 3 , S 0 ), where a byte and each syndrome consists of b binary bits, the steps of: providing an indication of the presence of two errors in any one record; responsive to said indication, decoding said syndromes by computing vectors P, Q and R which are functions of said four syndromes; calculating binary numbers u and v from said vectors by table look-up, where u=(log.sub.α P-log.sub.α Q) modulo-(2.sup.b -1) v=(log.sub.α R-log.sub.α Q) modulo-(2.sup.b -1); and calculating the value of d toward determining the locations of the errors, where d=(u+v) modulo-(2.sup.b -1).
Claim 5
Dependent Claim
130 words
In a method of correcting two errors in encoded uncorrected data in records of a predetermined length read from a storage device by decoding and processing four syndromes of error (S 1 , S 2 , S 3 , S 0 ), where a byte and each syndrome consists of b binary bits, the steps of: providing an indication of the presence of two errors in any one record; responsive to said indication, decoding said syndromes by computing vectors P, Q and R which are functions of said four syndromes; calculating binary numbers u and v from said vectors by table look-up, where u=(log.sub.α P-log.sub.α Q) modulo-(2.sup.b -1) v=(log.sub.α R-log.sub.α Q) modulo-(2.sup.b -1); and calculating the value of d toward determining the locations of the errors, where d=(u+v) modulo-(2.sup.b -1).
Claim 6
Dependent Claim
95 words
In the method of claim 3, the further steps of: determining a value t, having a specific mathematical relation to value d, from a look-up table wherein the value of d for each of (2 b -1) values of t is predetermined by computing the value of d using an expression which will provide for each valid value of d two values of t; and in the case of two errors, fetching from the computed value of d one of the two values of t for the purpose of determining the locations of the errors.
Claim 7
Dependent Claim
52 words
In the method of claim 3, the further steps of: determining a value t, corresponding to value d, from a look-up table of t vs. d in α d =α t (α t ⊕α o ); and calculating error location values y and z, where y=(u-t) modulo-(2.sup.b -1); and z=(t-v) modulo-(2.sup.b -1).
Claim 8
Dependent Claim
33 words
In the method of claim 5, the further step of: computing error patterns E y and E z using said log and antilog tables, where E.sub.y =R/(T.sup.2y S.sub.0 ⊕S.sub.2); and E.sub.z =S.sub.0 ⊕E.sub.y.
Claim 9
Dependent Claim
48 words
The method of claim 3, wherein the vectors P, Q and R are computed from said four syndromes using a log.sub.α S=i log table and an antilog table α i =S in GF(2 b ), where GF (2 b ) represents a finite field of 2 b elements.
Claim 10
Dependent Claim
16 words
The method of claim 3, wherein b is 8 and modulo-(2 b -1) is therefore modulo-255.
Claim 11
Dependent Claim
179 words
Apparatus for correcting two errors in encoded uncorrected data in records of a predetermined length read from a storage device by decoding and processing four syndromes of error, said apparatus comprising: means providing an indication of the presence of two errors in any one record; means responsive to said indication for decoding said syndromes by computing vectors which are functions of said four syndromes; means, including log and antilog look-up tables, for calculating two binary numbers u and v from said vectors; and means, including said binary numbers for calculating one of the two values of an interim variable t from the sum d of said binary numbers for the purpose of determining the locations of said errors; means for calculating values y and z identifying the locations of said errors by calculating the offset of said binary numbers u and v from said one value of the interim variable t; means, including said log and antilog tables, for computing error patterns of said two errors; and means for correcting said errors at said locations using said error patterns.
Claim 12
Dependent Claim
179 words
Apparatus for correcting two errors in encoded uncorrected data in records of a predetermined length read from a storage device by decoding and processing four syndromes of error, said apparatus comprising: means providing an indication of the presence of two errors in any one record; means responsive to said indication for decoding said syndromes by computing vectors which are functions of said four syndromes; means, including log and antilog look-up tables, for calculating two binary numbers u and v from said vectors; and means, including said binary numbers for calculating one of the two values of an interim variable t from the sum d of said binary numbers for the purpose of determining the locations of said errors; means for calculating values y and z identifying the locations of said errors by calculating the offset of said binary numbers u and v from said one value of the interim variable t; means, including said log and antilog tables, for computing error patterns of said two errors; and means for correcting said errors at said locations using said error patterns.
Claim 13
Dependent Claim
21 words
The apparatus of claim 9, including means, including said log and antilog tables, for computing said vectors from said four syndromes.
References Cited (Backward Citations)
US4541092A
Cited
US4464753A
Cited
US4525838A
Cited
US4637021A
Cited
US4769818A
Cited
US4706250A
Cited
US4703485A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-07-17 | 1993-01-16 | 1993-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-07-17 | 1997-01-16 | 1997-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-07-17 | 2001-01-16 | 2001-07-18 | $7700.00 | Window Closed / Lapsed |