【计算题】要发送的数据为 101110 。采用 CRC 的生成多项式是 P(X)=X3+1 。试求应添加在数据后面的余数

考查要点：本题主要考查循环冗余校验（CRC）的计算方法，涉及生成多项式的应用及二进制长除法运算。

解题核心思路：

1. 生成多项式转换：将生成多项式 $P(X)=X^3+1$ 转换为二进制形式 $1001$。
2. 数据扩展：将原始数据 $101110$ 后补 $3$ 个 $0$（余数位数等于生成多项式次数）。
3. 模2除法：用扩展后的数据多项式除以生成多项式，得到的余数即为校验码。

破题关键点：

• 正确对齐位数：在长除法中，需逐位比较被除数与除数的最高位，通过异或操作消去高位。
• 余数提取：最终余数的位数需与生成多项式次数一致（本题为 $3$ 位）。

步骤1：数据扩展

原始数据为 $101110$，补 $3$ 个 $0$ 后变为 $101110000$（共 $9$ 位）。

步骤2：生成多项式转换

生成多项式 $P(X)=X^3+1$ 对应二进制 $1001$（$4$ 位）。

步骤3：模2长除法

将 $101110000$ 除以 $1001$，逐位计算余数：

1. 初始对齐：

   • 被除数前 $4$ 位 $1011$ 与除数 $1001$ 异或：
     $1011 \oplus 1001 = 0010$
   • 余数暂为 $0010$，带下第 $5$ 位 $1$，得 $00101$。

2. 继续消去高位：

   • $00101$ 最高位为 $0$，商补 $0$，带下第 $6$ 位 $0$，得 $001010$。
   • 重复至余数最高位为 $1$，最终余数为 $011$。

步骤4：余数提取

最终余数为 $011$，即为添加的校验码。