刘谦春晚纸牌魔术背后的数学—海明码原理简介

2024-02-11 10:12

本文主要是介绍刘谦春晚纸牌魔术背后的数学—海明码原理简介,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在昨天2024年的春晚舞台上,魔术大师刘谦以一场令人拍案叫绝的纸牌魔术再度震撼全场。他巧妙地利用了数学原理,精准无误地让观众“随机”选择的纸牌完成了配对,尤其是令人忍俊不禁的是主持人尼格买提的纸牌却没有如愿配对,小尼碎了的话题也冲上了今天大年初一的热搜。然而,在这看似神秘莫测的魔术背后,却隐藏着一种在信息科学领域中广泛使用的纠错编码技术,小尼的操作有误,也就让他最后的结果与其他亲身参与的观众不一样了,从某种程度上讲参与者手上的最后半张牌就是一位校验码,查看校验码也就能知道你之前的操作是不是正确。那么现在,我们就从这场精彩的纸牌魔术出发,一同探索海明码等纠错码背后的原理。

  • 刘谦魔术背后的约瑟夫问题

刘谦魔术的前几步其实都是个看似建立纸牌随机顺序的过程(但其实还是有序的哈,只是男性与女性的卡牌顺序可能不同),而最后一步“好运留下来烦恼丢出去”恰恰是一个约瑟夫问题,这个弃牌过程保证了无论男女都是留下编号为1的牌,也就正好是能和之前保留半张牌的配对牌。因此探索这个问题,我们先简要介绍一下约瑟夫问题。

约瑟夫问题(Josephus Problem)是一个著名的理论和计算机科学中的数学难题,源于一个关于罗马历史学家弗拉维奥·约瑟夫斯的传说。故事中,约瑟夫和其他一些人被围困,他们决定通过一种自裁的方式减少人数以求得部分人的生存:他们站成一个圈,并从某个人开始报数,数到特定数值(比如每数到第M个人)时,这个人会被杀掉,然后从下一个人继续报数,直到最后只剩下一个人为止。在现代数学和算法领域中,约瑟夫问题通常形式化为以下描述:

设有N个人排成一个圆圈,从某个位置(例如编号为1的人)开始按顺时针方向报数,每当数到第M个人时,该人会被移出圆圈。接着从下一个未移除的人继续从1开始报数,直至圆圈中只剩余最后一个人。这个问题要求确定的是在给定N和M的情况下,最后幸存下来的人的初始编号是多少。解决约瑟夫问题一般采用递归或迭代的方法。

在刘谦的魔术中,每一张纸牌就如同一个比特位,通过巧妙的设计和预设规则(即海明码的构造原则),使得无论观众如何随机选择,魔术师都能准确判断出原始的信息内容(即选中的纸牌),而主持人出现的操作失误,也让他没有得到预期中的结果,所以从这个角度上看,这个魔术本质上讲其实还是可以等价为一个纠错问题,也就如何在校验位上把数据流中的错误体现出来。

  • 海明码简介

在计算机课程,尤其是纠错原理中,我们第一个接触的机制大概就是奇偶校验位,也就是在一段数据流的最后设计一个校验位,如果整个信息流中有奇数个1,那么校验位就是1,如果有偶数个1那么校验位就是0。

海明码是一种基于奇偶校验机制的,用于检测和纠正单个比特错误的线性纠错码,由美国数学家理查德·卫斯里·海明于1950年提出。如同刘谦在表演前对纸牌进行精心设计与安排,海明码通过对数据位增加冗余信息的方式,使得每个数据位都与其他几个数据位之间存在特定的关系,从而能在传输过程中发现并修正单一比特的错误。

我们知道之前很多如串口数据、网络传输包一旦校验失败,则整包重传,而海明码则不需要重传,他可以在添加校验位的情况下,自动找到错误码位置并更正,避免了整包重传的资源浪费情况发生。

而接下来我们就可以回答校验位个数的问题了,由于以16位数据为例,在已知只有一位数据错的情况下,校验位需要表示的情况共有2^4=16种,也就是需要4位表示,而如果是1024位数据,那么需要表示2^10=1024种情况,也就是10位校验位。那么拓展一下如果有两位错呢?那么这种情况下由于两位数据是任意的,从概率上讲是独立事件,校验位翻倍即可。

  • 海明码工作原理

1.基于偶校验设计

海明码一般使用偶校验,也就是当参与校验的校验位1的个数为奇数,则校验位为1;反之1的个数为偶数时,则校验位为0。

例子:数据位1111的 偶校验就是 11110

一般来说单纯的我校验只能检测一位数据是否有错,但无法纠错。

如我们刚刚所说,我们的校验位所能表示的情况数量必须大于数据流总长度,也就是2^校验位数 >= 校验位数 + 数据位数 +1

以数据位取4为例,代入可得校验位等于3

2.校验位与数据位的设置

在海明码的数据流中凡是2^n(其中n为正整数)的位置都是校验位,其余都是数据位,以7个bit的数据流为例,如下图:

位置

1

2

3

4

5

6

7

用途

校验位

校验位

数据位

校验位

数据位

数据位

数据位

3.确定校验位的校验范围

接下来需要确认校验位要用来校验哪些数据位。

首先把所有位置的二进制码表示写出来,左补齐至校验位个数,如本例中校验位为3,那么左补0使二进制码长度满3位。

位置

1

2

3

4

5

6

7

用途

校验位

校验位

数据位

校验位

数据位

数据位

数据位

所在位置二进制码

001

010

011

100

101

110

111

其中校验位左边的0是*表示,也就是可以指代任意多个0,右边的0用?表示,即只能代表一个0。如下:

位置

1

2

3

4

5

6

7

用途

校验位

校验位

数据位

校验位

数据位

数据位

数据位

所在位置二进制码

001

010

011

100

101

110

111

校验位通配符表示

*1

*1?

1??

4.确定校验矩阵

接下来将所有数据位按照上述匹配规则进行分组,(其中?代表一位,*代表任意位)。

位置

1

2

3

4

5

6

7

用途

校验位

校验位

数据位

校验位

数据位

数据位

数据位

所在位置二进制码

001

010

011

100

101

110

111

校验位通配符表示

*1

*1?

匹配*1与*1?;即1、2两组

1??

匹配*1与1??;即1、4两组

匹配*1?与1??;即1、4两组

匹配*1、*1?与1??即匹配所有组

纵向的匹配分组如下:

校验位位置

1

2

4

校验位通配符表示

*1

*1?

1??

匹配结果

001(1)

010(2)

100(4)

011(3)

011(3)

101(5)

101(5)

110(6)

110(6)

111(7)

111(7)

111(7)

因此我们可以确定

校验位1 负责校验1、3、5、7四位

校验位2 负责校验2、3、6、7四位

校验位4 负责校验4、5、6、7四位

假如要传递的数据为1110,那么如果进行偶校验,那么这段汉明码应该为1111110

5.纠错过程

我们刚刚也提到了1、2、4三个校验位将全部数据分为三组,那么不论哪一位出错,都可以得校验失败的结论,这个并不难理解。而海明码的纠错原理如下:

位置

1

2

3

4

5

6

7

用途

校验位

校验位

数据位

校验位

数据位

数据位

数据位

所在位置二进制码

001

010

011

100

101

110

111

校验位通配符表示

*1

*1?

匹配*1与*1?;即1、2两组

1??

匹配*1与1??;即1、4两组

匹配*1?与1??;即1、4两组

匹配*1、*1?与1??即匹配所有组

所属分组

1

2

1、2

4

1、4

2、4

1、2、4

然后你会发现有以下几种情况:

  • 三组校验全错:首先第7位属于三个组,那么如果三个组都校验失败则可知是第7位错。
  • 如果单独一组错这时可知是校验位出错,因为只有校验位自己单独一组。
  • 如果两组同时出错,则是两组交叉地带的位置出错,如1、2组都校验错,则是代表第3位即属于1、2组共同校验的位置出错。

而且海明码还有一个快速确定错误位置的算法,

1.分别对每个组校验,通过的记为0,出错的记为1.

2、将校验结果按照组别从大到小排列起来,得到一串1和0的组合。

假如我们刚刚接收的海明码序列为1111111,那么得到的校验结果从大到小排除就是111,这也就对应了出错位置为111二进制码所对应的位置即第7位,

春晚舞台上,刘谦的纸牌魔术吸引了无数观众的目光。他以其出神入化的手法,将普通的纸牌演绎得栩栩如生,仿佛拥有了生命的魔力。这一切的背后,不仅体现了魔术师本人精湛的技艺,更是科技与艺术完美结合的生动展现。海明码的精妙原理,为这场魔术增添了更多的科技色彩,让人们在欣赏艺术的同时,也领略到了科技的神奇魅力。

在这个充满未知的世界里,无论是魔术舞台还是科研前线,人类智慧的火花都将永不熄灭。科技的发展离不开人们的探索与创新,正是这些火花,照亮了我们前行的道路。而对于编码技术来说,未来的创新将不仅仅局限于技术的层面,更将体现在如何更好地服务于人类社会,为信息传输带来更多可能性。

总之,随着科技的发展,未来的编码技术将会更加先进,为我们的生活带来更多便利。而在这一过程中,人类智慧的火花将继续照亮前行的道路,推动科技与艺术的交融,为我们的世界增添更多美好。无论是魔术舞台还是科研前线,我们都将携手共进,不断创新,以迎接更美好的未来。

这篇关于刘谦春晚纸牌魔术背后的数学—海明码原理简介的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699534

相关文章

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

业务协同平台--简介

一、使用场景         1.多个系统统一在业务协同平台定义协同策略,由业务协同平台代替人工完成一系列的单据录入         2.同时业务协同平台将执行任务推送给pda、pad等执行终端,通知各人员、设备进行作业执行         3.作业过程中,可设置完成时间预警、作业节点通知,时刻了解作业进程         4.做完再给你做过程分析,给出优化建议         就问你这一套下

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit