US5121397A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for producing order independent signatures for error detection
Assignee: HP Inc
•
Filing: 1990-02-14
•
Granted: 1992-06-09
•
Expires: 2010-02-14
Abstract
Abstract A method and apparatus for detecting errors in communicated data words irrespective of the order in which the data words are communicated. In a system wherein a set of N bit data words are transferred from a source end to a receiver end over a communications medium, a method for detecting errors in received data words comprises the following steps: (a) summing data words to be transferred by accumulating the data words in N bit locations of a first N+1 bit register while storing any carry outs ("COs") in a reserved one of the N+1 bit locations, the contents of the first N+1 bit register defining an expected signature SE; (b) summing received data words received by accumulating the received data words in N bit locations of a second N+1 bit register while storing any COs in a reserved one of the N+1 bit locations of the second N+1 bit register, the contents of the second N+1 bit register defining an error detection signature S; and (c) comparing S and SE and providing an indication that an error has occurred in the data transfer when a discrepancy is detected.
Inventors
- 👤 Forrest E. Norrod
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:07
CPC Classifications
H; H03; H03M; H03M13/00
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
216 words
In a system of the type wherein a set of N bit data words are transferred from a source end to a receiver end over a communications medium, a method for detecting errors in received data words comprising the steps of: (a) summing, in modulo 2 N arithmetic, data words to be transferred from the source end by accumulating the data words in N bit locations of a first N+1 bit register while storing any carry outs ("COs") in a reserved one of the N+1 bit locations, the contents of the first N+1 bit register defining an expected signature SE; (b) summing, in modulo 2" arithmetic, data words received from the source end by accumulating the received data words in N bit locations of a second N+1 bit register while storing any COs in a reserved one of the N+1 bit locations of the second N+1 bit register, the contents of the second N+1 bit register defining an error detection signature S; and, (c) comparing S and SE, and detecting whether a discrepancy exists therebetween, and providing an indication that an error has occurred in the data transfer when a discrepancy is detected, discrepancies in the received data words being detected irrespective of the order in which the data words are transferred from the source end.
Claim 2
Dependent Claim
216 words
In a system of the type wherein a set of N bit data words are transferred from a source end to a receiver end over a communications medium, a method for detecting errors in received data words comprising the steps of: (a) summing, in modulo 2 N arithmetic, data words to be transferred from the source end by accumulating the data words in N bit locations of a first N+1 bit register while storing any carry outs ("COs") in a reserved one of the N+1 bit locations, the contents of the first N+1 bit register defining an expected signature SE; (b) summing, in modulo 2" arithmetic, data words received from the source end by accumulating the received data words in N bit locations of a second N+1 bit register while storing any COs in a reserved one of the N+1 bit locations of the second N+1 bit register, the contents of the second N+1 bit register defining an error detection signature S; and, (c) comparing S and SE, and detecting whether a discrepancy exists therebetween, and providing an indication that an error has occurred in the data transfer when a discrepancy is detected, discrepancies in the received data words being detected irrespective of the order in which the data words are transferred from the source end.
Claim 3
Dependent Claim
31 words
Method of claim 1 wherein step (a) further comprises appending a bit of value of "1" to the N bits of the data words to be transferred from the source end.
Claim 4
Dependent Claim
29 words
Method of claim 1 wherein step (b) further comprises appending a bit of value of "1" to the N bits of the data words received from the source end.
Claim 5
Dependent Claim
11 words
Method of claim 1 wherein N is a power of two.
Claim 6
Dependent Claim
219 words
In a system of the type wherein a set of N bit data words are transferred from a source and to a receiver end over a communications medium, apparatus for detecting errors in received data words comprising: (a) first means for summing, in modulo 2 N arithmetic, data words to be transferred from the source end by accumulating the received data words in N bit locations of a first N+1 bit register and storing any carry outs ("COs") in a reserved one of the N+1 bit register defining an expected signature SE; (b) second means for summing, in modulo 2 N arithmetic, data words received from the source end by accumulating the received data words in N bit locations of a second N+1 bit register and storing any COs in a reserved one of the N+1 bit locations of the second N+1 bit register, the contents of the second N+1 bit register defining an error detection signature S; and, (c) third means for comparing the error detection signature and expected signature and detecting whether any discrepancy exits therebetween, and providing an indication that an error has occurred in the data transfer when a discrepancy is detected, discrepancies in the received data words being detected irrespective of the order in which the data words are transferred from the source end.
Claim 7
Dependent Claim
219 words
In a system of the type wherein a set of N bit data words are transferred from a source and to a receiver end over a communications medium, apparatus for detecting errors in received data words comprising: (a) first means for summing, in modulo 2 N arithmetic, data words to be transferred from the source end by accumulating the received data words in N bit locations of a first N+1 bit register and storing any carry outs ("COs") in a reserved one of the N+1 bit register defining an expected signature SE; (b) second means for summing, in modulo 2 N arithmetic, data words received from the source end by accumulating the received data words in N bit locations of a second N+1 bit register and storing any COs in a reserved one of the N+1 bit locations of the second N+1 bit register, the contents of the second N+1 bit register defining an error detection signature S; and, (c) third means for comparing the error detection signature and expected signature and detecting whether any discrepancy exits therebetween, and providing an indication that an error has occurred in the data transfer when a discrepancy is detected, discrepancies in the received data words being detected irrespective of the order in which the data words are transferred from the source end.
Claim 8
Dependent Claim
20 words
Apparatus of claim 5 wherein the source and receiver ends of the communication medium comprise separate processors within the system.
Claim 9
Dependent Claim
16 words
Apparatus of claim 5 wherein the source end of the communication medium comprises a pixel processor.
Claim 10
Dependent Claim
19 words
Apparatus of claim 5 wherein the receiver end of the communication medium comprises a device for performing mathematical calculations.
Claim 11
Dependent Claim
13 words
Apparatus of claim 5 wherein the communication medium comprises an N bit bus.
Claim 12
Dependent Claim
30 words
Apparatus of claim 5 wherein the first means appends a bit of value of "1" to the N bits of the data words to be transferred from the source end.
Claim 13
Dependent Claim
28 words
Apparatus of claim 5 wherein the second means appends a bit of value of "1" to the N bits of the data words received from the source end.
Claim 14
Dependent Claim
179 words
In a system of the type for transferring N bit data words from a source to a receiver over a communication medium, apparatus comprising: (a) an adder for summing, using modulo 2 N arithmetic, the data words to be transferred; (b) an N+1 bit register coupled to an output port of the adder for receiving and storing N bits of the sum of the data words and a carry out provided by the adder; the adder comprising: (i) a first input port for receiving a first N bit data word; (ii) a second input port coupled to an output port of the N+1 bit register for receiving a second N+a bit data word from the output port of the N+1 bit register; the output port of the adder being coupled to a first input port of the N+a bit register for providing the N bits of the sum to the N+1 bit register; and, (iii) a carry out port coupled to a second input port of the N+1 bit register for providing the carry out provided by the adder.
Claim 15
Dependent Claim
179 words
In a system of the type for transferring N bit data words from a source to a receiver over a communication medium, apparatus comprising: (a) an adder for summing, using modulo 2 N arithmetic, the data words to be transferred; (b) an N+1 bit register coupled to an output port of the adder for receiving and storing N bits of the sum of the data words and a carry out provided by the adder; the adder comprising: (i) a first input port for receiving a first N bit data word; (ii) a second input port coupled to an output port of the N+1 bit register for receiving a second N+a bit data word from the output port of the N+1 bit register; the output port of the adder being coupled to a first input port of the N+a bit register for providing the N bits of the sum to the N+1 bit register; and, (iii) a carry out port coupled to a second input port of the N+1 bit register for providing the carry out provided by the adder.
Claim 16
Dependent Claim
42 words
Apparatus according to claim 12 wherein the first input port of the adder receives, in addition to the N bit data words, an additional bit value of "1" for appending to the N bit data words received at the first input port.
Claim 17
Dependent Claim
20 words
Apparatus according to claim 12 wherein the second input port of the N+1 bit register is an LSB bit location.
Claim 18
Dependent Claim
210 words
In a system of the type for transferring N bit data words from a source to a receiver over a communication medium, apparatus comprising: (a) an adder for summing, using modulo 2 N arithmetic, the data words to be transferred; (b) an N+1 bit register coupled to an output port of the adder for receiving and storing an N bit sum of the data words and a carry out provided by the adder; the adder comprising: (i) a first input port for receiving a first N bit data word; (ii) a second input port coupled to a first output port of the N+1 bit register for receiving a second N bit data word from the first output port of the N+1 bit register; the output port of the adder being coupled to a first input port of the N+1 bit register for providing the N bit sum to the N+1 bit register; (iii) a carry out port coupled to a second input port of the N+1 bit register for providing the carry out provided by the adder; and (iv) a carry in port coupled to a second output port of the N+1 bit register for receiving the carry out received at the second input port of the N+1 bit register.
Claim 19
Dependent Claim
210 words
In a system of the type for transferring N bit data words from a source to a receiver over a communication medium, apparatus comprising: (a) an adder for summing, using modulo 2 N arithmetic, the data words to be transferred; (b) an N+1 bit register coupled to an output port of the adder for receiving and storing an N bit sum of the data words and a carry out provided by the adder; the adder comprising: (i) a first input port for receiving a first N bit data word; (ii) a second input port coupled to a first output port of the N+1 bit register for receiving a second N bit data word from the first output port of the N+1 bit register; the output port of the adder being coupled to a first input port of the N+1 bit register for providing the N bit sum to the N+1 bit register; (iii) a carry out port coupled to a second input port of the N+1 bit register for providing the carry out provided by the adder; and (iv) a carry in port coupled to a second output port of the N+1 bit register for receiving the carry out received at the second input port of the N+1 bit register.
Claim 20
Dependent Claim
20 words
Apparatus according to claim 15 wherein the second input port of the N+1 bit register is an LSB bit location.
References Cited (Backward Citations)
US4142243A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-06-09 | 1995-12-09 | 1996-06-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-06-09 | 1999-12-09 | 2000-06-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-06-09 | 2003-12-09 | 2004-06-09 | $7700.00 | Window Closed / Lapsed |