使用长度为7的汉明码,位置从左到右从1开始编号。将原串的四个比特依次放在第 位。
将这四个位置中比特为1的位置编号全部异或,得到 。写成 ,再将 分别放到第 位。完整字符串中所有值为1的位置编号的异或和即为 。
设传输时第 位被翻转。对收到的字符串中所有值为1的位置编号求异或,相当于增加或去掉一次 ,所以结果恰好为 。再次翻转该位,再读取第 位即可。由于恰好翻转一位,这种策略下收到的异或结果总在1到7之间。
传输长度始终为7,满足限制。校验位1,2,4出错和数据位3,5,6,7出错都能用同一方法恢复。
朴素恢复方法是枚举16种原串并编码,寻找与受损字符串恰好相差一位的码字。任意两个不同码字的距离至少为3:距离为1会导致它们的校验异或值不同;距离为2则要求两个不同位置编号的异或为0,矛盾。因此候选码字唯一。由于输入规模固定,朴素解法也能通过全部条件。
主解法时间和额外空间均为 。朴素解法至多进行 次比特比较,也为 。位置异或值至多为7,原串的数值至多为15,8位掩码至多为255,所有整数运算都在有符号64位范围内。
Solution written by GPT6