密码读心术&纠错码是什么工作原理? - 基础数学 我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

查看: 461|回复: 0

[数学综合] 密码读心术&纠错码是什么工作原理?

[复制链接]

640

主题

654

帖子

3242

积分

版主

Rank: 7Rank: 7Rank: 7

积分
3242
发表于 2016-9-29 13:44:25 | 显示全部楼层 |阅读模式
这是一个读心术游戏,要玩这个游戏,首先需要36枚硬币。把其中25枚硬币交到一位没有疑心的朋友手上,请对方把所有硬币摆放放在一个5×5的网格中,正反面随机摆放。最终的结果可能如下表所示。
360截图-1192751343.jpg
此时对对方说:“一分钟之内,我会请你翻转其中的一枚硬币,正面反面随你。然后我会施展读心术,指出你翻动的那枚硬币。你猜的没错,我的确有可能记下了所有硬币的摆放顺序,好吧,让我们弄得再复杂一点,试试更大的网格。”
随后,你拿出更多硬币,以看似随机的方式添加新的一行和新的一列,使现在的网格变成6×6=36的......其实,整个添加过程毫不随机。你现在要做的就是数出每一行每一列中各有多少个反面硬币。如果第一列中的反面硬币数量为偶数(在这个案例中0也被视为偶数),便在这一列的末端再添加一个正面硬币。
依此类推,把每行每列中的反面硬币数量都变为偶数。此时就只剩右下角还有个空位,同样,还是根据它所在的列中的反面硬币数量来决定这枚硬币的正反。有趣的是,这样同时也会使该硬币所在行的反面硬币数量完成配对(维持偶数或变为偶数)。你能证明出这一点永远正确吗?技巧就是要发现在5×5网格中,该数字能告诉你反面硬币的数量是奇数还是偶数。
总而言之,此时的网格会变成下表所示。 360截图-1192966796.jpg 现在,你可以来变这个魔术了。转过身去,让你的朋友翻转其中的一枚硬币,使正面变反面,或反面变正面。翻好后,你转过身来。聚精会神盯着网格,对他说你将要施展读心术,然后指出被翻转的那枚硬币。
当然,事实上你根本就不是在对你朋友施展读心术。你只不过重新察看原来的那个5×5的网格,数出每行每列中正反面硬币的数量。然后注意其中的反面硬币的数量是奇数还是偶数,再把这些结果与后来添加的硬币进行比照,因为这将暗示出每一栏中的反面硬币的成对状况。此时,你的朋友已经翻转了原来5×5网格中的一枚硬币,那么,网格中就会有一行和一列与你后来添加的硬币指示的信息不符。找出此行和此列的交汇点,你便能找到那枚被翻转的硬币。
下表即翻转后的模样,现在你应该能找到哪一枚是被翻转的硬币了吧。
5×5方格第一列中含有偶数个反面硬币,而你后来添加在此列下方的硬币显示的也是反面,这就说明原本这一列中的反面硬币数量应为奇数。因此,被翻转的那枚硬币就在这列中。 360截图-1192982187.jpg
现在再来看每一行,其中第二行也出现了不一致的地方:该行中的反面硬币数量为奇数,而你留下的”检测位“却显示原本该行中的反面硬币数量应为偶数。至此,你已经读出了你朋友的心,对他说:“你翻转的硬币在第一列,第二行。”话音刚落,四周随即响起由衷的赞叹声和掌声。
如果你朋友翻转的那枚硬币是你后来添加进去的,结果又会怎么样呢?这也没问题。此时,右下角的那枚硬币便会指示出到底是最后一行还是最后一列出现了不一致的情况。如果是最后一行不匹配,你就知道被翻转的那枚硬币位于最后一行,此时,再检查哪一列出现不一致的情况即可。而如果检查下来是最后一列出现不一致的情况,那么被翻转的硬币刚好就是右下角那一枚。
依然如下表所示,但是其中的一枚新添加的硬币已被你的朋友翻转过。你能找出它吗?
答案为右上角那一枚。右下角的正面硬币说明第六列的反面硬币数量应为偶数——但此时却为奇数 。然后再来检查每一行。第一行就不一致,因为第六列的正面硬币表示前五个的反面硬币数量应为偶数,但实际上却为奇数,因此可能确认,右上角这枚硬币就是被翻转的那枚。 360截图-1192997578.jpg
以上便是纠错码的工作原理,计算机通过它来纠正讯息传输过程中可能出现的错误。将正反面的硬币分别替换成0和1,转眼之间这些网格就变成数码讯息了。比如,我们最初使用的那个5×5的网格中每一列都可看成一个波德码,通过上述方式,整个网格就变成了一段由5个符号所组成的讯息。而新加的行与列则被视为计算机的纠错系统。
举个例子,假如我们要将酷玩第3张专辑封面上的加密讯息发送出去的话,也可以使用一种类似的技巧来防止这个5×4的网格中的讯息出错。下表即专辑封面中包含的讯息,我们在此将彩色方块替换为1,将缝隙替换为0。 360截图-1193011406.jpg 然后,我们在此基础上新增由0和1组成的一行一列,用来表示原来网格中每一行每一列中的1的数量为偶数还是奇数。 360截图-1193026421.jpg
然后,假设在这段信息的传输过程中出现了一个错误,其中的一个数字被更改,那么平面设计师接收到的讯息如表4-12所示。 360截图-1193056437.jpg 借助于最后一行一列的纠错位,平面设计师便能查找出错误所在。在这里,第二行和第三列出现了不一致的情况。
像这样的纠错方法被应用在各行各业之中,从CD制作到卫星通讯等等,不一而足。我们都有过接电话时无法听清对方声音的经历。计算机之间在交流的过程中也会遇到同样的问题,但是,通过使用聪明的数学方法,我们已经成功地想出编码数据的方法,以摆脱此类干扰。这也正是NASA在“旅行者2号”宇宙飞船传回第一幅土星图片时做的事情。通过对纠错码的使用,他们得以将一幅失真的图片转换为一张无比清晰的照片。

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc

关于我们 | 网站地图 | 我爱数学网 ( 沪ICP备16005585号-3  

GMT+8, 2019-9-16 16:18 征信网

快速回复 返回顶部 返回列表