Cyclic Redundancy Check Simulation
written by Crystal Barchet and Teresa Carrigan
- What is it?
- How it works
- How to use it
- Things to notice
- Things to try
- Extending the model
- NetLogo features
- Related models
- Credits and References
- For more information
- Download the model
WHAT IS IT?
This model demonstrates sending a message using Cyclic Redundancy Check (CRC). CRC is a commonly used error detection technique.
HOW IT WORKS
A generator is chosen randomly from a list of allowed generators, and a random message created. The message is padded with zeroes (one less than the number of bits in the generator). This new message is divided by the generator by using modulo 2 arithmetic, which is the same as XOR. If the remainder is more than one digit less than the generator, then the front of it is padded with zeroes so that it is exactly one digit less than the generator. The new remainder is added onto the end of the original message and this is the packet to be sent.
HOW TO USE IT
The setup button generates a random message and selects a random generator.The slow-motion slider is an easy way to adjust the speed of the display. Set it to zero if you want to just see the answer quickly. 0.2 is a good setting for most purposes.
The step button does whatever step comes next, and then stops so you can take notes.
The go button finishes the entire problem, at a speed set by the slow-motion slider.
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 generates a random problem and then asks you to determine the answer. Please note that you can use the show-again button after a quiz to see all the steps in getting the correct answer.
THINGS TO NOTICE
When the orignal message is all zeroes, the CRC remainder added is also all zeroes.The CRC remainder will always be on fewer bit than the generator.
When you bring down the generator, it moves over until its leftmost 1 is under the leftmost one on the line above. Enough bits on the right are brought down so that the line above extends to the same column as the rightmost 1 of the generator.
All generators begin and end with a 1. That is because leading zeroes are stripped, and the mathematical theory behind how CRC works insists that generators be odd, and prefers them to be prime. With a prime generator, a generator of length n can detect all burst errors of length (n - 1) and will detect many errors of longer lengths. If an even generator is used, then we can not be certain to detect all burst errors of length (n - 1).
THINGS TO TRY
Set the slow-motion slider to about .2 seconds (or slower) and press the step button several times. Watch the demonstration of each step.Set the slow-motion slider to about .2 seconds and press the go button. Watch the entire demonstration.
Do each step by hand, then press step to check your work.
EXTENDING THE MODEL
Allow the user to input the beginning message.Allow the user to input the generator.
NETLOGO FEATURES
"min-one-of" reports the agent in the agentset that reports the lowest value for the given reporter."max-one-of" reports the agent in the agentset that reports the highest value for the given reporter.
"count" reports the number of agents in the given agentset.
RELATED MODELS
CREDITS AND REFERENCES
This model was written by Crystal Barchet and Teresa Carrigan, 2004.Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:
Contact Teresa Carrigan for appropriate licenses for redistribution for profit.
- this copyright notice is included.
- this model will not be redistributed for profit without permission from Teresa Carrigan.
To refer to this model in academic publications, please use: Barchet, C. and Carrigan, T. (2004). Cyclic Redundancy Check Simulation Blackburn College, Carlinville, IL.
In other publications, please use: Copyright 2004 by Crystal R. Barchet and Teresa Carrigan. All rights reserved.
FOR MORE INFORMATION
For more information about Cyclic Redundancy Check, see one of the following textbooks:
- Null, L. and Lobur, J. Essentials of Computer Organization and Architecture, First Edition, Jones & Bartlett, pages 73-76.
- Murdocca, M. and Heuring, V. Principles of Computer Architecture, First Edition, Prentice Hall, pages 365-366.
- Forouzan, B. Data Communications and Networking, Third Edition, McGrawHill, pages 249-253.
HomeApplets 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.