加人、購物、填表、付錢，你可能掃過無數(shù)次二維碼，但卻從來沒有認(rèn)真看過它。這個(gè)二維碼結(jié)構(gòu)看起來很簡單，左下、左上和右上有三個(gè)方塊用來定位。剩下的位置就是一堆黑色和白色小方塊組成一個(gè) 29×29 的大方塊，白色方塊表示 0，黑色方塊表示 1。由這些 0 和 1 構(gòu)成的二進(jìn)制字符串就可以轉(zhuǎn)換成各種數(shù)字、字母和符號(hào)了。但你仔細(xì)看，就會(huì)發(fā)現(xiàn)沒這么簡單。條碼系統(tǒng)誕生之初，就是希望創(chuàng)造一套簡單清晰可被印刷能被機(jī)器識(shí)別的圖形編碼，讓機(jī)器輕松獲取商品編號(hào)。這樣你在超市買東西的時(shí)候，收銀員就不需要手動(dòng)記錄，只需要掃一下就能知道多少錢了。這就是二維碼的前身——一維碼，今天我們都叫條形碼。以 UPC（Universal Product Code）碼為例，本質(zhì)上就是 30 條粗細(xì)不一的黑線。而黑色豎線和白色間隔的寬度，就是隱藏在條形碼里的二進(jìn)制信息。豎線和間隔都有 4 種寬度。最細(xì)的豎線代表一個(gè) 1，之后是兩個(gè) 1，三個(gè) 1，最粗的豎線就是 4 個(gè) 1。對(duì)應(yīng)的，4 種間隔寬度就是 0、00、000、0000。比如這里，就是 0110001，根據(jù)編碼表，代表 5。每 2 條豎線加 2 條間隔就能表示一個(gè)數(shù)字，這 48 條豎線和間隔就可以表示 12 位數(shù)字編號(hào)了。而左右最外側(cè)的雙排線則是所有條碼的固定開頭，代表 101，這么做的意義在于讓掃碼器知道這個(gè)條碼最細(xì)寬度，進(jìn)而識(shí)別出這個(gè)寬度的 2、3、4 倍。這樣，無論條碼按照什么尺寸印刷，掃碼器都可以完成識(shí)別，需要的信息也只有一條線這么多，其他地方都污損了也沒關(guān)系。只要讓掃碼器區(qū)分左右就好了。我們把分隔符左側(cè)的編碼表里的 0 變成 1、1 變成 0 ，就得到了分隔符右側(cè)的編碼表。巧妙的地方在于，左側(cè)所有組合里 1 的個(gè)數(shù)都是奇數(shù) ，而右側(cè)都是偶數(shù)。這樣，掃碼器從左往右讀取數(shù)據(jù)時(shí)只要發(fā)現(xiàn)一組數(shù)據(jù)里的 1 是偶數(shù)，那么就可以確認(rèn)掃反了。用逆碼表解讀數(shù)字，再重新組合，就能得到正確編號(hào)。最后，編號(hào)第 12 位數(shù)是根據(jù)前 11 位數(shù)計(jì)算出來的校驗(yàn)碼，以防止篡改。這三重設(shè)計(jì)保證了條形碼可以適應(yīng)各種復(fù)雜的現(xiàn)實(shí)情況，非?？煽俊?/span>但條形碼上能承載的信息還是太少了，所以，以矩陣形式承載更多信息的二維碼出現(xiàn)了。在這些奇奇怪怪的二維碼中， QR 碼脫穎而出，出現(xiàn)在了你的微信支付寶和火車票上。QR 的全稱是 Quick Response，快速響應(yīng)矩陣。最有代表性的就是這三個(gè)回字型方塊，這樣的排布方案可以讓你無論從哪個(gè)方向掃描二維碼都會(huì)自動(dòng)校正為正確方向，只要右下角沒方塊就是對(duì)的，很簡單。但 QR 碼是怎么實(shí)現(xiàn)校驗(yàn)、糾錯(cuò)同時(shí)保證準(zhǔn)確度的呢？我們找到了這份 126 頁的 QR 碼國際通用標(biāo)準(zhǔn)。今天的普通 QR 碼有 40 個(gè)版本，版本越大，尺寸越大。最小的版本 1 是一個(gè) 21×21 的正方形，版本號(hào)每加 1，正方形的邊長就多 4 格。最大的版本 40 就是一個(gè)這樣 177×177 的密恐正方形。以這個(gè)版本 3 的 QR 碼為例，大概由 5 個(gè)部分組成。1 是 3 個(gè)7×7 的回字形方塊和寬度為 1 的白色的分隔符。2 是這兩條黑白相間的定位圖案，告訴掃碼器橫豎的標(biāo)準(zhǔn)方向。3 是右下角的校正圖形，一個(gè) 5×5 的小方塊，尺寸越大，校正圖形越多。這樣，即使你用奇怪的角度掃描，算法依然可以根據(jù)這三組圖案提取輪廓，修正透視，獲得正面圖案。4 是由相同的兩組方塊組成的格式信息，每組 15 個(gè)，放置在定位方塊的旁邊。5 作為剩下的區(qū)域，會(huì)被分成 8 個(gè)一組的模塊，存儲(chǔ)數(shù)據(jù)和糾錯(cuò)碼。而在大于等于版本 7 的 QR 碼里，還需要在這兩處記錄 18 位的版本信息，提高掃碼器的效率。1、2、3 的設(shè)計(jì)只是讓 QR 碼可以被掃碼器認(rèn)出來，但 QR 碼真正厲害的地方在于，即使你這樣、這樣、或者這樣、它都能被正確識(shí)別。 現(xiàn)在，我們終于進(jìn)入到了 QR 碼的核心， Reed-Solomon 編碼。注意，接下來的內(nèi)容會(huì)有一點(diǎn)點(diǎn)難，但也只需要中學(xué)數(shù)學(xué)知識(shí)就夠了，如果你理解了會(huì)非常有意思，讓我們開始吧。
我們知道，二維碼是用黑白方格對(duì)應(yīng)的二進(jìn)制數(shù)據(jù)來表示信息，比如 1234 就可以編碼為 00011110110100，對(duì)應(yīng)成二維碼里的方格就是這樣。而 Reed-Solomon 編碼可以讓你隨便修改一定數(shù)量的格子，機(jī)器都能自動(dòng)還原成正確的數(shù)據(jù)。為了更好的解釋這一過程，我們簡化成 4 個(gè)格子，有 4 個(gè)數(shù)字，分別是 1、2、3、4。我們的目標(biāo)是，任選 2 格修改成其他數(shù)字，算法都可以自動(dòng)發(fā)現(xiàn)錯(cuò)的是哪一個(gè)，并且還原成修改前的數(shù)據(jù)。為了做到這件事，我們需要得到 4 個(gè)變量，錯(cuò)誤的兩個(gè)格子的位置，e1 和 e2，這兩個(gè)格子錯(cuò)誤的大小 y1 和 y2。假設(shè)我們知道 e1=3，e2=1，y1=-5，y2=1，那么機(jī)器就可以自動(dòng)調(diào)整成正確數(shù)據(jù)了。而在計(jì)算這 4 個(gè)未知數(shù)之前，還得先讓機(jī)器知道，這串?dāng)?shù)字錯(cuò)了。最簡單的方法，就是算 0。算出了 0 就是對(duì)的，不是 0 就是錯(cuò)的。比如我們所有人的設(shè)備都可以保存一個(gè)固定數(shù)值 g=1234，用輸入數(shù)值 m 1234 減固定值 g 1234 就剛好等于 0。但 g 是不會(huì)變的，如果我們想輸入 5678，結(jié)果就不是 0 了。這時(shí)我們就需要根據(jù)輸入值和固定值反推出一個(gè) p，無論我們想輸入什么，都能算出 0，這個(gè) p 就是糾錯(cuò)碼。比如固定數(shù)值 g= 100，輸入值是 5678，那 p 就可以是 -5578，如果我們輸入變成 1234，p 就會(huì)跟著變成 -1134。這樣，如果輸入值被篡改了，比如被改成了 6234，結(jié)果就不是 0，而是 5000，機(jī)器就知道輸入錯(cuò)了。糾錯(cuò)碼 p 和輸入值 m 都會(huì)出現(xiàn)在二維碼上，但這樣就帶了一個(gè)新問題，糾錯(cuò)碼被修改了怎么辦？如果 m+p-100 不等于 0，我們永遠(yuǎn)不可能知道是 m 錯(cuò)了還是 p 錯(cuò)了，但是如果我們可以把 m 和 p 組合成一個(gè)數(shù)字比如說 1234XXXX 呢？聽起來不錯(cuò)，但這樣減法就不行了，這 4 位數(shù)不管是多少都不可能得到 0，那怎么辦？比如我們讓 12340000 除以 3，余數(shù)等于 1，我們用 12340000 減去 1，就得到了 12339999，此時(shí)除以 3 的余數(shù)等于 0。但這樣帶來了兩個(gè)新問題， 3 的倍數(shù)有很多，很多錯(cuò)誤情況下一樣可以得到 0，而即使我們得到了一個(gè)余數(shù)，我們又怎么能通過余數(shù)知道哪一位數(shù)錯(cuò)了多少呢？這時(shí)，我們就需要改變計(jì)算規(guī)則了。隆重介紹——伽羅瓦域(Galois Field，GF)。伽羅瓦域厲害的地方在于，這是一個(gè)封閉的世界，里面的有限個(gè)數(shù)字不管怎么算都不會(huì)得到它們之外的結(jié)果。以 GF(2^3) 域?yàn)槔?，一共?8 個(gè)數(shù)，「0、1、2、3、4、5、6、7」，他們對(duì)應(yīng)的二進(jìn)制是這樣。伽羅瓦域的加法和減法運(yùn)算一樣，都是異或算法。比如 1-2 就是 001 異或 010，結(jié)果是 011，根據(jù)這個(gè)表 011 是 3，1+2 結(jié)果也一樣。6+7 就是 1，不管怎么加減，都只能得到這個(gè)域里的數(shù)字。而乘除法的規(guī)則復(fù)雜一些，結(jié)果大于 7，比如 6*7 就需要對(duì) 110 和 111 做模二乘法，再用模二除法除以提前預(yù)設(shè)的數(shù)值 1011，得到余數(shù) 100，就是 4。這就是伽羅瓦域 GF(2^3) 的完整乘法表，不管你怎么算，永遠(yuǎn)只能得到 0、1、2、3、4、5、6、7。除法也類似。還記得剛剛的除法嗎？現(xiàn)在如果我們用伽羅瓦域的規(guī)則，就不能再用 12340000 了，這個(gè)世界里只能有這 8 個(gè)數(shù)字，那我們還能怎么表現(xiàn) 12340000 呢？在多項(xiàng)式中，我們可以把每個(gè)格子里的數(shù)字作為 x 的系數(shù)，把格子的位數(shù)作為 x 的次方數(shù)。比如 1、2、3、4 就是 1*x^3+ 2*x^2+ 3*x^1+ 4*x^0，那么 12340000 的多項(xiàng)式 m(x) 就是這樣既然輸入數(shù)據(jù)變成了多項(xiàng)式，我們要除以的固定值 g 也應(yīng)該是一個(gè)有 x 的多項(xiàng)式。我們要得到的 4 位糾錯(cuò)碼， g(x) 就有 4 個(gè)因子，分別是x減2的零次方，x減2的一次方，x減2的二次方，x減2的三次方，這樣做的意義在于，因?yàn)檫@個(gè) g(x) 展開后的多項(xiàng)式最高位就是 x 的 4 次方，所以我們用 m(x) 除以 g(x) 能剛好就得到 4 位數(shù)的余數(shù)P(x)= 1*x^3 + 6*x^2 + 7*x + 4，把多項(xiàng)式的系數(shù)換成數(shù)字就是 1674。我們兩邊都乘 g(x) ，再把余數(shù) P(x) 移到左邊，別忘了伽羅瓦域里加和減是一樣的。所以我們可以神奇地發(fā)現(xiàn)，把原來的 M(x) 和余數(shù) P(x) 相加，得到的新多項(xiàng)式剛好可以被整除，而這 4 位余數(shù)就是我們要找的 4 位糾錯(cuò)碼。這樣我們得到了最終的輸入數(shù)據(jù) 12341674，用多項(xiàng)式表示就是這樣好，我們的準(zhǔn)備工作已經(jīng)全部完成了?，F(xiàn)在，你可以隨便修改這 8 個(gè)格子里的 2 個(gè)數(shù)，機(jī)器都可以完成自動(dòng)修正。首先，系統(tǒng)會(huì)把收到的輸入數(shù)據(jù)變成多項(xiàng)式，除以提前設(shè)定好的 g(x) ，得到余數(shù) 1645，不等于 0，說明輸入數(shù)據(jù)有誤。現(xiàn)在，只需要找到錯(cuò)誤位置 e1、e2 以及他們對(duì)應(yīng)的錯(cuò)誤大小 y1、y2 就行了。而這一切的關(guān)鍵，就在于四個(gè)隱藏著的方程組。我們知道正確的輸入數(shù)據(jù) M(x) 除以 g(x) 的余數(shù)是 0，那么 M(x) 就等于 g(x) 乘一個(gè)固定值 h。如果 g(x)=0， 正確的 M(x) 也會(huì)等于 0。而根據(jù) g(x) 的公式，恰好有 4 種情況會(huì)等于 0。分別是 x 等于 2 的 0 次方 1 次方 2 次方和 3 次方，用公式寫出來就是這樣：雖然我們不知道正確情況下 m1、m2、m3、m4、p1、p2、p3、p4 是多少，但是我們知道錯(cuò)誤情況下的，把我們收到的輸入數(shù)據(jù) 62241674 帶入這 4 個(gè)方程計(jì)算，能得到 4 個(gè)不等于 0 的結(jié)果。而這 4 個(gè)方程之所以不等于 0，是因?yàn)橛?2 個(gè)地方的數(shù)字出錯(cuò)了，出錯(cuò)的大小 y 乘 2 的 n 次方后相加就是方程的結(jié)果。而這 2 的這個(gè) n 次方又和出錯(cuò)數(shù)字的位置有關(guān)，如果 x=2^1 ，那么 n 就等于 1 乘出錯(cuò)的位置 e，如果 x=2^2 ，那么 n 就等于 2 乘出錯(cuò)的位置 e。用公式寫出來就是這樣：現(xiàn)在，我們有四個(gè)方程組，四個(gè)未知數(shù)，機(jī)器就能算出來現(xiàn)在，我們可以把收到數(shù)據(jù)的第 5 和第 7 位的數(shù)字 2 和 6，分別和 y1 和 y2 做異或運(yùn)算，得到 3 和 1，填回去，我們就得到正確的輸入數(shù)據(jù)了。需要說明的是，這是一個(gè)簡化后的計(jì)算過程，實(shí)際情況還要更復(fù)雜。這就是二維碼的秘密，把信息編碼為二進(jìn)制，按順序填上原始數(shù)據(jù)，再填上計(jì)算后的糾錯(cuò)碼，和其他信息，再和掩碼做一次異或運(yùn)算，最終成為你看到的樣子，一個(gè)可靠的碼。 1960 年，工程師 Irving S. Reed 和 Gustave Solomon 可能也不會(huì)想到，他們發(fā)布的這篇不到的 5 頁論文會(huì)在 60 年后成為當(dāng)代生活不可或缺的一部分，和無數(shù)精彩絕倫的論文一樣，成為這個(gè)世界底層看不見的一塊磚。 
