由一个有趣问题引出的巧妙方法.pdf
由一个有趣问题引出的巧妙方法.pdf
由一个有趣问题引出的巧妙方法 杨金民 2019-05-16 问题：公安局人员截获一情报：一恐怖分子将一瓶有毒矿泉水，掺进了一批发往世博会的矿泉水 中。现发现这批矿泉水共有 1000 瓶。为了获取证据，并把那瓶有毒的矿泉水挑拣出来，公安人员使出 的办法是用小老鼠来喝水。已知只要小老鼠喝了一点那瓶有毒的水，就会在 24 小时内死去。请问最简 的办法是需要多少只小老鼠，就可在 24 小时内将那瓶是有毒的挑拣出来。请具体描述出挑拣方法。 分析：这是一个搭配问题：瓶子与小老鼠的搭配问题。一方有 1000 瓶水，一方有 n 只小老鼠。目 标是：能从小老鼠的表现，能够得出有毒的到底是哪一瓶? 假定只用一只小老鼠，办法是让这只小老鼠对这 1000 瓶，每瓶的水都喝点，如果 24 小时内死了， 就说明这 1000 瓶中至少有 1 瓶发生了改变，由无毒变成了有毒。由此联想到奇偶校检法：对由 0 和 1 组成的串，它在存储或者传输过程中，串长不会发生变化，但是其中某个位置的 1 可能因为干扰变成 0，0 也可能变成 1。假定一个串最多只会有一个位发生变化。为了检测一个串在存储或者传输过程中 是否有上述改变，增设一个校检位（1 bit） 。如果串中的 1 的个数为奇数个，校检位设为 1，否则设为 0。 奇偶校检的本质含义是：统计 1 的个数，然后除以 2，取余数。余数自然只须 1 bit 来存储。对统 计结果，除以一个数 k，取余，其用意是进行压缩处理，缩小其值，节省存储空间。当然，压缩处理 有代价，那就是信息的丢失。上述奇偶校检，当传输中发生的位改变的数量为奇数个时，它能感知出 来，但是如果位改变的数量为偶数个时，它就不能感知。如果改成除以 4，取余，那么当位改变的数 量不为 4 的倍数时，它能感知出来；如果为 4 的倍数，它就不能感知出来。由此可见，除以 4 取余， 比除以 2 取余，感知能力增强了。不过代价也增大了，校检值须要 2 个 bits 来存储，增加了一个 bit。 而且要假定校检位在存储或者传输过程中不会改变。 到底是采用除以 2 取余，还是除以 4 取余？要看出错概率。传输一个 bit，假定发生位改变的概率 为 p。假定一次传输 8 bits，那么发生 0 个 bit 改变（即传输完全正确）的概率是 P0 = C80p0(1-p)8，发生 一个 bit 改变的概率是 P1 = C81p1(1-p)7，发生两个 bits 改变的概率是 P2 = C82p2(1-p)6，发生三个 bits 改变 的概率是 P3 = C83p3(1-p)7，依次类推，发生八个 bits 改变的概率是 P8 = C88p8(1-p)0。 设 p=0.01, 即传输改变概率为 1%，那么 P0 = 0.922； P1 = 0.074； P2 = 0.0026； P3 = 0.00005； 设 p=0.02, 即传输改变概率为 2%，那么 P0 = 0.851； P1 = 0.139； P2 = 0.010； P3 = 0.00006； 从上述计算可知：P2 成倍地小于 p; P1 远远大于 p。 从 P1 远远大于 p 可知，奇偶校检很有必要。采用奇偶校检后，尽管 8 个 bits 一起传输，传输中发 生了改变而又不能通过奇偶校检感知出来的概率为 P2 (P4, P6，...，因太小，都可忽略不计） ，比 p 都还 明显小，因此，奇偶校检显著地提升了传输的可靠性。记住，可靠性有个特性，就是只有提升的概念， 没有完全解决的概念。 接下来的问题是：假定通过奇偶校检，发现了一个位改变，能不能知道到底是哪一个位发生了改 变？如果知道，就可纠错，不须要重传了。 奇偶校检位，它自己在传输过程中也可能发生改变。在随后解决“到底是哪一位发生改变？”时， 把奇偶校检位也视作一个数据位来看待。 联系：1000 瓶中含有 1 瓶有毒矿泉水 检错； 1000 瓶中哪一瓶是有毒矿泉水 纠错； 用 1000 只小老鼠，每只对应一瓶， 自然一下子就能知道是哪一瓶有毒，不仅能检错，还能纠错。 不过成本太大而已，也是连幼儿园的小朋友都能想出的办法。这种办法叫直觉方法，不须要知识。 稍微动点脑筋，搞点分类，情形就大不一样。首先要标识每瓶矿泉水，用编号来标识：第 1，第 2， 第 3，...., 第 1000 瓶。为了阐释道理，缩小规模，假设只有 8 瓶矿泉水。标识成第 1，第 2，第 3，...., 第 8 瓶。其中有一瓶是有毒的。我们的策略是：递归地进行划分。在第一轮划分中，将整个 8 瓶一分 为二，分成 A,B 两组：A 组为第 1，第 2，第 3，第 4 瓶；B 组为第 5，第 6，第 7，第 8 瓶。在第二轮 划分中，对 A,B 两组再一分为二：第 1，第 2 瓶为 A 组；第 3，第 4 瓶为 B 组；第 5，第 6 瓶为 A 组； 第 7，第 8 瓶为 B 组。在第三轮划分中，第 1 瓶为 A 组；第 2 瓶为 B 组；第 3 瓶为 A 组；第 4 瓶为 B 组；第 5 瓶为 A 组；第 6 瓶为 B 组；第 7 瓶为 A 组；第 8 瓶为 B 组。至此，一组包含的元素个数为 1， 达到了最小粒度值，划分完毕。结果如下图所示，0 为 A 组，1 为 B 组： 对每一轮，选定一个组，例如 B 组，安排一只小老鼠，来喝其中的水。具体来说，让第一只小老 鼠对第 5，第 6，第 7，第 8 瓶中的水都喝一点；让第二只小老鼠对第 3，第 4，第 7，第 8 瓶中的水 都喝一点；让第三只小老鼠喝对第 2，第 4，第 6，第 8 瓶中的水都喝一点。24 小时后，如果 第一只小老鼠死了，说明有毒的在第 5，第 6，第 7，第 8 瓶中 有毒 {5,6,7,8} 第二只小老鼠死了，说明有毒的在第 3，第 4，第 7，第 8 瓶中 有毒 {3,4,7,8} 第三只小老鼠死了，说明有毒的在第 2，第 4，第 6，第 8 瓶中 有毒 {2,4,6,8} 现在知道有且仅只一瓶有毒，于是，求三个含毒集合的交集：{5,6,7,8} {3,4,7,8} {2,4,6,8} = {8} 于是，得出第 8 瓶为有毒的结论。 如果检测结果为：只有第二只小老鼠死了，第一、第三只小老鼠没有死，则说明： 第一只小老鼠没有死 {5,6,7,8} 无毒 有毒 {1,2,3,4} 有毒 {3,4,7,8} {1,2,5,6} 无毒 第二只小老鼠死了 第三只小老鼠没有死 {2,4,6,8} 无毒 有毒 {1,3,5,7} 求三个含毒集合的交集：{1,2,3,4} {1,3,7,8} {3,4,7,8} = {3} 于是，得出第 3 瓶为有毒的结论。 再来看规律： 对于 B 组，第一轮：α= {5,6,7,8}，第二轮：β = {3,4,7,8}；第三轮： = {2, 4, 6, 8}， 有：αβ = {8}； αβ = {7, 8}； α = {6, 8}； β = {4, 8} 即：2 仅只出现在中； 4 出现在β，中；6 出现在 α，中；7 出现在α，β中； 8 在α，β， 中都出现。而 1 在三轮α，β，中都没有出现。也就是说，1, 2, 3, 4, 5, 6, 7, 8 存在正交性， 即存在测试中的可区分性，这就是方法的巧妙所在。 进行归纳：对 n 瓶矿泉水进行递归二分。于是树的深度为：log2n + 1。须要log2n个小老鼠来喝 水，除了 root 结点外，每个小老鼠对应一层。选取其中的一组，假设为 A 组，让每层对应的小老鼠来 喝该层中 A 组瓶中的水。于是就可仅只须要log2n个小老鼠，就可把含毒的那瓶矿泉水挑拣出来。 上述方案的另一特点是：让第一只小老鼠，第二只小老鼠，第三只小老鼠来并行地处理第一轮， 第二轮，第三轮测试。 如果没有时间限制，可安排第一只小老鼠进行第一轮测试，如果在 24 小时没死的话，那么接着用 它进行第二轮测试，再过 24 小时，如果还没死，再用它进行第三轮测试。如果在某轮测试中，小老鼠 死了，那么就要用新的一只小老鼠来继续测试，直至完成最后一轮测试。这就叫串行处理。 假设总共有 1024 瓶矿泉水（=210），那么就要进行 10 轮测试，才能把有毒的那瓶挑拣出来。按照 上述串行测试办法，那么平均来说，要多少只小老鼠才能把那瓶有毒的挑拣出来呢？ 第 i 轮测试 1 2 3 4 5 6 7 8 9 10 第 i 轮测试后还 没死的概率 死在第 i 轮测试 的概率 1/2 1/22 1/23 1/24 1/25 1/26 1/27 1/28 1/29 1/210 1/2 1/22 1/23 1/24 1/25 1/26 1/27 1/28 1/29 1/210 仅须 1 只小老鼠，就可检测出来，须要依次检测 10 轮，检测总时间为 10*24 小时。检测办法是， 在第一轮测试中，让它对 1-500 号瓶，每瓶都喝一点，如果没死，说明有毒的在 501 至 1000 号之间， 于是在第二轮测试中，让它对 501-750 号瓶，每瓶都喝一点，如果没死，说明有毒的在 751 至 1000 号 之间。于是在第三轮测试中，让它对 751-875 号瓶，每瓶都喝一点，如果还没死，说明有毒的在 876 至 1000 号之间。有毒的范围在不断缩小，直至剩下 2 瓶，做最后一轮试验。 如果在第一轮中，小老鼠死了，说明有毒的在 1 至 500 号之间，于是在第二轮测试中，用新的一 只小老鼠，让它对 1-250 号瓶，每瓶都喝一点。在其它轮，依次类推。 最后一轮试验，也就是第 10 轮检测，小老鼠死与不死都没关系，都能完成检测，因为最后就只剩 两瓶了，让小老鼠喝其中的一瓶，如果死了说明喝的那瓶有毒，没死则说明剩下的那瓶有毒。仅用 1 只小老鼠就能挑拣出有毒的那瓶矿泉水，那就要求小老鼠从第 1 轮开始直至第 9 轮（倒数第二轮）检 测后，都一直没死，其概率自然为 p = 1/2*1/2*1/2*...*1/2 = 1/29 即：p = C90 ×1/29 如果是仅须 2 只小老鼠，就可检测出来，还是要依次检测 10 轮，检测总时间还是 10*24 小时。分 两层来考虑： 第一层：第一只小老鼠死在第 1 轮试验，第 2 轮试验，第 3 轮试验，.....，第 9 轮试验上； 第二层：在第一层的基础上，假设第一只小老鼠死在第 i 轮试验上，则要求第二只小老鼠从第 i+1 轮试验直至第 9 轮试验都不死； 因此，两者要同时成立，于是要且仅要 2 只小老鼠的概率为： 求概率： for i = 1 to 9 p = p + 1/2i × 1/2(9 - i) 即：p = C91 ×1/29 i 1 2 3 4 5 6 7 8 9 即：p = 1/2*1/28 + 1/22*1/27 + 1/23*1/26 + ... + 1/29 = 9 / 29 如果是要且仅要 3 只小老鼠，就可检测出来，须要时间还是 10*24 小时。那就要分三层了： 第一层：第一只小老鼠死在第 1 轮试验，第 2 轮试验，第 3 轮试验，.....，第 8 轮试验上； 第二层：在第一层的基础上，假设第一只小老鼠死在第 i 轮实验上，第二只小老鼠则可能是是死在第 i+1, i+2, ...., 第 9 轮试验上； 第三层：在第二层的基础上，假设第二只小老鼠死在第 j 轮实验上，第三只小老鼠直至第 9 轮试验都 没有死； 求概率： for i = 1 to 8 for j = i+1 to 9 p = p + 1/2i × 1/2(j - i) × 1/2(9 - j) 即：p = C92 ×1/29 i 1 j 的个数 2~9 = 8 2 3 3~9=7 4~9=6 4 5 6 7 8 5~9=5 6~9=4 7~9=3 8~9=2 9~9=1 以此类推，要且仅须 4 只小老鼠，就可检测出来，须要时间还是 10*24 小时。那就要分四层了： 第一层：第一只小老鼠死在第 1 轮试验，第 2 轮试验，第 3 轮试验，.....，第 7 轮试验上； 第二层：在第一层的基础上，假设第一只小老鼠死在第 i 轮试验上，第二只小老鼠则是死在第 i+1, i+2, ...., 第 8 轮试验上； 第三层：在第二层的基础上，假设第二只小老鼠死在第 j 轮试验上，第三只小老鼠直至第 9 轮试验都 没有死； 第四层：在第三层的基础上，假设第三只小老鼠死在第 k 轮试验上，第四只小老鼠直至第 9 轮试验都 没有死； 求概率： for i = 1 to 7 for j = i+1 to 8 for k = j+1 to 9 P = p + 1/2i * 1/2(j - i)* 1/2(k - j)* 1/2(9 - k) 即：p = C93 ×1/29 i 1 2 3 4 5 6 7 j 2~8 3~8 4~8 5~8 6~8 7~8 8~8 k 3~9= 7 4~9=6 5~9=5 6~9=4 7~9=3 8~9=2 9~9=1 4~9=6 5~9=5 6~9=4 7~9=3 8~9=2 9~9=1 5~9=5 6~9=4 7~9=3 8~9=2 9~9=1 6~9=4 7~9=3 8~9=2 9~9=1 7~9=3 8~9=2 9~9=1 8~9=2 9~9=1 9~9=1 再推，要且仅须 5 只小老鼠，就可检测出来，须要时间还是 10*24 小时。 那就要分六层了： 第一层：第一只小老鼠死在第 1 轮试验，第 2 轮试验，第 3 轮试验，.....，第 6 轮试验上； 第二层：在第一层的基础上，假设第一只小老鼠死在第 i 轮试验上，第二只小老鼠则是死在第 i+1, i+2, ...., 第 7 轮试验上； 第三层：在第二层的基础上，假设第二只小老鼠死在第 j 轮试验上，第三只小老鼠直至第 8 轮试验都 没有死； 第四层：在第三层的基础上，假设第三只小老鼠死在第 k 轮试验上，第四只小老鼠直至第 9 轮试验都 没有死； 第五层：在第四层的基础上，假设第四只小老鼠死在第 t 轮试验上，第五只小老鼠直至第 9 轮试验都 没有死； 求概率： for i = 1 to 6 for j = i+1 to 7 for k = j+1 to 8 for t = k+1 to 9 P =p + 1/2i * 1/2(j - i)* 1/2(k - j)* 1/2(t - k)*1/2(9 - t) 即：p = C94 ×1/29 i 1 2 3 4 5 6 j 2~7 3~7 4~7 5~7 6~7 7~7 6~8=3 7~8=2 8~8=1 7~8=2 8~8=1 8~8=1 7~9= 3 8~9= 2 9~9= 1 8~9= 2 9~9= 1 9~9= 1 k，t 3~8 = 6 4~8=5 5~8=4 6~8=3 4~9= 6 5~9= 5 6~9= 4 7~9= 3 8~9= 2 9~9= 1 5~9= 5 6~9= 4 7~9= 3 8~9= 2 9~9= 1 6~9= 4 7~9= 3 8~9= 2 9~9= 1 7~9= 3 8~9= 2 4~8=5 5~8=4 6~8=3 7~8=2 8~8=1 5~9= 5 6~9= 4 7~9= 3 8~9= 2 9~9= 1 6~9= 4 7~9= 3 8~9= 2 9~9= 1 7~9= 3 8~9= 2 9~9= 1 8~9= 2 9~9= 1 9~9= 1 5~8=4 6~8=3 7~8=2 8~8=1 6~9= 4 7~9= 3 8~9= 2 9~9= 1 7~9= 3 8~9= 2 9~9= 1 8~9= 2 9~9= 1 9~9= 1 8~9= 2 9~9= 1 9~9= 1 9~9= 1 7~8=2 8~8=1 9~9= 1 8~9= 2 9~9= 1 9~9= 1 再推，要且仅须 6 只小老鼠，就可检测出来，须要时间还是 10*24 小时。 那就要分六层了： 第一层：第一只小老鼠死在第 1 轮试验，第 2 轮试验，第 3 轮试验，.....，第 5 轮试验上； 第二层：在第一层的基础上，假设第一只小老鼠死在第 i 轮试验，第二只小老鼠则是死在第 i+1, i+2, ...., 第 6 轮试验上； 第三层：在第二层的基础上，假设第二只小老鼠死在第 j 轮试验，第三只小老鼠直至第 7 轮试验都没 有死； 第四层：在第三层的基础上，假设第三只小老鼠死在第 k 轮试验，第四只小老鼠直至第 8 轮试验都没 有死； 第五层：在第四层的基础上，假设第四只小老鼠死在第 t 轮试验，第五只小老鼠直至第 9 轮试验都没 有死； 第六层：在第五层的基础上，假设第五只小老鼠死在第 s 轮试验，第六只小老鼠直至第 9 轮试验都没 有死； 求概率： for i = 1 to 5 for j = i+1 to 6 for k = j+1 to 7 for t = k+1 to 8 for s = t+1 to 9 P = 1/2i * 1/2(j - i)* 1/2(k - j)* 1/2(t - k)*1/2(s - t)*1/2(9 -s 即：p = C95 ×1/29 归纳总结：for i = 1 to n- 4 for j = i+1 to n - 3 for k = j+1 to n - 2 for t = k+1 to n - 1 for s = t+1 to n 总的循环次数 = Cn5 这是一个接力赛的组合问题，即共有 n 关，由 5 个人来接力完成过 n 关。问有多少种接力情形。 举例如下： 假定整个有 16(=24)瓶矿泉水时，那么 要且仅要的小老鼠个数 发生的概率 1 即：p = C30 ×1/23 = 1*1/23 2 即：p = C31 ×1/23 = 3*1/23 3 即：p = C32 ×1/23 = (2+1)*1/23 4 即：p = C33 ×1/23 = 1*1/23 于是，平均须要 1*1*1/23 + 2*3*1/23 + 3*3*1/23+ 4*1*1/23 = 2.5 个小老鼠，才能从 16 瓶找中挑拣出哪 一瓶是有毒的。 假定整个有 32(=25)瓶矿泉水时，那么 要且仅要的小老鼠个数 概率 1 即：p = C40 ×1/24 = 1*1/24 2 即：p = C41 ×1/24 = 4*1/24 3 即：p = C42 ×1/24 = (3+2+1)*1/24 4 即：p = C44 ×1/24 = ((2+1)+1)*1/24 5 即：p = C44 ×1/24 = 1*1/24 于是，平均须要 1*1*1/23 + 2*4*1/23 + 3*6*1/23+ 4*4*1/23 + 5*1*1/23= 3 个小老鼠，才能从 32 瓶找中 挑拣出哪一瓶是有毒的。 假定整个有 64(=26)瓶矿泉水时，那么 要且仅要的小老鼠个数 概率 1 即：p = C50 ×1/25 = 1*1/25 2 即：p = C51 ×1/25 = 5*1/25 3 即：p = C52 ×1/25 = (4+3+2+1)*1/25 4 即：p = C53 ×1/25 = ((3+2+1)+(2+1)+1)*1/25 5 即：p = C54 ×1/25 = 5*1/25 6 即：p = C55 ×1/25 = 1*1/25 于是，平均须要 1*1*1/23 + 2*5*1/23 + 3*10*1/23+ 4*10*1/23 + 5*5*1/23 + 6*1*1/23= 3.5 个小老鼠，才能 从 64 瓶找中挑拣出哪一瓶是有毒的。 假定整个有 128(=27)瓶矿泉水时，那么 要且仅要的小老鼠个数 概率 1 即：p = C60 ×1/26 = 1*1/26 2 即：p = C61 ×1/26 = 6*1/26 3 即：p = C62 ×1/26 = (5 4 即：p = C63 ×1/26 = ([4+3+2+1] + + 4+ 3 + 2 + 1)*1/26 [3+2+1] + [2+1] + [(2+1)+1] + 1)*1/26 5 即：p = C64 ×1/26 = ( [(3+2+1)+(2+1) +1] + [1] )*1/26 6 即：p = C65 ×1/26 = 6*1/26 7 即：p = C66 ×1/26 = 1*1/26 于是，平均须要 1*1*1/23 + 2*6*1/23 + 3*15*1/23+ 4*20*1/23 + 5*15*1/23 + 6*6*1/23+ 7*1*1/23=4 个小 老鼠，才能从 128 瓶找中挑拣出哪一瓶是有毒的。 假定整个有 256(=28)瓶矿泉水时，那么 要且仅要的小老鼠个数 概率 1 即：p = C70 ×1/27 = 1*1/27 = 2 即：p = C71 ×1/27 = 3 即：p = C72 ×1/27 = (6+5+4 +3+2+1)*1/27= 21 4 即：p = C73 ×1/27 = ([5+4+3+2+1] + 1 7*1/27 = 7 [4+3+2+1] + [3+2+1] + [2+1] + [1])*1/27= 35 5 即：p = C74 ×1/27 = ( [(4+3+2+1)+(3+2+1) +(2+1) +1] + [(3+2+1) +(2+1) +1] + [(2+1) + 1] + [1 ] ) * 1/27 = 35 6 即：p = C75 ×1/27 = ([(3+2+1) + (2+1) + 1 + (2+1) + 1 [(2+1) + 1 7 即：p = C76 ×1/27 = 7*1/27= 7 8 即：p = C77 ×1/27 = 1*1/27 = + 1] + +1 ] + [1]) *1/27 = 21 1 于 是 ， 平 均 须 要 1*1*1/23 + 2*7*1/23 + 3*21*1/23+ 4*35*1/23 + 5*35*1/23 + 6*21*1/23+ 7*7*1/23+ 8*1*1/23 = 4.5 个小老鼠，才能从 256 瓶找中挑拣出哪一瓶是有毒的。 归纳与推广： 假定小老鼠会有三个状态：中毒死亡，打颤，正常。每个状态等概率发生，那么， 第 i 轮试验 1 2 3 4 5 6 7 8 第 i 轮试验后 2/3 (2/3)2 (2/3)3 (2/3)4 (2/3)5 (2/3)6 (2/3)7 (2/3)8 (2/3)6×1/3 (2/3)7×1/3 还没死的概率 死在第 i 轮试 1/3 2/3×1/3 (2/3)2×1/3 (2/3)3×1/3 (2/3)4×1/3 (2/3)5×1/3 验的概率 要且仅须 3 只小老鼠，就可检测出来，须要时间还是 10*24 小时。 那就要分三层了： 第一层：第一只小老鼠死在第 1 轮试验，第 2 轮试验，第 3 轮试验，.....，第 6 轮试验上； 第二层：在第一层的基础上，假设第一只小老鼠死在第 i 轮实验上，第二只小老鼠则可能是是死在第 i+1, i+2, ...., 第 7 轮试验上； 第三层：在第二层的基础上，假设第二只小老鼠死在第 j 轮实验上，第三只小老鼠直至第 7 轮试验都 没有死； 求概率： for i = 1 to 6 for j = i+1 to 7 p = p + (2/3)i -1×1/3 × (2/3)(j - i) -1 ×1/3 × (2/3)(7 - j) 即：p = C72 ×(2/3)5×(1/3)2 含义是：每轮试验都是彼此相互独立的，依次进行了 7 轮试验，7 轮实验中，任选两轮，发生了小老 鼠死亡，剩下的五轮自然是都没有发生小老鼠死亡。 由此引出汉明码(Hamming coding) 设传输中，有 15 bits 的数据位，再加上 1 bit 的奇偶校检位，共 16 位。假设通过奇偶校检，感知到了 有一位发生改变。接下来的问题是：到底是哪一位发生了改变？ 同样的道理，该问题是要对 16 个位置，挑拣出到底是哪一个位置发生了改变。首先是对 16 个位置进 行一分为二，递归下去，得到如下的情形： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 第一层 第二层 第三层 第四层 于是传输中，还要增设 4 bits 的层校检位。原始数据在传输或者存储前，先生成奇偶校检位，然后再 生成层校检位。传输给接收方。接收者收到 20 bits 的数据后，先对前 15 bits 的数据位，计算奇偶校检 值，然后和接收到的第 16 bit（奇偶校检位）比较，如果相同，则说明整个 16 bits 的数据传输完全正 确。 如果不相同，则说明前面 16 bits 中有且仅有某个位置的 bit 值在传输中因为干扰发生了改变。接下来 就使用层校检来确定到底是哪一位发生了改变。 接收者使用接收到的前 16 bits 数据，计算层校检位，共 4 层，因此有四个 bits，设为 c1, c2, c3, c4 如果计算出的 c1 接收到的 c1 改变位 {9,10,11,12,13,14,15,16} 否则，改变位 {1,2,3,4,5,6,7,8} 如果计算出的 c2 接收到的 c2 改变位 {5,6,7,8,13,14,15,16} 否则，改变位 {1,2,3,4,9,10,11,12} 如果计算出的 c3 接收到的 c3 改变位 {3,4,7,8,11,12,15,16} 否则，改变位 {1,2,5,6,9,10,13,14} 如果计算出的 c4 接收到的 c4 改变位 {2,4,6,8,10,12,14,16} 否则，改变位 {1,3,5,7,9,11,13,15} 再对四个改变位的集合做交运算，就得出了到底是哪一位发生了改变。如是它的值是 0 ，就对它纠错， 改成 1。如是它的值是 1 ，就对它纠错，改成 0。 举例：四层检测发现：计算出的 c1 = 接收到的 c1，计算出的 c2 = 接收到的 c2，计算出的 c3 = 接收到 的 c3，计算出的 c4 = 接收到的 c4， 那么，改变位 = {1,2,3,4,5,6,7,8} {1,2,3,4,9,10,11,12} {1,2,5,6,9,10,13,14} {1,3,5,7,9,11,13,15} = {1} 即第 1 位发生改变。因此，总是会认为有一位发生改变。 对四层检测中，我们可以发现： 四层中都出现的有 1 个(C44)：第 16 位； 出现在三层中的有 4 个(C43)：第 8,12,14,15 位； 出现在二层中的有 6 个(C42)：第 4,6,7,10,11,13 位； 出现在一层中的有 4 个(C41)：第 2,3,5,9 位； 四层中都不出现的有 1 个(C40)：第 1 位； 注意：假设有两个位发生了改变时，例如，第 2 和第 3 位发生了改变。按照层校检方法：在三、四层 报错。于是{1,2,3,4,5,6,7,8} {1,2,3,4,9,10,11,12} {3,4,7,8,11,12,15,16} {2,4,6,8,10,12,14,16} = {4} 即检测出第 4 位发生改变，而实际是第 2 和第 3 位发生改变。这时，层检测法变得毫无意义。 也就是说，该方法的前提就是：有且仅有一个位发生了改变，该方法所起的作用是定位这个改变到底 发生在哪一个位置。尽管真实情况是可能有多个位发生了改变，但该方法总是会判定出某一位发生改 变，而且与真实的不相符。 于是，使用该方法之前，先要得出有且仅有一个位发生了改变的这一结论，然后才可使用该方法来解 决“到底是哪一位发生了改变？”这一问题。