CRC位序困惑

Question

我正在逐位计算 CCITT CRC-16。我这样做是因为它是一个原型(prototype)，稍后应该移植到 VHDL 并最终在硬件中检查串行比特流。

在网上我找到了一个单比特的 CRC-16 更新步骤代码。写了一个测试程序，它工作。除了一件奇怪的事情:我必须从最低位到最高位提供一个字节的位。如果我这样做，我会得到正确的结果。

在 CRC-16 的 CCITT 定义中，位应该从最高位到最低位。我要计算 CRC 的数据流也采用这种格式，因此我当前的代码对我来说有点无用。

我很困惑。我没想到以错误的方式喂食钻头会奏效。

问题:为什么可以写入 CRC 以获取两种不同位顺序的数据，以及如何转换我的单位更新代码，使其首先接受数据 MSB？

供引用，这里是相关代码。已删除初始化和最终检查以保持示例简短:

typedef unsigned char bit;

void update_crc_single_bit (bit * crc, bit data)
{
  // update CRC for a single bit:
  bit temp[16];
  int i;

  temp[0] = data ^ crc[15]; 
  temp[1] = crc[0]; 
  temp[2] = crc[1]; 
  temp[3] = crc[2]; 
  temp[4] = crc[3]; 
  temp[5] = data ^ crc[4] ^ crc[15]; 
  temp[6] = crc[5]; 
  temp[7] = crc[6]; 
  temp[8] = crc[7]; 
  temp[9] = crc[8]; 
  temp[10] = crc[9]; 
  temp[11] = crc[10]; 
  temp[12] = data ^ crc[11] ^ crc[15]; 
  temp[13] = crc[12]; 
  temp[14] = crc[13]; 
  temp[15] = crc[14];

  for (i=0; i<16; i++)
    crc[i] = temp[i];
}

void update_crc_byte (bit * crc, unsigned char data)
{
  int j;
  // calculate CRC lowest bit first
  for (j=0; j<8; j++)
  {
    bit b = (data>>j)&1;
    update_crc_single_bit(crc, b);
  }
}

编辑:因为这里有些困惑:我必须逐位计算 CRC，并且每个字节的 MSB 在前。我不能简单地存储这些位，因为上面显示的代码是最终将在硬件中(没有内存)的东西的原型(prototype)。

如果我按以下顺序输入比特流，上面显示的代码会生成正确的结果(显示的是接收到的比特的索引。每个字节首先传输 MSB):

|- first byte -|-   second byte     -|-  third byte 
7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8,....

我需要对单个更新循环进行转换，使其使用自然顺序(例如收到的)生成相同的 CRC:

|- first byte -|-   second byte     -|-  third byte 
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,.... 

Answer 1

如果您查看 RevEng 16-bit CRC Catalogue ，您会看到有两个不同的 CRC，称为“CCITT”，其中一个被标记为“CCITT-False”。在这个过程中的某个时候，有人对 CCITT 16 位 CRC 是什么感到困惑，并且这种困惑被广泛传播。这两个 CRC 是这样描述的，第一个 (KERMIT) 是真正的 CCITT CRC:

KERMIT

width=16 poly=0x1021 init=0x0000 refin=true refout=true xorout=0x0000 check=0x2189 name="KERMIT"

和

CRC-16/CCITT-FALSE

width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1 name="CRC-16/CCITT-FALSE"

你会注意到，真实的反射(reflect)出来了，假的没有反射(reflect)出来，还有一个区别就是初始化。在反射(reflect)的 CRC 中，首先处理数据的最低位，因此看起来您正在尝试计算真正的 CCITT CRC。

当反射(reflect) CRC 时，异或运算到寄存器的多项式中位的顺序也会发生变化，因此 0x1021 变为 0x8408。这是您可以检查的简单 C 实现:

#include <stddef.h>

#define POLY 0x8408

unsigned crc16_ccitt(unsigned crc, unsigned char *buf, size_t len)
{
    int k;

    while (len--) {
        crc ^= *buf++;
        for (k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    }
    return crc;
}

我不知道您所说的“在 CRC-16 的 CCITT 定义中，位应该从最高位到最低位”是什么意思。你指的是什么定义？

在this Altera document ，您可以看到硬件实现的 CRC 移位寄存器实现。这是图表的副本:

对于您的代码，您需要反转寄存器、temp[]、索引。 temp[0] 是 temp[15] 等等。