Patent US5027357A successfully refreshed from Google Patents.
US5027357A
Expired / Lapsed
US
⏱️ 0.0 years remaining
ECC/CRC error detection and correction system
Assignee: Advanced Micro Devices Inc
•
Filing: 1988-10-14
•
Granted: 1991-06-25
•
Expires: 2008-10-14
Abstract
Abstract Occurrence of uncorrectable errors in a stored sector of data which includes a data block, an error checking and correcting (ECC) block and an error detecting (CRC) block is detected. ECC logic is connected to a data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying a location and a value for correctable errors in the sector. CRC logic is connected to the data bus and responsive to the CRC block in the sector for generating a syndrome identifying detected errors in the data block. An evaluation logic circuit is included that is coupled to the ECC logic and the CRC logic and responsive to the error polynomial and the syndrome for generating an uncorrectable error signal if the detected errors do not match the correctable errors. The error checking and correcting code is a Reed-Solomon code as in the X3B11 standard. Likewise the CRC code is a Reed-Solomon code as in the X3B11 standard. The evaluation logic implements a reverse CRC generation polynomial having a plurality of terms in the same order as the error polynomial. Detection logic receives the plurality of terms of the error polynomial, generates an estimated CRC syndrome based on the reverse CRC generation polynomial, and generates the uncorrectable error signal if the estimated CRC syndrome is not equal to the generated CRC syndrome.
Inventors
- 👤 Chung-Li Yu
- 👤 Edward T. Pak
- 👤 Ho-Ming Leung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 10:47
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; H03M13/091; H03M13/13; H03M13/15; H03M13/151; H03M13/158; H03M13/1515
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
201 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, an apparatus for signalling the occurrence of uncorrectable errors in a sector, the apparatus comprising: a data bus, connected to the store, for communication of the sector; first means, connected to the data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying location and value for correctable errors in the sector; second means, connected to the data bus and responsive to the ED block in the sector, for generating a syndrome identifying detected errors in the data block; and evaluation means, coupled to the first means and the second means and responsive to the error polynomial and the syndrome, for generating an uncorrectable error signal if the detected errors do not match the correctable errors; wherein the first means includes means for performing a forward Chien Search over the sector so that the error polynomial has an order with respect to bytes of data within the data block, and wherein the syndrome is generated in a reverse order with respect to the order.
Claim 2
Dependent Claim
201 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, an apparatus for signalling the occurrence of uncorrectable errors in a sector, the apparatus comprising: a data bus, connected to the store, for communication of the sector; first means, connected to the data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying location and value for correctable errors in the sector; second means, connected to the data bus and responsive to the ED block in the sector, for generating a syndrome identifying detected errors in the data block; and evaluation means, coupled to the first means and the second means and responsive to the error polynomial and the syndrome, for generating an uncorrectable error signal if the detected errors do not match the correctable errors; wherein the first means includes means for performing a forward Chien Search over the sector so that the error polynomial has an order with respect to bytes of data within the data block, and wherein the syndrome is generated in a reverse order with respect to the order.
Claim 3
Dependent Claim
233 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, an apparatus for signalling the occurrence of uncorrectable errors in a sector, the apparatus comprising: a data bus, connected to the store, for communication of the sector; first means, connected to the data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying location and value for correctable errors in the sector, wherein the error polynomial has a plurality of terms, and the first means generates the plurality of terms of the error polynomial from low order to high order with respect to bytes of data in the data block; second means, connected to the data bus and responsive to the ED block in the sector, for generating a syndrome identifying detected errors in the data block, wherein the syndrome is a second polynomial with a plurality of terms, and the second means generates the plurality of terms in the second polynomial from high order to low order based on a CRC generation polynomial with a plurality of terms; and evaluation means, coupled to the first means and the second means and responsive to the error polynomial and the syndrome, for generating an uncorrectable error signal if the detected errors do not match the correctable errors.
Claim 4
Dependent Claim
233 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, an apparatus for signalling the occurrence of uncorrectable errors in a sector, the apparatus comprising: a data bus, connected to the store, for communication of the sector; first means, connected to the data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying location and value for correctable errors in the sector, wherein the error polynomial has a plurality of terms, and the first means generates the plurality of terms of the error polynomial from low order to high order with respect to bytes of data in the data block; second means, connected to the data bus and responsive to the ED block in the sector, for generating a syndrome identifying detected errors in the data block, wherein the syndrome is a second polynomial with a plurality of terms, and the second means generates the plurality of terms in the second polynomial from high order to low order based on a CRC generation polynomial with a plurality of terms; and evaluation means, coupled to the first means and the second means and responsive to the error polynomial and the syndrome, for generating an uncorrectable error signal if the detected errors do not match the correctable errors.
Claim 5
Dependent Claim
20 words
The apparatus of claim 2, wherein: the first means includes means for performing a backward Chien Search over the sector.
Claim 6
Dependent Claim
23 words
The apparatus of claim 2, wherein: the ECC block is a first Reed-Solomon polynomial; and the ED block is a second Reed-Solomon polynomial.
Claim 7
Dependent Claim
27 words
The apparatus of claim 4, wherein: the first Reed-Solomon polynomial and the second Reed-Solomon polynomial are specified by international standard X3B11 for 51/4 inch optical storage media.
Claim 8
Dependent Claim
67 words
The apparatus of claim 2, wherein the evaluation means includes: means for reversing the second polynomial to generate a reverse second polynomial having a plurality of terms from low order to high order; and detection means, coupled with the means for reversing and receiving the plurality of terms of the error polynomial as generated and responsive to the reverse second polynomial, for generating the uncorrectable error signal.
Claim 9
Dependent Claim
42 words
The apparatus of claim 6, wherein: the plurality of terms of the error polynomial includes a final term that is received last by the detection means; and the detection means generates the uncorrectable error signal in response to receiving the final term.
Claim 10
Dependent Claim
61 words
The apparatus of claim 6, wherein the detection means includes: means for combining the error polynomial with a reverse CRC generation polynomial to generate an estimated reverse second polynomial; and means, connected to the means for combining and the means for reversing, for comparing the reverse second polynomial with the estimated reverse second polynomial to indicate the occurrence of uncorrectable errors.
Claim 11
Dependent Claim
42 words
The apparatus of claim 8, wherein: the plurality of terms of the error polynomial includes a final term that is received last by the detection means; and the detection means generates the uncorrectable error signal in response to receiving the final term.
Claim 12
Dependent Claim
198 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, a method for signalling the occurrence of uncorrectable errors in a sector, the method comprising the steps of: communicating the sector across a data bus; generating, in error detecting and correcting logic in response to the sector on the data bus, an error polynomial including a plurality of terms, the error polynomial identifying location and value for correctable errors in the sector; generating, in error detecting logic in response to the sector on the data bus, a syndrome identifying detected errors in the data block, and storing the syndrome; and generating, in combining logic in response to the error polynomial and the syndrome, an uncorrectable error signal if the detected errors do not match the correctable errors; wherein the step of generating an error polynomial includes performing a forward Chien Search over the sector so that the error vector has an order with respect to bytes of data within the data block, and wherein the syndrome is generated in a reverse order with respect to the order.
Claim 13
Dependent Claim
198 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, a method for signalling the occurrence of uncorrectable errors in a sector, the method comprising the steps of: communicating the sector across a data bus; generating, in error detecting and correcting logic in response to the sector on the data bus, an error polynomial including a plurality of terms, the error polynomial identifying location and value for correctable errors in the sector; generating, in error detecting logic in response to the sector on the data bus, a syndrome identifying detected errors in the data block, and storing the syndrome; and generating, in combining logic in response to the error polynomial and the syndrome, an uncorrectable error signal if the detected errors do not match the correctable errors; wherein the step of generating an error polynomial includes performing a forward Chien Search over the sector so that the error vector has an order with respect to bytes of data within the data block, and wherein the syndrome is generated in a reverse order with respect to the order.
Claim 14
Dependent Claim
212 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, a method for signalling the occurrence of uncorrectable errors in a sector, the method comprising the steps of: communicating the sector across a data bus; generating, in error detecting and correcting logic in response to the sector on the data bus, an error polynomial including a plurality of terms, the error polynomial identifying location and value for correctable errors in the sector, the plurality of terms of the error polynomial being generated from low order to high order with respect to bytes of data in the data block; generating, in error detecting logic in response to the sector on the data bus, a syndrome identifying detected errors in the data block, and storing the syndrome, the syndrome being a second polynomial with a plurality of terms, the plurality of terms in the second polynomial being generated from high order to low order based on a CRC generation polynomial with a plurality of terms; and generating, in combining logic in response to the error polynomial and the syndrome, an uncorrectable error signal if the detected errors do not match the correctable errors.
Claim 15
Dependent Claim
212 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, a method for signalling the occurrence of uncorrectable errors in a sector, the method comprising the steps of: communicating the sector across a data bus; generating, in error detecting and correcting logic in response to the sector on the data bus, an error polynomial including a plurality of terms, the error polynomial identifying location and value for correctable errors in the sector, the plurality of terms of the error polynomial being generated from low order to high order with respect to bytes of data in the data block; generating, in error detecting logic in response to the sector on the data bus, a syndrome identifying detected errors in the data block, and storing the syndrome, the syndrome being a second polynomial with a plurality of terms, the plurality of terms in the second polynomial being generated from high order to low order based on a CRC generation polynomial with a plurality of terms; and generating, in combining logic in response to the error polynomial and the syndrome, an uncorrectable error signal if the detected errors do not match the correctable errors.
Claim 16
Dependent Claim
22 words
The method of claim 11, wherein: the step of generating an error polynomial includes performing a backward Chien Search over the sector.
Claim 17
Dependent Claim
23 words
The method of claim 11, wherein: the ECC block is a first Reed-Solomon polynomial and the ED block is a second Reed-Solomon polynomial.
Claim 18
Dependent Claim
27 words
The method of claim 13, wherein: the first Reed-Solomon polynomial and the second Reed-Solomon polynomial are specified by international standard X3B11 for 51/4 inch optical storage media.
Claim 19
Dependent Claim
59 words
The method of claim 11, wherein the step of generating an uncorrectable error signal includes: reversing the second polynomial to implement a reverse second polynomial having a plurality of terms from low order to high order; and generating the uncorrectable error signal in response to the plurality of terms of the error polynomial and to the reverse second polynomial.
Claim 20
Dependent Claim
38 words
The method of claim 15, wherein: the plurality of terms of the error polynomial includes a final term; and the step of generating the uncorrectable error signal generates the uncorrectable error signal upon receipt of the final term.
Claim 21
Dependent Claim
51 words
The method of claim 15, wherein the step of generating the uncorrectable error signal includes: combining the error polynomial with a reverse CRC generation polynomial to generate an estimated reverse second polynomial; and comparing the reverse second polynomial with the estimated reverse second polynomial to indicate the occurrence of uncorrectable errors.
Claim 22
Dependent Claim
35 words
The method of claim 17, wherein: the plurality of terms of the error polynomial includes a final term that is received last; and the uncorrectable error signal is generated upon receipt of the final term.
Claim 23
Dependent Claim
239 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, an apparatus for signalling the occurrence of uncorrectable errors in a sector, the apparatus comprising: a data bus, connected to the store, for communication of the sector; first means, connected to the data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying location and value for correctable errors in the sector, wherein the error polynomial has a plurality of terms generated from low order to high order with respect to bytes of data in the data block; second means, connected to the data bus and responsive to the ED block in the sector, for generating a syndrome identifying detected errors in the data block, wherein the syndrome is a second polynomial with a plurality of terms generated from high order to low order based on a CRC generation polynomial with a plurality of terms; means for reversing the second polynomial to implement a reverse second polynomial having a plurality of terms from low order to high order; and detection means, coupled with the means for reversing, and receiving the plurality of terms of the error polynomial as generated and responsive to the reverse second polynomial, for generating an uncorrectable error signal if the detected errors do not match the correctable errors.
Claim 24
Dependent Claim
239 words
In a data storage system storing sectors of data in a store, each sector including a data block, an error checking and correcting (ECC) block, and an error detecting (ED) block, an apparatus for signalling the occurrence of uncorrectable errors in a sector, the apparatus comprising: a data bus, connected to the store, for communication of the sector; first means, connected to the data bus and responsive to the ECC block in the sector, for generating an error polynomial identifying location and value for correctable errors in the sector, wherein the error polynomial has a plurality of terms generated from low order to high order with respect to bytes of data in the data block; second means, connected to the data bus and responsive to the ED block in the sector, for generating a syndrome identifying detected errors in the data block, wherein the syndrome is a second polynomial with a plurality of terms generated from high order to low order based on a CRC generation polynomial with a plurality of terms; means for reversing the second polynomial to implement a reverse second polynomial having a plurality of terms from low order to high order; and detection means, coupled with the means for reversing, and receiving the plurality of terms of the error polynomial as generated and responsive to the reverse second polynomial, for generating an uncorrectable error signal if the detected errors do not match the correctable errors.
Claim 25
Dependent Claim
42 words
The apparatus of claim 19, wherein: the plurality of terms of the error polynomial includes a final term that is received last by the detection means; and the detection means generates the uncorrectable error signal in response to receiving the final term.
Claim 26
Dependent Claim
61 words
The apparatus of claim 19, wherein the detection means includes: means for combining the error polynomial with a reverse CRC generation polynomial to generate an estimated reverse second polynomial; and means, connected to the means for combining and the means for reversing, for comparing the reverse second polynomial with the estimated reverse second polynomial to indicate the occurrence of uncorrectable errors.
Claim 27
Dependent Claim
20 words
The apparatus of claim 19, wherein: the first means includes means for performing a forward Chien Search over the sector.
Claim 28
Dependent Claim
20 words
The apparatus of claim 19, wherein: the first means includes means for performing a backward Chien Search over the sector.
Claim 29
Dependent Claim
23 words
The apparatus of claim 19, wherein: the ECC block is a first Reed-Solomon polynomial; and the ED block is a second Reed-Solomon polynomial.
Claim 30
Dependent Claim
27 words
The apparatus of claim 24, wherein: the first Reed-Solomon polynomial and the second Reed-Solomon polynomial are specified by international standard X3B11 for 51/4 inch optical storage media.
References Cited (Backward Citations)
US4750178A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-06-24 | 1994-12-24 | 1995-06-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-06-24 | 1998-12-24 | 1999-06-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-06-24 | 2002-12-24 | 2003-06-25 | $7700.00 | Window Closed / Lapsed |