如何製作 QR Code #3：資料編碼
我們會在這篇文章中討論如何根據原始訊息和容錯等級，決定使用何種編碼模式和 QR Code 的版本，並完成資料的編碼。
選擇編碼模式
正常來說，人們喜歡用最低的成本來完成某件事情，製作 QR Code 的道理也一樣，如果今天有個數字字串要編碼，我們肯定會優先採用數字模式來編碼，而不是文數字模式，因為前者字元的平均編碼長度接近 3.4，而後者的平均編碼長度則接近 5.5。
讓我們看看下面例子：
input | 0123
-------------+----------------------------------
Numeric | 00000011000011
Alphanumeric | 0000000000100001011101
Byte | 00110000001100010011001000110011很明顯，對於純數字字串，採用數字模式編碼是最優的選擇，當編碼後的字串長度越短，就代表我們所需要的碼元會越少，也就是說 QR Code 的版本可能會越小。
一般來說，我自己選擇編碼的方式是這樣的：
- 能用數字模式，就用數字模式，否則進入 2.
- 能用文數字模式，就用文數字模式，否則進入 3.
- 能用位元組模式，就用位元組模式，否則進入 4.
- 能用漢字模式，就用漢字模式，否則編碼失敗
雖然這看起來很像廢話，不過是最簡單的選擇方法，我敢說大部分的情況，照著上面的步驟可以得到最優的模式。
當然也有不那麼簡單的方法，請閱讀《ISO/IEC 18004:2015 Annex J》。
選擇 QR Code 的版本
在確定編碼模式後，我們就要來選擇 QR Code 的版本了，在相同版本的情況下，因為容錯等級的不同，可供儲存的容量就會不同，所以容錯等級也是需要考量的因素之一。
為了選擇合適的版本，我們必須查表，表可以在下面三個地方找到：
- 《ISO/IEC 18004:2015 Table 7, in p33-p36》
- Information capacity and versions of the QR Code
- Charater Capacities by Version, Mode, and Error Correction
題外話，在我研究 QR Code 的編碼和解碼時，標準文件和 thonky.com 幫了我相當多的忙，值得有時間的讀者閱讀（不過標準一本要價不斐就是了）。
相信讀者可以一眼看出表要怎麼查，如果不懂的話第二個連結裡有相關說明。
我們再次用 0123 舉例，設容錯等級為 H，並使用數字模式編碼。
因為 0123 的長度為 4，查表可以發現 1-H 的 QR Code 最大容量為 17，所以使用版本 1 的 QR Code 就可以滿足我們的需求。
指示器（indicator）
在決定編碼模式和版本後，我們需要在編碼後的字串前，加入相關的指示器，以供解碼時使用。
指示器共有兩種，第一個是模式指示器（mode indicator），第二個是字元長度指示器（character count indicator），表列如下。
mode indicatorMode | Indicator
------------------+-----------
Numeric | 0001
Alphanumeric | 0010
Byte | 0100
Kanji | 1000
Structured Append | 0011
ECI | 0111
FNC1 1st | 0101
FNC1 2nd | 1001
Terminator | 0000character count indicatorVersion | 1-9 | 10-26 | 27-40
-------------+---------+---------+---------
Numeric | 10 | 12 | 14
Alphanumeric | 9 | 11 | 13
Byte | 8 | 16 | 16
Kanji | 8 | 10 | 12
綜合一下目前為止我們得到的訊息：
Version : 1-H
Message : 0123
Mode : Numeric
Encoded : 00000011000011一個正確的資料編碼包含：模式指示器、字元長度指示器和編碼後訊息，因為模式是數字模式，所以模式指示器的值為 0001，又因為版本為 1，所以字元長度指示器的長度為 10，說成白話就是我們要把 0123 的長度 4 轉換成長度為 10 的二進位數，也就是把 4 變成 0b0000000100。
所以根據上面的規則，我們的 0123 會變成：
0001、0000000100、00000011000011
以下提供些許範例供讀者參考，模式和版本選擇方法如先前所述，Encoded 為「模式指示器＋字元長度指示器＋編碼後訊息」，並且其中頓號僅為分隔之用，實際不需要加上。
EC level: M
Message : 8498929829
Encoded : 0001、0000001010、1101010001110111110011110101101001EC level: Q
Message : BYTE
Encoded : 0010、000000100、0100001000110100100111EC level: L
Message : Yeecy is the best!
Encoded : 0100、00010010、010110010110010101100101011000110111100100100000011010010111001100100000011101000110100001100101001000000110001001100101011100110111010000100001
終止符號（terminator）
接下來要先知道 QR Code 可以放入的碼元數量，我們可以透過查表得到，來源如下：
- 《ISO/IEC 18004:2015 Table 7, in p33-p36》
- Information capacity and versions of the QR Code
- Error Correction Code Words and Block Information
針對前面兩個來源，我們關注的是「data bits」欄位，針對後一個來源，我們須把「Total Number of … and EC Level」欄位的數值乘以 8（原因之後的文章會提到），才能得到可以放入的碼元數量。
查表後，對於 1-H QR Code，我們發現能放入的碼元數目為 72，觀察由 0123 得到的資料編碼：
0001000000010000000011000011
計算一下發現長度為 28，少於 72 許多，我們直接在該資料編碼的後方加入終止符號 0000，得到：
0001000000010000000011000011、0000
如果今天資料編碼的長度為 70，沒辦法放下 0000，根據標準，我們直接補兩個 0 就可以了，倘若長度為 72，那就不填入終止符號。
註：終止符號為模式指示器中的其中一個模式。
填充（padding）
假如進行到這裡，資料編碼的長度滿足「data bits」欄位的大小，那麼就不需要進行填充。
填充分成兩個部分，首先如果資料編碼的長度不為 8 的倍數，那麼就補 0 補到長度變 8 的倍數，接著再填充 11101100、00010001、11101100、00010001⋯⋯，直到長度滿足「data bits」欄位的值。
我們舉簡單一點的例子，假設資料編碼為：
010000
因為長度僅為 6，我們把他補到長度為 8：
01000000
程式的實現中，可以使用 8 - len(x)&7 來得到需要補多少個 0，這個寫法是我在 redis 的原始碼中看到的，非常厲害。
接著我們假設「data bits」欄位的值為 32，那麼填充完的結果會變成：
01000000、11101100、00010001、11101100
如此一來就完成資料編碼囉！
完整範例
假設容錯等級為 Q，欲編碼訊息為：
YEECY
觀察訊息，選擇使用文數字模式。
查表，發現 1-Q 的 QR Code 在文數字模式下可以容納 16 個字元，由於 YEECY 的長度為 5，所以確定採用的 QR Code 版本為 1。
文數字模式的模式指示器為：
0010
且字元長度指示器為：
9
所以我們把 YEECY 的長度 5 轉換成長度為 9 的二進位表示，得到：
000000101
再用文數字模式編碼 YEECY，得到：
1100000100001010000010100010
綜合起來：
00100000001011100000100001010000010100010
並且可以算出訊息長度為 41。
接著查詢版本 1 QR Code 的可容納碼元數，得到結果為：
104
由於長度為 41，小於 104，可以填入終止符號：
001000000010111000001000010100000101000100000
因為訊息長度為 45，不為 8 的倍數，我們補 0 得：
001000000010111000001000010100000101000100000000
現在的長度為 48，我們補 11101100、00010001 直到長度變成 104：
00100000001011100000100001010000010100010000000011101100000100011110110000010001111011000001000111101100
就這樣，資料編碼完成。
結語
這篇文章中的 0 和 1 有點多，寫到眼睛有點花，如果讀者發現內容有誤的話，請留言告訴我。
至於打算按照文章實現程式的讀者，我建議把需要的表格存成檔案，再寫一個類別來管理資料的讀取，不然寫到最後你的思緒和程式碼都會很亂。
下一篇文章將會介紹如何根據得到的資料編碼，計算出相應的錯誤校正碼。
感謝你的閱讀，我是 Yeecy，我們下一篇文章見。
