crc-ccitt -- 16-bit.htm

CRC16的源程序

  -- "A Painless Guide to CRC Error Detection Algorithms" 
  <LI><A 
  href="http://www.embedded.com/internet/0001/0001connect.htm">http://www.embedded.com/internet/0001/0001connect.htm</A> 
  -- another detailed discussion which includes a table containing check values 
  which were not included in the first document above.&nbsp; The table is at <A 
  href="http://www.embedded.com/internet/0001/0001contable1.htm">http://www.embedded.com/internet/0001/0001contable1.htm</A>, 
  but the check value for the 16-bit CRC-CCITT seems to be incorrect (the others 
  seem to be correct). 
  <LI>The following page also contained the seemingly incorrect check value for 
  the 16-bit CRC-CCITT: <A 
  href="http://www.aerospacesoftware.com/checks.htm">http://www.aerospacesoftware.com/checks.htm</A> 

  <LI>Link not functioning on April 3, 2003 -- C-language source code which 
  allowed reproducing the seemingly incorrect check value for the 16-bit 
  CRC-CCITT was found at: <A 
  href="http://www.programmingparadise.com/utility/crc.html">http://www.programmingparadise.com/utility/crc.html</A> 

  <LI>Link not functioning (but still cached by Google) on April 3, 2003 -- The 
  first external indication that the 16-bit CRC-CCITT values which seemed to be 
  incorrect above may actually be incorrect was gleaned from: <A 
  href="http://www.cs.ucla.edu/classes/spring00/cs33/proj/PROJECT_3.html">http://www.cs.ucla.edu/classes/spring00/cs33/proj/PROJECT_3.html</A> 
  </LI></UL>
<P><BR>
<HR width="100%">

<H3><A name=style></A>Style Notes</H3>
<UL>
  <LI>Why are the long-hand example and source code embedded in HTML 
  tables?&nbsp; Because they are in fixed-width font and confining the font tags 
  within tables aids in editing the document. 
  <LI>Why isn't the source code written using more of the compact forms allowed 
  by the C-language?&nbsp; To make it more accessible to BASIC 
  programmers.&nbsp; Note that the variables in these C-language routines hold 
  16-bit values.&nbsp; Shifting the value 0x8000 (32,768 decimal) by left one 
  bit is equivalent to multiplying by two; but a 16-bit variable cannot hold 
  0x10000 -- it becomes zero, not 65,536. </LI></UL>
<HR width="100%">

<H3><A name=addendum></A>Addendum</H3>This addendum is a quick attempt to 
address "the rest of the story" as it has become more clear to me after several 
e-mail exchanges with Sven Reifegerste, whose web page is linked <A 
href="http://www.joegeluso.com/software/articles/ccitt.htm#refs">above</A>. 
<P>To begin with, I have yet to see a specific reference to an <A 
href="http://www.itu.int/">ITU</A> (formerly CCITT) document that clearly 
identifies exactly where "the" algorithm for the CRC16-CCITT is given.&nbsp; If 
anyone can cite "chapter and verse", please let me know where the official 
specification may be found. 
<P>At this point, I'm left with what I can find on the web and what seems most 
credible to me.&nbsp; The article by Ross Williams, cited <A 
href="http://www.joegeluso.com/software/articles/ccitt.htm#refs">above</A>, 
seems to have stood the test of time and explains things in a way that 
(eventually) make sense to me.&nbsp; I count it as very credible. 
<P>The snippets of C code scattered around the web which claim to produce a 
CRC16-CCITT have taken on a life of their own, whether they are actually doing 
what they advertise or not. 
<P>I have not yet made a thorough investigation into everything that will be 
said below, so it may be subject to extensive revision once I find time to do 
so. 
<P>It seems that most of the CRC code on the web actually does implement some 
form of CRC algorithm -- as opposed to some less-robust kind of checksum.&nbsp; 
It is questionable in some cases whether their algorithm actually implements the 
CRC that they claim it does. 
<P>Assuming that an algorithm is actually implementing some kind of CRC, certain 
features of that algorithm are crucial when accurately implementing a particular 
CRC: 
<OL>
  <LI>The polynomial 
  <LI>The initial value 
  <LI>Whether or not "zero" bits are explicitly appended to the message 
</LI></OL>There seems to be no controversy that the "correct" (truncated) 
polynomial is for the CRC16-CCITT is 0x1021. 
<P>According to the document by Ross Williams, the initial value for "the" 
CRC16-CCITT is 0xFFFF.&nbsp; There seems to be little controversy over this, 
either. 
<P>It is usually the case that no one really wants to explicitly append "zero" 
bits to the end of a message to calculate a CRC.&nbsp; The mathematics of 
calculating a CRC do allow a shortcut to avoid this time-wasting exercise -- but 
if the shortcut is taken without making a corresponding change in the initial 
value, then the result is a _different_ CRC. 
<P>The question at this point is: 
<BLOCKQUOTE>Does the official specification for the CRC16-CCITT say that 
  initial value of 0xFFFF applies to a message _with_ or _without_ "zero" bits 
  explicitly appended to the message?</BLOCKQUOTE>It makes sense to me that the 
initial value of 0xFFFF applies to a message _with_ "zero" bits explicitly 
appended to the message.&nbsp; Why?&nbsp; Because the purpose of a CRC is to 
detect errors, not necessarily to be implemented in a compact algorithm or to 
have parameters that are easy to remember. 
<P>Whatever clever technique is used to calculate a CRC, it is always emulating 
a simple implementation in which "zero" bit _are_ explicitly appended to the 
message.&nbsp; I think it unlikely that the official specification for the 
CRC16-CCITT would be in terms of anything but the most basic implementation. 
<P>The paper by Ross Williams says: 
<BLOCKQUOTE>"In theory (i.e. with no assumptions about the message), the 
  initial value has no affect on the strength of the CRC 
algorithm"</BLOCKQUOTE>But did the committee that designed the CRC16-CCITT make 
_no_ assumptions about the message?&nbsp; I suspect that they made one or more 
assumptions about the kinds of messages that were important to them.&nbsp; If 
the "correct" check value for message, "123456789", using "the" CRC16-CCITT is 
0x29B1, why would they choose an initial value of 0x84CF (see table below) for 
the initial value?&nbsp; Remember, the ultimate definition of a CRC requires 
"zero" bits to be explicitly added to the end of the message -- all other 
implementations use tricks (clever techniques) to accomplish an equivalent 
calculation.&nbsp; Why would the CCITT (now ITU) want to specify an initial 
value of 0x84CF to error-check the kinds of messages that were important to 
them? 
<P>It seems that the same CRC can be calculated using the parameters below: 
<BR>&nbsp; 
<TABLE border=1>
  <TBODY>
  <TR>
    <TD><B>Initial Value</B></TD>
    <TD><B>"Zero" bits explicitly</B> <BR><B>appended to message</B></TD>
    <TD>
      <CENTER><B>CRC for the test message,</B></CENTER><B>"123456789"</B></TD></TR>
  <TR>
    <TD>
      <CENTER>0xFFFF</CENTER></TD>
    <TD>
      <CENTER>Yes</CENTER></TD>
    <TD>
      <CENTER>0x5ECC</CENTER></TD></TR>
  <TR>
    <TD>
      <CENTER>0x1D0F</CENTER></TD>
    <TD>
      <CENTER>No</CENTER></TD>
    <TD>
      <CENTER>0x5ECC</CENTER></TD></TR>
  <TR>
    <TD>
      <CENTER>---</CENTER></TD>
    <TD>
      <CENTER>---</CENTER></TD>
    <TD>
      <CENTER>---</CENTER></TD></TR>
  <TR>
    <TD>
      <CENTER>0x84CF</CENTER></TD>
    <TD>
      <CENTER>Yes</CENTER></TD>
    <TD>
      <CENTER>0x29B1</CENTER></TD></TR>
  <TR>
    <TD>
      <CENTER>0xFFFF</CENTER></TD>
    <TD>
      <CENTER>No</CENTER></TD>
    <TD>
      <CENTER>0x29B1</CENTER></TD></TR></TBODY></TABLE>
<P>Which is "the" CRC16-CCITT?&nbsp; I think it is 0x5ECC. 
<P>Because I haven't seen "chapter and verse" from an ITU document clearly 
calling for some "shortcut" algorithm using the 0xFFFF initial value, I remain 
convinced that the "correct" check value for message, "123456789", using "the" 
CRC16-CCITT is 0x5ECC -- not 0x29B1, as is more widely claimed. 
<P>Is this spitting into the wind?&nbsp; Probably so.&nbsp; I don't imagine that 
<FONT color=#000000>publishing this page is going to cause the "incorrect" 
implementations to disappear.</FONT>&nbsp; It is offered mainly to help others 
avoid the frustration that I experienced -- what almost everyone else said was 
the "correct" check value doesn't seem to be correct when trying to calculate 
the CRC16-CCITT from first principles.&nbsp; This page attempts to provide 
information which may be helpful in resolving this issue. 
<P>As Sven Reifegerste pointed out to me, the "correct" check value for the 
CRC32 seems to be calculated in a way that is similar to most implementations of 
the CRC16-CCITT -- everyone seems to calculate CRC32 with an initial value of 
0xFFFFFFFF but _without_ "zero" bits explicitly appended to the message.&nbsp; 
The CRC32 is much more widely used -- it is calculated and stored for each file 
that is archived in a .zip (compressed) file.&nbsp; I'm not prepared to spit 
into that hurricane.&nbsp; And I think that those who are trying to come to 
grips with exactly how to implement a CRC calculation will find that beginning 
with a 16-bit CRC, such as CRC16-CCITT, may be more manageable than wrestling 
with a 32-bit CRC algorithm. 
<P>
<HR width="100%">
<BR>Copyright 2001-2003, Joe Geluso <BR>All disclaimers apply -- use at your own 
risk. <BR>This page may reproduced only if it is not altered and it is 
reproduced in its entirety -- including the link to the author's web site. 
<BR>This page was last modified on April 4, 2003, 4:30pm. <BR>
<HR width="100%">
<BR>Return to the <A 
href="http://www.joegeluso.com/software/articles/index.htm">Articles index</A> 
</BODY></HTML>