代码之家  ›  专栏  ›  技术社区  ›  etuardu

从等式实现CRC算法

  •  3
  • etuardu  · 技术社区  · 12 年前

    我正在处理一个设备,它说要使用这种16位循环冗余检查:

    CCITT CRC-16 with polynomial x^16 + x^12 + x^5 + x^1
    

    我寻找这种算法的实现,但我只找到了方程最后一项等于 1 (即。 x^0 )而不是 x^1 喜欢 this one this .

    我本来打算自己实现这个算法,但我意识到我不知道如何开始。它应该如何从一个方程开始进行CRC计算?

    2 回复  |  直到 12 年前
        1
  •  2
  •   cha0site    12 年前

    此PDF文件解释了主题: hackersdelight.org/crc.pdf .

    我还推荐Andrew Tanenbaum的《计算机网络》,因为它有一章是关于CRC算法的。

    最后,我要仔细检查一下,您的设备是否确实实现了这种形式的CRC,而不是标准的CRC。这可能只是一个拼写错误。

        2
  •  1
  •   Mark Adler    12 年前

    你是对的,多项式是错的。一个正确的CRC多项式必须总是有一个1项。CCITT CRC-16多项式是x^16+x^12+x^5+1,如@guga所示,或位形式的0x1021(省略了x^16)。看看这个 catalog of 16-bit CRCs .

    除了多项式之外,那里的信息还提供了您需要的其他关键信息。明确地:

    width=16 poly=0x1021 init=0x1d0f refin=false refout=false xorout=0x0000 check=0xe5cc
    

    这意味着CRC不是位反映的,而是用 0x1d0f ,并且结果并不排除任何内容。因此,无字节的CCITT CRC是 0x1d0英尺 它还提供了ASCII数字“123456789”的9字节字符串的校验值, 0xe5cc 。您应该使用它来检查您的实现情况。

    Ross Williams guide 将告诉您关于实施CRC需要了解的所有信息。