| ??? 08/12/07 17:12 Modified: 08/12/07 17:15 Read: times |
#143126 - Thanks for the hint Responding to: ???'s previous message |
Jan said:
Write down the bits of CRC (say c15..c0) and the input byte (say, b7..b0). Now, start to do the CRC manually, bitwise, observing where the individual bits go. You will find out, that within the first 4 bits, the bits won't get mixed too much, and in fact only the high nibble of the original CRC xored with high nibble of the input byte is xored into CRC shifted left by that nible, into 3 positions (this comes from the fact that the 3 nonzero bits in the 1021 poly are sufficently far from each other, and the highest nonzero bit is sufficiently far from the "overflow" end).
Now try to write down the same in nibbles form; and do it for both nibbles. You will then see how the algo works... Thank you. That helped a lot. I understand it now. You have indeed created a very clever optimization! Too bad it's necessary to start over from the very beginning for every different polynomial. (c: Have you run into articles like this one that raise some doubt about how a correct implementation of CCITT CRC-16 is really supposed to work? It points out that many websites (including the online CRC calculator that you have mentioned) give 29B1h as the CRC for the test string "123456789". However, the author of the site believes for one reason or another that the correct result is actually E5CCh. I don't suppose this would matter too much if your use of the algorithm was limited only to your own programs. Of course it would matter a lot if you were exchanging data with somebody else's program that calculated the CRCs differently. -- Russ |
