前段时间在计算机组成原理的专业课中学习到了汉明码的校验过程，不禁回想起之前看到的一道通过小白鼠测试毒试剂的经典面试题，发现这个测试过程实质上就是汉明码的校验过程

面试题：8个试剂，其中一个有毒，有三只小白鼠，每个试剂发作需要十二小时，问最短需要多少时间能找出有毒的试剂

解法：

3只小鼠能组成8种状态

第一只喂食【1、3、5、7】四支试剂
第二只喂食【2、3、6、7】四支试剂
第三只喂食【4、5、6、7】四支试剂

# [3、2、1]
0 0 1 = 1  # 2、3没死，1死了，说明第1支试剂有毒
0 1 0 = 2  # 1、3没死，2死了，说明第2支试剂有毒
0 1 1 = 3  # 3没死，1、2死了，说明第3支试剂有毒
1 0 0 = 4  # 1、2没死，3死了，说明第4支试剂有毒
1 0 1 = 5  # 2没死，1、3死了，说明第5支试剂有毒
1 1 0 = 6  # 1没死，2、3死了，说明第6支试剂有毒
1 1 1 = 7  # 三只都死了，说明第7支试剂有毒
0 0 0 = 0  # 三只都没死，说明前7支试剂都没毒，第8支试剂有毒

可以看出十二个小时就可以找出有毒的试剂

汉明码

汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）

汉明码需要几个检测位有个公式: 2^k≥n+k+1, 其中k为检测位的个数，n为原始数据的位数

假设要传输一个4位数据0011，那么我们添加3个检测位即可，它们分别放在第2⁰，2¹，2²即第1，2，4位，如图

那么各检测位C_i承担的检测任务为

C₁检测的g₁小组包含第1，3，5，7···位，其二进制编码为X…XXX1

C₂检测的g₂小组包含第2，3，6，7···位，其二进制编码为X…XX1X

C₃检测的g₃小组包含第4，5，6，7···位，其二进制编码为X…X1XX

如果按照配偶原则配置汉明码的话，要保证检测的小组中1的个数为偶数，则有

C₁=3⨁5⨁7=1

C₂=3⨁6⨁7=0

C₃=5⨁6⨁7=0

那么得到的7位汉明码则为1000011，若经传输以后数据变为1000001，有1位数据发送改变，可以进行纠错

D₁=1⨁3⨁5⨁7=0

D₂=2⨁3⨁6⨁7=1

D₃=3⨁5⨁6⨁7=1

则出错位数为D₃D₂D₁=110=6，则可知道是第6位数据出错，纠错以后可知原始的4位数据应该是0011

D₃D₂D₁能组成8种状态

# [3、2、1]
0 0 1 = 1  # 第2、3检测小组未出问题，第1个检测小组出现问题，说明汉明码第1位数据出错
0 1 0 = 2  # 第1、3检测小组未出问题，第2个检测小组出现问题，说明汉明码第2位数据出错
0 1 1 = 3  # 第3检测小组未出问题，第1、2个检测小组出现问题，说明汉明码第3位数据出错
1 0 0 = 4  # 第1、2检测小组未出问题，第3个检测小组出现问题，说明汉明码第4位数据出错
1 0 1 = 5  # 第2检测小组未出问题，第1、3个检测小组出现问题，说明汉明码第5位数据出错
1 1 0 = 6  # 第1检测小组未出问题，第2、3个检测小组出现问题，说明汉明码第6位数据出错
1 1 1 = 7  # 第1、2、3个检测小组都出现问题，说明汉明码第7位数据出错
0 0 0 = 0  # 3个检测小组都未出问题，说明传输数据没有出错

至此可以看出，这道经典面试题的解答思想和汉明码的校验过程是高度相似的，三只小白鼠喝的试剂分别就是三个检测小组，第一只小白鼠喝的1、3、5、7号试剂，二进制编码就是XX1，第二只小白鼠喝的2、3、6、7号试剂，二进制编码就是X1X，第三只小白鼠喝的4、5、6、7号试剂，二进制编码就是1XX，通过代表三个检测小组的三只小白鼠喝了试剂以后死亡与否来找出是哪个试剂有毒，这个过程实际上与汉明码的校验过程高度相似，思想实际上是相同的