www.JoeGeluso.com

CRC16-CCITT


Overview

This page presents accurate implementations (long-hand and programmed) of the 16-bit CRC-CCITT specification, which is: A C-language program is included which produces CRC values which conform to this specification.  The program also includes a routine which demonstrates how an incorrect "check value" which has been found on the web may be generated.
 


General

Why yet another document on calculating CRCs?  Because this one: Important features of a standard CRC are that it:
  • Can be used to validate data
  • Is reproducible by others
  • The first feature above is easy to realize in a closed system if corruption of data is infrequent (but substantial when it occurs).  The term "closed system" refers to a situation where the CRC need not be communicated to others.  A correct implementation of a 16-bit CRC will detect a change in a single bit in a message of over 8000 bytes.  An erroneous CRC implementation may not be able to detect such subtle errors.  If errors are usually both rare and large (affecting several bits), then a faulty 16-bit CRC implementation may still be adequate in a closed system.

    The second feature above -- that the CRC is reproducible by others -- is crucial in an open system; that is, when the CRC must be communicated to others.  If the integrity of data passed between two applications is to be verified using a CRC defined by a particular standard, then the implementation of that standard must produce the same result in both applications -- otherwise, valid data will be reported as corrupt.

    Reproducibility may be satisfied by even a botched implementation of a standard CRC in most cases -- if everyone uses the same erroneous implementation of the standard.  But this approach:

    It appears that some CRC implementations available on the web produce incorrect values for the 16-bit CRC-CCITT.  How to tell if a CRC16-CCITT implementation was botched?  By calculating the CRC for a reference string.

    The CRC value for the 9-byte reference string, "123456789" is 0xE5CC.  Some web pages report that the value for reference string should be 0x29B1 -- but this value is returned by an implementation which does NOT conform to the specification above.  CRC values for other reference strings are listed elsewhere in this document.

    The bolding and italics above are used to emphasize the correct value and distort the incorrect value in the hope that it will discourage propagation of the incorrect value.

    Why focus on the 16-bit CRC-CCITT (polynomial 0x1021) and not CRC16 (polynomial 0x8005), which appears to have wider use?  Because the 16-bit CRC-CCITT:

    Why use a 16-bit CRC instead of a 32-bit CRC?  Because it:



    Results from the C-language Implementations

    The following CRC values were produced by the program whose source code is listed elsewhere in this document.  The "Good_CRC" values are in accordance with the CRC-CCITT specification as defined at the top of this document.  The "Bad_CRC" values are produced by an implementation which reports the incorrect check value that is reported on some web pages for the reference string "123456789".  The validity of the "Good_CRC" values below is demonstrated elsewhere in this document.
     
     

    Message

    Good_CRC

    Bad_CRC

    Message Length (bytes)

    -None-
    0x1D0F
    0xFFFF
    0
    A
    0x9479
    0xB915
    1
    123456789
    0xE5CC
    0x29B1
    9
    A string of 256 upper case "A" 
    characters with no line breaks
    0xE938
    0xEA0B
    256

    Among the problems with the "Bad_CRC" implementation is that it does not augment a zero-length message with 16 zero bits, as is required (either implicitly or explicitly) when calculating the standard CRC.  Thus, it reports a CRC of 0xFFFF -- not 0x1D0F -- for a zero-length message.


    Long-hand Calculation for a One-byte Message

    The purpose of this section is to demonstrate that the "Good_CRC" values listed in the previous section do, in fact, conform to the CRC-CCITT specification as defined at the top of this document
     
    Calculation of the 16-bit CRC-CCITT for a one-byte message consisting of the letter "A":

                             Quotient=  111100001110111101011001
          poly=       ------------------------------------------
    10001000000100001 ) 1111111111111111010000010000000000000000
                        10001000000100001
                        -----------------       red bits are initial value
                         11101111110111111      bold bits are message
                         10001000000100001      blue bits are augmentation
                         -----------------
                          11001111100111100
                          10001000000100001
                          -----------------
                           10001111000111010
                           10001000000100001
                           -----------------
                            00001110000110110
                            00000000000000000
                            -----------------
                             00011100001101100
                             00000000000000000
                             -----------------
                              00111000011011000
                              00000000000000000
                              -----------------
                               01110000110110001
                               00000000000000000
                               -----------------
                                11100001101100010
                                10001000000100001
                                -----------------
                                 11010011010000110
                                 10001000000100001
                                 -----------------
                                  10110110101001110
                                  10001000000100001
                                  -----------------
                                   01111101011011110
                                   00000000000000000
                                   -----------------
                                    11111010110111100
                                    10001000000100001
                                    -----------------
                                     11100101100111010
                                     10001000000100001
                                     -----------------
                                      11011011000110110
                                      10001000000100001
                                      -----------------
                                       10100110000101110
                                       10001000000100001
                                       -----------------
                                        01011100000011110
                                        00000000000000000
                                        -----------------
                                         10111000000111100
                                         10001000000100001
                                         -----------------
                                          01100000000111010
                                          00000000000000000
                                          -----------------
                                           11000000001110100
                                           10001000000100001
                                           -----------------
                                            10010000010101010
                                            10001000000100001
                                            -----------------
                                             00110000100010110
                                             00000000000000000
                                             -----------------
                                              01100001000101100
                                              00000000000000000
                                              -----------------
                                               11000010001011000
                                               10001000000100001
                                               -----------------
                                                1001010001111001 = CRC
     

    Conversion of the binary value above to hexadecimal by segmenting the bits to nibbles:
                            binary nibbles   1001 0100 0111 1001
                            hexadecimal         9    4    7    9


    Source Code for the C-language Implementations

     
    /*
    demonstrates how the incorrect check value of 0x29B1 may be reported
    for the test string "123456789" when it should be 0xE5CC.
    */

    #include <stdio.h>
    #include <string.h>

    #define           poly     0x1021          /* crc-ccitt mask */

    /* global variables */
    char text[1000];
    unsigned short good_crc;
    unsigned short bad_crc;
    unsigned short text_length;

    int main(void)
    {
        void go();
        void repeat_character(unsigned char, unsigned short);

        sprintf(text, "%s", "");
        go();

        sprintf(text, "%s", "A");
        go();

        sprintf(text, "%s", "123456789");
        go();

        repeat_character(65, 256);
        go();

        return 0;
    }

    void go(void)
    {
        void update_good_crc(unsigned short);
        void augment_message_for_good_crc();
        void update_bad_crc(unsigned short);

        unsigned short ch, i;

        good_crc = 0xffff;
        bad_crc = 0xffff;
        i = 0;
        text_length= 0;
        while((ch=text[i])!=0)
        {
            update_good_crc(ch);
            update_bad_crc(ch);
            i++;
            text_length++;
        }
        augment_message_for_good_crc();
        printf(
        "\nGood_CRC = %04X,  Bad_CRC = %04X,  Length = %u,  Text = \"%s\"",
           good_crc,         bad_crc,         text_length,  text
        );
    }

    void repeat_character(unsigned char ch, unsigned short n)
    {
        unsigned short i;
        for (i=0; i<n; i++)
        {
            text[i] = ch;
        }
        text[n] = 0;
    }

    void update_good_crc(unsigned short ch)
    {
        unsigned short i, v, xor_flag;

        /*
        Align test bit with leftmost bit of the message byte.
        */
        v = 0x80;

        for (i=0; i<8; i++)
        {
            if (good_crc & 0x8000)
            {
                xor_flag= 1;
            }
            else
            {
                xor_flag= 0;
            }
            good_crc = good_crc << 1;

            if (ch & v)
            {
                /*
                Append next bit of message to end of CRC if it is not zero.
                The zero bit placed there by the shift above need not be
                changed if the next bit of the message is zero.
                */
                good_crc= good_crc + 1;
            }

            if (xor_flag)
            {
                good_crc = good_crc ^ poly;
            }

            /*
            Align test bit with next bit of the message byte.
            */
            v = v >> 1;
        }
    }

    void augment_message_for_good_crc()
    {
        unsigned short i, xor_flag;

        for (i=0; i<16; i++)
        {
            if (good_crc & 0x8000)
            {
                xor_flag= 1;
            }
            else
            {
                xor_flag= 0;
            }
            good_crc = good_crc << 1;

            if (xor_flag)
            {
                good_crc = good_crc ^ poly;
            }
        }
    }

    void update_bad_crc(unsigned short ch)
    {
        /* based on code found at
        http://www.programmingparadise.com/utility/crc.html
        */

        unsigned short i, xor_flag;

        /*
        Why are they shifting this byte left by 8 bits??
        How do the low bits of the poly ever see it?
        */
        ch<<=8;

        for(i=0; i<8; i++)
        {
            if ((bad_crc ^ ch) & 0x8000)
            {
                xor_flag = 1;
            }
            else
            {
                xor_flag = 0;
            }
            bad_crc = bad_crc << 1;
            if (xor_flag)
            {
                bad_crc = bad_crc ^ poly;
            }
            ch = ch << 1;
        }
    }


    References

    The following web page contains a javascript calculator that is handy for what-if comparisons in calculating various CRCs by slightly different methods and with any initial value -- very well done:


    The following web pages were among those which were helpful in developing the text and program in this document:



    Style Notes


    Addendum

    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 above.

    To begin with, I have yet to see a specific reference to an ITU (formerly CCITT) document that clearly identifies exactly where "the" algorithm for the CRC16-CCITT is given.  If anyone can cite "chapter and verse", please let me know where the official specification may be found.

    At this point, I'm left with what I can find on the web and what seems most credible to me.  The article by Ross Williams, cited above, seems to have stood the test of time and explains things in a way that (eventually) make sense to me.  I count it as very credible.

    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.

    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.

    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.  It is questionable in some cases whether their algorithm actually implements the CRC that they claim it does.

    Assuming that an algorithm is actually implementing some kind of CRC, certain features of that algorithm are crucial when accurately implementing a particular CRC:

    1. The polynomial
    2. The initial value
    3. Whether or not "zero" bits are explicitly appended to the message
    There seems to be no controversy that the "correct" (truncated) polynomial is for the CRC16-CCITT is 0x1021.

    According to the document by Ross Williams, the initial value for "the" CRC16-CCITT is 0xFFFF.  There seems to be little controversy over this, either.

    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.  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.

    The question at this point is:

    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?
    It makes sense to me that the initial value of 0xFFFF applies to a message _with_ "zero" bits explicitly appended to the message.  Why?  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.

    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.  I think it unlikely that the official specification for the CRC16-CCITT would be in terms of anything but the most basic implementation.

    The paper by Ross Williams says:

    "In theory (i.e. with no assumptions about the message), the initial value has no affect on the strength of the CRC algorithm"
    But did the committee that designed the CRC16-CCITT make _no_ assumptions about the message?  I suspect that they made one or more assumptions about the kinds of messages that were important to them.  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?  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.  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?

    It seems that the same CRC can be calculated using the parameters below:
     
    Initial Value "Zero" bits explicitly
    appended to message
    CRC for the test message,
    "123456789"
    0xFFFF
    Yes
    0xE5CC
    0x1D0F
    No
    0xE5CC
    ---
    ---
    ---
    0x84CF
    Yes
    0x29B1
    0xFFFF
    No
    0x29B1

    Which is "the" CRC16-CCITT?  I think it is 0xE5CC.

    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 0xE5CC -- not 0x29B1, as is more widely claimed.

    Is this spitting into the wind?  Probably so.  I don't imagine that publishing this page is going to cause the "incorrect" implementations to disappear.  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.  This page attempts to provide information which may be helpful in resolving this issue.

    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.  The CRC32 is much more widely used -- it is calculated and stored for each file that is archived in a .zip (compressed) file.  I'm not prepared to spit into that hurricane.  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.
     


    Addendum #2 -- ITU/CCITT publications and "the" CRC16-CCITT

    Thank you to the several people who responded to the request for "chapter and verse" where the official specification may be found for "the" CRC16-CCITT.

    The ITU (formerly CCITT) documents that have come to my attention so far are:

    1. Recommendation V.41 -- "Code-Independent Error Control System."
    2. Recommendation X.25 -- "Interface between Data Terminal Equipment (DTE) and Data Circuit-terminating Equipment (DCE) for terminals operating in the packet mode and connected to public data networks by dedicated circuit"
    3. Recommendation T.30 -- "Procedures for document facsimile transmission in the general switched telephone network"
    ITU allows three free downloads (another page on their site says three free downloads per year?) of their standards, as mentioned here:
    http://www.itu.int/publications/index.html
    Do be careful to follow the instructions as they are presented -- I wasted a free download by not doing so.
     

    All three documents mentioned above use the same truncated polynomial -- 0x1021.

    Recommendation V.41 seems to specify an initial value of "zero" -- which differs from the usual implementations of CRC16-CCITT.

    Recommendation X.25 seems to:

    1. Use an initial value of 0xFFFF, but
    2. Require the step of performing one's complement, and
    3. Be composed of the sum of two remainders obtained from two separate polynomial divisions.
    The result from the X.25 calculation may be mathematically equivalent to a usual implementation of CRC16-CCITT, but that isn't clear to me at this point.

    Recommendation T.30 seems to:

    1. Use an initial value of 0xFFFF, but
    2. Require the step of performing one's complement
    Thus, T.30 seems to depart from usual implementations of CRC16-CCITT in that it requires performing one's complement.

    There seems to be relatively good agreement among the routines found on the web concerning _some_ parts of "the" CRC16-CCITT specification.  But at this point (July 2003), I am not aware of an ITU/CCITT document that agrees with other parts of "the" CRC16-CCITT specification (as it is normally rendered in routines found on the web), and:

    1. Requires a non-zero initial value
    2. Does not require the step of performing one's complement
    Perhaps I missed something in one of the documents mentioned above?

    It is also becoming less clear to me that the ITU/CCITT intended or documented the calculation of a stand-alone CRC.  Their documents seem to be more focused on a FCS (Frame Check Sequence) that can be used to validate a serial transmission immediately upon receipt rather than being concerned about ensuring that disk files (static data) are intact or unmodified (to the extent that a CRC is good for such a purpose) after a period of months or years.



    Last Modified -- August 27, 2005
    Copyright 2001-2005, Joe Geluso
    All disclaimers apply -- use at your own risk.
    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.


    Return to the Articles index