您当前的位置:华夏生活网行业资讯正文

信息激流中的编码拾遗

2020-03-31 06:00:57  阅读:5538+ 作者:责任编辑。陈微竹0371

我是一个无神论者,没有理由假定,在数学,物理和化学之外存在任何真理

——弗朗西斯·柯林斯

进制是人类所能得到的最简单的数字系统,只有两个数字:和1。

这代表了一个比特bit,比特是信息量的最小单位——就跟定一宇宙最小尺度的普朗克长度一样,是构成世界最基础的元素。

▲ 蓝色是相对论量子力学的贡献,红色来自广义相对论——两种理论是不相容的,在两者的“交界处”,最小尺度的普朗克长度,普朗克能量和普朗克质量于是被定义出来。

我喜欢类比,但类比的事物一定要足够深刻,才能获取新的认知。

比如弦论物理学家大栗博司,就把电磁学理论类比为金融市场里的货币,于是电场与汇率,磁场与利率产生了联系,并推导出了金本位制与希格斯波色子之间的奇妙联系。

比特的世界里,同样存在着奇妙的联系和发现——bit是自然观在人类心灵中存在的最纯粹的事物之一,它是真实的,具备崇高的抽象品质。它对于现实世界而言,就像音乐对于空气中的一千种噪音有一样的意义。

1

如前文《「编码之美」布莱叶指尖上的世界》所述,二进制数并不是传达信息的唯一方法:字母,单词,莫尔斯码,阿羽依盲文,巴比尔编码,布莱叶盲文,都可拿来表达信息。

《刷新三观的起名学》更是例举了伊始于熊崎健翁天马行空的编码方式,让命名学从简答占卜的龙马负图,神龟贡书逐步发展为一门无所不包的玄学。

例举的这些复杂信息系统,都是建立在比特洪流之上的。

比特所传递的信息量极少,人和小于1bit的内容根本算不上是信息。由于比特是最小的信息量单位,因此复杂的信息就可以用多个比特来表达。

《长安十二时辰》当中,望楼和望楼之间,时不时出现的信号板传递的加密信息就是多个比特的组成的,加密的信息通过密码本,就能找到对应的话术。

而在美国浪漫主义诗人亨利·沃兹沃斯·朗费罗笔下,则描写了美国版本的望楼:

“保罗·里威尔的朋友有两盏提灯,如果英国军队从陆路进犯,他会在教堂钟楼上挂起一盏提灯。如果英国军队从海路进军,他会将两盏提灯都在教堂的钟楼上挂起。”

这个编码系统里,如果用0表达熄灭,1表达亮灯,则四种组合表达了三种含义:

0 0 = 英军不会入侵

0 1 = 英军陆路入侵

1 0 = 英军陆路入侵

1 1 = 英军水路入侵

在后人看来,里威尔的编码方式非常老道。用通信理论的术语来说,他运用了“冗余”(Redundancy)来抵消“噪声”(Noise)的影响。噪声——通常用来表示影响通信效果的事物,在这个故事里,黑夜中暗淡的灯光很难让人远距离识别出点亮的是哪一盏提灯,这就是“噪声”,但由于冗余编码的存在,里威尔巧妙地消解了潜在可能产生严重后果的误会。

利用二进制的显著优点就在于,我们不必思考每一种可能的具体现实含义,就像布莱叶盲文那样,只需要简单的数字组合,就能够知道我们是否已经毫无遗漏地穷尽了每一种可能性。

如果你刚刚上手针孔相机,一定会对曝光速度的精确控制(倒易率计算)头疼不已。

幸好,高级胶片相机为简化摄影的难度,已经通过编码解决了这个棘手的问题。

如果你仔细观察35mm胶片,就会发现卷轴上的两排黑银交错的方格。

这些方格共有12个,用数字1-12进行标注,叫做DX编码。银色的方格代表值为1的比特,黑色的方格代表值为0的比特。按照惯例,方格1和7始终都是银色的。

这些比特位代表啥意思呢?

作为摄影发烧友的你,一定会非常熟悉ISO的含义。实际上,这代表着胶片对光的敏感程度,或称为胶片速度。胶片速度是由美国标准协会ASA制定的,共有24个等级。

对24个等级编码,需要几个比特位呢?简单的计算2x2x2x2x2=32告诉我们——最多5个。于是,我们只需要方格2,3,4,5,6——即第一行就可以将24种可能表达完毕。

除非你更喜欢完全手动控制的针孔相机,或者喜欢使用自带测光表设定曝光速度的高级胶片相机,绝大多数的胶片相机都在使用这些编码来自动工作。

在这些相机内部,跟胶卷卷轴接触的位置,共有六个金属触点,对应着胶片DX编码上1-6的六个位置。银色是由金属覆盖的——是导体,而涂有黑色颜料的方格——是绝缘体。

方格1是电流流入的地方,所以总有银色金属包裹,这个电流会流经2-6当中1个或多个方格,相机上2-6不同触点感受到电流,就可以识别出胶片的速度。比如4,5点位有电流,而2,3,6没有电流,这就从另一方面代表着胶片速度是250 ASA。

再深入一层,你还会发现DX编码设计更多的秘密:

对于廉价相机来说,并不需要设计6个触点——而是3个,只需要1-3的点位,就能够区分最常见的50,100,200,400四种不同的胶片。

这是编码设计的窍门之一——利用灵活和极具兼容性的简码实现了经济性。

对于高级相机来说,则会用到8-12的5个方格——用来对胶卷曝光和曝光宽容度进行编码。这些信息能够指导胶片的冲洗方式——黑白冲洗,彩色冲洗还是彩色幻灯片。

2

用产品代码UPC,是日常生活中最常见的编码了。

食品上,商品上,书本上,它无处不在。

不管是零售业结算,还是自动存货管理,它和计算机携手,成为了一项非常成功的发明,大大地提高了工作效率,降低了劳动强度。

有趣的是,UPC和我们此前介绍的编码一样——它也是二维码,尽管第一印象并不直观。

这种编码要比以前提及的编码都要复杂,因为它的设计采用了很多全新的有趣想法。

最简单的UPC码是由30条不同宽度的垂直黑色条纹组成的。条纹之间的间隔不同,条纹的下面还标有数字。

我们大家可以把UPC码看作两部分:条纹和间隔。

条纹有四种宽度:宽条纹的宽度分别是最细条纹宽度的2倍,3倍和4倍。

间隔有四种宽度:宽间隔的宽度分别是最小间隔宽度的2倍,3倍和4倍。

这样一来,UPC就可以被转译成一行比特位——与你的期望不同的一点是,UPC条形码下面的数字并不重要,因为识别数字需要更加高深的技术才能实现:OCR光学识别。

扫描仪看到的只是条形码的一个横断截面。

根据条纹或间隔的宽度,这个横断截面被解读为一系列的1和0:1-4个0形成了4种宽度的间隙,1-4个1形成了4种宽度的条纹。

虽然UPC只有30个条纹,但UPC码却可以表达远超30个比特位的信息——实际上,一共是113个比特位。

前三位通常是101——就是最左面的双排护线,用来帮助扫描仪定位。护线还有一个重要的作用——了解单个比特位的宽度。假如没有这个宽度的参考标准,那么所有的UPC码都要采用同样的大小规格来印刷——而这是不可能达成的。

护线后面是6组比特串,每串有7个比特位,这一共是42个比特位。

每一组都可以是数字0-9的编码。

然后是一个5比特位的中间护线——就跟左护线一样,这也是个固定格式——01010。

显然,这么做同样有更深的寓意——就跟左护线一样。的确,这是一个内置的检错码,如果扫描仪没有在该出现检错码的地方找到中间护线,该UPC码就无法被识别——这条线是用来预防条形码被有意篡改或无意被印错的一种方法。

中间护线后面仍然是42个6组的比特串,最后再连着一个101固定格式的右护线——当然,右护线也有自己的秘密——能轻松实现UPC的反向扫描(即便倒过来也能正确识别)。

然而,三条护线并非是条形码最有趣的部分。

绝对不能小看设计者的智慧。

同样是6组的7位编码,左右两侧对数字0-9的编码规则却完全不同。

以数字0为例:

左侧编码:0001101

右侧编码:1110010

看出端倪了吗?

再来看数字5:

左侧编码:0110001

右侧编码:1001110

这里有两个规律:

一个是显而易见的:即每个数字的左右编码都是互补的,称为补码,其中左码以0开头以1结束,右码以1开头以0结束。

找到第二个规律则要多花一些时间:左编码都只有奇数个1,而右编码都只有偶数个1——这就是为何需要7个一组的原因,因为这是另一种检查错误和一致性的方法。

还记得前文提到过的反向扫描么?如果扫描仪从左向右扫描首先遇到的是偶数个1的比特串,即偶校验,它就会知道,这个条形码是反的,于是调用偶校验的编码表解码,而后面的自然是奇校验了——应该调用另一张编码表来解码。

利用左右两个解码表,无论哪个方向,上面的条形码都可以被解读出来,12个数字是:

0 51000 01251 7

太令人失望了!这不就是条形码下面写着的数字么?

既然机器能够识别条形码,为何需要多此一举地把解码后的数字也印刷出来呢?

这是一个好问题。现实世界的复杂性就在于,什么都可能发生——当条形码被污损无法被识别时,至少还能让收银员手动输入这些数字——你一定遇到过这一幕。

至于数字所代表的具体含义,与编码设计的关系就不大了,比如第一位数字通常意味着商品的类别,比如0是票卷,2则意味着肉或农产品。

左码的五位通常代表公司的编码,右码的五位通常代表这家公司商品的编码。也就是说,条形码当中并不包含价格的信息——实时变动的价格是在商店的计算机数据库里面维护的。

表达0-9的10个数字,至少需要几个比特位?

答案是4个无疑,但条形码却使用了7个比特位来表达。

这样做的原因是增加了2项校验:补码校验,奇偶校验。

但这仍然不够——这就是被称为模校验(ModuleCheck)的技术。

条形码的最后一位数字是由模校验计算得到的——如果计算的值与最后一位不符,则计算机认为UPC码无效。

模校验位该如何计算呢?

最后一位数字是由前11位数字的计算得出的:前六位数字和的三倍与后五位数字之和取除以10的余数,再用10减掉这个余数。

这就是UPC码的第三种冗余校验。

最终,113个比特位,只编码了11个十进制数字,平均每个数字所用的恶比特位超过了10个。

这信息熵也太惨不忍睹了!

但细想起来,这个代价却是值得的——这是面向实用性的编码,从实际使用场景而来,当然不同于自然语言的编码的诉求——有限规则内最大限度提升信息熵。条形码正是采用了大量的冗余校验,才确保了它的可靠性和实用性。

3

使你从来就没听说过二维QR码,也可能已经使用很久了。

名片,海报,传单,横幅......如今,QR码被大范围的应用于各种各样的宣传材料中,它慢慢的变强大。

QR码可以看作是二维堆叠的比特信息(每一个比特位用黑色或白色小方块来表达),早期版本的二维条码系统仅测量21 x 21个比特位,能够表达4个字符的数据。

而当前最大版本则含有177 x 177个比特位,可以容纳1264个字符的ASCII文本或最多7089个数字。

但是,大多数的人们仍然不了解,它是如何工作的,能做什么——它实在是太复杂难懂了。

简单说来,二维码由一组正方形组成——其中一些正方形用于图像传感器定位自身(即三个角上的红色正方形),而其余的单元格包含版本和格式信息以及数据本身——当然,也少不了纠错编码。

两条橙色条纹显示了黑白相间的点(很像斑马线),这些条纹的作用是告诉扫描器黑白点的列和行的位置,它们以时间模式的名字命名。

二维码的紫色区域告诉扫描器将要编码的信息类型(例如网站URL、短信、vCard信息、字母数字、数字等)。

淡紫色区域代表二维码的版本号——它们用于版本号从6到40的二维码。如果二维码版本低于6,扫描仪不需要定义版本,因为它可以从二维码的各个区域进行计算。

右下角的粉色方块也是每一个二维码的恒定部分——它充当对齐标记。在一些较大的二维码中,可能会看到其中一些,因为扫描仪需要用更多的二维码来确保更精确的对齐。

你可能会想,除了上面提到的不能随便更改的部分,剩下的部分可以随意操作。

如果你这么想,你是对的也是错的。

信息能够最终靠多种办法来进行编码,不一样的编码可以在同一个二维码中使用:

数字(10比特表达3位数字)

字母(11比特表达2个字符,但不能存储小写字母)

字节(8个比特表达一个字节)

汉字(13个比特表达一个汉字)

二维码的剩余部分被分成不同的部分(称为模块)——每个模块由八个黑/白方块组合在一起(最好的方法是像字节一样思考这些方块)。

如果你碰巧查看了这个词条的维基百科链接,你一定会被大量的数学公式搞糊涂了。不必烦恼,看看上面的二维码——这是由知名品牌Marc Jacobs创造的,信不信由你,它其实就是一个功能齐全的二维码(尽管女孩掩盖了很大一块)——这都要归功于Reed-Solomon校正算法。

做一个类比:假设你想和其他人交流信息,但是这些信息会在一路上被破坏。纠错码的主要观点是,我们不必使用一整本字典,而是可以选出一小部分精挑细选的单词,即“简化的字典”,里面的每个单词都和其他单词大不相同。当我们收到一条消息时,我们只需在精简字典中:

1)识别哪些单词被损坏(因为它们不在精简字典中)

2)通过查找字典中最相似的单词来更正损坏的单词

也就是说,如果一个单词被破坏了,那没什么大不了的,因为我们大家可以通过查字典找到最接近的单词,这可能是正确的单词。但是如果输入的消息被破坏得太严重,有可能选择错误的单词,但这种可能性却很小。

“如果发现本网站发布的资讯影响到您的版权,可以联系本站!同时欢迎来本站投稿!