Validation of RAM-resident software programs

• US 5,357,527 A
• Filed: 12/31/1992
• Issued: 10/18/1994
• Est. Priority Date: 12/31/1992
• Status: Expired due to Fees

• Current Assignee: Trimble Navigation Limited (Trimble Inc.)
• Original Assignee: Trimble Navigation Limited (Trimble Inc.)
• Inventors: Coates, Thomas M., Schipper, John F.
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US07/999,160
• Time in Patent Office: 656 Days
• Field of Search: 371/37.4, 371/37.6, 371/37.7, 371/35
• US Class Current: 714/755
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

A method for transmitting and verifying the accuracy of a software program, expressed as a stream of J bits.. A first forward error correction error coding, detection and correction (ECDC) procedure is applied to the program, where the first ECDC procedure is expressible as a stream of K1 error coding bits plus L1 additional bits representing the procedure for determining the values of the K1 bits and for detecting the presence of and correcting an error in the original stream of J bits plus the K1 error coding bits, as received by a recipient. A second ECDC procedure is then applied to the K1+L1 bits used in the first ECDC program, where the second ECDC procedure is expressible as a stream of K2 error coding bits plus L2 additional bits representing the procedure for determining the values of the K2 bits and for detecting the presence of and correcting an error in the (K1+L1}bits that represent the first ECDC procedure. This second ECDC procedure is applied to check the accuracy of transmission of the bits representing the first ECDC procedure, which is applied to the software program itself. The bit stream of J bits can be decomposed into 8 or 16 mutually exclusive subsidiary bit streams, to each of which the above error checking procedure is applied, to take advantage of certain kinds of error statistics that may be present.

Claims

1. A method for transmitting and verifying the accuracy of a software program transmitted to a recipient thereof, the method comprising the steps of:

receiving and storing a software program, expressed as an ordered set of J bits, that is to be transmitted;

expressing a selected first forward error correction, error coding, detection and correction (ECDC) procedure as an ordered set of L1 bits plus K1 associated error check bits, and applying this first ECDC procedure and associated error check bits to the set of J bits representing the software program;

expressing a selected second ECDC procedure as an ordered set of L2 bits plus K2 associated error check bits, and applying this second ECDC procedure and associated error check bits to the set of L1+K1 bits representing the first ECDC procedure;

transmitting the J bits representing the software program, the L1+K1 bits representing the first ECDC procedure, and the L2+K2 bits representing the second ECDC procedure; and

applying the second ECDC procedure to the ordered set of L1+K1 bits to verify the validity of, or correct, these L1+K1 bits; and

applying the first ECDC procedure to the ordered set of J bits to verify the validity of, or correct, these J bits.

2. The method of claim 1, further comprising the steps of choosing said second ECDC procedure to be identical to said first ECDC procedure and using said first ECDC procedure for operations requiring use of said second ECDC procedure.

3. A method for transmitting and verifying the accuracy of a software program transmitted to a recipient thereof, the method comprising the steps of:

receiving and storing a software program that is to be transmitted;

determining the number of consecutive bits J in the software program;

augmenting the J-bit stream by adding a selected number K1 of additional bits that serve as error check bits for a first error coding, detection and correction (ECDC) procedure, applied to the original J-bit stream;

assigning bit values to the K1 additional bits by applying the first ECDC coding procedure to the original J-bit stream;

inserting the K1 additional bits and associated bit values at K1 selected positions in the original stream of J bits to form a (J+K1)-bit stream;

augmenting the (J+K1)-bit stream by adding a selected number L1 of bits that implement the first ECDC procedure for the original J-bit stream, to form a (J+K1+L1)-bit stream;

augmenting the (J+K1+L1)-bit stream with a selected number K2 of additional bits that serve as error check bits for a second ECDC procedure, applied to the (K1+L1)-bit stream;

assigning bit values to the K2 additional bits by applying the second ECDC coding procedure to the (K1+L1)-bit stream;

inserting the K2 additional bits and associated bit values at K2 selected positions in the original J-bit stream to form a (J+K1+L1+K2)-bit stream;

augmenting the (J+K1+L1+K2)-bit stream by adding a selected number L2 of additional bits that implement the second ECDC procedure, applied to the (K1+L1)-bit stream, to form a (J+K1+L1+K2+L2)-bit stream;

transmitting the (J+K1+L1+K2+L2)-bit stream to a recipient of this bit stream;

verifying the accuracy of the K1+L1 bits of the first ECDC procedure, as received by the recipient, by applying the second ECDC procedure to these K1+L1 bits;

when an error is discovered in the K1+L1 bits of the first ECDC procedure bits, correcting this error, using the second ECDC procedure;

verifying the accuracy of the J bits of the software program, as received by the recipient, by applying the first ECDC procedure to these J bits; and

when an error is discovered in the J bits of the software program, correcting this error, using the first ECDC procedure.

4. The method of claim 3, further comprising the step of choosing said K1 selected positions in said (J+K1)-bit stream to be the consecutively numbered bit positions for which the number is of the form 2^k (k=0. 1, 2, . . . , K1).

5. The method of claim 3, further comprising the step of choosing said K1 selected positions in said (J+K1)-bit stream to be the consecutively numbered bit positions for which the number is of the form J+k (k=1, 2, . . . , K1).

6. The method of claim 3, further comprising the step of choosing said first ECDC procedure to be the Hamming error check procedure, where said number K1 satisfies the inequality J≦

2^K1 -K1-1.

7. The method of claim 3, further comprising the step of choosing said second ECDC procedure to be the Hamming error check procedure, where said number K2 satisfies the inequality L1+K1≦

2^K2 -K2-1.

8. The method of claim 3, further comprising the steps of choosing said second ECDC procedure to be identical to said first ECDC procedure and using said first ECDC procedure for operations requiring use of said second ECDC procedure.

9. A method for transmitting and verifying the accuracy of a software program transmitted to a recipient thereof, the method comprising the steps of:

receiving and storing a software program as an ordered sequence of j 8-bit bytes;

forming eight bit streams S-1, S-2, . . . , S-8 from the sequence of 8j bits, where bit stream S-h is an ordered sequence that includes bit number h of each of the j 8-bit bytes (h=1, 2, . . . ,

     8);

applying the following procedure separately to each of the bit streams S-h (h=1, 2, . . . ,

     8);

receiving and storing a bit stream S-h to be transmitted;

determining the number of bits j in this bit stream;

augmenting the j-bit stream by adding a selected number K1 of additional bits that serve as error check bits for a first ECDC procedure, applied to the original j-bit stream S-h;

assigning bit values to the K1 additional bits by applying the first ECDC procedure to the original j-bit stream S-h;

inserting the K1 additional bits and associated bit values at K1 selected positions in the stream S-h of j bits to form a (j+K1)-bit stream;

augmenting the (j+K1)-bit stream by adding a selected number L1 of bits that implement the first ECDC procedure for the original J-bit stream, to form a (j+K1+L1)-bit stream;

augmenting the (j+K1+L1)-bit stream with a selected number K2 of additional bits that serve as error check bits for a second ECDC procedure, applied to the (K1+L1)-bit stream;

assigning bit values to the K2 additional bits by applying the second ECDC procedure to the (K1+L1)-bit stream;

inserting the K2 additional bits and associated bit values at K2 selected positions in the j-bit stream S-h to form a (j+K1+L1+K2)-bit stream;

augmenting the (j+K1+L1+K2)-bit stream by adding a selected number L2 of additional bits that implement the second ECDC procedure, applied to the (K1+L1)-bit stream, to form a (j+K1+L1+K2+L2)-bit stream;

transmitting the (j+K1+L1+K2+L2)-bit stream to a recipient of this bit stream;

verifying the accuracy of the K1+L1 bits of the first ECDC procedure, as received by the recipient, by applying the second ECDC. procedure to these K1+L1 bits;

when an error is discovered in the K1+L1 bits of the first ECDC procedure, using the second ECDC procedure to correct this error;

verifying the accuracy of, or correcting, the j bits of the bit stream S-h, as received by the recipient, by applying the first ECDC procedure to these j bits; and

when an error is discovered in the j bits of the original bit stream S-h, using the first ECDC procedure to correct this error; and

reassembling the eight bit streams S-h (h=1, 2, . . . ,

     8), as received by the recipient, into a single ordered stream of 8j bits that represents the transmitted software program, as received by the recipient.

10. A method for transmitting and verifying the accuracy of a software program transmitted to a recipient thereof, the method comprising the steps of:

receiving and storing a software program as an ordered sequence of 2j 8-bit bytes, numbered consecutively m=1, 2, . . . , 2j;

forming 16 bit streams S-1, S-2, . . . , S-16 from the sequence of 16j bits, where bit stream S-h (h=2k-1;

k=1, 2, . . . ,

     8) is an ordered sequence that includes bit number h of each of the j odd-numbered 8-bit bytes (h=1, 3, 5, . . . ,

     15), and where bit stream S-h (h=2k;

k=1, 2, . . . ,

     8) is an ordered sequence that includes bit number h of each of the j even-numbered 8-bit bytes (h=2, 4, . . .

     16);

applying the following procedure separately to each of the bit streams S-h (h=1, 2, . . . ,

     16);

receiving and storing a bit stream S-h to be transmitted;

determining the number of bits j in this bit stream;

augmenting the j-bit stream by adding a selected number K1 of additional bits that serve as error check bits for a first ECDC procedure, applied to the original j-bit stream S-h;

assigning bit values to the K1 additional bits by applying the first ECDC procedure to the original j-bit stream S-h;

inserting the K1 additional bits and associated bit values at K1 selected positions in the stream S-h of j bits to form a (j+K1)-bit stream;

augmenting the (j+K1)-bit stream by adding a selected number L1 of bits that implement the first ECDC procedure for the original J-bit stream, to form a (j+K1+L1)-bit stream;

augmenting the (j+K1+L1)-bit stream with a selected number K2 of additional bits that serve as error check bits for a second ECDC procedure, applied to the (K1+L1)-bit stream;

assigning bit values to the K2 additional bits by applying the second ECDC procedure to the (K1+L1)-bit stream;

inserting the K2 additional bits and associated bit values at K2 selected positions in the j-bit stream S-h to form a (j+K1+L1+K2)-bit stream;

augmenting the (j+K1+L1+K2)-bit stream by adding a selected number L2 of additional bits that implement the second ECDC procedure, applied to the (K1+L1)-bit stream, to form a (j+K1+L1+K2+L2)-bit stream;

transmitting the (j+K1+L1+K2+L2)-bit stream to a recipient of this bit stream;

verifying the accuracy of the K1+L1 bits of the first ECDC procedure, as received by the recipient, by applying the second ECDC procedure to these K1+L1 bits;

when an error is discovered in the K1+L1 bits of the first ECDC procedure, using the second ECDC procedure to correct this error;

verifying the accuracy of, or correcting, the j bits of the bit stream S-h, as received by the recipient, by applying the first ECDC procedure to these j bits; and

when an error is discovered in the j bits of the original bit stream S-h, using the first ECDC procedure to correct this error; and

reassembling the 16 bit streams S-h (h=1, 2, . . . ,

     16), as received by the recipient, into a single ordered stream of 16j bits that represents the transmitted software program, as received by the recipient.