CRC原理与实现

原理

循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码个一种散列函数，主要用来检测或校验数据传输或者保存后可能出现个错误。生成个数字拉传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。

二进制数与其生成多项式一一对应，如\(1101\leftrightarrow x^3+x^2+1\)

设原始多项式\(P(x)\)，生成多项式为\(G(x)\)长度为\(r\)，生成的校验码多项式为\(R(x)\)，将\(P(x)\)乘以\(x^r\)，再模二除以\(G(x)\)，所得余式即为\(R(x)\)。

两种办法计算这个模二除法，假设原始多项式1100，生成多项式1001

第一种

模二除法意味着可以随意增减系数为偶数的项。 \[ \begin{equation}\begin{split} \frac{x^r P(x)}{G(x)}&\xlongequal{}\frac{x^6+x^5}{x^3+1}\\&\xlongequal{add\: 2x^3} x^3+\frac{x^5+x^3}{x^3+1}\\ &\xlongequal{add\: 2x^2} x^3+x^2+\frac{x^5+x^3}{x^3+1}\\&\xlongequal{add\: 2} x^3+x^2+\frac{x^2+1}{x^3+1} \end{split}\end{equation} \]

\(x^2+1\)除不尽，所以\(R(x)=101\)

第二种

\[ \begin{equation}\begin{split} &\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }1101\\ &1001\overline{\big)1100000}\\ &\text{ } \text{ }\:\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\underline{1001}\\ &\text{ }\text{ }\:\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }1010\\ &\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\underline{\text{ }1001}\\ &\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }1100\\ &\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\underline{\text{ }1001}\\ &\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }101 \end{split}\end{equation} \]

同样得到\(R(x)=101\)

常见的CRC算法

名称	生成多项式
CRC-1	\(x+1\)
CRC-4	\(x^4+x+1\)
CRC-12	\(x^{12}+x^{11}+x^3+x+1\)
CRC-16	\(x^{16}+x^{12}+x^2+1\)
CRC-ITU  CRC-CCITT	\(x^{16}+x^{12}+x^5+1\)

代码算法

CRC-CCITT算法（Python实现）

def crc_ccitt(data):
    crc = 0x0000
    poly = 0x1021

    for byte in data:
        byte_reversed = int(format(byte, '08b')[::-1], 2)
        crc ^= (byte_reversed << 8)
        for _ in range(8):
            if crc & 0x8000:
                crc = (crc << 1) ^ poly
            else:
                crc <<= 1
            crc &= 0xFFFF

    # 输出反转（低/高字节分别反转）
    crc = int(format(crc, '016b')[::-1], 2)
    return crc.to_bytes(2)