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

Question

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

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

Answer 1

0x11021表示来自F2[X]的多项式p = x^16+x^12+x^5+x^0。消息（连同初始值和扩充）也由多项式表示。 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;
    }
}

这会检查 good_crc 的最高有效位是否设置为零。换句话说，它检查 x^15 处的系数是否设置为 1 或 0。
```
if (good_crc & 0x8000)
{
    xor_flag= 1;
}
```
good_crc = good_crc << 1; 这会将 good_crc 乘以 x。因此 x^15 处的系数变为 x^16 处的系数， good_crc "overflows" 其 16 位（这就是我们存储 xor_flag 的原因）。
good_crc = good_crc ^ poly; 如果设置了 xor_flag 那么这个 "subtracts" x^16 = x^12+x^5+x^0 mod p 来自 good_crc.

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

What Truncated polynomial mean in CRC16 CCITT context

c

crc16