CRC位序混淆

Question

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

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

在CRCITT的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计算.我不能简单地存储这些位,因为上面显示的代码是最终会出现在硬件中的原型(没有内存).

如果我按以下顺序输入比特流,则上面显示的代码会产生正确的结果(显示的是接收比特的索引.每个字节首先发送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位CRC目录,您会看到有两个不同的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"

您将注意到真实的一个被反映,假的一个没有,并且初始化还有另一个区别.在反射的CRC中,首先处理数据的最低位,因此您似乎正在尝试计算真正的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;
}

我不知道你的意思是"在CRCITT的CCITT定义中,这些位应该是最高位到最低位".你指的是什么定义？

在此Altera文档中,您可以看到用于硬件实现的CRC的移位寄存器实现.这是图表的副本:

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