11
0说话人1: 各位好，又到聊天时间。先问个问题，你今天扫了几个码？
说话人2: 早餐付款、进楼门禁、加购物群、骑单车，少说四五个。
说话人1: 我们每天都在扫这个黑白小方块，可它到底怎么把信息藏进去的？为什么缺了一角、沾了油污，照样能扫出来？
说话人2: 对啊，我一直以为它就是随机画满的黑白格子。
说话人1: 那可小看它了。今天聊的内容，是李坚毅博士围绕二维码的编码与纠错机制创作整理的。这小方块不是随机图案，而是一整套精密系统，里面藏着射影几何、编码理论，还有一门特别硬核的代数。
说话人2: 扫个码还扫出数学课了？行，你从头讲。
说话人1: 先说最小单位。每个小方格叫模块，黑格代表1，白格代表0，整个码就是一个0和1组成的二维方阵。它一共有40个尺寸版本，版本号和边长是严格的线性关系：边长等于17加4倍版本号。版本1是21乘21，每升一级横竖各加4格；版本40代入公式就是17加4乘40等于177，177乘177一共31329个格子。
说话人2: 这些格子全装数据吗？
说话人1: 不全是。左上、右上、左下三个回字形大方块叫定位图案，专门让摄像头找到它，码外围还要留至少4格宽的空白边距。
说话人2: 我注意到每个码都有那三个大眼睛，为什么是三个不是四个？
说话人1: 三个点确定一个平面，四个角反而容易产生歧义。定位图案横竖方向的宽度比例固定为1比1比3比1比1，黑、白、黑、白、黑，中间3格实心。
说话人2: 可我要是斜着拍、歪着拍，这比例不就变形了吗？
说话人1: 这就说到李博士整理的这期内容里专门讲的射影不变性。正方形斜着投影到墙上会变成梯形，边长全变了，但这个1比1比3比1比1的比例特征，透视变形后依然稳定可辨。算法满画面搜索，找到三个满足这个比例、还呈三角形排布的图案，就锁定了二维码。找到后还要把歪图掰正，这一步叫单应性变换：用一个3乘3矩阵建立标准图和照片的映射，齐次坐标可整体缩放，9个参数去掉1个缩放自由度，正好剩8个自由度。
说话人2: 8个自由度得解方程吧？
说话人1: 对。一对对应点给横、纵两个方程，最少要4对点、8个方程解8个未知数，三个定位图案先给3个角点，第4个点由同步信息补上。
说话人2: 那要是纸皱了、贴在瓶身上弯了呢？一个整体矩阵救不了曲面吧？
说话人1: 救不了。所以版本2以上，码内部还撒了很多5乘5的校正图案，版本越高越多，像遍布地图的控制点，用分段仿射或薄板样条插值把局部扭曲拉回来，误差能压到比一个像素还小。第6行、第6列还各有一条黑白严格交替的同步线，数一数交替次数就能算出一个格子对应多少像素宽，整张网格坐标全推出来了。
说话人2: 等于自带一把刻度尺。那数据怎么塞进去？
说话人1: 二维码设计了四种编码模式，见人下菜碟。数字模式专门对付纯数字，每3个数字打成一个包编码成10位二进制。
说话人2: 为什么偏偏是10位？
说话人1: 3位十进制数从000到999一共1000种组合，10位二进制能表示2的10次方也就是1024种状态，1024大于1000，刚好全装下，浪费极少。
说话人2: 来个实际的数算算。
说话人1: 比如673。它等于512加128加32加1，也就是2的9次方、7次方、5次方、0次方之和，写成10位二进制就是1010100001。数字个数不是3的倍数时，剩1个用4位，因为2的4次方等于16大于等于10；剩2个用7位，2的7次方等于128大于等于100，一位不浪费。
说话人2: 那字母呢？
说话人1: 字母数字模式的字符集有数字、大写英文字母和9个符号，共45个，每2个字符打包成11位。45的平方是2025，2的11次方是2048，又是刚刚好。编码时第一个字符编号乘45加第二个字符编号，再转11位。比如字母A编号10、数字1编号1，A1就等于45乘10加1等于451，451等于256加128加64加2加1，写成11位就是00111000011。其余数据走字节模式，一个字节8位，通用但最不省地方；日文汉字模式每个汉字只用13位，省下约三分之一空间。李博士把这套思路梳理得很清楚：本质就是用尽量短的比特数覆盖字符组合空间，和字典压缩是同一个思想源头。
说话人2: 二维码真正厉害的，是不是还不是编码？
说话人1: 对，它的看家本领是破破烂烂还能把数据救回来，背后是里德-所罗门纠错码，一套建在有限域上的代数系统。
说话人2: 有限域？听着就硬。
说话人1: 普通算术里有无穷多个数，但二维码用的是只有256个元素的世界，叫伽罗华域G F 二的八次方，正好一个字节8位。这里面有个本原元叫阿尔法，所有非零元素都是它的幂，从零次方排到254次方，然后阿尔法的255次方回到1，就像钟面12点后回到1点。加法是按位异或，乘法是模一个八次多项式的多项式乘法，那道多项式是x的八次方加x的四次方加x的三次方加x的二次方加1。它保证这256个元素对加减乘除全部封闭，每个非零元素都有逆元，除法永远除得通，纠错代数这才有了根基。
说话人2: 那怎么编出纠错码？
说话人1: 假设k个信息码元后面跟2t个校验码元。先把信息多项式整体乘x的2t次方，相当于向左挪2t位腾位置；再除以生成多项式，它是2t个一次因式的乘积，根是连续2t个阿尔法的幂，除完取余式。
说话人2: 除法取余？这不就是小学的带余除法吗？
说话人1: 一模一样，只是减法全换成异或、没有借位。最后把余式补回空位，完整码字就天然能被生成多项式整除。解码时先算校验症状，就知道错在第几位、错几个，只要不超过t个就能精确还原。t由纠错等级定：L级纠正约百分之七的码元错误，M级百分之十五，Q级百分之二十五，H级百分之三十，冗余越多容量越小。
说话人2: 容量差多少？
说话人1: 同样版本1，L级能装25个数字字符，H级只剩10个；字节容量版本1最低17字节，版本40配L级能到2953字节。码元还不顺序写入，而是分块编码再交错排列，这样被撕掉一大块，伤害也摊薄到很多个码字块上，每块只错一点，都还在抢救范围内。
说话人2: 这就是别把鸡蛋放一个篮子里的代数版。
说话人1: 哈哈对。李博士还特意提到，连怎么解码的说明书都自带保险。格式信息一共15位：2位纠错等级、3位掩码编号、10位BCH校验位，5位信息配10位校验最多纠3位错误，而且在码里存两份互为备份；版本7以上还有18位版本信息，同样双备份，摄像头直接读版本号，不用数格子猜尺寸。
说话人2: 对了，网上总说二维码会不会有一天被用完，像车牌那样号段耗尽？
说话人1: 这是经典误会。车牌是预先分配的编号资源，发一个少一个；二维码却是从输入数据到图案的确定性映射，你输入内容，它就按版本、纠错等级、编码模式、掩码这套参数算出图案。输入空间无限，自然没有耗尽一说，同样输入永远得到同样图案，也不存在抢注冲突。
说话人2: 那你一直提到的掩码是干嘛的？
说话人1: 数据直接画成格子，常出现大片连在一起的黑块白块，甚至凑巧长得像定位图案，摄像头就懵了。所以从8种标准掩码里挑一种跟数据格子异或，把规律性打散，功能区纹丝不动。比如编号0的掩码，行号加列号能被2整除的格子翻色，画出来就是棋盘格。8种全部试画，按连续5个同色、2乘2同色方块、类定位图案比例、黑白失衡这四条扣分，总分最低的胜出。
说话人2: 连匀不匀都要考试。
说话人1: 哈哈，是为了好认。到这儿，找码、掰正、分格、编码、纠错到匀色，一条完整链路就闭合了。
说话人2: 今天之前我真以为二维码就是个印刷图案，没想到它是套穿着黑白格外套的数学系统。
说话人1: 李坚毅博士有这样一段感悟：人们每天无数次举起手机，却很少低头认真看一眼那个小方块。在这小小方块的身体里，住着几何学、代数学和信息论。真正了不起的工程从不大声喧哗，它只是安静地躺在每一张海报、每一个包装盒上，替整颗星球搬运信息。
说话人2: 说得我下次扫码都要肃然起敬了。
说话人1: 下次一次扫成功，别忘了那是有限域里的256个元素在默默加班。我们下期接着聊。
