Archived

This topic is now archived and is closed to further replies.

Xorcist

CRC Hell... Help!

Recommended Posts

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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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 / 101
101
---
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]

Share this post


Link to post
Share on other sites