- Forward


Checksums and Cyclic Redundancy Checks
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • 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 Process
Back SMYC Forward
  • 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
Parity Checksums
Back SMYC Forward
  • 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]
Another Common Checksum
Back SMYC Forward
  • The Validation Value:
    • A byte
  • The Algorithm:
    • Calculate the sum (modulo 256) of the bytes in the message
Cyclic Redundancy Checks
Back SMYC Forward
  • 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)
An Example
Back SMYC Forward
  • The Validation Value:
    • A byte in hexadecimal (transmitted as a 2-character string)
  • The Algorithm
    • XOR each of the characters in the message together
An Example (cont.)
Back SMYC Forward

The Algorithm

javaexamples/io/Checksum.java (Fragment: 0)
 
An Example (cont.)
Back SMYC Forward

Comparing the Validation and Check Values

javaexamples/io/Checksum.java (Fragment: 1)
 
An Example (cont.)
Back SMYC Forward

Checking a Sample Message

javaexamples/io/ChecksumDriver.java
 
There's Always More to Learn
Back -