再谈老鼠毒药面试题

Subscribe Send me a message home page


面试的常见题:1000瓶药水,1瓶有毒药,服用后一小时毒发,毒药可以无限稀释,那么一小时内用几只小白鼠能够找出毒药?

网络上有很多关于此题解法的讨论,大多提及二进制的表达,在此便不再赘述。这里只是想指出此题的背景也许和Hamming error correction相关。

无毒的药水可以看成在发送端为0的bit; 有毒的药水可以看成在传输过程过被损坏的bit(由零翻转成1)。在Hamming error correction/detection的算法中,我们需要在原始数据后面加上check bit。这里我们可以认为check bit的数据为零,因为发送端的bit均为零。并且这一部分并不包含在1000个bit(药水)之中,所以check bit的这一部分可以认为没有出错。 这样一来,原先的题目就变成Hamming error correction的一个直接应用了。

因为只有一瓶毒药,所以我们面对的是single error case。根据Hamming error detection算法,对收到信息中的每一个1的位置的二进制表示相加得到一个和,并加上收到信息中的check bit的值(在这个例子中为零)便可以得到出错的bit的位置。因为在收到的信息中只有一位非零(因为只有一瓶毒药),所以求和相当于将一瓶混有来自不同瓶的药水喂给一直小白鼠。

Figure-1: First error-correction code

关于位置表达的一些思考。因为现在我们已经对二进制十分熟悉,所以想要表达5个不同的位置,自然会想到使用3个bit。但是在书中,Hamming提到他曾经试图使用Figure-1的的表达方式。也就是说为了表达5个不同的位置需要使用5个bit:

0: <10000> 1: <01000> 2: <00100> 3: <00010> 4: <00001>

显然这样的表达是十分浪费的。但是究竟浪费在何处?可能的原因是以下两点。

关于Hamming error correction/detection的另一个感想是,从书中可以看到这个算法和两个概念紧密联系: 一个是parity; 一个是high dimensional space。 而parity某种程度上是module的一个特例。所以事后来看在Cyclic Redundancy Checks算法中所使用的多项式是一个十分“自然的“选择,它将high dimension space和module联系了起来。

----- END -----

Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png


Comments