Coding a CRC-Generating Algorithm in C
(Page 1 of 4 )
When you sit down to implement any theory regardless of its simplicity, soon you will find that it is harder than it seems. All sorts of details will need to be dealt with that you may not have thought about while coming up with the solution to the problem in theory. In the following article I will implement a CRC-generating code. So stick with me if you are interested.
Last time I presented the theory behind generating a checksum from a sequence of ones and zeros and from a generator polynomial. If you missed it and you do not understand the basic concepts of this technique, please stop reading this article and seek out that one, entitled Cyclic Redundancy Check.
I will present the software and hardware solution. Let's start with the software. I will try to implement all this as generally as possible, using only the C language. This will give you the option to use the code within some microcontrollers, with nice C++ GUIs as well. Nevertheless, before I get down to some concrete C code, we need to look into a few implementation issues and define some rules that will help us make fast, general code.
We will use a registry that has the length of the check sum width. After this we will push in at one end the input data binary sequence and make the operation with the generator polynomial in the registry. The generator polynomial, in fact, is also a binary number that has the length of the checksum generated.
Because the first bit is one for every generator polynomial, we will store only the further bits. This will lead to the fact that by using a 2 byte register, for instance, we can use a 17-width generator polynomial, and as a result, detect burst error with a length of 17.
If we append to our input data zeros of the count of the registry width, this will not change our end result (as I explained in my earlier article), and it will make it certain that, once we shift the last bit into our registry, we are done, and we no longer need to make a partial shift operation in the registry.
As for the algorithm, first we could implement the method I presented in my theory article: division, the way we learned it from primary school. Then again, that would be awfully slow for a large amount of data, because it implies a shift operation for every bit of the input, and afterward a subtraction (which is an XOR bitwise operation).
Using this approach, we will need to shift our data bit by bit into our register from the right side, and once one bit makes it into the left side, just subtract the generator polynomial. Because we've already thrown away the first bit of the generator polynomial, we can also throw away the first bit from the register, make an additional shift and only afterward make an xor operation with our generator polynomial's stored bits.
Next: Keep it simple >>
More C# Articles
More By Gabor Bernat
