二維碼的設(shè)計(jì)原理和生成規(guī)格

1、二維碼的生成細(xì)節(jié)和原理二維碼又稱QR Code，QR全稱Quick Response，是一個(gè)近幾年來(lái)移動(dòng)設(shè)備上超流行的一種編碼方式，它比傳統(tǒng)的Bar Code條形碼能存更多的信息，也能表示更多的數(shù)據(jù)類型：比如：字符，數(shù)字，日文，中文等等。這兩天學(xué)習(xí)了一下二維碼圖片生成的相關(guān)細(xì)節(jié)，覺(jué)得這個(gè)玩意就 是一個(gè)密碼算法，在此寫一這篇文章 ，揭露一下。供好學(xué)的人一同學(xué)習(xí)之?；A(chǔ)知識(shí)首先，我們先說(shuō)一下二維碼一共有40個(gè)尺寸。官方叫版本Version。Version 1是21 x 21的矩陣，Version 2是 25 x 25的矩陣，Version 3是29的尺寸，每增加一個(gè)version，就會(huì)增加4的尺寸

2、，公式是：(V-1)*4 + 21（V是版本號(hào)） 最高Version 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。下面我們看看一個(gè)二維碼的樣例：定位圖案 Position Detection Pattern是定位圖案，用于標(biāo)記二維碼的矩形大小。這三個(gè)定位圖案有白邊叫Separators for Postion Detection Patterns。之所以三個(gè)而不是四個(gè)意思就是三個(gè)就可以標(biāo)識(shí)一個(gè)矩形了。 Timing Patterns也是用于定位的。緣由是二維碼有40種尺寸，尺寸過(guò)大了后需要有根標(biāo)準(zhǔn)線，不然掃描的時(shí)候可能會(huì)掃歪了。 Alignment Pat

3、terns 只有Version 2以上（包括Version2）的二維碼需要這個(gè)東東，同樣是為了定位用的。功能性數(shù)據(jù) Format Information 存在于全部的尺寸中，用于存放一些格式化數(shù)據(jù)的。 Version Information 在 = Version 7以上，需要預(yù)留兩塊3 x 6的區(qū)域存放一些版本信息。數(shù)據(jù)碼和糾錯(cuò)碼 除了上述的那些地方，剩下的地方存放 Data Code 數(shù)據(jù)碼 和 Error Correction Code 糾錯(cuò)碼。數(shù)據(jù)編碼我們先來(lái)說(shuō)說(shuō)數(shù)據(jù)編碼。QR碼支持如下的編碼：Numeric mode數(shù)字編碼，從0到9。如果需要編碼的數(shù)字的個(gè)數(shù)不是3的倍數(shù)，那么，最后

4、剩下的1或2位數(shù)會(huì)被轉(zhuǎn)成4或7bits，則其它的每3位數(shù)字會(huì)被編成 10，12，14bits，編成多長(zhǎng)還要看二維碼的尺寸（下面有一個(gè)表Table 3說(shuō)明白這點(diǎn)）Alphanumeric mode字符編碼。包括 0-9，大寫的A到Z（沒(méi)有小寫），以及符號(hào)$ % * + . / : 包括空格。這些字符會(huì)映射成一個(gè)字符索引表。如下所示：（其中的SP是空格，Char是字符，Value是其索引值） 編碼的過(guò)程是把字符兩兩分組，然后轉(zhuǎn)成下表的45進(jìn)制，然后轉(zhuǎn)成11bits的二進(jìn)制，如果最后有一個(gè)落單的，那就轉(zhuǎn)成6bits的二進(jìn)制。而編碼模式和 字符的個(gè)數(shù)需要依據(jù)不同的Version尺寸編成9, 11或13

5、個(gè)二進(jìn)制（如下表中Table 3）Byte mode, 字節(jié)編碼，可以是0-255的ISO-8859-1字符。有些二維碼的掃描器可以自動(dòng)檢測(cè)是否是UTF-8的編碼。Kanji mode這是日文編碼，也是雙字節(jié)編碼。同樣，也可以用于中文編碼。日文和漢字的編碼會(huì)減去一個(gè) 值。如：在0X8140 to 0X9FFC中的字符會(huì)減去8140，在0XE040到0XEBBF中的字符要減去0XC140，然后把前兩位拿出來(lái)乘以0XC0，然后再加上后兩位，最 后轉(zhuǎn)成13bit的編碼。如下圖示例：Extended Channel Interpretation (ECI) mode主要用于特別的字符集。并不是全部的掃

6、描器都支持這種編碼。Structured Append mode用于混合編碼，也就是說(shuō)，這個(gè)二維碼中包含了多種編碼格式。FNC1 mode這種編碼方式主要是給一些特別的工業(yè)或行業(yè)用的。比如GS1條形碼之類的。簡(jiǎn)潔起見(jiàn)，后面三種不會(huì)在本文 中商量。下面兩張表中， Table 2 是各個(gè)編碼格式的“編號(hào)”，這個(gè)東西要寫在Format Information中。注：中文是1101 Table 3 表示了，不同版本（尺寸）的二維碼，對(duì)于，數(shù)字，字符，字節(jié)和Kanji模式下，對(duì)于單個(gè)編碼的2進(jìn)制的位數(shù)。（在二維碼的規(guī)格說(shuō)明書(shū)中，有各種各樣的編碼規(guī)范表，后面還會(huì)提到）下面我們看幾個(gè)示例，示例一：數(shù)字編碼在

7、Version 1的尺寸下，糾錯(cuò)級(jí)別為H的情況下，編碼： 012345671. 把上述數(shù)字分成三組: 012 345 672. 把他們轉(zhuǎn)成二進(jìn)制: 012 轉(zhuǎn)成 0000001100； 345 轉(zhuǎn)成 0101011001； 67 轉(zhuǎn)成 1000011。3. 把這三個(gè)二進(jìn)制串起來(lái): 0000001100 0101011001 10000114. 把數(shù)字的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (version 1-H是10 bits ):8個(gè)數(shù)字的二進(jìn)制是 00000010005. 把數(shù)字編碼的標(biāo)志0001和第4步的編碼加到前面: 00 0101011001 1000011示例二：字符編碼在Version 1的尺寸下，

8、糾錯(cuò)級(jí)別為H的情況下，編碼: AC-421. 從字符索引表中找到 AC-42 這五個(gè)字條的索引 (10,12,41,4,2)2. 兩兩分組: (10,12) (41,4) (2)3.把每一組轉(zhuǎn)成11bits的二進(jìn)制:(10,12) 10*45+12 等于 462 轉(zhuǎn)成 (41,4) 41*45+4 等于 1849 轉(zhuǎn)成 11100111001(2) 等于 2 轉(zhuǎn)成 0000104. 把這些二進(jìn)制連接起來(lái)： 11100111001 0000105. 把字符的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (Version 1-H為9 bits ):5個(gè)字符，5轉(zhuǎn)成 0000001016. 在頭上加上編碼標(biāo)識(shí) 0010 和第5步

9、的個(gè)數(shù)編碼: 01 11100111001 000010結(jié)束符和補(bǔ)齊符假如我們有個(gè)HELLO WORLD的字符串要編碼，依據(jù)上面的示例二，我們可以得到下面的編碼，編碼字符數(shù)HELLO WORLD的編碼0010000001011 10001011100 10110111100 001101我們還要加上結(jié)束符：編碼字符數(shù)HELLO WORLD的編碼結(jié)束0010000001011 10001011100 10110111100 0011010000按8bits重排如果全部的編碼加起來(lái)不是8個(gè)倍數(shù)我們還要在后面加上足夠的0，比如上面一共有78個(gè)bits，所以，我們還要加上2個(gè)0，然后按8個(gè)bits分好

10、組：00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000補(bǔ)齊碼（Padding Bytes）最后，如果如果還沒(méi)有達(dá)到我們最大的bits數(shù)的限制，我們還要加一些補(bǔ)齊碼（Padding Bytes），Padding Bytes就是重復(fù)下面的兩個(gè)bytes：11101100 00010001 （這兩個(gè)二進(jìn)制轉(zhuǎn)成十進(jìn)制是236和17，我也不知道為什么，只知道Spec上是這么寫的）關(guān)于每一個(gè)Version的每一種糾錯(cuò)級(jí)別的最大Bits限 制，可以參看QR Code Spec的第2

11、8頁(yè)到32頁(yè)的Table-7一表。假設(shè)我們需要編碼的是Version 1的Q糾錯(cuò)級(jí)，那么，其最大需要104個(gè)bits，而我們上面只有80個(gè)bits，所以，還需要24個(gè)bits，也就是需要3個(gè)Padding Bytes，我們就添加三個(gè)，于是得到下面的編碼：00100 00001 11 01001101 0100011101100 00010糾錯(cuò)碼上面我們說(shuō)到了一些糾錯(cuò)級(jí)別，Error Correction Code Level，二維碼中有四種級(jí)別的糾錯(cuò)，這就是為什么二維碼有殘缺還能掃出來(lái)，也就是為什么有人在二維碼的中心位置加入圖標(biāo)。錯(cuò)誤修正容量L水平7%的字碼可被修正M水平15%的字碼可被修正Q

12、水平25%的字碼可被修正H水平30%的字碼可被修正那么，QR是怎么對(duì)數(shù)據(jù)碼加上糾錯(cuò)碼的？首先，我們需要對(duì)數(shù)據(jù)碼進(jìn)行分組，也就是分成不同的Block，然后對(duì)各個(gè)Block進(jìn)行糾錯(cuò)編碼，對(duì)于如何分組，我們可以查看QR Code Spec的第33頁(yè)到44頁(yè)的Table-13到Table-22的定義表。注意最后兩列： Number of Error Code Correction Blocks：需要分多少個(gè)塊。 Error Correction Code Per Blocks：每一個(gè)塊中的code個(gè)數(shù)，所謂的code的個(gè)數(shù)，也就是有多少個(gè)8bits的字節(jié)。舉個(gè)例子：上述的Version 5 + Q糾錯(cuò)

13、級(jí)：需要4個(gè)Blocks（2個(gè)Blocks為一組，共兩組），頭一組的兩個(gè)Blocks中各15個(gè)bits數(shù)據(jù) + 各 9個(gè)bits的糾錯(cuò)碼（注：表中的codewords就是一個(gè)8bits的byte）（再注：最后一例中的（c, k, r ）的公式為：c = k + 2 * r，由于后腳注解釋了：糾錯(cuò)碼的容量小于糾錯(cuò)碼的一半）下圖給一個(gè)5-Q的示例（由于二進(jìn)制寫起來(lái)會(huì)讓表格太大，所以，我都用了十進(jìn)制）組塊數(shù)據(jù)對(duì)每個(gè)塊的糾錯(cuò)碼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

14、 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

15、 236 17 236 17 236235 159 5 173 24 147 59 33 106 40 255 172 82 2 131 32 178 236注：二維碼的糾錯(cuò)碼主要是通過(guò)Reed-Solomon error correction（里 德-所羅門糾錯(cuò)算法）來(lái)實(shí)現(xiàn)的。對(duì)于這個(gè)算法，對(duì)于我來(lái)說(shuō)是相當(dāng)?shù)暮?jiǎn)單，里面有很多的數(shù)學(xué)計(jì)算，比如：多項(xiàng)式除法，把1-255的數(shù)映射成2的n次方 （0=n=255）的伽羅瓦域Galois Field之類的神一樣的東西，以及基于這些基礎(chǔ)的糾錯(cuò)數(shù)學(xué)公式，由于我的數(shù)據(jù)基礎(chǔ)差，對(duì)于我來(lái)說(shuō)太過(guò)簡(jiǎn)單，所以我一時(shí)半會(huì)兒還有點(diǎn)沒(méi)搞明白，還在學(xué)習(xí) 中，所以，我在這里就不

16、展開(kāi)說(shuō)這些東西了。還請(qǐng)大家見(jiàn)諒了。（當(dāng)然，如果有伴侶很明白，也繁請(qǐng)教教我）最終編碼穿插放置如果你以為我們可以開(kāi)頭畫(huà)圖，你就錯(cuò)了。二維碼的混亂技術(shù)還沒(méi)有玩完，它還要把數(shù)據(jù)碼和糾錯(cuò)碼的各個(gè)codewords交替放在一起。如何交替呢，規(guī)章如下：對(duì)于數(shù)據(jù)碼：把每個(gè)塊的第一個(gè)codewords先拿出來(lái)按順度排列好，然后再取第一塊的其次個(gè)，如此類推。如：上述示例中的Data Codewords如下：塊 167857013487388519411950618610338塊 224624666711813424273886221981991466塊 318223024711950711813487388261

17、34151507塊 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對(duì)于糾錯(cuò)碼，也是一樣：塊 121319911451152472412232292481541171541118616111139塊 28720496602021821241572001342712920917163163120133塊 314811617

18、721276133752422387619523018910108240192141塊 423515951732414759331064025517282213132178236和數(shù)據(jù)碼取的一樣，得到：213，87，148，235，199，204，116，159， 39，133，141，236然后，再把這兩組放在一起（糾錯(cuò)碼放在數(shù)據(jù)碼之后）得到：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, 19

19、4, 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, 2

20、38, 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, 236Remainder Bits最后再加上ReminderBits，對(duì)于某些Version的QR，上面的還不夠長(zhǎng)度，還要加上Remainder Bits，比如：上述的5Q版的二維碼，還要加上7個(gè)bits，Remainder Bits加零就好了。關(guān)于哪些

21、Version需要多少個(gè)Remainder bit，可以參看QR Code Spec的第15頁(yè)的Table-1的定義表。畫(huà)二維碼圖Position Detection Pattern首先，先把Position Detection圖案畫(huà)在三個(gè)角上。Alignment Pattern然后，再把Alignment圖案畫(huà)上關(guān)于Alignment的位置，可以查看QR Code Spec的第81頁(yè)的Table-E.1的定義表（下表是不完全表格）下圖是依據(jù)上述表格中的Version8的一個(gè)例子（6，24，42）Timing Pattern接下來(lái)是Timing Pattern的線（這個(gè)不用多說(shuō)了）Format Information再接下來(lái)是Formation Information，下圖中的藍(lán)色部分。Format Information是一個(gè)15個(gè)bits的信息，每一個(gè)bit的位置如下圖所示：（注意圖中的Dark Module，那是永久消失的）這15個(gè)bits中包括： 5個(gè)數(shù)據(jù)bits：其中，2個(gè)bits用于表示使用什么樣的Error Correction Level， 3個(gè)bits表示使用什么樣的Mask 10個(gè)糾錯(cuò)bits。