完整版二維碼的生成細(xì)節(jié)和原理

1、二維碼的生成細(xì)節(jié)和原理2013-10-29 09:46 陳皓 酷殼網(wǎng) 字號(hào)：T | T收視Q二維碼又稱QR Code , QR全稱Quick Response，是一個(gè)近幾年來移動(dòng)設(shè)備上超流行的一種編碼方式，它比傳統(tǒng)的Bar Code條形碼能存更多的信息，也能表示更多的數(shù)據(jù)類型AD : 51CTO學(xué)院：IT精品課程在線看!二維碼又稱QR Code，QR全稱Quick Response，是一個(gè)近幾年來移動(dòng)設(shè)備上超流行的一種編碼方式，它比傳統(tǒng)的 Bar Code條形碼能存更多的信息，也能 表示更多的數(shù)據(jù)類型：比如：字符，數(shù)字，日文，中文等等。這兩天學(xué)習(xí)了一下 二維碼圖片生成的相關(guān)細(xì)節(jié)，覺得這個(gè)玩意就

2、是一個(gè)密碼算法，在此寫一這篇文章，揭露一下。供好學(xué)的人一同學(xué)習(xí)之。關(guān)于 QR Code Specification，可參看這個(gè) PDF:http:/raide nii. net/files/datasheets/misc/qr_code.pdf基礎(chǔ)知識(shí)首先，我們先說一下二維碼一共有 40個(gè)尺寸。官方叫版本Version 。Version 1是21 x 21的矩陣，Version 2 是25 x 25的矩陣，Version 3 是29的尺寸，每增加一個(gè)version，就會(huì)增加4的尺寸，公式是：(V-1)*4 + 21( V是版本號(hào))最高 Version 40 ， (40-1)*4+21 = 17

3、7 ，所以最高是 177 x 177 的正方形。F面我們看看一個(gè)二維碼的樣例:Pcsiiion DrteciLon 、Quiet ZoneFuncEionzncjdinjRegionSepara：ar5 rir P= Version 7 以上，需要預(yù)留兩塊 3 x 6 的區(qū)域存放一些版本信息。數(shù)據(jù)碼和糾錯(cuò)碼? 除了上述的那些地方，剩下的地方存放 Data Code 數(shù)據(jù)碼 和 ErrorCorrection Code 糾錯(cuò)碼。數(shù)據(jù)編碼我們先來說說數(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 說明了這點(diǎn)）Alphanumeric mode字符編碼。包括 0-9，大寫的A到Z （沒有小寫），以及符號(hào)$ % * +- . / :包括空格。這些字符會(huì)映射成一個(gè)字符索引表。如下所示：（其中的 SP 是空格， Char 是字符， Value 是其索引值） 編碼的過程是把 字符兩兩分組， 然后轉(zhuǎn)成下表的 45 進(jìn)制，然后轉(zhuǎn)成 11bits 的二進(jìn)制， 如果最后 有一個(gè)落單的，那就轉(zhuǎn)成 6bits 的二進(jìn)制。而編碼模式和 字符

5、的個(gè)數(shù)需要根據(jù) 不同的 Version 尺寸編成 9, 11 或13 個(gè)二進(jìn)制（如下表中 Table 3 ）Chsr : *曲亡血ULFHharharVa U0Char陽EiOtarVhI*亡hsVali.e0 06&G12I16024U : 30SP36-421 : 177D13J19p25V : 31s37f432 : 29aE14K20Q26W : 32%38443 - 3ggF15L21R27X : 33*対4 4A出16M22S28Y : 34+4C5 ! 5BH17N23T29Z : 3541Byte mode,字節(jié)編碼，可以是0-255的ISO-8859-1字符。有些二維碼的掃描

6、器可以自動(dòng)檢測(cè)是否是 UTF-8的編碼。Kanji mode這是日文編碼，也是雙字節(jié)編碼。同樣，也可以用于中文編碼。日文和漢字的編碼會(huì)減去一個(gè) 值。如：在0X8140 to 0X9FFC 中的字符會(huì)減去8140，在0XE040到0XEBBF中的字符要減去0XC140，然后把前兩位拿出來乘以0XC0，然后再加上后兩位，最 后轉(zhuǎn)成13bit的編碼。如下圖示例：Input charactsr占”(Shrit JIS 舟Iue)935FE4AA1. Scbiact&UC orC14C9W-8140-121FE*AA-C14O = 236AZ Multiply m s o. by 012 x CO DS

7、O23xCOtA4OlAddlsh.O84 + 1F-D9F1A40 + 6A = IAAA4. Coi/ento 13 bit binaryDD9F- 01101 1001 11111AAA41 101010101010Exte nded Cha nnel In terpretatio n (ECI) mode主要用于特殊的字符集。并不是所有的掃描器都支持這種編碼。Structured Appe nd mode用于混合編碼，也就是說，這個(gè)二維碼中包含了多種編碼格式。FNC1 mode這種編碼方式主要是給一些特殊的工業(yè)或行業(yè)用的。比如GS1條形碼之類的簡(jiǎn)單起見，后面三種不會(huì)在本文中討論F面兩張

8、表中,? Table 2是各個(gè)編碼格式的“編號(hào)”，這個(gè)東西要寫在FormatIn formatio n 中。注：中文是 1101? Table 3表示了，不同版本（尺寸）的二維碼，對(duì)于，數(shù)字，字符，字節(jié)和Kanji模式下，對(duì)于單個(gè)編碼的2進(jìn)制的位數(shù)。（在二維碼的規(guī)格說明書中，有各種各樣的編碼規(guī)范表，后面還會(huì)提到）Table 2 Mode indrcatorsModeIndicatorECI0111NurTieTic0001Alphanumenc010B-bit Ryte0100Kanji1000Structured Append0011FNC101 Oi (First position 100

9、1 (Second position)Terminator (End of Message)000Table 3 Number of in Ctiaracter Count IndicatorVersionNumenc MkxfeAlpha numeric ModeB-twt Byte ModeKanjiMode1 tofi109aB10tc261241161027 to 4014131612F面我們看幾個(gè)示例,示例一：數(shù)字編碼在Version 1的尺寸下，糾錯(cuò)級(jí)別為 H的情況下，編碼：012345671. 把上述數(shù)字分成三組：012 345 672. 把他們轉(zhuǎn)成二進(jìn)制 : 012 轉(zhuǎn)成 00

10、00001100 ； 345 轉(zhuǎn)成 0101011001 ； 67 轉(zhuǎn)成 1000011 。3. 把這三個(gè)二進(jìn)制串起來 : 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 步的編碼加到前面 : 0001 0000001000 0000001100 0101011001 1000011示例二：字符編碼在 Version 1 的尺寸下，糾錯(cuò)級(jí)別為 H 的情況下，編碼 : AC-421. 從字符索引表中找到 AC-42 這

11、五個(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)成 00111001110(41,4) 41*45+4 等于 1849 轉(zhuǎn)成 11100111001(2) 等于 2 轉(zhuǎn)成 0000104. 把這些二進(jìn)制連接起來： 00111001110 11100111001 0000105. 把字符的個(gè)數(shù)轉(zhuǎn)成二進(jìn)制 (Version 1-H 為 9 bits ): 5 個(gè)字符，5 轉(zhuǎn)成0000001016. 在頭上加上編碼標(biāo)識(shí) 0010 和第 5 步的個(gè)數(shù)編碼

12、: 0010 00000010100111001110 11100111001 000010結(jié)束符和補(bǔ)齊符假如我們有個(gè) HELLO WORLD 的字符串要編碼，根據(jù)上面的示例二，我們可以 得到下面的編碼，編碼 字符數(shù) HELLO WORLD 的編碼01100001011 01111000110 100010111000010 00000101110110111000 10011010100 001101我們還要加上結(jié)束符：編碼 字符數(shù) HELLO WORLD 的編碼 結(jié)束01100001011 01111000110 100010111000010 0000010110000101101110

13、00 10011010100 001101按 8bits 重排如果所有的編碼加起來不是 8 個(gè)倍數(shù)我們還要在后面加上足夠的 0，比如上面一 共有 78 個(gè) bits ，所以，我們還要加上 2 個(gè) 0，然后按 8 個(gè) bits 分好組：00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 010000 00補(bǔ)齊碼( Padding Bytes ) 最后，如果如果還沒有達(dá)到我們最大的 bits 數(shù)的限制，我們還要加一些補(bǔ)齊碼 ( Padding Bytes )， Padding Bytes

14、就是重復(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 的第 28 頁到 32 頁的 Table-7 一表。假設(shè)我們需要編碼的是 Version 1 的 Q 糾錯(cuò)級(jí)， 那么，其最大需要 104 個(gè) bits ， 而我們上面只有 80 個(gè) bits ，所以，還需要 24 個(gè) bits ，也就是需要 3 個(gè) Padding Bytes ，我們就添加三個(gè)，于是得到下面的編碼：0010

15、0000 01011011 00001011 01111000 11010001 01110010 1101110001001101 01000011 0100000011101100 00010001 11101100糾錯(cuò)碼上面我們說到了一些糾錯(cuò)級(jí)別， Error Correction Code Level ，二維碼中有四 種級(jí)別的糾錯(cuò)， 這就是為什么二維碼有殘缺還能掃出來， 也就是為什么有人在二 維碼的中心位置加入圖標(biāo)。錯(cuò)誤修正容量L 水平 7% 的字碼可被修正M 水平 15% 的字碼可被修正Q 水平 25% 的字碼可被修正H 水平 30% 的字碼可被修正那么，QR是怎么對(duì)數(shù)據(jù)碼加上糾錯(cuò)碼

16、的？首先，我們需要對(duì)數(shù)據(jù)碼進(jìn)行分組, 也就是分成不同的Block，然后對(duì)各個(gè)Block進(jìn)行糾錯(cuò)編碼，對(duì)于如何分組，我們可以查看 QR Code Spec 的第33頁到44頁的Table-13 到Table-22 的定義表。注意最后兩列：:需要分多少個(gè)塊Number of Error Code Correct ion BlocksError Correction Code Per Blocks :每一個(gè)塊中的 code 個(gè)數(shù)，所謂的code的個(gè)數(shù)，也就是有多少個(gè)8bits的字節(jié)5134L2G1(134108.13)M462(614112)Q1222(33.15.9)(34.16.9)H8622(

17、33J1J1)(34J2.11)a172LP 362(66,68,9)|M644(43.27,8Q94(43J9.12)H1124(43,15,14)A (c. k. r)： e - total nurrber of eodeuvordsk = number of data codewords r nunber of error correction capecityb Error ccrrectian capacily less liian ha f be number of error coreclon codewords b reduce prCtb&bilrly dt旳之彥0血?jiǎng)?wù)舉個(gè)例

18、子：上述的 Version 5 + Q 糾錯(cuò)級(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 ，因?yàn)楹竽_注解釋了：糾錯(cuò)碼的容量小于糾 錯(cuò)碼的一半）下圖給一個(gè) 5-Q 的示例（因?yàn)槎M(jìn)制寫起來會(huì)讓表格太大，所以，我都用了十進(jìn)制）組 塊數(shù)據(jù) 對(duì)每個(gè)塊的糾錯(cuò)碼67 85 70 134 87 38 85 1941119 50 6 18 6 103 381246 246 66 7

19、118 134 242 7238 86 22 198 199 146 6213 199 11 45 115 247 241 223 229248 154 117 154 111 86 161 111 3987 204 96 60 202 182 124 157 200134 27 129 209 17 163 163 120 133182 230 247 119 50 7 118 134187 38 82 6 134 151 50 7270 247 118 86 194 6 151 50216 236 17 236 17 236 17 236148 116 177 212 76 133 75

20、242 23876 195 230 189 10 108 240 192 141235 159 5 173 24 147 59 33 106 40255 172 82 2 131 32 178 236注：二維碼的糾錯(cuò)碼主要是通過 Reed-Solomon error correction （里 德- 所 羅門糾錯(cuò)算法）來實(shí)現(xiàn)的。對(duì)于這個(gè)算法，對(duì)于我來說是相當(dāng)?shù)膹?fù)雜，里面有很 多的數(shù)學(xué)計(jì)算，比如：多項(xiàng)式除法，把 1-255 的數(shù)映射成 2 的 n 次方 （0=n=255 ）的伽羅瓦域 Galois Field 之類的神一樣的東西， 以及基于這些 基礎(chǔ)的糾錯(cuò)數(shù)學(xué)公式， 因?yàn)槲业臄?shù)據(jù)基礎(chǔ)差， 對(duì)于我

21、來說太過復(fù)雜， 所以我一時(shí) 半會(huì)兒還有點(diǎn)沒搞明白， 還在學(xué)習(xí) 中，所以，我在這里就不展開說這些東西了。 還請(qǐng)大家見諒了。（當(dāng)然，如果有朋友很明白，也繁請(qǐng)教教我） 最終編碼 穿插放置如果你以為我們可以開始畫圖， 你就錯(cuò)了。 二維碼的混亂技術(shù)還沒有玩完， 它還 要把數(shù)據(jù)碼和糾錯(cuò)碼的各個(gè) codewords 交替放在一起。如何交替呢， 規(guī)則如下：對(duì)于數(shù)據(jù)碼：把每個(gè)塊的第一個(gè) codewords 先拿出來按順度排列好，然后再取 第一塊的第二個(gè)，如此類推。如：上述示例中的 Data Codewords 如下：103 38塊 1 67 85 70 134 87 38 85 194 119 50 6 18

22、638 86 22 198 199 146 6塊 2 246 246 66 7 118 134 242 7塊 3 182 230 247 119 507 118 134 87 38 82 6134 151 50 7塊 4 70 247 118 86 194 6151 5016 236 17 236 17236 17 236我們先取第一列的： 67 ， 246， 182然后再取第二列的： 67 ， 246， 182 如此類推： 67， 246 ， 182， 70，38，6，50，17 ，7，236對(duì)于糾錯(cuò)碼，也是一樣：70， 85，246 ，230 ，247,246 , 230 , 247 21

23、191124242222114539571391塊202018121520879660422470塊24151115111611863984741111312201616121327174993303塊141117211324 231923181024191476757610867232 850980213塊2315171410251713172352459 33408223259376521864和數(shù)據(jù)碼取的一樣，得到：213， 87， 148，235， 199，204 ， 116 ，159 , 39, 133 , 141 , 236然后，再把這兩組放在一起（糾錯(cuò)碼放在數(shù)據(jù)碼之后）得到：67

24、, 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,

25、 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, 236Rema

26、inder Bits最后再加上ReminderBits，對(duì)于某些Version的QR，上面的還不夠長(zhǎng)度,還要加上Remainder Bits，比如：上述的5Q版的二維碼，還要加上 7個(gè)bits ,Remainder Bits 加零就好了。關(guān)于哪些 Version 需要多少個(gè)Remainder bit ， 可以參看QR Code Spec的第15頁的Table-1的定義表。畫二維碼圖Positi on Detectio n Pattern首先，先把Position Detection圖案畫在三個(gè)角上。:IB !Alig nment Pattern然后，再把Alignment圖案畫上關(guān)于Align

27、ment 的位置，可以查看 QR Code Spec的第81頁的Table-E.1的定義表（下表是不完全表格）Table E.t Rcw/eolumn coordhates of cent&r moduh of Mignment PatternsVersionNumber of Alignment PatternsRqw/Cq umn coordinates of certer module102r 1 161631622416265163061B34766223086I624429662646W662850下圖是根據(jù)上述表格中的 Version8的一個(gè)例子(6 , 24 , 42)Versi

28、on 8 QR Code0.0El ElED 24O o 4262442Timi ng PatternFormat In formati on再接下來是Formation Information，下圖中的藍(lán)色部分。Format In formation是一個(gè)15個(gè)bits的信息，每一個(gè)bit的位置如下圖所示:（注意圖中的Dark Module ，那是永遠(yuǎn)出現(xiàn)的）這15個(gè)bits中包括：?5個(gè)數(shù)據(jù)bits :其中，2個(gè)bits用于表示使用什么樣的 Error CorrectionLevel,3個(gè)bits表示使用什么樣的 Mask?10個(gè)糾錯(cuò)bits。主要通過BCH Code來計(jì)算然后15個(gè)bit

29、s還要與101010000010010 做XOR操作。這樣就保證不會(huì)因?yàn)槲覀冞x用了 00的糾錯(cuò)級(jí)別，以及000的Mask，從重造成全部為白色，這會(huì)增 加我們的掃描器的圖像識(shí)別的困難。F面是一個(gè)示例:OQ1Q100101ooi tom oo00101001101110010101000001001D100000011001110Asgume Error Correction Level M and Mask Pattern Reference; Data;BCHbits;Unmasked bit sequence:Ma&k pattern for XORoperation: Format inf

30、ormation module pattern:關(guān)于 Error Correction Level女口下表所示:Error Corr action LevelBinary indicatorL01M00Q11H10關(guān)于Mask圖案如后面的Table 23所示Version Information再接下來是Version In formation （版本7以后需要這個(gè)編碼），下圖中的藍(lán)色部分。Version Information共是18個(gè)bits，其中包括6個(gè)bits的版本號(hào)以及12 個(gè)bits的糾錯(cuò)碼，下面是一個(gè)示例:Version nu mberData:BCH bits;Format Infor