Error Detection & Correction (Ch 5)

Hamming Codes

One critical thing to understand about Hamming codes is that although a given code may be x number of bits, it represents a message that is shorter. For example, a 7-bit Hamming code represents a 4-bit message and 3 “extra bits” of error detection information.

The animation linked below shows how we could start with a 4-bit message and then make 3 check bits by computing the parity (whether there are an even or odd number of 1’s) for different groupings of the message bits. These three error detecting bits together with the 4-bit original message make a 7-bit message in which we can detect and correct an error. You do not need to know how this process is done, but going through it might help cement the basic idea behind Hamming codes.

Hamming Code Simulator

Hint

  • Enter the code by clicking boxes. Click multiple times to cycle between 0 and 1.
  • When you hit the screen that says Encoder, click the 3 gray circles to calculate the check bits. The circle shows what message bits are used to compute the parity. Even # of ones is 0, odd is 1.
  • On the Enter Errors screen, click one square to cause a “transmission error” in the message. Note that if you make more than one error, you will fool the correction mechanism!
  • On the Decoder screen, click the gray circles again to perform the correction.

Optional: Validation

Error detection codes are built into many of the numbering systems we use in daily life to prevent simple mistakes. Things like credit card numbers and book ISBNs are designed so that if someone mistypes a digit the error is easily detected.

Credit Cards

The basic process for checking a credit card looks like this:

You can try it out by hand with your own card or on this spreadsheet:

Credit Card Validation Spreadsheet.

Book ISBN numbers are validated with a stair step code. You will build a program to do this later on in the course, but if you are interested you can read about how the validation works here.