Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
Russ Cooper
08/12/07 11:12
Modified:
  08/12/07 11:15

Read: 687 times
Phoenix, Az
USA


 
#143126 - Thanks for the hint
Responding to: Jan Waclawek'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


List of 32 messages in thread
TopicAuthorDate
CRC16 CCITT - What a challenge!      Jan Waclawek      08/06/07 13:08      
   Have you seen this?      Richard Erlacher      08/06/07 17:40      
      Of course!      Jan Waclawek      08/07/07 02:36      
         Balance      Russ Cooper      08/07/07 07:16      
            I know, Russ,      Jan Waclawek      08/07/07 07:53      
         Code? What code?      Russ Cooper      08/07/07 07:24      
            in the code library - look to the left column      Jan Waclawek      08/07/07 07:37      
               Thanks! I missed that note in the first post.      Russ Cooper      08/07/07 08:37      
   I need a hint      Russ Cooper      08/11/07 00:56      
      write down the bits      Jan Waclawek      08/11/07 01:22      
         Thanks for the hint      Russ Cooper      08/12/07 11:12      
            Your observations plus a comparison in C      Dan Henry      08/12/07 11:58      
               The rest of the story ...      Russ Cooper      08/12/07 16:43      
                  Compilers, but Keil C51 8.09 for the stated 28~      Dan Henry      08/12/07 17:04      
                  and this processes only a nibble, isn't it...      Jan Waclawek      08/12/07 23:27      
                     No, it process the entire byte.      Dan Henry      08/13/07 12:59      
                        now it\'s my pencil time...      Jan Waclawek      08/13/07 13:40      
                           FYFI      Dan Henry      08/13/07 14:40      
                              Clarification re: 8-bit optimized term      Dan Henry      08/13/07 17:46      
                              on optimisation      Jan Waclawek      08/14/07 02:56      
                                 Jan's optimization      Dan Henry      08/14/07 07:16      
                                    Re: on optimization      Dan Henry      08/19/07 09:18      
                                       Can you please be more specific?      Jan Waclawek      08/19/07 13:56      
                                          More specifically ...      Dan Henry      08/25/07 15:10      
            and what      Jan Waclawek      08/12/07 23:27      
               More on checksums        Russ Cooper      08/18/07 09:59      
   No reason to hide the excreted code      Dan Henry      08/12/07 17:41      
      Excreted code needs context like any other code      Dan Henry      08/12/07 19:01      
   One More Comment      Michael Karas      08/13/07 02:45      
      ... and a marginal remark ...      Jan Waclawek      08/13/07 07:02      
         Init all ones frequently specified      Dan Henry      08/13/07 13:06      
   18 cycles      Jan Waclawek      08/16/07 08:16      

Back to Subject List