存档传输中的校验位可以由一串二进制多项式运算产生。它能帮助发现部分数据损坏,但一个短余数不可能唯一代表所有长消息,更不能证明消息来源可信。
先把规则写清楚
本例采用明确列出的生成多项式二进制串,最高位和最低位均为一。把消息末尾补上多项式次数个零,做模二长除法:对齐最高位后逐位异或,直到剩余位数不足。所得余数补齐宽度,附在原消息后构成码字。
本例输入与推演结果
消息11110101011000000,生成多项式100101,余数宽度5。
长除法各次异或后: 0110000101100000000000 0010101101100000000000 0000111001100000000000 0000011100100000000000 0000001110000000000000 0000000111010000000000 0000000011111000000000 0000000001101100000000 0000000000100110000000 0000000000000011000000 0000000000000001010100 0000000000000000011110 余数11110,码字1111010101100000011110。 翻转位编号 | 改后码字 | 校验余数 | 检测到变化 [1] | 1011010101100000011110 | 01100 | True [4] | 1111110101100000011110 | 10011 | True [0] | 0111010101100000011110 | 11000 | True [8] | 1111010111100000011110 | 11100 | True [4, 9, 12, 19] | 1111110100101000011010 | 00011 | True [5, 16, 19] | 1111000101100000111010 | 11010 | True [14, 17] | 1111010101100010001110 | 00100 | True [8, 10, 16, 18] | 1111010111000000110110 | 10110 | True
这里的编号只用来辨认本例中的对象,不能当成另一份记录里的固定身份。阅读表格时先找到输入,再顺着运算顺序对照输出;空列表、零值和不存在的结果有不同含义,不能混用。表中分数保留精确值,小数显示仅为阅读方便。
怎样自己复核
完整码字用同一多项式相除应余零。把一位或多位翻转后再除,余数非零才表示本例检测到了错误;余零只能说明校验没有发现异常。多项式各系数只在零一之间,不使用普通整数除法中的借位。
按表中位序从左往右编号,手动翻转指定位置,保留每一次异或之后的串。检验时要包含附加的校验位,不能只检查原消息。若要判断某类错误能否全部检出,需要研究那一类错误的结构,少量示例通过并不能代替完整证明。
适用范围
本例是教学用的直接长除法,初始余数为零,没有位反射或最终异或,不声称兼容任何现成文件格式。不同参数即使多项式相同,也可能产生不同的校验值。
本例是一套可复现的游戏机制练习,不依赖具体品牌或某个软件的默认设置。修改任何边界约定、输入参数或操作顺序后,应重新推演并保存中间状态。发现差异时先定位第一处不一致,再判断是规则不同还是计算错误,不要只把最终答案调整到看起来相同。
