Much of the literature on CRCs, and in particular on their table-driven implementations, is a little obscure or at least seems so to me. This document is an attempt to provide a clear and simple no-nonsense explanation of CRCs and to absolutely nail down every detail of the operation of their high-speed implementations. The model algorithm can be parameterized to behave like most of the CRC implementations around, and so acts as a good reference for describing particular algorithms. A low-speed implementation of the model CRC algorithm is provided in the C programming language. Lastly there is a section giving two forms of high-speed table driven implementations, and providing a program that generates CRC lookup tables.
|Published (Last):||18 September 2012|
|PDF File Size:||6.79 Mb|
|ePub File Size:||3.70 Mb|
|Price:||Free* [*Free Regsitration Required]|
Williams 1. To do this, the transmitter constructs a value called a checksum that is a function of the message, and appends it to the message. The receiver can then use the same function to calculate the checksum of the received message and compare it with the appended checksum to see if the message was correctly received. For example, if we chose a checksum function which was simply the sum of the bytes in the message mod i. All numbers are in decimal.
If the checksum itself is corrupted, a correctly transmitted message might be incorrectly identified as a corrupted one. However, this is a safe-side failure. Unfortunately, this possibility is completely unavoidable and the best that can be done is to minimize its probability by increasing the amount of information in the checksum e. However, this document addresses only CRC algorithms, which fall into the class of error detection algorithms that leave the data intact and append a checksum on the end.
If a number of random corruptions occur, there is a 1 in chance that they will not be detected. While basically a good idea, it fails in this case because the formula used is not sufficiently "random"; with a simple summing formula, each incoming byte affects roughly only one byte of the summing register no matter how wide it is.
For example, in the second example above, the summing register could be a Megabyte wide, and the error would still go undetected. This problem can only be solved by replacing the simple summing formula with a more sophisticated formula that causes each incoming byte to have an effect on the entire checksum register. The CRC algorithms to be described satisfy the second condition very well, and can be configured to operate with a variety of checksum widths.
All sorts of schemes spring to mind. We could construct tables using the digits of pi, or hash each incoming byte with all the bytes in the register. We could even keep a large telephone book on-line, and use each incoming byte combined with the register bytes to index a new phone number which would be the next register value.
The possibilities are limitless. While addition is clearly not strong enough to form an effective checksum, it turns out that division is, so long as the divisor is about as wide as the checksum register.
Upon receipt of the message, the receiver can perform the same division and compare the remainder with the "checksum" transmitted remainder.
These can be considered to be the hexadecimal number which can be considered to be the binary number Suppose that we use a checksum register one-byte wide and use a constant divisor of , then the checksum is the remainder after is divided by While in this case, this calculation could obviously be performed using common garden variety bit registers, in the general case this is messy.
A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHM
CRC: A Paper On CRCs