循环冗余校验（CRC）算法原理

循环冗余校验（CRC）算法是一种数据校验方法，用于检测在数字通信中数据传输过程中出现的差错。该算法基于多项式除法，通过对发送方的数据进行除法运算并产生冗余校验码，再将数据和冗余校验码一起发送到接收方，接收方再对接收到的数据进行同样的除法运算，将结果与发送方传输的冗余校验码进行比较，以判断数据是否被修改或损坏。

CRC算法的原理是将数据看作二进制数，将其转化为多项式形式，然后进行除法运算。具体而言，发送方需要事先确定一个生成多项式G(x)，然后将数据D(x)左移若干位，使其次数等于G(x)的次数，然后对两个多项式进行模2除法，得到余数R(x)，将其作为冗余校验码附加到数据D(x)的末尾，得到发送数据S(x)。接收方接收到S(x)后，对其进行同样的除法运算，得到余数R'(x)，如果R'(x)为0，则表明数据没有被修改或损坏；否则，表明数据存在差错。

CRC算法的优点是简单、快速、可靠，被广泛应用于各种数字通信标准中，如以太网、无线局域网等。

相关问题

循环冗余校验crc编码怎么求

### 计算循环冗余校验 (CRC) 编码

#### 基本原理
CRC 算法的核心在于将待发送的数据视为一个非常大的二进制整数，并通过特定的生成多项式对该数值执行模2除法操作。所得的余数即为 CRC 校验码，该值会被追加至原始数据之后一同传输给接收端，在那里会再次进行相同的计算来验证数据完整性。

#### 数据准备阶段
假设有一个8比特的信息序列`1001 1100`以及选定的标准16位生成多项式之一 `G(x)=x^16 + x^15 + x^2 + 1` 或者表示成二进制形式就是`1100...00101`(其中省略号代表中间全部填充零)[^1]。

为了使被除数能够容纳下可能产生的最大余数——也就是等于或小于所选生成多项式的最高次幂减去一次方的结果长度，因此需要先在消息串后补上相应数量（此处为16）个'0'[^3]。

于是初始输入变为:`1001 1100 0000 0000`

#### 执行模2除法过程
接下来按照常规长除法规则来进行处理, 不过这里所有的加法都基于异或(XOR)运算而不是普通的十进制相加:

def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler):
    len_input = len(input_bitstring)
    initial_padding = initial_filler * (len(polynomial_bitstring) - 1)
    input_padded_array = list(input_bitstring + initial_padding)
    
    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')
        
        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
            
    return ''.join(input_padded_array)[len_input:]

crc_result = crc_remainder("10011100", "11000000000000101", '0')  
print(f"CRC result is {crc_result}")

上述Python函数实现了模拟手工完成整个除法流程的功能；最终输出的是经过转换后的CRC检验值字符串[crc_result].

#### 结果解释
最后获得的十六位CRC校验码将会附加上述信息字节流末端形成完整的传输单元供后续检错用途。值得注意的是实际应用中往往存在多种不同规格参数组合而成的具体实现方案，比如常见的CRC-16、CRC-CCITT等变种版本均采用了各自独特的生成多項式定义。