CODEWITHSUNDEEP
ccrc16
Hairi
Hairi

Reputation: 3715

What Truncated polynomial mean in CRC16 CCITT context

Trying to understand this explanation of CRC16 CCITT, I came across to the term "truncated polynomial". Comparing the long-hand calculation for a one-byte message with the corresponding C code, I found out that the macro definition of poly doesnt match the calculation example from the above. Into the C code the polynomial is 0x1021 while into the calculation example above the polynomial used is bigger, 0x11021.

They use the term truncated polynomial for this: 0x1021. What pattern do they use to extend this 0x1021 to this 0x11021?

Upvotes: 1

Views: 2860

Answers (1)

Marek Klein
Marek Klein

Reputation: 1490

0x11021 represents polynomial p = x^16+x^12+x^5+x^0 from F2[X]. Message (together with initial value and augmentation) is also represented by a polynomial. CRC is basically just message modulo polynomial p. Therefore CRC never needs more than 2 bytes. Since p = 0 mod p we can write x^16 = x^12+x^5+x^0 mod p. So 0x1021 represents x^12+x^5+x^0.

Now lets see how update_good_crc works:

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;
    }
}

  1. This checks whether most significant bit of good_crc is set to zero. In other words, it checks whether coefficient at x^15 is set to 1 or 0.

    if (good_crc & 0x8000)
{
    xor_flag= 1;
}

  2. good_crc = good_crc << 1; this multiplies good_crc by x. Thus coefficient at x^15 becomes coefficient at x^16 and good_crc "overflows" its 16 bits (that's why we stored xor_flag).

  3. good_crc = good_crc ^ poly; if xor_flag is set then this "subtracts" x^16 = x^12+x^5+x^0 mod p from good_crc.

Upvotes: 2

Related Questions