如何製作 QR Code #8：資料放置與格式資訊
本文將會介紹怎麼加上格式資訊，並放置《如何製作 QR Code #5》中得到的由 0 和 1 組成的最終訊息，到了這裡，距離完整產生 QR Code 已經不遠了，請讀者要堅持到最後喔！
格式資訊
容錯等級 & 遮罩（mask）
在格式資訊裡，包含了容錯等級、遮罩編號和錯誤校正碼，而錯誤校正碼要使用 BCH 碼（Bose–Chaudhuri–Hocquenghem code）來得到。
又來？一開始的資料使用 RS 碼，上次的版本資訊用格雷碼，怎麼現在的格式資訊要用卻是 BCH 碼呢？
別急，QR Code 中的容錯等級共有 4 種，遮罩共有 8 種，表列如下：
error correction level ec level | bits
----------+--------
L | 01
M | 00
Q | 11
H | 10mask pattern mask | condition
-------+----------------------------
000 | (r + c) % 2 = 0
001 | r % 2 = 0
010 | c % 3 = 0
011 | (r + c) % 3 = 0
100 | (c//3 + r//2) % 2 = 0
101 | (r * c)%2 + (r * c)%3 = 0
110 | ((r * c)%3 + r*c) % 2 = 0
111 | ((r * c)%3 + r + c) % 2 = 0
上面兩張表僅為編碼時使用，跟解碼的表不一樣，請不要像 Yeecy 一開始一樣，以為解碼的表和編碼的表會是一樣的，而 mask pattern 表中的 condition 欄位，我們留待下一篇文章解釋，現在只需要關心的 mask 欄位。
開頭提到格式資訊裡，包含了容錯等級、遮罩編號和錯誤校正碼，有了上面的表，我們就有了容錯等級和遮罩編號的 0 和 1 的表示。
假設容錯等級為 L，使用遮罩 001，我們可以得到不含錯誤校正碼的格式資訊為：
01001
錯誤校正碼
因為容錯等級和遮罩排列組合起來也就只有 32 種，就像版本資訊一樣，我們建個表就能解決上面的問題了，表列如下：
data bits | ec bits
-----------+----------------
01000 | 1111010110
01001 | 1011100001
01010 | 0110111000
01011 | 0010001111
01100 | 1000111101
01101 | 1100001010
01110 | 0001010011
01111 | 0101100100
-----------+----------------
00000 | 0000000000
00001 | 0100110111
00010 | 1001101110
00011 | 1101011001
00100 | 0111101011
00101 | 0011011100
00110 | 1110000101
00111 | 1010110010
-----------+----------------
11000 | 0101001101
11001 | 0001111010
11010 | 1100100011
11011 | 1000010100
11100 | 0010100110
11101 | 0110010001
11110 | 1011001000
11111 | 1111111111
-----------+----------------
10000 | 1010011011
10001 | 1110101100
10010 | 0011110101
10011 | 0111000010
10100 | 1101110000
10101 | 1001000111
10110 | 0100011110
10111 | 0000101001接續上面的例子，我們可以發現 01001 對應的錯誤校正碼為 1011100001，把它們併起來，可以得到 010011011100001。
對於格式資訊，我們在將其放上圖片前，必須先與格式資訊的遮罩 101010000010010 進行異或（XOR）運算。
010011011100001 ⟵ format info
XOR 101010000010010 ⟵ mask
----------------------
111001011110011 ⟵ masked format info以上式子的結果即是我們所要的格式資訊，另外提醒一下，這裡的遮罩和上面表格的 mask pattern 無關。
因為格式資訊的遮罩是固定的，讀者可以自己建出算完遮罩後的表，以節省運算時間，例如：
data bits | format info
-----------+-------------------
01001 | 111001011110011
. | .
. | .
. | .放置格式資訊
現在就讓我們填入格式資訊，格式資訊的排放方法如下：
- - - - - - - - E - - - - - - - -
- - - - - - - - D - - - - - - - -
- - - - - - - - C - - - - - - - -
- - - - - - - - B - - - - - - - -
- - - - - - - - A - - - - - - - -
- - - - - - - - 9 - - - - - - - -
- - - - - - - - - - - - - - - - - - - - -
- - - - - - - - 8 - - - - - - - -
0 1 2 3 4 5 - 6 7 7 8 9 A B C D E
-
-
-
-
- - - - - - - - -
- - - - - - - - 6
- - - - - - - - 5
- - - - - - - - 4
- - - - - - - - 3
- - - - - - - - 2
- - - - - - - - 1
- - - - - - - - 0其中 A 表 10，B 表 11，C 表 12，D 表 13，E 表 14，短槓表示先前已經填入的功能圖案，我們由 0 開始，一直填到 E 為止。
附圖為上面範例的實際填入過程，供讀者參考。
最終訊息
相信大家都看過維基百科上關於資料放置的說明圖片，並且會被奇怪的箭頭和數字編號搞得頭昏眼花。
對於了解 QR Code 原理的讀者，不難看出上圖畫得相當嚴謹，不過如果對 QR Code 不那麼熟悉，這些方塊就顯得有些難懂了。
圖片右邊幾個類似經典遊戲俄羅斯方塊的圖案，到底代表著什麼，而這些圖案又是否存在其他的變形呢？就讓我們繼續看下去。
之字形遍歷
之字形遍歷在放置資料中，是相當重要的方法，讓我們先暫時忘掉前面的疑問，專注於下面的範例。
範例一：向上
input:
1, 2
3, 4
5, 6
output:
6, 5, 4, 3, 2, 1觀察輸入與輸出的關係，不難發現起點是右下角的 6，接著往左到 5，在向右上到 4，往左到 3，直到抵達最後的 1，我們可以發現移動軌跡是之字形的。
範例二：向下
input:
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
output:
12, 11, 8, 7, 4, 3, 2, 1, 6, 5, 10, 9我們一樣從右下角的 12 開始，用之字形向上，直到碰到 3 為止，接下來因為沒辦法再往右上移動了，所以要往左邊跳一格來到 2，接著使用反之字形向下，也就是先向左到 1，向右下到 6，向左到 5，重複一樣方法直到碰到 9。
範例三：向上，但左邊沒空間
input:
1
2
3
4
output:
4, 3, 2, 1萬一我們沒辦法向左移動該怎麼辦呢？那就直接往上就行了。我們從下面的 4 開始，因為無法向左移動，所以直接向上，依此規則，直到走到 1 為止。
範例四：向下，但左邊沒空間
input:
1, 2, 3
4, 5, 6
7, 8, 9
10, 11, 12
13, 14, 15
output:
15, 14, 12, 11, 9, 8, 6, 5, 3, 2, 1, 4, 7, 10, 13我們從 15 開始，之字形移動到 2，因為沒辦法再往右上移動，所以向左一格到 1，接下來向下反之字形移動，但是由於左邊沒有空間，所以直接向下，一直到抵達 13 為止。
範例五：有禁入區域
input:
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
13, 14, 15, 16
forbid position
(1, 1), (1, 2), (2, 1), (2, 2)
output:
16, 15, 12, 8, 4, 3, 2, 1, 5, 9, 14, 13從 forbid position 可以發現，input 中的 6, 7, 10 和 11 都是不可進入的區域，所以在進行之字形遍歷時，我們不可以印出位在禁入區域的值，只要我們不印出位在禁入區域的值，看起來就像沒進入禁入區域過。
首先從 16 出發，往左移到 15，往右上到 12，因為 11 不能讀取，我們經過它，但不印出，接著往右上到 8，遵循此原則直到抵達 13。
範例六：跳行（column）
input:
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
13, 14, 15, 16skip column:
1output:
16, 15, 12, 11, 8, 7, 4, 3, 1, 5, 9, 13
跳行的意思是我們要無視掉位於行 1 的所有值，也就是等價於：
input:
1, 3, 4
5, 7, 8
9, 11, 12
13, 15, 16output:
16, 15, 12, 11, 8, 7, 4, 3, 1, 5, 9, 13
不難看出 2、6、10 和 14 消失了，就像被社會性抹殺一樣，現在我們照著範例四的方法就能得到輸出。
放置最終訊息
好了，我們就來解答前面的問題吧！到底方塊代表著什麼，而又有多少變形呢？其實答案是不重要。我們只要能寫出上面之字形遍歷的演算法，根本就不用知道這些東西。
我們在上一篇文章和前面格式資訊的部分，可以得到代表個別圖形的 (r, c, m) 集合，只要將之字形遍歷的演算法稍稍修改，就可以拿來放置最終訊息了。
現在我們讓禁入區域為以前填過的所有圖案的 (r, c, m) 集合，並跳過行 6，開始用之字形放置最終訊息，過程請參考附圖。
注意到行 6 是每種版本 QR Code 必須跳過的行數，並不會因為版本不同而導致需要跳過的行數改變，也就是說，只要跳過行 6，也只需跳過行 6。
附圖使用的最終訊息來自《如何製作 QR Code #5》的完整範例。
結語
到此，我們離完成 QR Code 僅有幾步之遙，敏銳一點的讀者應該會發現，上圖中的白色和黑色看起來有聚在一起的現象，跟平常看到的黑白交錯的 QR Code 有些不同，事實上，為了避免出現連續白色塊和黑色塊的情況，我們需要使用資料遮罩（data masking）來解決問題。
下一篇文章要來介紹資料遮罩，並決定如何從 8 種遮罩樣式中，挑選出最好的那一個，並完成最後的圖片。
感謝你的閱讀，我是 Yeecy，我們下一篇文章見。
