c - CRC16 CCITT 上下文中的截断多项式意味着什么

Question

试图理解this在解释 CRC16 CCITT 时，我遇到了术语“截断多项式”。将一个字节消息的长手计算与相应的C代码进行比较，发现poly的宏定义与上面的计算示例不符。在 C 代码中，多项式是 0x1021，而在上面的计算示例中，使用的多项式更大，0x11021。

他们为此使用术语截断多项式:0x1021。他们使用什么模式将此 0x1021 扩展为此 0x11021？

Answer 1

0x11021表示多项式 p = x^16+x^12+x^5+x^0来自 F2[X]。消息(连同初始值和扩充)也由多项式表示。 CRC 基本上只是消息模多项式 p .因此 CRC 永远不需要超过 2 个字节。自 p = 0 mod p我们可以写x^16 = x^12+x^5+x^0 mod p .所以0x1021代表x^12+x^5+x^0 .

现在让我们看看如何update_good_crc作品:

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. 这会检查 good_crc 的最高有效位是否设置为零。换句话说，它检查 x^15 处的系数是否设置为 1 或 0。

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

2. good_crc = good_crc << 1;这会将 good_crc 乘以 x。因此 x^15 处的系数成为 x^16 处的系数good_crc 会“溢出”它的 16 位(这就是我们存储 xor_flag 的原因)。

3. good_crc = good_crc ^ poly;如果xor_flag设置然后这个“减去”x^16 = x^12+x^5+x^0 mod p来自 good_crc。