模二除法详解

模二除法（Modulo-2 Division）是一种特殊的除法运算，用于计算二进制数据的CRC校验码。这种运算与普通的除法类似，但区别在于它使用 不进位的异或运算 来代替普通除法中的减法操作。模二除法的结果为二进制余数，应用在校验过程中以检验数据完整性。

模二除法的基本规则

• 模二除法的每一步相当于使用 异或（XOR） 运算替代减法。
• 模二除法中，不需要进位，只需要逐位比较和异或操作。

举例说明模二除法

假设我们有一组二进制数据 110101，要对它进行CRC校验，使用生成多项式 1011。这里，我们演示模二除法的具体步骤。

1. 准备原始数据和生成多项式：

   • 原始数据：110101
   • 生成多项式：1011（长度为4位）

2. 数据扩展：为了计算CRC校验码，需要在数据末尾添加3位0（因为生成多项式是4位，CRC校验码的长度为生成多项式位数减1）。

   • 扩展后的数据：110101000

3. 模二除法操作：

   • 将生成多项式 1011 对扩展后的数据 110101000 进行“除法”（使用异或操作），具体过程如下：

   步骤 1：

   • 当前被除数：1101（取扩展后的前4位）
   • 生成多项式：1011
   • 异或结果：0110

   步骤 2：

   • 将结果 0110 的下一位（扩展数据中的下一位 0）放下，形成新的被除数：1100
   • 异或 1011：结果为 0111

   步骤 3：

   • 将结果 0111 的下一位 1 放下，形成新的被除数：1111
   • 异或 1011：结果为 0100

   步骤 4：

   • 将结果 0011 的下一位 0 放下，形成新的被除数：1000
   • 异或 1011：结果为 0011

   步骤 5：

   • 将结果 0011 的下两位 0 放下，形成新的被除数：1100
   • 异或 1011：结果为 0111

1. 最终余数为 0101，即为 CRC 校验码。

2. 验证数据完整性：接收方可以使用相同的生成多项式再次进行模二除法。如果运算结果余数为 0，则表示数据没有错误；如果不为零，则表明数据有误。

   def xor_division(dividend, divisor):
       """ Perform modulo-2 division (XOR division) and return the remainder. """
       # Convert divisor and dividend to lists of integers for easy manipulation
       dividend = list(map(int, dividend))
       divisor = list(map(int, divisor))
       divisor_len = len(divisor)
       
       # Perform XOR division
       for i in range(len(dividend) - len(divisor) + 1):
           # Only apply XOR if the current bit is 1
           if dividend[i] == 1:
               for j in range(divisor_len):
                   dividend[i + j] ^= divisor[j]  # XOR operation
   
       # The remainder is the last bits of the modified dividend
       remainder = ''.join(map(str, dividend[-(divisor_len - 1):]))
       return remainder
   
   def calculate_crc(data, generator):
       """ Append CRC remainder to data and return the data with CRC code. """
       # Append zeros to the data based on the length of the generator polynomial
       data_padded = data + '0' * (len(generator) - 1)
       remainder = xor_division(data_padded, generator)
       return data + remainder  # Original data + CRC code
   
   # Example usage
   data = '110101'         # Original data
   generator = '1011'      # CRC generator polynomial
   
   # Calculate CRC and append it to the data
   data_with_crc = calculate_crc(data, generator)
   print(f"Original Data: {data}")
   print(f"Generator Polynomial: {generator}")
   print(f"Data with CRC code: {data_with_crc}")
   

总结

• 模二除法的本质是对二进制数据逐位异或运算。
• 在 CRC 中，这种运算用于生成和验证校验码，以检测传输过程中的数据错误。