Method and apparatus for producing order independent signatures for error detection
AssigneeHewlett-Packard Company
InventorForrest E. Norrod
Life of this patent
Estimating the term…
Abstract
A method and apparatus according to the invention detects errors in communicated data words irrespective of the order in which the data words are communicated.
Claims14
An error detection method for use in a system wherein a set of N digit data words are transferred from a source end to a receiver end over a communications medium, comprising the steps of:
- (a) summing, in modulo M.sup.N arithmetic, where M represents the number of levels representable by the digits of the system, data words to be transferred from the source end by accumulating the data words in a first register while storing any carry outs ("COs"), the contents of the first register defining an expected signature SE;
- (b) summing, in modulo M.sup.N arithmetic, data words received from the source end by accumulating the received data words in a second register while storing any COs, the contents of the second register defining an error detection signature S;
- and,
- (c) comparing S and SE, detecting whether a discrepancy exists therebetween, and providing an indication that an error has occurred in the data transfer when a discrepancy is detected.
A system wherein a set of N digit data words are transferred from a source end to a receiver end over a communications medium, said system including apparatus for detecting errors in received data words comprising:
- (a) first means for summing, in modulo M.sup.N arithmetic, where M represents the number of levels representable by the digits of the system, data words to be transferred from the source end by accumulating the data words in a first register and storing any carry outs ("COs"), the contents of the first register defining an expected signature SE;
- (b) second means for summing, in modulo M.sup.N arithmetic, data words received from the source end by accumulating the received data words in a second register and storing any COs, the contents of the second register defining an error detection signature S;
- and,
- (c) third means for comparing the error detection signature and expected signature, detecting whether any discrepancy exists therebetween, and providing an indication that an error has occurred in the data transfer when a discrepancy is detected.
In a system of the type for transferring N digit data words from a source to a receiver over a communication medium, apparatus comprising:
- (a) an adder for summing, using modulo M.sup.N arithmetic, where M represents the number of levels representable by the digits of the system, the data words to be transferred;
- (b) an N+1 digit register coupled to an output port of the adder for receiving and storing N digits 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 digit data word;
- (ii) a second input port coupled to an output port of the N+1 digit register for receiving a second N+1 digit data word from the output port of the N+1 digit register;
- the output port of the adder being coupled to a first input port of the N+1 digit register for providing the N digits of the sum to the N+1 digit register;
- and,
- iii a carry out port coupled to a second input port of the N+1 digit register for providing the carry out provided by the adder.
Dependencies are inferred from the claim text.