如何製作 QR Code #4：錯誤校正
錯誤校正是 QR Code 能夠抗汙損的秘密，在本文中會介紹如何根據資料編碼得到錯誤校正碼，不過不用擔心不懂伽羅瓦體和里德－所羅門碼，畢竟天無絕人之路，我們會有辦法克服的。
在正式進入錯誤校正之前，我們要先介紹新東西。
碼字（codeword）
在 QR Code 中，一個碼字長八個位元，例如 10110010 長度為 8，可以視做一個碼字。
還記得在《如何製作 QR Code #3》中，如果編碼的長度不為 8 的倍數，需要將它補 0 補到長度變成 8 的倍數嗎？這正是為了保證可以把編碼切成整數個碼字，以便產生錯誤校正碼。
我們拿上一篇文章最後的範例為例：
00100000001011100000100001010000010100010000000011101100000100011110110000010001111011000001000111101100
我們把它切分成一個個的碼字：
00100000、00101110、00001000、01010000、01010001、00000000、11101100、00010001、11101100、00010001、11101100、00010001、11101100
接著轉換為十進位數：
32、46、8、80、81、0、236、17、236、17、236、17、236
換成使用十進位數來表示碼字，是為了節省文章版面，以保證不會充斥著 0 和 1，導致閱讀困難，同時也方便我們理解。
QR Code 中的碼字一共分為兩種，一種是資料碼字（data codeword），正是我們上面的 13 個十進位數，另一種則是錯誤校正碼字（error correction codeword），我們稍後會提到。
錯誤校正（error correction）
伽羅瓦體（Galois field）
老實說，距離最後一次碰到離散數學（discrete mathematics）已經過了將近兩年，雖然看相關文章時還能略懂一二，不過我也不是很確定自己的理解正不正確，請有興趣的讀者自行研究，Yeecy 的能力不足請見諒。
里德－所羅門碼（Reed-Solomon code）
里德－所羅門碼（後以 RS 碼稱之）建立於伽羅瓦體之上，屬編碼理論（coding theory）的範疇，數學能力夠的讀者可以自己研究一下，基本上，Github 會有別人開源的 RS 碼函式庫，去找一個自己語言能用的下載下來，我想，用下面的關鍵字排列組合一下應該可以找到。
error correcting
error correction
universal
reed-solomon
codec
encoder
decoder
library
module理論上函式庫提供的函式會長得很類似，假設函式介面如下：
RSCode_encode(message, n, k, generator, fcr, prim, c_exp)看到上面這麼多參數不用害怕，因為 Yeecy 已經替你害怕過了，我們來解釋一下參數代表什麼。
- message 代表要生成錯誤校正碼的訊息，也就是上面的那 13 個碼字，至於要傳入 13 個十進位數、13個 八進位數、13 個位元組、一個字串還是其他的形式，就請讀者參考自己函式庫的說明文件（documentation）。
- n 通常是資料碼字的個數加上錯誤校正碼字的個數。
- k 通常是資料碼字的個數。
- generator 應設為 2，其實這個參數就是標準裡頭的 α。
- fcr 設為 0 就可以。
- prim 根據標準敘明，應設為 0x11D（0b100011101）。
- c_exp 應設為 8，因為 QR Code 的 RS 碼採用 GF(2⁸)。
如果還是很懵懂沒關係，之後會有範例。
取得錯誤校正碼
敏銳一點的讀者可能會有個疑問，資料碼字的個數已經有了，那要怎麼知道錯誤校正碼字的個數呢？
這個時候靜下心來，回想過去我們遇到未知的數字是怎麼處理的，嗯，沒錯，相信大家的心中會浮出兩個字：查表。
對於錯誤校正碼字的個數，我們需要查表，以下提供兩個來源：
我們就用下面的連結說明吧，話說 thonky.com 上有關於怎麼進行 RS 碼編碼的過程，讀者可以在閱讀完本文後，前往參考。
上一篇文章中，我們採用的是 1-Q 的 QR Code，所以我們關注 1-Q 對應的「EC Codewords Per Block」欄位，查表不難發現我們需要的錯誤校正碼字個數為 13。
我們暫時先不管「Per Block」代表什麼意思，具體說明留待下篇文章，先專注在錯誤校正本身。
現在我們有：
32、46、8、80、81、0、236、17、236、17、236、17、236
和錯誤校正碼字個數 13。
我們調用 RSCode_encode() 並設定參數如下：
- message = 32、46、8、80、81、0、236、17、236、17、236、17、236
- n = 13 + 13 = 26
- k = 13
- generator = 2
- fcr = 0
- prim = 0x11D
- c_exp = 8
根據我的經驗，函式庫實現會把 message 的傳入值和錯誤校正碼一起回傳，得到：
32、46、8、80、81、0、236、17、236、17、236、17、236、 20、104、90、153、8、98、220、216、223、228、140、14、126
如果只回傳錯誤校正碼，那是件很棒的事，如果不是，我們把錯誤校正碼獨立出來：
20、104、90、153、8、98、220、216、223、228、140、14、126
大部分的時候把輸入值和錯誤校正碼合在一起是很合理的做法，不過 QR Code 可以算是例外，原因下一章會提到。
以下提供數個範例供讀者參考，參數除 message、n 和 k 外，都與上面相同。
version : 1-L
message : [16, 32, 202, 2, 11, 0, 236, 17, 236, 17, 236, 17, 236, 17, 236, 17, 236, 17, 236]
(n, k) : (26, 19)
ec_codewords : [149, 41, 100, 238, 142, 10, 173]version : 1-M
message : [32, 83, 11, 120, 217, 210, 41, 187, 224, 236, 17, 236, 17, 236, 17, 236]
(n, k) : (26, 16)
ec_codewords : [112, 250, 156, 210, 72, 24, 190, 74, 251, 243]version : 2-M
message : [65, 114, 134, 226, 194, 6, 178, 146, 2, 2, 2, 2, 2, 2, 3, 162, 2, 131, 35, 98, 194, 3, 19, 146, 144, 236, 17, 236]
(n, k) : (44, 28)
ec_codewords : [168, 128, 121, 206, 206, 96, 203, 237, 131, 207, 135, 229, 26, 110, 48, 110]
結語
這篇文章我重構過好幾次，第一次讀完可能會覺得滿頭問號，如果讀者沒有打算自己實現，可以把這篇文章的內容當作數學魔術看過去就好，不然就只能請讀者花費點時間，弄清楚要怎麼用函式庫把錯誤校正碼算出來。
如果能成功得到錯誤校正碼，那就太棒了，之後的 QR Code 生成會變得有趣許多，另外，如果得到的錯誤校正碼與上面寫的不一樣，不代表有錯，可能是存在某些預設的參數不同造成的，不過這應該不構成問題，通用 RS 碼解碼器還是可以幫我們解碼解出來的。
反正就跟著文章走，等到生出自己的 QR Code 圖片後，再用手機或其他方式解碼，解成功就成功，失敗就回來除錯，如此而已。
下一篇文章會來解開尚未說明的「Per Block」和它背後的秘密。
感謝你的閱讀，我是 Yeecy，我們下一篇文章見。
