Hamming Error Detection Simulation

written by Teresa Carrigan


Top

WHAT IS IT?

This model demonstrates detection and correction of single bit errors, using Hamming SEC (single-error-correction, even parity) with eight data bits.

Top

HOW IT WORKS

First a random 12-bit pattern is generated. This represents either stored data or a message received, that is already in Hamming SEC. Next the check bits are marked; they will be the bits that occupy positions 1, 2, 4, and 8.

Each position is then marked with the binary equivalent of the position number. This will help us determine easily which bits are checked by which check bit. Each check bit has a single one in the binary equivalent of its position number, and checks all bits that have a one in that same place in the binary equivalent.

Next we check the parity of each check bit group. If any group has odd parity, we know that there is an error in one of the bits in that group, and we mark its check bit in red.

After checking every check bit group, if there are no red check bits, then no error occurred and we can just strip the check bits to get the data. If there was an error, we add the position numbers of all the red check bits to get the position of the bit that has been flipped. If the sum of the red check bit positions is greater than the number of bits we have, then multiple errors occurred and we cannot fix the error. Otherwise, we simply flip the erroneous bit, and then strip the check bits to give the correct data bits.

Top

HOW TO USE IT

The setup button generates a random 12-bit pattern.

The step button demonstrates the next step, and then stops so you can take notes. This is useful when you are first learning the method.

The go button does every remaining step, at a speed determined by the slow-motion slider. This is useful when you do not need to take notes between each step.

The show-again button starts the exact problem from the beginning. You may then click either the step button or the go button to see the same demonstration.

The quiz button will generate a random problem and ask you to determine whether or not an error in transmission is detected.

The slow-motion slider is an easy way to adjust the speed of the display. Set it to zero if you want to show the final result as quickly as possible. 0.3 is a good setting for most purposes.

Top

THINGS TO NOTICE

The group of bits checked by a check bit is easily determined by looking at the binary equivalent of the position number. Each bit in that group will have a 1 in the same place.

In order to use the original data, we must not only correct any possible error but also strip the check bits to get the original data back.

Top

THINGS TO TRY

Set slow-motion to 0.3, click setup, and then click go.

Click setup. Work each step by hand, and then click the step button to check your answer.

Top

EXTENDING THE MODEL

Allow the user to input the starting bit-pattern.

Allow the user to input the starting bit pattern.

Allow for a different number of data bits, set by a slider.

Modify the model to use a Hamming double-error-correcting code.

Top

NETLOGO FEATURES

one-step uses the NetLogo run command combined with a global integer variable step to run the next step, without needing nested ifelse blocks.

The arrow uses "other-BREED-here" to interact with the yellow bits.

Top

RELATED MODELS

Top

CREDITS AND REFERENCES

This model was written by Teresa W. Carrigan, 2004.

Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:

  1. this copyright notice is included.
  2. this model will not be redistributed for profit without permission from Teresa Carrigan.
Contact Teresa Carrigan for appropriate licenses for redistribution for profit.

To refer to this model in academic publications, please use: Carrigan, T. (2004). Hamming Error Detection Simulation Blackburn College, Carlinville, IL.

In other publications, please use: Copyright 2004 by Teresa W. Carrigan. All rights reserved.

Top

FOR MORE INFORMATION

For more information on Hamming Codes, see one of the following textbooks:
  1. Null, L. and Lobur, J. Essentials of Computer Organization and Architecture, First Edition, Jones and Bartlett, pages 77-82.
  2. Murdocca, M. and Heuring, V. Principles of Computer Architecture, First Edition, Prentice Hall, pages 359-365.

Home

Applets on this website were written by Teresa Carrigan in 2004, for use in computer science courses at Blackburn College, with the exception of the Fireworks applet. The applets made with NetLogo require Java 1.4.1 or higher to run. The applets made with NetBeans require Java 1.4.2 or higher to run. Applets might not run on Windows 95 or Mac OS 8 or 9. You may obtain the latest Java plugin from Sun's Java site.