Error check code recomputation method time independent of message length
First Claim
1. In a data packet communication network comprising a plurality of transmission links for interconnecting a source node of the network to a destination node of the network, one of said plurality of transmission links being selected for conveying a digitally coded data packet message of a given length from the source node to the destination node, the selected transmission link including at least one intermediate node which intentionally alters a portion of the message to form an altered message that is ultimately routed to the destination node over said selected link, said message including an error-check code initially computed at the source node for use in detecting the presence of errors in said message effectuated during transmission over the selected transmission link, a method for recomputing at the intermediate node a new error-check code to be transmitted as part of the altered message to the destination node, while preserving the integrity of the initially computed error-check code, said method comprising the steps of:
- (a) determining, by an intermediate node of the selected transmission link, a read content of the digitally coded message;
(b) deriving, by the intermediate node, a representation of a difference message based on said read content of the message and knowledge of the intended alteration of the portion thereof, said difference message representation including a difference portion representation and a null portion representation having zeros trailing the difference portion;
(c) computing, by the intermediate node, a difference error-check code for said difference message representation in a predetermined number of computational operations using an algorithm based on the difference portion and null portion representations thereof, said predetermined number being independent of the length of said message; and
(d) combining, by the intermediate node, the derived computed error-check code with the derived difference error-check code to form said new error-check code for the altered message, wherein the message includes a sequence of digitally coded bits;
the difference portion representation includes a sequence of a digitally coded bits and the null portion representation represents a sequence of m bits all coded a binary zero;
wherein the error-check code includes a cyclic-redundancy-check (CRC) code generated by a generating polynomial g(x) for a finite Galois field GF(2r), where r is an integer, andwhere a difference CRC between unaltered and altered data messages is selected to be computed by the expression Xm d(x) modulo g(x) over GF(2),where d(x) represents the digital code of the difference sequence and GF(2) represents a finite Galois field, step (c) includes the steps of;
expanding m into a binary expression represented by the terms kr-1, . . . k2, k1, k0, where ki is an element of a set 0 and 1;
computing a resultant term Z(x)=Xm mod g(x) in r steps by initially setting Z(x) equal to xexp(kr-1) for the first step and then recursively generating Z(x) for the steps i=r-2 to 0, by the expression Z(x)=Z(x)2 xexp(ki); and
thereafter, performing a Galois field multiplication of the resultant term Z(x) times d(x)mod g(x) over GF(2) to yield the difference CRC code.
5 Assignments
0 Petitions
Accused Products
Abstract
In a data packet communications network capable of transmitting a digitally coded data packet message including an error-check code from a source node to a destination node over a selected transmission link which includes at least one intermediate node operative to intentionally alter a portion of a message to form an altered message which is ultimately routed to the destination node, a method of recomputing at the intermediate node a new error-check code for the altered message with a predetermined number of computational operations, i.e. computational time, independent of the length of the message, while preserving the integrity of the initially computed error-check code of the message.
-
Citations
10 Claims
-
1. In a data packet communication network comprising a plurality of transmission links for interconnecting a source node of the network to a destination node of the network, one of said plurality of transmission links being selected for conveying a digitally coded data packet message of a given length from the source node to the destination node, the selected transmission link including at least one intermediate node which intentionally alters a portion of the message to form an altered message that is ultimately routed to the destination node over said selected link, said message including an error-check code initially computed at the source node for use in detecting the presence of errors in said message effectuated during transmission over the selected transmission link, a method for recomputing at the intermediate node a new error-check code to be transmitted as part of the altered message to the destination node, while preserving the integrity of the initially computed error-check code, said method comprising the steps of:
-
(a) determining, by an intermediate node of the selected transmission link, a read content of the digitally coded message; (b) deriving, by the intermediate node, a representation of a difference message based on said read content of the message and knowledge of the intended alteration of the portion thereof, said difference message representation including a difference portion representation and a null portion representation having zeros trailing the difference portion; (c) computing, by the intermediate node, a difference error-check code for said difference message representation in a predetermined number of computational operations using an algorithm based on the difference portion and null portion representations thereof, said predetermined number being independent of the length of said message; and (d) combining, by the intermediate node, the derived computed error-check code with the derived difference error-check code to form said new error-check code for the altered message, wherein the message includes a sequence of digitally coded bits;
the difference portion representation includes a sequence of a digitally coded bits and the null portion representation represents a sequence of m bits all coded a binary zero;
wherein the error-check code includes a cyclic-redundancy-check (CRC) code generated by a generating polynomial g(x) for a finite Galois field GF(2r), where r is an integer, andwhere a difference CRC between unaltered and altered data messages is selected to be computed by the expression Xm d(x) modulo g(x) over GF(2), where d(x) represents the digital code of the difference sequence and GF(2) represents a finite Galois field, step (c) includes the steps of; expanding m into a binary expression represented by the terms kr-1, . . . k2, k1, k0, where ki is an element of a set 0 and 1; computing a resultant term Z(x)=Xm mod g(x) in r steps by initially setting Z(x) equal to xexp(kr-1) for the first step and then recursively generating Z(x) for the steps i=r-2 to 0, by the expression Z(x)=Z(x)2 xexp(ki); and thereafter, performing a Galois field multiplication of the resultant term Z(x) times d(x)mod g(x) over GF(2) to yield the difference CRC code. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
10. The method in accordance with claim 9 including the step of setting the value of n=r/2.
-
Specification