US5671237A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cyclical redundancy check method and apparatus
Assignee: Cirrus Logic Inc
•
Filing: 1994-10-18
•
Granted: 1997-09-23
•
Expires: 2014-10-18
Abstract
Abstract A one stage CRC generation system (400) and a two stage CRC generation system (600) feature a CRC generator/checker (700) which outputs a programmable number of CRC bytes. The CRC generation/checker (700) comprises a segmenting circuit (710) for segmenting an input stream of user data into a plurality m of sub-streams!; a circuit (712) which forms a linear combination of the plurality m of sub-streams and operates upon the linear combination in order to generate CRC bytes; and, a checker circuit (714) for comparing the generated CRC bytes with previously generated CRC bytes. The two stage system (600) includes a first CRC generator/checker (601); a memory (602) which receives both the user data and K 1 number of primary CRC bytes generated by first CRC generator/checker (601); and, a second CRC generator/checker (603) which uses the primary CRC bytes and K 1 number of its own generated verification CRC bytes to check the user data after retrieval from memory (602) and prior to encoding. In addition, second CRC generator/checker (603) can optionally apply K 2 -K 1 number of its verification CRC bytes to encoder (604) for use as secondary CRC bytes. The number of CRC bytes K 1 and K 2 actually outputted by the respective CRC generator/checkers (601, 603) is programmable.
Inventors
- 👤 Christopher P. Zook
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 13:36
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/35
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
113 words
A cyclical redundancy check (CRC) generator which generates CRC information for error checking purposes, comprising: an interleaving circuit for dividing an input stream of data into three interleaves, the interleaving circuit including a multiplier for multiplying each byte of one interleave by a constant M 1 which is a power of a field element α and for multiplying each byte of another interleave by a constant M 2 which is a power of the field element α, and wherein M 1 =α 25 and M 2 =α 112 ; a circuit which forms a linear combination of the three interleaves and operates upon the linear combination in order to generate the CRC information.
Claim 2
Dependent Claim
113 words
A cyclical redundancy check (CRC) generator which generates CRC information for error checking purposes, comprising: an interleaving circuit for dividing an input stream of data into three interleaves, the interleaving circuit including a multiplier for multiplying each byte of one interleave by a constant M 1 which is a power of a field element α and for multiplying each byte of another interleave by a constant M 2 which is a power of the field element α, and wherein M 1 =α 25 and M 2 =α 112 ; a circuit which forms a linear combination of the three interleaves and operates upon the linear combination in order to generate the CRC information.
Claim 3
Dependent Claim
25 words
The apparatus of claim 1, wherein the constants M 1 and M 2 are chosen so that a linear combination of certain bytes is non-zero.
Claim 4
Dependent Claim
50 words
The apparatus of claim 1, wherein the circuit which forms a linear combination of the three interleaves and operates upon the linear combination in order to generate the CRC information comprises k number of sub-circuits for generating k bytes of CRC information with respect to the linear combination of interleaves.
Claim 5
Dependent Claim
63 words
The apparatus of claim 1, wherein each interleave forms at least part of a data polynomial, and wherein the circuit which forms a linear combination of the three interleaves and operates upon the linear combination in order to generate the CRC information comprises k number of divider sub-circuits for generating k bytes of CRC information with respect to the linear combination of interleaves.
Claim 6
Dependent Claim
26 words
The apparatus of claim 4, wherein each divider sub-circuit divides the data polynomial by a divisor which is related to a root of an ECC polynomial.
Claim 7
Dependent Claim
173 words
A cyclical redundancy check (CRC) generator which generates CRC information for error checking purposes, comprising: an interleaving circuit for dividing an input stream of data and producing a plurality of interleaves; a circuit which forms a linear combination of the plurality of interleaves and operates upon the linear combination in order to generate the CRC information; wherein the circuit which forms a linear combination of the plurality of interleaves and operates upon the linear combination in order to generate the CRC information comprises a plurality of sub-circuits, each sub-circuit comprising: an adder, the adder having a first input port, a second input port, and an output port, the first port of the adder having the plurality of interleaves multiplexed thereto; a multiplier, the multiplier having an output port thereof selectively connected to the second input port of the adder; a register for storing CRC information, the register having an input port connected to the output port of the adder and an output port selectively connected to the second input port of the adder.
Claim 8
Dependent Claim
173 words
A cyclical redundancy check (CRC) generator which generates CRC information for error checking purposes, comprising: an interleaving circuit for dividing an input stream of data and producing a plurality of interleaves; a circuit which forms a linear combination of the plurality of interleaves and operates upon the linear combination in order to generate the CRC information; wherein the circuit which forms a linear combination of the plurality of interleaves and operates upon the linear combination in order to generate the CRC information comprises a plurality of sub-circuits, each sub-circuit comprising: an adder, the adder having a first input port, a second input port, and an output port, the first port of the adder having the plurality of interleaves multiplexed thereto; a multiplier, the multiplier having an output port thereof selectively connected to the second input port of the adder; a register for storing CRC information, the register having an input port connected to the output port of the adder and an output port selectively connected to the second input port of the adder.
Claim 9
Dependent Claim
20 words
The apparatus of claim 6, wherein the multiplier multiplies by a factor related to a root of an ECC polynomial.
Claim 10
Dependent Claim
67 words
The apparatus of claim 6, wherein k number of sub-circuits are provided numbered from a first sub-circuit to a k th sub-circuit, and wherein the registers of the sub-circuits are connected so that CRC information stored in the register of a K 1 th of the sub-circuits is shifted to the register of the first sub-circuit, K 1 being a constant less than or equal to k.
Claim 11
Dependent Claim
10 words
The apparatus of claim 8, wherein K 1 is programmable.
Claim 12
Dependent Claim
111 words
A cyclical redundancy check (CRC) generator which generates CRC information for error checking purposes, comprising: means for dividing an input stream of data into three interleaves, the means for dividing including a multiplier for multiplying each byte of one interleave by a constant M 1 which is a power of a field element α and for multiplying each byte of another interleave by a constant M 2 which is a power of the field element α, and wherein M 1 =α 25 and M 2 =α 112 ; means for forming a linear combination of the three interleaves and operating upon the linear combination in order to generate the CRC information.
Claim 13
Dependent Claim
111 words
A cyclical redundancy check (CRC) generator which generates CRC information for error checking purposes, comprising: means for dividing an input stream of data into three interleaves, the means for dividing including a multiplier for multiplying each byte of one interleave by a constant M 1 which is a power of a field element α and for multiplying each byte of another interleave by a constant M 2 which is a power of the field element α, and wherein M 1 =α 25 and M 2 =α 112 ; means for forming a linear combination of the three interleaves and operating upon the linear combination in order to generate the CRC information.
Claim 14
Dependent Claim
25 words
The apparatus of claim 10, wherein the constants M 1 and M 2 are chosen so that a linear combination of certain bytes is non-zero.
Claim 15
Dependent Claim
62 words
The apparatus of claim 10, wherein each interleave forms at least part of a data polynomial, and means for forming a linear combination of the plurality of interleaves and for operating upon the linear combination in order to generate the CRC information comprises k number of dividers for generating k bytes of CRC information with respect to the linear combination of interleaves.
Claim 16
Dependent Claim
25 words
The apparatus of claim 12, wherein each divider divides the data polynomial by a divisor which is related to a root of an ECC polynomial.
Claim 17
Dependent Claim
52 words
The apparatus of claim 12, wherein the means for forming a linear combination of the plurality of interleaves and for operating upon the linear combination in order to generate the CRC information outputs K 1 number of bytes of CRC information, K 1 being a constant less than or equal to k.
Claim 18
Dependent Claim
10 words
The apparatus of claim 14, wherein k 1 is programmable.
Claim 19
Dependent Claim
103 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: dividing an input stream of data into three interleaves, wherein each byte of one interleave is multiplied by a constant M 1 which is a power of a field element. α, each byte of another interleave is multiplied by a constant M 2 which is a power of the field element α, and wherein M 1 =α 25 and M 2 =α 112 ; and, forming a linear combination of the three interleaves and operating upon the linear combination in order to generate the CRC information.
Claim 20
Dependent Claim
103 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: dividing an input stream of data into three interleaves, wherein each byte of one interleave is multiplied by a constant M 1 which is a power of a field element. α, each byte of another interleave is multiplied by a constant M 2 which is a power of the field element α, and wherein M 1 =α 25 and M 2 =α 112 ; and, forming a linear combination of the three interleaves and operating upon the linear combination in order to generate the CRC information.
Claim 21
Dependent Claim
25 words
The method of claim 16, wherein the constants M 1 and M 2 are chosen so that the linear combinations of the interleaves are non-zero.
Claim 22
Dependent Claim
120 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: dividing an input stream of data and producing a plurality of interleaves; forming a linear combination of the plurality of interleaves and operating upon the linear combination in order to generate the CRC information by applying the plurality of interleaves to k number of sub-circuits for generating k bytes of CRC information with respect to the linear combination of interleaves, the sub-circuits being numbered from a first sub-circuit to a k th sub-circuit: and storing CRC information in a register of each sub-circuit and shifting CRC information stored in the register of the k th sub-circuit to the register of the first sub-circuit.
Claim 23
Dependent Claim
120 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: dividing an input stream of data and producing a plurality of interleaves; forming a linear combination of the plurality of interleaves and operating upon the linear combination in order to generate the CRC information by applying the plurality of interleaves to k number of sub-circuits for generating k bytes of CRC information with respect to the linear combination of interleaves, the sub-circuits being numbered from a first sub-circuit to a k th sub-circuit: and storing CRC information in a register of each sub-circuit and shifting CRC information stored in the register of the k th sub-circuit to the register of the first sub-circuit.
Claim 24
Dependent Claim
27 words
The method of claim 18, wherein for sub-circuit j, the linear combination applied thereto is divided by a factor related to a root of an ECC polynomial.
Claim 25
Dependent Claim
114 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: dividing an input stream of data and producing a plurality of interleaves; forming a linear combination of the plurality of interleaves and operation upon the linear combination in order to generate the CRC information by applying the plurality of interleaves to k number of sub-circuits for generating k bytes of CRC information with respect to the linear combination of interleaves. the sub-circuits being numbered from a first sub-circuit to a k th sub-circuit; and comparing a CRC value inputted to a comparison one of the sub-circuits to CRC information stored in the register of the comparison sub-circuit.
Claim 26
Dependent Claim
114 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: dividing an input stream of data and producing a plurality of interleaves; forming a linear combination of the plurality of interleaves and operation upon the linear combination in order to generate the CRC information by applying the plurality of interleaves to k number of sub-circuits for generating k bytes of CRC information with respect to the linear combination of interleaves. the sub-circuits being numbered from a first sub-circuit to a k th sub-circuit; and comparing a CRC value inputted to a comparison one of the sub-circuits to CRC information stored in the register of the comparison sub-circuit.
Claim 27
Dependent Claim
167 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: (a) dividing an input stream of data into a plurality of interleaves, the input stream being obtained from a communication channel; (b) forming a linear combination of the plurality of interleaves and operating upon the linear combination in order to generate the CRC information; (c) comparing the generated CRC information with decoded CRC information obtained from the communication channel; (d) producing an error signal when a discrepancy is detected between the generated CRC information and the decoded CRC information obtained from the communication channel; wherein the CRC information generated in step (b) constitutes K 1 number of bytes stored in registers j=1, . . . k, wherein the decoded CRC information constitutes K 1 number of decoded CRC bytes j=1, . . . k sequentially applied to a comparator, and wherein the comparison step comprises using the comparator to compare the contents of register j with decoded CRC byte j.
Claim 28
Dependent Claim
167 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: (a) dividing an input stream of data into a plurality of interleaves, the input stream being obtained from a communication channel; (b) forming a linear combination of the plurality of interleaves and operating upon the linear combination in order to generate the CRC information; (c) comparing the generated CRC information with decoded CRC information obtained from the communication channel; (d) producing an error signal when a discrepancy is detected between the generated CRC information and the decoded CRC information obtained from the communication channel; wherein the CRC information generated in step (b) constitutes K 1 number of bytes stored in registers j=1, . . . k, wherein the decoded CRC information constitutes K 1 number of decoded CRC bytes j=1, . . . k sequentially applied to a comparator, and wherein the comparison step comprises using the comparator to compare the contents of register j with decoded CRC byte j.
Claim 29
Dependent Claim
38 words
The method of claim 21, further comprising sequentially shifting K 1 -1 number of values stored in registers j=2, . . . k into a selected one of the registers for comparison with a corresponding decoded CRC byte.
Claim 30
Dependent Claim
12 words
The method of claim 22, wherein K 1 is a programmable integer.
Claim 31
Dependent Claim
175 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: (a) dividing an input stream of data into a plurality of interleaves, the input stream being obtained from a communication channel; (b) forming a linear combination of the plurality of interleaves and operating upon the linear combination in order to generate the CRC information; (c) comparing the generated CRC information with decoded CRC information obtained from the communication channel; (d) producing an error signal when a discrepancy is detected between the generated CRC information and the decoded CRC information obtained from the communication channel; wherein the CRC information generated in step (b) constitutes K 1 number of bytes stored in registers j=1, . . . k; wherein the decoded CRC information constitutes K 1 number of decoded CRC bytes j=1, . . . k sequentially applied to a comparator and wherein the comparison step comprises using the comparator to compare the contents of register j with decoded CRC byte j, and wherein K 1 is a programmable integer.
Claim 32
Dependent Claim
175 words
A cyclical redundancy check (CRC) method which generates CRC information for error checking purposes, the method comprising: (a) dividing an input stream of data into a plurality of interleaves, the input stream being obtained from a communication channel; (b) forming a linear combination of the plurality of interleaves and operating upon the linear combination in order to generate the CRC information; (c) comparing the generated CRC information with decoded CRC information obtained from the communication channel; (d) producing an error signal when a discrepancy is detected between the generated CRC information and the decoded CRC information obtained from the communication channel; wherein the CRC information generated in step (b) constitutes K 1 number of bytes stored in registers j=1, . . . k; wherein the decoded CRC information constitutes K 1 number of decoded CRC bytes j=1, . . . k sequentially applied to a comparator and wherein the comparison step comprises using the comparator to compare the contents of register j with decoded CRC byte j, and wherein K 1 is a programmable integer.
Claim 33
Dependent Claim
206 words
A cyclical redundancy check (CRC) system comprising: a host port connected to a host device; a first CRC generator connected to the host port for generating primary CRC information based on input data received from the host device; a memory for storing therein input data received from the host device and the primary CRC information generated with respect thereto by the first CRC generator; a second CRC generator connected to the memory for generating verification CRC information for checking data retrieved from the memory; an encoder connected to form encoded information by utilizing the data retrieved from the memory including the primary CRC information; a utilization port connected to a utilization channel; a decoder connected to receive input data at the utilization port and to decode the input data into decoded input data including decoded CRC information, the decoder being connected to apply the decoded input data including the decoded CRC information to the second CRC generator and to the memory, the second CRC generator validating decoded CRC information included in the decoded input data, and wherein the first CRC generator is connected to receive decoded input data including the decoded CRC information stored in the memory for validating decoded CRC information received from the memory.
Claim 34
Dependent Claim
206 words
A cyclical redundancy check (CRC) system comprising: a host port connected to a host device; a first CRC generator connected to the host port for generating primary CRC information based on input data received from the host device; a memory for storing therein input data received from the host device and the primary CRC information generated with respect thereto by the first CRC generator; a second CRC generator connected to the memory for generating verification CRC information for checking data retrieved from the memory; an encoder connected to form encoded information by utilizing the data retrieved from the memory including the primary CRC information; a utilization port connected to a utilization channel; a decoder connected to receive input data at the utilization port and to decode the input data into decoded input data including decoded CRC information, the decoder being connected to apply the decoded input data including the decoded CRC information to the second CRC generator and to the memory, the second CRC generator validating decoded CRC information included in the decoded input data, and wherein the first CRC generator is connected to receive decoded input data including the decoded CRC information stored in the memory for validating decoded CRC information received from the memory.
Claim 35
Dependent Claim
33 words
The apparatus of claim 25, wherein the second CRC generator compares the primary CRC information and the verification CRC information generated by the second CRC generator to determine errors attributable to the memory.
Claim 36
Dependent Claim
46 words
The apparatus of claim 25, wherein the second CRC generator also generates secondary CRC information based on data obtained from the memory and wherein the encoder is also connected to the second CRC generator and also utilizes the secondary CRC information to form the encoded information.
Claim 37
Dependent Claim
51 words
The apparatus of claim 25, wherein the first CRC generator comprises: an interleaving circuit for dividing an input stream of data into a plurality of interleaves; a circuit which forms a linear combination of the plurality of interleaves and operates upon the linear combination in order to generate the CRC information.
Claim 38
Dependent Claim
51 words
The apparatus of claim 25, wherein the second CRC generator comprises: an interleaving circuit for dividing an input stream of data into a plurality of interleaves; a circuit which forms a linear combination of the plurality of interleaves and operates upon the linear combination in order to generate the CRC information.
Claim 39
Dependent Claim
189 words
A cyclical redundancy check (CRC) method comprising: using a first CRC generator to generate primary CRC information based on input data received from a host device; storing in a memory the input data received from the host device and the primary CRC information generated with respect thereto by the first CRC generator; using a second CRC generator connected to the memory for generating verification CRC information with respect to data retrieved from the memory; forming encoded information by utilizing the data retrieved from the memory including the primary CRC information; decoding input data received from a utilization channel into decoded input data including decoded CRC information; applying the decoded input data including the decoded CRC information to the second CRC generator and to the memory; storing the decoded input data including the decoded CRC information in the memory; using the second CRC generator to validate the decoded CRC information included in the decoded input data; applying the decoded input data including the decoded CRC information from the memory to the first CRC generator; and using the first CRC generator to validate the decoded CRC information received from the memory.
Claim 40
Dependent Claim
189 words
A cyclical redundancy check (CRC) method comprising: using a first CRC generator to generate primary CRC information based on input data received from a host device; storing in a memory the input data received from the host device and the primary CRC information generated with respect thereto by the first CRC generator; using a second CRC generator connected to the memory for generating verification CRC information with respect to data retrieved from the memory; forming encoded information by utilizing the data retrieved from the memory including the primary CRC information; decoding input data received from a utilization channel into decoded input data including decoded CRC information; applying the decoded input data including the decoded CRC information to the second CRC generator and to the memory; storing the decoded input data including the decoded CRC information in the memory; using the second CRC generator to validate the decoded CRC information included in the decoded input data; applying the decoded input data including the decoded CRC information from the memory to the first CRC generator; and using the first CRC generator to validate the decoded CRC information received from the memory.
Claim 41
Dependent Claim
35 words
The method of claim 30, further comprising using the second CRC generator to compare the primary CRC information and verification CRC information generated by the second CRC generator to determine errors attributable to the memory.
Claim 42
Dependent Claim
22 words
The method of claim 30, wherein the second CRC generator generates secondary CRC information with respect to data retrieved from the memory.
Claim 43
Dependent Claim
18 words
The method of claim 32, further comprising forming the encoded information by also using the secondary CRC information.
References Cited (Backward Citations)
US4413339A
Cited
US4564945A
Cited
US4777635A
Cited
US4775978A
Cited
US4763332A
Cited
US4907233A
Cited
US5134619A
Cited
US5375127A
Cited
US5444719A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-09-22 | 2001-03-24 | 2001-09-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-09-22 | 2005-03-24 | 2005-09-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-09-22 | 2009-03-24 | 2009-09-23 | $7700.00 | Window Closed / Lapsed |