Okay I'm going nuts because I can't find a proper reference and no one seems to know the exact process for generating a CRC when the division doesn't work out. Let me elaborate by saying all the references I have found always ended up with a smaller number being subtracted (XORed) from a larger one during the division process... However what am I supposed to do when I run into a situation like this: Using 1101011110100 as my data and (X^5 + X3 + X2 + 1) as my polynomial code when I append the CRC zeros to the end and do the division as such:

             11101?
        ___________________
101101 /1101011110100|00000
        101101
        ------
         110001
         101101
         ------
          111001
          101101
          ------
           101001
           000000
           ------
           1010010
           0101101
           -------
           11111111 <- Here is the problem...

45 (101101) goes into 255 (11111111) 5 times with 30 left over, but if I actually do out the multiplication and follow through with the rest of the problem I get a CRC of 11000 which I know is wrong, because the original numbers are 220800 and 45, which leaves a remainder of 30 (11110) [4906 * 45 + 30 = 220800]. So what am I doing wrong! If anyone can give me a simpler example of the same typr of situation with the proper steps or a link to a complete explaination of the "by hand" method of generating a CRC I'd greatly appreciate it. [edited by - Xorcist on July 27, 2003 9:47:06 PM]

Where are the zeros coming from? Why are you bringing them down like that?

Which zeros? The ones I appended to the end? The remainder (i.e. the CRC value) is supposed to be one digit less than the polynomial value. This is how I've seen it done in my networking book and serveral tutorials. But none of these give a full explaination of CRC and how to handle various cases such as the one I listed. If you are asking about the fourth division operation I do, those zeros come from the fact 45 (101101) goes into 41 (101001) zero times. Is this not what I am supposed to do?

Note: I did not finish the problem, I stopped at the part that's causing me trouble, but if you continue with the problem and use those added zeros the CRC comes out to be 11000.


[edited by - Xorcist on July 27, 2003 10:17:27 PM]

Forget it, I found this link: http://www.macs.hw.ac.uk/~pjbk/nets/crc/

the stepwise calculator showed my what I was doing wrong. Guess I don't have to worry about multiplication issues. If the leading bit is a one and it has the same number of digits as the polynomial code, you divide anyways even if the number is larger.

[edited by - Xorcist on July 28, 2003 12:34:23 PM]

I wrote a really good CRC article back in the day, and although I never finished the section of CRC tables (and thus never released it), I could always help you out if you have any more troubles

You have to remember that this is Modulo-2 subtraction, so regular multiplication rules won't work when you try to reverse your work. Take this really simple example:

10011000     / 101101---  111  101  ---   100   101   ---     100     101     ---      01      

10011000b = 152
101 = 5

152 / 5 = 30 remainder 2, yet 01b = 1. So the math doesn't follow standard base-10 arithmetic rules, which can be a tad confusing. Just have confidence in the process

EDIT: As for the "by hand" method of doing a CRC, it's really just a list of steps. You start out with your divisor, comparing it's highest bit to the highest bit of the dividend. They will both be one, so the first time around you're doing an XOR. You then get a new number. Keep the leading zeros (if any)! Compare the highest bit of your divisor against the highest bit of the result. If they're both 1, do another XOR, and repeat the process. Otherwise, keep moving the divisor "down the bits" until you find a 1 bit, and then XOR. When the lowest bit of the divisor reaches the lowest bit of the dividend, then this is the last time you can check for 1 bits and do a XOR. Whether or not you end up doing an XOR is irrelevant, as you have reached the end and are finished!

[edited by - Zipster on July 27, 2003 12:36:35 AM]

Thanks, thats the step by step process I was looking for.