小 A 想给小 B 传输一串长度为 的二进制数 ,但由于外界环境的干扰,传输的二进制数的某一位可能发生改变,为了应对这个问题,小 A 学习了海明码。
海明码(Hamming code)是一种线性误差更正码,由理查德·海明(Richard Hamming)在1950年发明。它能够检测和纠正单一比特的错误。海明码通过在数据位之间插入额外的校验位来实现这种错误检测和更正的功能。
设 ,则小 A 会在这 位二进制码的后面补上 位 。
其中 的值为所有二进制第 位为 的数 的 异或和。例如 ,则 ,而 为所有 的异或和,即 。
这样将小A 将 传输给小 B ,那么小B 得到的是 ,小 B 就可以通过 和 的值来判断他收到的 和 相比,是否有某一位发生了改变,如果发生了那改变的是哪一位?
现在小 B 希望得到 到底是什么,请你帮帮他!
小 A 贴心的为小 B 提供了一个判断过程:
- 若 ,则说明 。
- 若 ,按接下来的步骤处理:
- 设一个未知数 。
- 对于每一个 ,我们设 的值为所有二进制第 位为 的数 的 异或和.
- 若 ,我们就令 二进制的第 位是 。
- 若 ,我们就令 二进制的第 位是 。
- 最后若 则 。
- 否则对于所有 而 。