US5912909A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for efficient implementation of checksum calculations
Assignee: Xylon LLC
•
Filing: 1997-10-14
•
Granted: 1999-06-15
•
Expires: 2017-10-14
Abstract
Abstract An apparatus and method is disclosed for an improved implementation for calculating a checksum. The present invention includes a plurality of addition circuits forming at least a first and a final addition stage. The addition circuits receive a data bit stream and perform addition on data bit pairs emanating from the data bit stream to obtain a checksum value. Carry bits generated by the addition circuits are propagated as additional upper data bits until the final addition stage wherein the carry bits are added to lower bits to obtain a final checksum value. The data bit stream may be a sixty-four bit data stream such that the data bit pairs are four sixteen bit pairs. The final stage accepts a limited carry value input to guarantee that a final carry bit is not generated at the final addition stage. Thus, the checksum circuit propagates the carry bits from each addition down the pipeline wherein the carry bits can be added at the end rather than at each addition stage. Further, the checksum circuit guarantees that there will never be a carry-out at the final addition stage thus eliminating the need for a final adder or carry look-ahead logic.
Inventors
- 👤 Dean Joseph McCoy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 12:28
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/727; G06F11/00; G06F11/07; G06F11/08; G06F11/10; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/11
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
87 words
A checksum calculating circuit, comprising a plurality of addition circuits forming at least a first and a final addition stage, the addition circuits receiving a data bit stream and performing addition on data bit pairs emanating from the data bit stream to obtain a checksum value, wherein carry bits generated by the addition circuits are propagated as additional upper data bits until the final addition stage and wherein the carry bits are added to lower bits at the final addition stage to obtain a final checksum value.
Claim 2
Dependent Claim
87 words
A checksum calculating circuit, comprising a plurality of addition circuits forming at least a first and a final addition stage, the addition circuits receiving a data bit stream and performing addition on data bit pairs emanating from the data bit stream to obtain a checksum value, wherein carry bits generated by the addition circuits are propagated as additional upper data bits until the final addition stage and wherein the carry bits are added to lower bits at the final addition stage to obtain a final checksum value.
Claim 3
Dependent Claim
18 words
The checksum calculating circuit of claim 1 wherein the data bit stream comprises a sixty-four bit data stream.
Claim 4
Dependent Claim
17 words
The checksum calculating circuit of claim 2 wherein the data bit pairs comprise four sixteen bit pairs.
Claim 5
Dependent Claim
32 words
The checksum calculating circuit of claim 1 wherein the final stage accepts a limited carry value input to guarantee that a final carry bit is not generated at the final addition stage.
Claim 6
Dependent Claim
210 words
A checksum circuit for generating a sixteen bit checksum output value, comprising: a first level addition stage comprising a first and second adder, the first and second adder each receiving and adding a pair of sixteen bit data and generating seventeen bit data outputs as a result; the second level addition stage for receiving the seventeen bit data outputs and generating eighteen bit data as a result; a register for storing and outputting the eighteen bit data of the second level addition stage; a third level addition stage, coupled to the register, for receiving the eighteen bit data of the register and adding the sixteen bit checksum output to generate a nineteen bit data output; a fourth level addition stage receiving the nineteen bit data output, the nineteen bit data output being divided into a lower sixteen bits and an upper three bits, the upper three bits representing the carry bits from the first, second and third level addition stages, the fourth level addition stage generating sixteen bit data as a result of the addition of the lower sixteen bits and the upper three bits; and a register, for storing the sixteen bit data of the fourth level addition stage and outputting the sixteen bit data as a checksum value.
Claim 7
Dependent Claim
210 words
A checksum circuit for generating a sixteen bit checksum output value, comprising: a first level addition stage comprising a first and second adder, the first and second adder each receiving and adding a pair of sixteen bit data and generating seventeen bit data outputs as a result; the second level addition stage for receiving the seventeen bit data outputs and generating eighteen bit data as a result; a register for storing and outputting the eighteen bit data of the second level addition stage; a third level addition stage, coupled to the register, for receiving the eighteen bit data of the register and adding the sixteen bit checksum output to generate a nineteen bit data output; a fourth level addition stage receiving the nineteen bit data output, the nineteen bit data output being divided into a lower sixteen bits and an upper three bits, the upper three bits representing the carry bits from the first, second and third level addition stages, the fourth level addition stage generating sixteen bit data as a result of the addition of the lower sixteen bits and the upper three bits; and a register, for storing the sixteen bit data of the fourth level addition stage and outputting the sixteen bit data as a checksum value.
Claim 8
Independent Claim
105 words
A method of calculating a checksum value, comprising the steps of: receiving a data bit stream using a plurality of addition circuits forming at least a first and a final addition stage; dividing the data bit stream into data bit pairs; performing addition on the data bit pairs to obtain a checksum value; propagating carry bits generated by the addition on the data bit pairs as additional upper data bits of an intermediate checksum value until the final addition stage; and adding the propagated carry bits to lower bits of the intermediate checksum value at the final addition stage to obtain a final checksum value.
Claim 9
Independent Claim
105 words
A method of calculating a checksum value, comprising the steps of: receiving a data bit stream using a plurality of addition circuits forming at least a first and a final addition stage; dividing the data bit stream into data bit pairs; performing addition on the data bit pairs to obtain a checksum value; propagating carry bits generated by the addition on the data bit pairs as additional upper data bits of an intermediate checksum value until the final addition stage; and adding the propagated carry bits to lower bits of the intermediate checksum value at the final addition stage to obtain a final checksum value.
Claim 10
Dependent Claim
16 words
The method of claim 6 wherein the data bit stream comprises a sixty-four bit data stream.
Claim 11
Dependent Claim
15 words
The method of claim 7 wherein the data bit pairs comprise four sixteen bit pairs.
Claim 12
Dependent Claim
30 words
The method of claim 6 wherein the final stage accepts a limited carry value input to guarantee that a final carry bit is not generated at the final addition stage.
References Cited (Backward Citations)
US5218563A
Cited
US5329475A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-06-14 | 2002-12-14 | 2003-06-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-06-14 | 2006-12-14 | 2007-06-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-06-14 | 2010-12-14 | 2011-06-15 | $7700.00 | Window Closed / Lapsed |