CRC 方法无法检测到哪些错误？

Question

假设 16 位 CRC 多项式 x1⁶+x12+x5+1 = 0x11021。该多项式可以：

1. 检测所有单位错误（与数据大小无关）。
2. 检测高达 16 位宽度的所有突发错误（与数据大小无关）。
3. 检测所有奇数个位错误（因为它有 4 个多项式项；数据 与尺寸无关）。
4. 检测高达 32571 位数据大小的 3 位错误 (HD4)。

考虑到以上几点都是对的...... CRC 无法检测到什么样的错误？

Answer 1

2. 应该检测最多 16 位的所有单突发错误。

3. 0x11021 是 2 个“质数”多项式 0xf01f 和 0x3 的乘积。 0x3 因子是检测到所有奇数位错误的原因（它是奇偶校验因子）。

4. 由于检测到所有奇数位错误，因此该语句变为检测数据大小为 32751 位或消息大小为 32767 位的所有 2 位错误，其中包括附加到数据位的 16 位 CRC。对于强力方法，使用除第一位为 1 之外的所有 0 位的位串，然后计算该串的 CRC，直到 CRC 仅有一个 1 位作为最高有效位。这可以通过从 0x8000 的 CRC 开始并循环直到再次循环回 0x8000 来模拟，这将需要 32767 个周期。因此，如果 bit[0] 和 bit[32768] == 1（所有其他位 == 0），则计算出的 CRC 将为零，无法检测到 2 个错误位。

CRC无法检测到哪些错误？

突发总距离超过 16 位的多重突发错误，本质上是长度超过 16 位的单个突发错误。

某些具有 4 个或更多随机分布位错误的模式将无法检测到。如下表所示，未检测到错误的可能性相当低。随着误码数的增加，故障率也会增加，但除非有很多误码，否则故障率仍然很低。随机位模式大约有 1/65536 的时间会通过 CRC16 检查，但这在正常的消息发送/接收序列中是不寻常的。

48 bit data, 16 bit crc, => 64 bit message
2^64 - 1 possible error patterns
       84 of        635376 possible patterns of  4 error bits fail
     2430 of      74974368 possible patterns of  6 error bits fail
   133001 of    4426165368 possible patterns of  8 error bits fail
  4621021 of  151473214816 possible patterns of 10 error bits fail   
100246083 of 3284214703056 possible patterns of 12 error bits fail

---

4 位情况的示例代码。将

e

设置为要测试的错误位数。

static uint16_t crctbl[65536];

int main()
{
uint32_t I[16];                 /* indexes */
uint32_t e = 4;                 /* # error bits */
uint32_t i, j;
uint64_t d;
uint32_t crc;
uint32_t fail = 0;
uint64_t tst = 0;

    for(j = 0; j < 0x10000; j++){ /* generate table */
        crc = j;
        for (i = 0; i < 16; i++) {
            crc <<= 1;
            if (crc & 0x10000)
                crc ^= 0x11021;
        }
        crctbl[j] = (uint16_t)crc;
    }
    for(i = 0; i < e; i++)      /* init I */
        I[i] = i;
    while(1){
        d = 0;                  /* set up pattern */
        for(i = 0; i < e; i++)
            d |= ((uint64_t)1 << (63-I[i]));
        for(j = 0; j < 4; j++){ /* generate crc */
            crc = crctbl[       (d >> 48)&0xffff ];
            crc = crctbl[crc ^ ((d >> 32)&0xffff)];
            crc = crctbl[crc ^ ((d >> 16)&0xffff)];
            crc = crctbl[crc ^ ((d >>  0)&0xffff)];
        }
        tst++;
        if (crc == 0)           /* if failed */
            fail++;
        i = e - 1;              /* advance indexes */
        if (++I[i] < 64)        /*  to next permuation */
            continue;
        --I[i];
        j = 63;
        while (I[i--] >= j--) {
            if (i == 0)         /* show progress */
                printf("%u\n", I[0]);
            if (i == (uint32_t)(0-1))
                goto done0;
        }
        j = I[++i];
        while (i < e)
            I[i++] = ++j;
    }
done0:
    printf("%llu %u\n", tst, fail);
    return 0;
}