前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >纠错码与魔术(三)——汉明纠错码魔术初步

纠错码与魔术(三)——汉明纠错码魔术初步

作者头像
magic2728
发布2023-01-30 16:06:21
4690
发布2023-01-30 16:06:21
举报
文章被收录于专栏:MatheMagicianMatheMagician

早点关注我,精彩不错过!

本系列前面两篇已经介绍了纠错码的基本原理和在魔术中的应用和一些魔术例子,相关内容请戳:

纠错码与魔术(二)——魔术《矩阵感应》等

纠错码与魔术(一)——纠错码与汉明码简介

在mathematical card magic书中,还有很多基于纠错编码中重要的一类——hamming编码的设计精良的效果,在此和大家分享。

A horse of a different color

视频1 A horse of a different color

这个魔术是用重复加奇偶校验,并不是严格的hamming编码,不然前面4位有3位都是自由位,那还怎么玩?其编码规律是(a, b, x, a, b, a + b)其中,a, b, x是bool变量,其中加法是不进位的逻辑加法,也就是异或运算,当然也可以叫模2加法。而这个bool量可以用比如红黑,奇偶,是否大牌等等方式来定义,这里我们用的是最显然的红黑。显然,这里其实一共只有3bit的有效关注信息,因为后面的3位都可以看作是校验。而观众此时连你关注的是红黑都不知道,更别提去发现这隐藏的校验规律了。这规律使得,任何对红黑颜色的改变,都会自动在结果里编码出信息,进而解码出变化的是哪一张。具体怎么做呢?

首先,如果观众进行完变化以后,发现后面三个校验都没有问题,显然只有一个可能,那就是变化的是x,解码结束;如果有错误,如果是单个错误,显然那改变的也就是这个校验位1和2,或者是6上,因为只有他们才不会有连带影响;如果是两个错误,则改变必然发生在4,5位,其中一个错误一定在第6位,剩下4,5哪个被检测不一致,问题就在对应的1,2上。

于是,执行解码的时候,也可以直接看1,4和2,5两组牌是否完全一致开始,一致则根据第6张是否正确判断是没改还是第6,不一致则再看6是否正确决定不一致的两张中到底是哪一张改变。这些解码方法的不同本质上都是线性方程组求解过程消元过程的区别,并没有本质区别,怎么方便记忆,快,就怎么来。

这种通过暗含的线性关系构造的结构,使得在万全不知情的情况下,观众就把重要的信息给透露了出来,魔术便来了。

魔术表演方面,后面3张牌是交给另一个观众,也就是托完成的。只要这一点可以接受,整个魔术就是天衣无缝的。不过倒是可以通过选牌过程的软限制,使得两次编码的颜色自动相等,而托的那一次选正确的,观众自己选的唯一一次自由的颜色就让他自由吧!如果你仔细观察还可以发现,选择过程是可以托先选,观众再选的,只要要求观众选的不能都黑而且托选牌摆放位置可以调节即可,因为此时托的三张颜色组合必然是2红1黑,0红3黑。

但是,这个托的选择还是很碍眼,那能不能够完全不要托,或者托干的事情,看起来更隐蔽一点?请看下面的魔术。

Give any five cards

视频2 Given any five cards

我们来把所有的(a, b, a, b, a + b)的共5个位中所有可能的4种情况里,1的可能数量数一下会发现,恰好是{0,3,4}个(00000,01011或10101,11110),而这5位里剩下的就是0了,所以做一个减法函数在上面这个集合上,得到的值域结果是{1,2,5}。然后,这两个集合居然恰好是0:5集合的相互对立事件!也就是说,无论观众选出来的牌到底有几个表示1的红色,都存在一个排列,使得上面纠错编码的暗含等式成立,当数量是1,2,5时,那就让黑色代表1就好了,而告诉魔术师到底谁代表谁,这1bit的信息,岂不是易如反掌!

而托要做的,硬生生从尴尬地选出三张特定颜色的牌,变成了不经意地排列了一下5张牌的顺序,并用左右手示意或者从左往右还是反过来的方式而已!

仅仅付出了必须要改变的代价,就能够获得如此随意的自由度,只需要的校验码(parity code)随编码映射方式的不同而左右摇摆,太神了!

其实再用对称角度一想,这里5张2颜色选项的对称组合只有5vs0,4vs1,3vs2这么3种情况。需要构造前4个位置的copy语言成立,其解除了3vs2有两种对称的,其余还都是一致的。因此所有的判断都落脚在是否破坏了copy的前4bit,如果没有,则一定是最后一位被改变,若是不需要判断是否改变,那直接就能做了,如果需要,那也只是需要1bit的红黑分别代表0还是1的信息罢了。

这个作品里,这1bit信息我们采用了复合编码的方法纳入了。在编码时,保证同颜色的子序列都是数值递增(红1黑0)或递减的(红0黑1)。于是当发生转换以后,5vs0的变成4vs1不影响;4vs1的变成5vs0仍然可以判别一个长为4单调序列中插入一张的情况,变成3vs2则二者不一致取长的保持;3vs2的如果变成4vs1则是长为3的单调序列插入一张,而2vs3则不一致的看长为2的,一致则直接一致,这里的3vs2编码和前面4vs1变来的竟然完全兼容。于是根据以上判断,递增为红1黑0,否则相反。之所以这么设计,是因为这个编码的内容可以对颜色本身编码的校验码具有不变性,故二者可以互相独立编码,十分方便了,这也是我对这个魔术的一点小改进和贡献。

值得一提的是,在看原书《Mathematical Card Tricks》的同名魔术的时候,我并没有仔细研读那里关于颜色递增递减来编码红黑编码方法的讨论,你要知道对于想快点学会这个魔术效果的爱好者来说看那些繁复的说明是多么费脑筋。但是当我真的表演的时候,我竟然顺着这个思路推导出以上的策略,回头看到书里的描述,竟然一模一样!

我惊叹于这世间的数学巧合,让我如此不能自拔。

下一篇,我们会继续围绕汉明码的魔术应用给大家讲解,魔术内容先睹为快:

视频3 Multiple Persenality

视频4 A Small Ternary Linear Code

我们是谁:

MatheMagician,中文“数学魔术师”,原指用数学设计魔术的魔术师和数学家。既取其用数学来变魔术的本义,也取像魔术一样玩数学的意思。文章内容涵盖互联网,计算机,统计,算法,NLP等前沿的数学及应用领域;也包括魔术思想,流程鉴赏等魔术内容;以及结合二者的数学魔术分享,还有一些思辨性的谈天说地的随笔。希望你能和我一起,既能感性思考又保持理性思维,享受人生乐趣。欢迎扫码关注和在文末或公众号留言与我交流!

扫描二维码

关注更多精彩

纠错码与魔术(二)——魔术《矩阵感应》等

破解魔术的秘密(四)——前移原理介绍和案例分享

你真的分得清“前后左右”和“东西南北”吗?(四)——无处不在的相对方位

编码通信与魔术初步(七)——二进制编码经典魔术《街头猜数字》

知道魔术的秘密很了不起吗?

点击阅读原文,往期精彩不错过!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-11-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 MatheMagician 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档