crc循环冗余检验计算题

### 关于CRC循环冗余校验

CRC（Cyclic Redundancy Check，循环冗余校验）是一种基于多项式除法的错误检测技术。其基本原理是在发送端按照特定算法计算出一个校验值附加到数据后面，在接收端再重新计算该值并与接收到的校验值比较来判断传输过程中是否有误。

对于给定的一个二进制序列作为消息以及另一个较短的二进制序列作为生成多项式的系数表示形式，通过模2除法运算得出余数即为所求得CRC码字[^1]。

具体来说：

- 发送方将待传送的信息位串左移若干位形成被除数；
- 使用预定义好的生成多项式执行模2除法操作直到商长度等于原信息位串；
- 所得到的最终余数就是用来做纠错验证用的CRC校验码，并将其附加上去构成完整的帧结构准备发出；

下面给出一道简单的练习题用于理解上述过程：

假设要发送的消息M=1001110, 采用标准CRC-3 (G(x)=x^3+x+1)，则整个编码后的字符串应如何构建？

解题步骤如下所示:

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:]

message = "1001110"
generator_polynomial = "1011" # G(x)=x^3+x+1 对应的二进制表达
crc_code = crc_remainder(message, generator_polynomial, '0')
print(f"CRC Code: {crc_code}")
encoded_message = message + crc_code
print(f"Encoded Message: {encoded_message}")

运行此Python脚本可以获取到经过CRC处理之后的实际输出结果。