CRC

Question

我正在使用 16 位 CRC 并有一个查找 table(LUT) 生成器，它为给定的多项式生成 LUT。我使用的生成器代码使用 Koopman 符号（例如 CCITT 的 0x8810），因此生成第一个 table 行：

 0x0000, 0x8810, 0x9830, 0x1020, 0xB870, 0x3060, 0x2040, 0xA850,

我在互联网上找到了一个已经计算出的 CCITT-table，但它显然使用了不同的符号，第一行给出为：

0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,

我的问题是：短符号和长符号（0x8810 与 0x11021）是否使用不同的 table 产生相同的结果（即 LUT 的用法不同）或者 CRC 是否不同使用不同符号的相同多项式？

ps:据我所知，0x8810 和 0x11021 是非反射 Koopman/"normal" 符号，0x8408 和 0x10811 是反射符号（对于 CCITT）

pps：第二个 table 的 "usage code" 给出为：

uint16_t crc16_block(uint16_t crc, uint8_t *data, int len){
    int i;

    for (i = 0; i < len; i++)
        crc = (crc << 8) ^ crc16_tbl[(crc >> 8) ^ data[i]];

    return crc;
}

Answer 1

考普曼符号表示多项式，但不是多项式。您不能将它用作您使用的查找 table 生成器的输入。您的第一个 table 没有用，因为隐含多项式没有低位 1.

Koopman 符号依赖于所有 CRC 多项式都以 1 结尾的事实。多项式总是有一个 + 1 项。当转换为二进制时，它们总是以 1 开头（x 的最高次幂），并且总是以 1 结尾。 10001000000100001，或 0x11021，对于 CCITT 多项式，x¹⁶+x¹²+x⁵+1.

这个数字的烦人之处在于它需要 17 位来表示。您希望有一个仅使用 16 位的符号，以便更容易地在具有 16 位整数的计算机程序中指定多项式（或者类似地，需要 32 位而不是 33 位来指定 32 位 CRC）。

有两种解决方法。跌高1，或跌低1。通常你会看到跌高1。 IE。 0x1021，再加上您还需要提供 CRC 的长度，在本例中为 16。所以规范是 16, 0x1021。（您还需要指定其他内容，但现在我们将限制在 CRC 和多项式的大小上。）

Koopman 意识到，如果您改为删除 low 1，您甚至不需要指定长度，并且仍然指定 16 位的 16 位 CRC 多项式。您通过向下移动一个来降低低 1。所以 0x11021 变成 0x8810。高1还在，所以它隐式定义了CRC的长度。

但是，要使用 Koopman 表示法中的 CRC，您必须将其上移一位并加一以获得用于计算的多项式和 table.

CRC - 16 位查找 table 使用不同的多项式符号

CRC - 16bit Lookup table using different polynomial notations

c