CRC位序混淆

Question

我正在计算一个CCITT CRC-16一点一点。我是这样做的，因为它是一个原型，以后应该移植到VHDL中，最后在硬件中检查串行比特流。

在网络上，我发现了一个位CRC-16更新步骤代码。写了一个测试程序然后就成功了。除了一件奇怪的事情:我必须从最低位到最高位给字节的位。如果我这样做，我会得到正确的结果。

在CCITT对CRC-16的定义中，比特应该是从最高位到最低位的馈送。我想要计算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。我不能简单地存储这些位，因为上面所示的代码是一个原型，最终会出现在硬件中(没有内存)。

上面所示的代码如果我按以下顺序按位流进给(所示为接收位的索引)，则生成正确的结果。每个字节首先传输MSB )：

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

我需要对单个update循环进行转换，使其使用自然顺序(例如接收到的)生成相同的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位CRC目录，你会发现有两个不同的CRCs叫做"CCITT"，其中一个被标记为"CCITT-False“。在此过程中的某个地方，有人对CCITT 16位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"

您将注意到，真实的一个被反映出来，而虚假的一个没有，并且在初始化中还有另一个不同之处。在反射CRCs中，数据的最低位首先被处理，所以看起来您正在试图计算真正的CCITT CRC。

当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;
}

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

在这份Altera文件中，您可以看到用于硬件实现的CRC的移位寄存器实现。下面是图表的副本：

​

​

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

Answer 2

更新-如果您查看：

RevEng 16位CRC目录

有一个链接到：

联机CRC计算器

前三个标记为CRC-CCITT使用多项式0x11021对发送或接收到LSB的数据进行操作。唯一的区别是初始值：

CRC-CCITT (XModem) - crc初始化为0x0000，与前缀0x0000相同。

CRC-CCITT (0xFFFF) - crc初始化为0xFFFF，与0x84CF前缀相同。

CRC-CCITT ( 0x1D0F ) -初始化为0x1D0F的crc，与0xFFFF前缀相同。

所以我猜你想用这三个中的一个。

Answer 3

通常，比特首先在线路上传输最不重要的比特。因此，如果您有一个字节数组，第一个位是第一个字节中最不重要的位，然后是最不重要的位.所以，到了第一个字节中最重要的一点，然后是下一个字节中最不重要的一点。这是你正在进行的多分类中位(系数)的顺序。试试我在https://github.com/mojadita/crc.git的例程(您有CRC16-CCITT的表)