US5491701A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Burst error corrector
Assignee: Cirrus Logic Inc
•
Filing: 1994-10-18
•
Granted: 1996-02-13
•
Expires: 2014-10-18
Abstract
Abstract A burst error correction system comprising a CRC generator/checker; a syndrome/ECC generator; and an error corrector. Using codeword data, the CRC generator/checker generates m number of CRC bytes. The CRC bytes are shifted out to the syndrome/ECC generator for use in the generation of a plurality of ECC bytes. In a write operation, syndrome/ECC generator groups the data bytes and the CRC bytes for each codeword into a predetermined number of interleaves. The ECC bytes are generated so that the sum of the bytes in each interleave for a codeword is zero, and so that the ECC bytes generated by the syndrome/ECC generator constitute at least L number of consecutive roots of the codeword. The syndrome/ECC generator comprises an interleave dependent ECC factor subgenerator and two interleave independent ECC factor subgenerators. In the general processing of a read codeword, in a first state of operation the entire codeword is inputted, for regenerating CRC bytes (and adding the regenerated bytes to the received CRC bytes of the codeword, thereby yielding CRC check remainder bytes) and for generating syndromes. The syndromes are utilized to determine if the codeword is correct or if an error burst has occurred. When a portion of an error burst occurs in the data portion, a data error burst processing and correction state is begun. When a portion of the error burst occurs in the CRC portion, a CRC error burst processing state is begun.
Inventors
- 👤 Christopher P. Zook
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 21:32
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; H03M13/091; G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1004; G06F11/1008; G06F11/1068; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; H03M13/13; H03M13/17; H03M13/35; H04; H04L; H04L1/00; H04L1/004; H04L1/0041; H04L1/0045; H04L1/0056; H04L1/0057; H04L1/0071
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
107 words
An error correction system for detecting an error burst in a received codeword, the system comprising: a CRC generator for generating check CRC bytes over data bytes of the codeword; a syndrome generator which uses the data bytes of the codeword and CRC bytes of the codeword to generate syndromes and an error pattern; a error corrector which uses the syndromes to determine the beginning of an error burst in the codeword and which uses the error pattern to correct the codeword; a checker unit which uses the error pattern and the check CRC bytes generated by the CRC generator for verifying that the codeword is correctable.
Claim 2
Dependent Claim
107 words
An error correction system for detecting an error burst in a received codeword, the system comprising: a CRC generator for generating check CRC bytes over data bytes of the codeword; a syndrome generator which uses the data bytes of the codeword and CRC bytes of the codeword to generate syndromes and an error pattern; a error corrector which uses the syndromes to determine the beginning of an error burst in the codeword and which uses the error pattern to correct the codeword; a checker unit which uses the error pattern and the check CRC bytes generated by the CRC generator for verifying that the codeword is correctable.
Claim 3
Dependent Claim
15 words
The apparatus of claim 1, wherein the codeword includes header information read from storage media.
Claim 4
Dependent Claim
18 words
The apparatus of claim 2, wherein the header information includes identification of a sector stored on the media.
Claim 5
Dependent Claim
27 words
The apparatus of claim 1, wherein the checker unit adds the check CRC bytes with the CRC bytes of the codeword to obtain CRC check remainder bytes.
Claim 6
Dependent Claim
46 words
The apparatus of claim 4, wherein the checker unit verifies that the codeword is correctable if: (1) the error burst is detected by the error corrector to have begun in the CRC bytes of the codeword, and (2) the CRC check remainder bytes are all zero.
Claim 7
Dependent Claim
52 words
The apparatus of claim 4, wherein, when the error burst is detected by the error corrector to have begun in the data bytes of the codeword, the checker unit generates CRC bytes over the error pattern and compares the CRC bytes generated over the error pattern with the CRC check remainder bytes.
Claim 8
Dependent Claim
53 words
The apparatus of claim 6, wherein if the error burst began in the data bytes of the codeword and continued to the CRC bytes of the codeword, the correction of the codeword is verified by the checker unit if the CRC check remainder bytes equal the CRC bytes generated over the error pattern.
Claim 9
Dependent Claim
24 words
The apparatus of claim 4, wherein the checker unit verifies that the codeword is correctable if the CRC check remainder bytes are all zero.
Claim 10
Dependent Claim
18 words
The apparatus of claim 1, wherein the error corrector detects a three byte error burst in the codeword.
Claim 11
Dependent Claim
165 words
A codeword generator for generating electrical signals corresponding to a codeword, the codeword generator comprising: means for receiving data bytes and outputting electrical signals corresponding to the received data bytes as a first component of the codeword; a CRC generator which uses the received data bytes to generate electrical signals corresponding to m number of cyclical redundancy bytes as a second component of the codeword; and an ECC generator which uses the received data bytes and the cyclical redundancy bytes to generate electrical signals corresponding to a plurality of error correction bytes as a third component of the codeword, the ECC generator configured to group the data bytes and the m number of CRC bytes into L number of interleaves, wherein L number of the plurality of error correction bytes are such that a sum of bytes in a corresponding interleave for a codeword is zero, and wherein the error correction bytes generated by the ECC generator constitute a plurality of roots of the codeword.
Claim 12
Dependent Claim
165 words
A codeword generator for generating electrical signals corresponding to a codeword, the codeword generator comprising: means for receiving data bytes and outputting electrical signals corresponding to the received data bytes as a first component of the codeword; a CRC generator which uses the received data bytes to generate electrical signals corresponding to m number of cyclical redundancy bytes as a second component of the codeword; and an ECC generator which uses the received data bytes and the cyclical redundancy bytes to generate electrical signals corresponding to a plurality of error correction bytes as a third component of the codeword, the ECC generator configured to group the data bytes and the m number of CRC bytes into L number of interleaves, wherein L number of the plurality of error correction bytes are such that a sum of bytes in a corresponding interleave for a codeword is zero, and wherein the error correction bytes generated by the ECC generator constitute a plurality of roots of the codeword.
Claim 13
Dependent Claim
26 words
The apparatus of claim 10, wherein the error correction bytes generated by the ECC generator constitute at least L number of consecutive roots of the codeword.
Claim 14
Dependent Claim
47 words
The apparatus of claim 10, wherein the ECC generator generates five error correction bytes, the five error correction bytes being generated to cause each interleave to have α 0 as a root and to cause the codeword to have α 1 and α -1 as a root.
Claim 15
Dependent Claim
92 words
The apparatus of claim 10, wherein the ECC generator comprises an interleave-dependent ECC factor sub-generator, the interleave dependent ECC factor sub-generator operating in accordance with clock cycles and comprising: L number of interleave parity sum registers; an adder for adding an input byte applied to the interleave-dependent ECC factor sub-generator to contents of a selected one of the interleave parity sum registers during a clock cycle; the interleave parity sum registers being connected whereby each interleave parity sum register has an input byte added thereto by the adder every Lth clock cycle.
Claim 16
Dependent Claim
55 words
The apparatus of claim 13, wherein the ECC generator further comprises at least one interleave-independent ECC factor sub-generator for generating an interleave-independent ECC factor; and wherein the interleave-independent ECC factor is transferred into at least one of the interleave parity sum registers in a process of outputting the error correction bytes from the ECC generator.
Claim 17
Dependent Claim
71 words
The apparatus of claim 14, wherein the ECC generator generates five error correction bytes E 0 -E 4 , wherein there are first and second interleave-independent ECC factor sub-generators, wherein the interleave-dependent ECC factor sub-generator generates bytes E 2 -E 4 and wherein ECC factors generated by the first and second interleave-independent ECC factor sub-generators are used to generate error correction byte E 0 and error correction byte E 1 .
Claim 18
Dependent Claim
130 words
The apparatus of claim 14, wherein the interleave-independent ECC factor sub-generator includes an S 1 syndrome generator, the S 1 syndrome generator comprising: a S 1 syndrome register; a S 1 syndrome first adder connected to add together contents of the S 1 syndrome register and an input byte applied to the S 1 syndrome generator; a S 1 syndrome first feedback multiplier for multiplying the output of the S 1 syndrome first adder by a first multiplication constant; a S 1 syndrome second adder for adding a multiple of a parity sum to the input byte applied to the S 1 syndrome generator when the input byte applied to the S 1 syndrome generator is any of the last three bytes of the codeword immediately preceding error correction bytes.
Claim 19
Dependent Claim
131 words
The apparatus of claim 16, wherein the interleave-independent error correction byte sub-generator includes an S -1 syndrome generator, the S -1 syndrome generator comprising: a S -1 syndrome register; a S -1 syndrome first adder connected to add together contents of the S -1 syndrome register and an input byte applied to the S -1 syndrome generator; a S -1 syndrome first feedback multiplier for multiplying the output of the S -1 syndrome first adder by a first multiplication constant; a S -1 syndrome second adder for adding a multiple of a parity sum to the input byte applied to the S -1 syndrome generator when the input byte applied to the S -1 syndrome generator is any of the last three bytes of the codeword immediately preceding error correction bytes.
Claim 20
Dependent Claim
32 words
The apparatus of claim 17, wherein the first multiplication constant of the S 1 generator is α 1 and the first multiplication constant of the S -1 generator is α -1 .
Claim 21
Independent Claim
143 words
A method of correcting errors in a digital data stream retrieved from a disk drive storage device, the method comprising: receiving data bytes from the disk drive storage device and outputting the data bytes as a first component of a codeword; using the received data bytes to generate electrical signals corresponding to m number of cyclical redundancy (CRC) bytes as a second component of the codeword; and grouping the data bytes and the m number of CRC bytes into L number of interleaves; using the grouped data bytes and CRC bytes to generate electrical signals corresponding to a plurality of error correction bytes, wherein L number of the plurality of error correction bytes are such that a sum of bytes in a corresponding interleave for a codeword is zero, and wherein the error correction bytes constitute a plurality of roots of the codeword.
Claim 22
Independent Claim
143 words
A method of correcting errors in a digital data stream retrieved from a disk drive storage device, the method comprising: receiving data bytes from the disk drive storage device and outputting the data bytes as a first component of a codeword; using the received data bytes to generate electrical signals corresponding to m number of cyclical redundancy (CRC) bytes as a second component of the codeword; and grouping the data bytes and the m number of CRC bytes into L number of interleaves; using the grouped data bytes and CRC bytes to generate electrical signals corresponding to a plurality of error correction bytes, wherein L number of the plurality of error correction bytes are such that a sum of bytes in a corresponding interleave for a codeword is zero, and wherein the error correction bytes constitute a plurality of roots of the codeword.
Claim 23
Dependent Claim
21 words
The method of claim 19, wherein the error correction bytes constitute at least L number of consecutive roots of the codeword.
Claim 24
Dependent Claim
45 words
The method of claim 19, wherein five error correction bytes are generated, the five error correction bytes being generated to cause each interleave to have α 0 as a root and to cause the codeword to have α 1 and α -1 as a root.
Claim 25
Dependent Claim
85 words
An error correction method for detecting an error burst in a received codeword, the method comprising: generating check CRC bytes over data bytes of the codeword; using the data bytes of the codeword and CRC bytes of the codeword to generate syndromes and an error pattern; using the syndromes to determine the beginning of an error burst in the codeword and using the error pattern to correct the codeword; using the error pattern and the check CRC bytes to verify that the codeword is correctable.
Claim 26
Dependent Claim
85 words
An error correction method for detecting an error burst in a received codeword, the method comprising: generating check CRC bytes over data bytes of the codeword; using the data bytes of the codeword and CRC bytes of the codeword to generate syndromes and an error pattern; using the syndromes to determine the beginning of an error burst in the codeword and using the error pattern to correct the codeword; using the error pattern and the check CRC bytes to verify that the codeword is correctable.
Claim 27
Dependent Claim
15 words
The method of claim 22, wherein the codeword includes header information read from storage media.
Claim 28
Dependent Claim
18 words
The method of claim 23, wherein the header information includes identification of a sector stored on the media.
Claim 29
Dependent Claim
25 words
The method of claim 22, wherein the check CRC bytes are added to the CRC bytes of the codeword to obtain CRC check remainder bytes.
Claim 30
Dependent Claim
39 words
The method of claim 25, wherein the codeword is verified as correctable if: (1) the error burst is detected to have begun in the CRC bytes of the codeword, and (2) the CRC check remainder bytes are all zero.
Claim 31
Dependent Claim
47 words
The method of claim 25, wherein, when the error burst is detected to have begun in the data bytes of the codeword: CRC bytes are generated over the error pattern; and the CRC bytes generated over the error pattern are compared with the CRC check remainder bytes.
Claim 32
Dependent Claim
50 words
The method of claim 27, wherein if the error burst began in the data bytes of the codeword and continued to the CRC bytes of the codeword, the correction of the codeword is verified by if the CRC check remainder bytes equal the CRC bytes generated over the error pattern.
Claim 33
Dependent Claim
17 words
The method of claim 22, wherein the method detects a three byte error burst in the codeword.
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) | 1999-02-12 | 1999-08-14 | 2000-02-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-12 | 2003-08-14 | 2004-02-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-12 | 2007-08-14 | 2008-02-13 | $7700.00 | Window Closed / Lapsed |