如何製作 QR Code #5：建構最終訊息
在本文中，我們將揭露「Per Block」和它背後的秘密，事實上，根據 QR Code 版本和容錯等級的不同，我們需要把依照《如何製作 QR Code #3》得到的訊息，進行錯誤校正後，將資料碼字和錯誤校正碼字按一定規則重新排列，才能得到最終訊息。
表格說明
進入正題前，先回到上次的表格：
我們看第二個連結的表格，先解說每個欄位的意思，下面以「組」表 Group，以「塊」表 Block。
- Total Number … EC Level ⟶ 資料碼字的總數，跟 7. 相同
- EC Codewords Per Block ⟶ 每塊的錯誤校正碼字數
- Number of Blocks in Group 1 ⟶ 組 1 有幾個塊
- Number of Data … Group 1’s Blocks ⟶ 組 1 的塊中，有幾個資料碼字
- Number of Blocks in Group 2 ⟶ 組 2 有幾個塊
- Number of Data … Group 2’s Blocks ⟶ 組 2 的塊中，有幾個資料碼字
- Total Data Codewords ⟶ 與 1. 相同，只是增加了計算過程
從上面不難發現：
- 組數最小為 1，最多為 2
- 不同組的塊數不一定相同
- 同組的塊，資料碼字數相同
- 不同組的塊，資料碼字數不同（因為碼字數相同就不用分組了呢）
- 不論是哪組的塊，錯誤校正碼字數都相同
- 可以由 3.、4.、5. 和 6. 計算出 1.
雖然看起來可能有點饒舌，不過我們先在此約定一些簡稱，以利後續討論：
- Total Number … EC Level ⟶ total_dc
- EC Codewords Per Block ⟶ num_ecc
- Number of Blocks in Group 1 ⟶ num_block_g1
- Number of Data … Group 1’s Blocks ⟶ num_dc_per_block_g1
- Number of Blocks in Group 2 ⟶ num_block_g2
- Number of Data … Group 2’s Blocks ⟶ num_dc_per_block_g2
資料碼字的分組
範例一：1 組、該組只有 1 塊
我們先從完全虛構的範例開始，不管錯誤校正，假設：
data_codewords = [1, 2, 3, 4]
num_block_g1 = 1
num_dc_per_block_g1 = 4
num_block_g2 = 0
num_dc_per_block_g2 = 0由上面的設定，可以發現：
- num_block_g1 是 1，代表組一（group 1）只有一個塊
- num_dc_per_block_g1 是 4，代表組一內的每個塊要放 4 個資料碼字
- num_block_g2 是 0，代表組二不存在
我們依此分配資料碼字到各個塊中，得到：
group 1
block 1: [1, 2, 3, 4]範例二：1 組、該組有 N 塊
這個範例是上面的延伸，應該很好理解，只要按順序填完就好。
data_codewords = [1, 2, 3, 4, 5, 6, 7, 8]
num_block_g1 = 4
num_dc_per_block_g1 = 2
num_block_g2 = 0
num_dc_per_block_g2 = 0由上面的設定，可以發現：
- num_block_g1 是 4，代表組一有 4 個塊
- num_dc_per_block_g1 是 2，代表組一內的每個塊要放 2 個資料碼字
- num_block_g2 是 0，代表組二不存在
我們依此分配資料碼字到各個塊中，得到：
group 1
block 1: [1, 2]
block 2: [3, 4]
block 3: [5, 6]
block 4: [7, 8]範例三：2 組、組一有 1 塊、組二有 1 塊
多加了一個組，不過原理相同。
data_codewords = [1, 2, 3, 4, 5, 6, 7, 8, 9]
num_block_g1 = 1
num_dc_per_block_g1 = 4
num_block_g2 = 1
num_dc_per_block_g2 = 5由上面的設定，可以發現：
- num_block_g1 是 1，代表組一有 1 個塊
- num_dc_per_block_g1 是 4，代表組一內的每個塊要放 4 個資料碼字
- num_block_g2 是 1，代表組二有 1 個塊
- num_dc_per_block_g2 是 5，代表組二內的每個塊要放 5 個資料碼字
我們依此分配資料碼字到各個塊中，得到：
group 1
block 1: [1, 2, 3, 4]
group 2
block 1: [5, 6, 7, 8, 9]範例四：2 組、組一有 N 塊、組二有 M 塊
各組內的塊數不同了，但有了上面的範例，讀者應該可以看出分組結果。
data_codewords = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
num_block_g1 = 2
num_dc_per_block_g1 = 3
num_block_g2 = 4
num_dc_per_block_g2 = 4由上面的設定，可以發現：
- num_block_g1 是 2，代表組一有 2 個塊
- num_dc_per_block_g1 是 3，代表組一內的每個塊要放 3 個資料碼字
- num_block_g2 是 4，代表組二有 4 個塊
- num_dc_per_block_g2 是 4，代表組二內的每個塊要放 4 個資料碼字
我們依此分配資料碼字到各個塊中，得到：
group 1
block 1: [1, 2, 3]
block 2: [4, 5, 6]
group 2
block 1: [7, 8, 9, 10]
block 2: [11, 12, 13, 14]
block 3: [15, 16, 17, 18]
block 4: [19, 20, 21, 22]資料碼字的分組講到這裡就差不多了，我們接著要按照資料碼字的分組，來計算錯誤校正碼字。
錯誤校正碼字的分組
我們接下來要做的，就是把每個塊中的資料碼字，丟進 RS 碼編碼器，然後取得錯誤校正碼字。
拿上面的範例四為例：
因為 RS 碼編碼器需要知道錯誤校正碼字的數量，所以假設：
num_eec = 2- num_eec 是 2，代表每一塊需要生成 2 個錯誤校正碼字
我們把每一塊的資料碼字拿去編碼，RS 碼編碼器的參數設定與上一篇文章提到的相同，得到：
group 1
block 1: [1, 2, 3], [4, 4]
block 2: [4, 5, 6], [45, 42]
group 2
block 1: [7, 8, 9, 10], [4, 8]
block 2: [11, 12, 13, 14], [172, 168]
block 3: [15, 16, 17, 18], [20, 8]
block 4: [19, 20, 21, 22], [81, 85]其中左邊為資料碼字，右邊為錯誤校正碼字。
重新排列
接下來我們要重新排列碼字，先用簡單的例子解釋：
group 1
block 1: [1, 2, 3, 4]
block 2: [5, 6, 7, 8]
block 3: [9, 10, 11, 12]首先從第一塊的第一個碼字開始拿，接著第二塊的第一個碼字，如果每一塊的第一個都拿完了，就拿第一塊的第二個碼字，以此類推，可以得到：
[1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12]這樣就完成了資料碼字的重新排列，我們再看一個例子：
group 1
block 1: [1, 2]
group 2
block 1: [3, 4, 5]
block 2: [6, 7, 8]我們將其重排，可以得到：
[1, 3, 6, 2, 4, 7, 5, 8]注意到如果第一組的第一塊沒有第三個碼字的話，就跳過，直接拿第二組第一塊的第三個碼字。
至於錯誤校正碼字的方法也一樣，不過我們要先把資料碼字和錯誤校正碼字分別重排，我們用上面的例子示範：
group 1
block 1: [1, 2, 3], [4, 4]
block 2: [4, 5, 6], [45, 42]
group 2
block 1: [7, 8, 9, 10], [4, 8]
block 2: [11, 12, 13, 14], [172, 168]
block 3: [15, 16, 17, 18], [20, 8]
block 4: [19, 20, 21, 22], [81, 85]首先，我們只看資料碼字，將其重排可以得到：
[1, 4, 7, 11, 15, 19, 2, 5, 8, 12, 16, 20, 3, 6, 9, 13, 17, 21, 10, 14, 18, 22]接著，我們重排錯誤校正碼字，得到：
[4, 45, 4, 172, 20, 81, 4, 42, 8, 168, 8, 85]現在我們把重排好的資料碼字和錯誤校正碼字併在一起，就完成最終訊息的建構了：
[1, 4, 7, 11, 15, 19, 2, 5, 8, 12, 16, 20, 3, 6, 9, 13, 17, 21, 10, 14, 18, 22, 4, 45, 4, 172, 20, 81, 4, 42, 8, 168, 8, 85]要記得我們先放資料碼字，再放錯誤校正碼字，不會有資料碼字沒放完，就放錯誤碼字的情況。
在放置完後，要把每個數字換成長度為 8 的二進位數喔（因為一個碼字的長度為 8）。
剩餘位元（remainder bits）
最後我們要來添加剩餘位元，也就是根據剩餘位元的數量，決定在最終訊息的後面加上幾個 0。
剩餘位元的數量根據版本不同而有所差異，表列如下：
version | remainder bits
--------+---------------
1 | 0
2-6 | 7
7-13 | 0
14-20 | 3
21-27 | 4
28-34 | 3
35-40 | 0假設虛構訊息如下，並且版本為 34：
0101
查表，發現版本 34 需要添加 3 個剩餘位元：
0101000
如此一來就得到加上剩餘位元的最終訊息了。
完整範例
讓我們接續《如何製作 QR Code #3》的完整範例：
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因為使用的 QR Code 的版本為 1-Q，查表得：
num_ecc = 13
num_block_g1 = 1
num_dc_per_block_g1 = 13
num_block_g2 = 0
num_dc_per_block_g2 = 0我們將其分組得：
group 1
block 1: [32, 46, 8, 80, 81, 0,236, 17, 236, 17, 236, 17, 236]接下來，計算錯誤校正碼字得到：
group 1
block 1: [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]重排資料碼字（在此範例中不變）：
[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]接下來把資料碼字和錯誤校正碼字併起來，得到：
[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]這樣最終訊息就完成了！不過因為 QR Code 的碼元只有兩種顏色，所以把它們都變成長度為 8 的二進位數：
00100000, 00101110, 00001000, 01010000, 01010001, 00000000, 11101100, 00010001, 11101100, 00010001, 11101100, 00010001, 11101100, 00010100, 01101000, 01011010, 10011001, 00001000, 01100010, 11011100, 11011000, 11011111, 11100100, 10001100, 00001110, 01111110再合併起來：
0010000000101110000010000101000001010001000000001110110000010001111011000001000111101100000100011110110000010100011010000101101010011001000010000110001011011100110110001101111111100100100011000000111001111110因為版本 1 沒有剩餘位元，所以我們可以準備製作圖片囉！
結語
本文介紹的內容相較於上一篇文章簡單，不過要把整個流程寫成程式可能是件有點小挑戰的事，不過生活中總是要有些小挑戰才有趣，你說是吧？以上，編碼篇的四篇文章至此告個段落。
下一篇文章是生成篇的第一篇，Yeecy 會告訴讀者在產生圖片前，要做什麼事情才能讓程式寫起來輕鬆一些，不懂程式的讀者也能來看看文章的內容，或許能從中得到些什麼也說不定。
感謝你的閱讀，我是 Yeecy，我們下一篇文章見。
