• When a message is transmitted there is some chance (depending on the communications channel) that it will be corrupted.
• Checksums provide a way for the receiver to validate messages.

• The Sender:
  • Calculates a "validation value" (using a pre-determined algorithm) for the message before sending it
  • Transmits the "validation value" along with the message
• The Receiver:
  • Calculates the "check value" using the exact same algorithm
  • Compares the "check value" with the "validation value"
  • If the two are different, the transmission was corrupted

• The Validation Value:
  • A single bit
• Common Algorithms:
  • In an odd parity scheme, the parity bit is set to make the number of bits containing ones odd (e.g., a byte with two ones will have its parity bit set to 1)
  • In an even parity scheme, the parity bit is set to make the number of bits containing ones even
• Bit Counting:
  • There are many algorithms, some obvious [e.g., table look up] some not so obvious [iterate while b & (b-1) is non-zero]

• The Validation Value:
  • A byte
• The Algorithm:
  • Calculate the sum (modulo 256) of the bytes in the message

• The Idea:
  • Compute a validation value that reflects the value and position of individual bits
• The Algorithm:
  • Make the individual bits exponents in a polynomial of the form:
    b _n-1 x ^n-1 + b _n-2 x ^n-2 + ... +
  • Then divides by another polynomial (which depends on the specific form of the CRC)

• The Validation Value:
  • A byte in hexadecimal (transmitted as a 2-character string)
• The Algorithm
  • XOR each of the characters in the message together

javaexamples/io/Checksum.java (Fragment: 0)

            /**
     * Add a string to a checksum
     *
     * @param s          The string
     * @param checksum   The original checksum 
     * @returns          The new checksum
     */
    protected static int addToChecksum(String s, int checksum)
    {
        int current, i, length;
        
        length = s.length();
        for (i=0; i <= length-1; i++) {
            
            current = (int)(s.charAt(i));  // Get a char
            checksum ^= current;           // xor the char into the checksum
        }
        
        return checksum;
    }
    

    
    /**
     * Determine the checksum for a string
     *
     * @param s          The string
     * @returns          The checksum
     */
    protected static int calculateChecksum(String s)
    {
        return addToChecksum(s, 0);
    }
        

javaexamples/io/Checksum.java (Fragment: 1)

            /**
     * Determine if a String has the proper checksum
     *
     * @param s          The string
     * @param crcString  The proper checksum (in hex)
     * @returns          true if proper and false otherwise
     */
    public static boolean check(String s, String crcString)
    {
        int   actual, desired;

        actual  = calculateChecksum(s);
        desired = Hex.hexStringToInt(crcString);

        return (actual == desired);
    }
        

javaexamples/io/ChecksumDriver.java

        package io;

import java.util.*;
import convert.Hex;

/**
 * An example that uses the Checksum class
 *
 * @author  Prof. David Benrstein, James Madison University
 * @version 1.0
 */
public class ChecksumDriver
{
    /**
     * The entry point of the application
     *
     * @param args   The command line arguments
     */
    public static void main(String[] args)
    {
       boolean            ok;
       int                validationValue;
       String             checkValue, gpgga, token;
       StringTokenizer    tokenizer;
        

       // An NMEA  message from a GPS receiver
       gpgga = "$GPGGA,210230,3855.4487,N,09446.0071,W,"+
               "1,07,1.1,370.5,M,-29.5,M,,*7A";

       checkValue = "";
       validationValue  = 0;
       tokenizer = new StringTokenizer(gpgga, "$,");

       while (tokenizer.hasMoreElements())
       {
          token = (String)(tokenizer.nextElement());

          if (token.substring(0,1).equals("*"))
          {
             // The validation value (7A in the String above)
             checkValue = token.substring(1);
          } 
          else
          {
             // The check value
             validationValue = Checksum.addToChecksum(token, validationValue);
          }
       }

       ok = (validationValue == Hex.hexStringToInt(checkValue));


       if (ok) System.out.println("It's good!");
       else    System.out.println("No good!");
    }

}