二維碼又稱QR Code，QR全稱Quick Response，是一個近幾年來移動設備上超流行的一種編碼方式，它比傳統的Bar Code條形碼能存更多的信息，也能表示更多的數據類型：比如：字符，數字，日文，中文等等。這兩天學習了一下二維碼圖片生成的相關細節，覺得這個玩意就是一個密碼算法，在此寫一這篇文章 ，揭露一下。供好學的人一同學習之。

基礎知識

首先，我們先說一下二維碼一共有40個尺寸。官方叫版本Version。Version 1是21 x 21的矩陣，Version 2是 25 x 25的矩陣，Version 3是29的尺寸，每增加一個version，就會增加4的尺寸，公式是：(V-1)*4 21(V是版本号) 最高Version 40，(40-1)*4 21 = 177，所以最高是177 x 177 的正方形。

下面我們看看一個二維碼的樣例：

定位圖案

• Position Detection Pattern是定位圖案，用于标記二維碼的矩形大小。這三個定位圖案有白邊叫Separators for Postion Detection Patterns。之所以三個而不是四個意思就是三個就可以标識一個矩形了。
• Timing Patterns也是用于定位的。原因是二維碼有40種尺寸，尺寸過大了後需要有根标準線，不然掃描的時候可能會掃歪了。
• Alignment Patterns 隻有Version 2以上(包括Version2)的二維碼需要這個東東，同樣是為了定位用的。
• 功能性數據
• Format Information 存在于所有的尺寸中，用于存放一些格式化數據的。
• Version Information 在 >= Version 7以上，需要預留兩塊3 x 6的區域存放一些版本信息。
• 數據碼和糾錯碼
• 除了上述的那些地方，剩下的地方存放 Data Code 數據碼 和 Error Correction Code 糾錯碼。
• 數據編碼
• 我們先來說說數據編碼。QR碼支持如下的編碼：
• Numeric mode 數字編碼，從0到9。如果需要編碼的數字的個數不是3的倍數，那麼，最後剩下的1或2位數會被轉成4或7bits，則其它的每3位數字會被編成 10，12，14bits，編成多長還要看二維碼的尺寸(下面有一個表Table 3說明了這點)
• Alphanumeric mode 字符編碼。包括 0-9，大寫的A到Z(沒有小寫)，以及符号$ % * - . / : 包括空格。這些字符會映射成一個字符索引表。如下所示：(其中的SP是空格，Char是字符，Value是其索引值) 編碼的過程是把字符兩兩分組，然後轉成下表的45進制，然後轉成11bits的二進制，如果最後有一個落單的，那就轉成6bits的二進制。而編碼模式和字符的個數需要根據不同的Version尺寸編成9, 11或13個二進制(如下表中Table 3)

• Byte mode, 字節編碼，可以是0-255的ISO-8859-1字符。有些二維碼的掃描器可以自動檢測是否是UTF-8的編碼。
• Kanji mode 這是日文編碼，也是雙字節編碼。同樣，也可以用于中文編碼。日文和漢字的編碼會減去一個值。如：在0X8140 to 0X9FFC中的字符會減去8140，在0XE040到0XEBBF中的字符要減去0XC140，然後把結果前兩個16進制位拿出來乘以0XC0，然後再加上後兩個16進制位，最後轉成13bit的編碼。如下圖示例：

• Extended Channel Interpretation (ECI) mode 主要用于特殊的字符集。并不是所有的掃描器都支持這種編碼。
• Structured Append mode 用于混合編碼，也就是說，這個二維碼中包含了多種編碼格式。
• FNC1 mode 這種編碼方式主要是給一些特殊的工業或行業用的。比如GS1條形碼之類的。
• 簡單起見，後面三種不會在本文 中讨論。
• 下面兩張表中，
• Table 2 是各個編碼格式的“編号”，這個東西要寫在Format Information中。注：中文是1101
• Table 3 表示了，不同版本(尺寸)的二維碼，對于，數字，字符，字節和Kanji模式下，對于單個編碼的2進制的位數。(在二維碼的規格說明書中，有各種各樣的編碼規範表，後面還會提到)

• 下面我們看幾個示例，
• 示例一：數字編碼
• 在Version 1的尺寸下，糾錯級别為H的情況下，編碼： 01234567
• 1. 把上述數字分成三組: 012 345 67
• 2. 把他們轉成二進制: 012 轉成 0000001100； 345 轉成 0101011001； 67 轉成 1000011。
• 3. 把這三個二進制串起來: 0000001100 0101011001 1000011
• 4. 把數字的個數轉成二進制 (version 1-H是10 bits ): 8個數字的二進制是 0000001000
• 5. 把數字編碼的标志0001和第4步的編碼加到前面: 0001 0000001000 0000001100 0101011001 1000011
• 示例二：字符編碼
• 在Version 1的尺寸下，糾錯級别為H的情況下，編碼: AC-42
• 1. 從字符索引表中找到 AC-42 這五個字條的索引 (10,12,41,4,2)
• 2. 兩兩分組: (10,12) (41,4) (2)
• 3.把每一組轉成11bits的二進制:
• (10,12) 10*45 12 等于 462 轉成 00111001110
• (41,4) 41*45 4 等于 1849 轉成 11100111001
• (2) 等于 2 轉成 000010
• 4. 把這些二進制連接起來：00111001110 11100111001 000010
• 5. 把字符的個數轉成二進制 (Version 1-H為9 bits ): 5個字符，5轉成 000000101
• 6. 在頭上加上編碼标識 0010 和第5步的個數編碼: 0010 000000101 00111001110 11100111001 000010
• 結束符和補齊符
• 假如我們有個HELLO WORLD的字符串要編碼，根據上面的示例二，我們可以得到下面的編碼，
• 編碼字符數HELLO WORLD的編碼001000000101101100001011 01111000110 10001011100 10110111000 10011010100 001101
• 我們還要加上結束符：
• 編碼字符數HELLO WORLD的編碼結束001000000101101100001011 01111000110 10001011100 10110111000 10011010100 0011010000
• 按8bits重排
• 如果所有的編碼加起來不是8個倍數我們還要在後面加上足夠的0，比如上面一共有78個bits，所以，我們還要加上2個0，然後按8個bits分好組：
• 00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000
• 補齊碼(Padding Bytes)
• 最後，如果如果還沒有達到我們最大的bits數的限制，我們還要加一些補齊碼(Padding Bytes)，Padding Bytes就是重複下面的兩個bytes：11101100 00010001 (這兩個二進制轉成十進制是236和17，我也不知道為什麼，隻知道Spec上是這麼寫的)關于每一個Version的每一種糾錯級别的最大Bits限制，可以參看QR Code Spec的第28頁到32頁的Table-7一表。
• 假設我們需要編碼的是Version 1的Q糾錯級，那麼，其最大需要104個bits，而我們上面隻有80個bits，所以，還需要補24個bits，也就是需要3個Padding Bytes，我們就添加三個，于是得到下面的編碼：
• 00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100
• 上面的編碼就是數據碼了，叫Data Codewords，每一個8bits叫一個codeword，我們還要對這些數據碼加上糾錯信息。
• 糾錯碼
• 上面我們說到了一些糾錯級别，Error Correction Code Level，二維碼中有四種級别的糾錯，這就是為什麼二維碼有殘缺還能掃出來，也就是為什麼有人在二維碼的中心位置加入圖标。
• 錯誤修正容量L水平7%的字碼可被修正M水平15%的字碼可被修正Q水平25%的字碼可被修正H水平30%的字碼可被修正
• 那麼，QR是怎麼對數據碼加上糾錯碼的？首先，我們需要對數據碼進行分組，也就是分成不同的Block，然後對各個Block進行糾錯編碼，對于如何分組，我們可以查看QR Code Spec的第33頁到44頁的Table-13到Table-22的定義表。注意最後兩列：
• Number of Error Code Correction Blocks ：需要分多少個塊。
• Error Correction Code Per Blocks：每一個塊中的code個數，所謂的code的個數，也就是有多少個8bits的字節。

• 舉個例子：上述的Version 5 Q糾錯級：需要4個Blocks(2個Blocks為一組，共兩組)，頭一組的兩個Blocks中各15個bits數據 各 9個bits的糾錯碼(注：表中的codewords就是一個8bits的byte)(再注：最後一例中的(c, k, r )的公式為：c = k 2 * r，因為後腳注解釋了：糾錯碼的容量小于糾錯碼的一半)
• 下圖給一個5-Q的示例(因為二進制寫起來會讓表格太大，所以，我都用了十進制，我們可以看到每一塊的糾錯碼有18個codewords，也就是18個8bits的二進制數)
• 組塊數據對每個塊的糾錯碼1167 85 70 134 87 38 85 194 119 50 6 18 6 103 38213 199 11 45 115 247 241 223 229 248 154 117 154 111 86 161 111 392246 246 66 7 118 134 242 7 38 86 22 198 199 146 687 204 96 60 202 182 124 157 200 134 27 129 209 17 163 163 120 13321182 230 247 119 50 7 118 134 87 38 82 6 134 151 50 7148 116 177 212 76 133 75 242 238 76 195 230 189 10 108 240 192 141270 247 118 86 194 6 151 50 16 236 17 236 17 236 17 236235 159 5 173 24 147 59 33 106 40 255 172 82 2 131 32 178 236
• 注：二維碼的糾錯碼主要是通過Reed-Solomon error correction(裡德-所羅門糾錯算法)來實現的。對于這個算法，對于我來說是相當的複雜，裡面有很多的數學計算，比如：多項式除法，把1-255的數映射成2的n次方(0<=n<=255)的伽羅瓦域Galois Field之類的神一樣的東西，以及基于這些基礎的糾錯數學公式，因為我的數據基礎差，對于我來說太過複雜，所以我一時半會兒還有點沒搞明白，還在學習中，所以，我在這裡就不展開說這些東西了。還請大家見諒了。(當然，如果有朋友很明白，也繁請教教我)
• 最終編碼
• 穿插放置
• 如果你以為我們可以開始畫圖，你就錯了。二維碼的混亂技術還沒有玩完，它還要把數據碼和糾錯碼的各個codewords交替放在一起。如何交替呢，規則如下：
• 對于數據碼：把每個塊的第一個codewords先拿出來按順度排列好，然後再取第一塊的第二個，如此類推。如：上述示例中的Data Codewords如下：
• 塊 167857013487388519411950618610338
• 塊 224624666711813424273886221981991466
• 塊 31822302471195071181348738826134151507塊 4702471188619461515016236172361723617236
• 我們先取第一列的：67， 246， 182， 70
• 然後再取第二列的：67， 246， 182， 70， 85，246，230 ，247
• 如此類推：67， 246， 182， 70， 85，246，230 ，247 ……… ……… ，38，6，50，17，7，236
• 對于糾錯碼，也是一樣：
• 塊 121319911451152472412232292481541171541118616111139塊 28720496602021821241572001342712920917163163120133塊 314811617721276133752422387619523018910108240192141塊 423515951732414759331064025517282213132178236
• 和數據碼取的一樣，得到：213，87，148，235，199，204，116，159，…… …… 39，133，141，236
• 然後，再把這兩組放在一起(糾錯碼放在數據碼之後)得到：
• 67, 246, 182, 70, 85, 246, 230, 247, 70, 66, 247, 118, 134, 7, 119, 86, 87, 118, 50, 194, 38, 134, 7, 6, 85, 242, 118, 151, 194, 7, 134, 50, 119, 38, 87, 16, 50, 86, 38, 236, 6, 22, 82, 17, 18, 198, 6, 236, 6, 199, 134, 17, 103, 146, 151, 236, 38, 6, 50, 17, 7, 236, 213, 87, 148, 235, 199, 204, 116, 159, 11, 96, 177, 5, 45, 60, 212, 173, 115, 202, 76, 24, 247, 182, 133, 147, 241, 124, 75, 59, 223, 157, 242, 33, 229, 200, 238, 106, 248, 134, 76, 40, 154, 27, 195, 255, 117, 129, 230, 172, 154, 209, 189, 82, 111, 17, 10, 2, 86, 163, 108, 131, 161, 163, 240, 32, 111, 120, 192, 178, 39, 133, 141, 236
• 這就是我們的數據區。
• Remainder Bits
• 最後再加上Reminder Bits，對于某些Version的QR，上面的還不夠長度，還要加上Remainder Bits，比如：上述的5Q版的二維碼，還要加上7個bits，Remainder Bits加零就好了。關于哪些Version需要多少個Remainder bit，可以參看QR Code Spec的第15頁的Table-1的定義表。
• 畫二維碼圖
• Position Detection Pattern
• 首先，先把Position Detection圖案畫在三個角上。(無論Version如何，這個圖案的尺寸就是這麼大)

• Alignment Pattern
• 然後，再把Alignment圖案畫上(無論Version如何，這個圖案的尺寸就是這麼大)

• 關于Alignment的位置，可以查看QR Code Spec的第81頁的Table-E.1的定義表(下表是不完全表格)

• 下圖是根據上述表格中的Version8的一個例子(6，24，42)

• Timing Pattern
• 接下來是Timing Pattern的線(這個不用多說了)

• Format Information
• 再接下來是Formation Information，下圖中的藍色部分。

• Format Information是一個15個bits的信息，每一個bit的位置如下圖所示：(注意圖中的Dark Module，那是永遠出現的)

• 這15個bits中包括：
• 5個數據bits：其中，2個bits用于表示使用什麼樣的Error Correction Level， 3個bits表示使用什麼樣的Mask
• 10個糾錯bits。主要通過BCH Code來計算
• 然後15個bits還要與101010000010010做XOR操作。這樣就保證不會因為我們選用了00的糾錯級别和000的Mask，從而造成全部為白色，這會增加我們的掃描器的圖像識别的困難。
• 下面是一個示例：

• 關于Error Correction Level如下表所示：

• 關于Mask圖案如後面的Table 23所示。
• Version Information
• 再接下來是Version Information(版本7以後需要這個編碼)，下圖中的藍色部分。

• Version Information一共是18個bits，其中包括6個bits的版本号以及12個bits的糾錯碼，下面是一個示例：

• 而其填充位置如下：

• 數據和數據糾錯碼
• 然後是填接我們的最終編碼，最終編碼的填充方式如下：從左下角開始沿着紅線填我們的各個bits，1是黑色，0是白色。如果遇到了上面的非數據區，則繞開或跳過。

• 掩碼圖案
• 這樣下來，我們的圖就填好了，但是，也許那些點并不均衡，如果出現大面積的空白或黑塊，會告訴我們掃描識别的困難。所以，我們還要做Masking操作(靠，還嫌不複雜)QR的Spec中說了，QR有8個Mask你可以使用，如下所示：其中，各個mask的公式在各個圖下面。所謂mask，說白了，就是和上面生成的圖做XOR操作。Mask隻會和數據區進行XOR，不會影響功能區。(注：選擇一個合适的Mask也是有算法的)

• 其Mask的标識碼如下所示：(其中的i,j分别對應于上圖的x,y)

• 下面是Mask後的一些樣子，我們可以看到被某些Mask XOR了的數據變得比較零散了。

• Mask過後的二維碼就成最終的圖了。
• 好了，大家可以去嘗試去寫一下QR的編碼程序，當然，你可以用網上找個Reed Soloman的糾錯算法的庫，或是看看别人的源代碼是怎麼實現這個繁鎖的編碼。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!