Error check code recomputation method time independent of message length

• US 5,428,629 A
• Filed: 06/20/1994
• Issued: 06/27/1995
• Est. Priority Date: 11/01/1990
• Status: Expired due to Term

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Dong, Ping, Gutman, Michael
• Primary Examiner(s): Nguyen, Hoa T.
• Assistant Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US08/263,902
• Time in Patent Office: 372 Days
• Field of Search: 371/37.1, 371/37.2, 371/37.3, 371/37.4, 371/37.5, 371/37.6, 371/37.7, 371/37.8
• US Class Current: 714/758
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control

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.

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(2^r), where r is an integer, and

where a difference CRC between unaltered and altered data messages is selected to be computed by the expression X^m 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 k_r-1, . . . k₂, k₁, k₀, where k_i is an element of a set 0 and 1;

computing a resultant term Z(x)=X^m mod g(x) in r steps by initially setting Z(x) equal to xexp(k_r-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)² xexp(k_i); 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.

2. The method in accordance with claim 1 wherein step (c) includes the steps of:

using the digital code of the difference sequence as the code of an r-tuple of the Galois filed, converting said code into its corresponding logarithm j of the field;

adding the number m+r of the corresponding null sequence to the converted logarithm j modulo (2^r -1) to yield a sum (m+r+j) modulo (2^r -1); and

using said sum as another logarithm of the field, inversely converting said another logarithm to its corresponding r-tuple digital code which becomes the difference CRC code for the difference message.

3. The method in accordance with claim 2 including the steps of:

configuring a first look-up table to convert an r-tuple digital code to its corresponding logarithm of said field; and

configuring a second look-up table to inversely convert a logarithm of the field to the corresponding digital code of its r-tuple; and

wherein the converting step includes the step of using the digital code of the difference sequence to look up its corresponding logarithm of the field in the first table; and

wherein the step of inversely converting includes the step of using the sum to look up its corresponding r-tuple digital code of the field in the second table.

4. The method in accordance with claim 1 wherein step (c) includes:

dividing the digital code of the difference sequence into j separate r-bit subsequences;

using each r-bit subsequence as an r-tuple of the Galois field, converting the digital code of each r-bit subsequence into its corresponding logarithm i of the field;

adding the number m+r+t to each converted logarithm i modulo (2^r -1) to yield j subsums (m+r+t+i) modulo (2^r -1), where t represents the trailing number of bits from the end of the corresponding r-bit subsequence to the beginning of the null sequence;

using each of said j subsums as other logarithms of the field, inversely converting each of said other logarithms to its corresponding r-tuple digital code yielding j subdifference CRC codes; and

summing (modulo

     2) said j subdifference CRC codes to compute the difference CRC code of the difference message.

5. The method in accordance with claim 4 including the steps of:

configuring a first look-up table to convert an r-tuple digital code to its corresponding logarithm of said field; and

configuring a second look-up table to inversely convert a logarithm of the field to the corresponding digital code of its r-tuple; and

wherein the converting step includes the step of using the digital code of each r-bit subsequence to look up its corresponding logarithm i of the field in the first table; and

wherein the step of inversely converting includes the step of using each subsum to look up its corresponding r-tuple digital code of the field in the second table.

6. The method in accordance with claim 4 wherein the step of inversely converting includes the steps of:

dividing each subsum i of the j subsums by a predetermined value c to yield for each subsum i, k_i value with a reminder Ri;

using the k_i values as other logarithms of the field, inversely converting each of said other logarithms to its corresponding r-tuple digital codes represented by Y_i ;

passing each Y_i code through a bit-wise CRC encoder, generated by the generating polynomial g(x), Ri times to yield the j subdifference CRC codes.

7. The method in accordance with claim 6 including the steps of:

configuring a first look-up table to convert an r-tuple digital code to its corresponding logarithm of said field; and

configuring a second look-up table to inversely convert a logarithm of the field to the corresponding digital code of its r-tuple; and

wherein the converting step includes the step of using the digital code of each r-bit subsequence to look up its corresponding logarithm i of the field in the first table; and

wherein the step of inversely converting includes the step of using each k_i value to look up its corresponding r-tuple digital code y_i of the field in the second table.

8. The method in accordance with claim 1 including the step of configuring a look-up table of a size 2 deg g(x) for the squaring operation of the term Z;

and wherein the computing step includes the step using the term Z to look up its square Z² in said look-up table for each step i=r-2 to 0 during the recursive generation of the resultant term Z.

9. The method in accordance with claim 1 wherein the computing step includes the steps of splitting the term Z(x)=x^m mod g(x) into two polynomials Z_a (x) and Z_b (x) both with degree less than r such that

10. The method in accordance with claim 9 including the step of setting the value of n=r/2.