QR二維碼編、解碼原理

1、二維碼基礎(chǔ)二維碼基礎(chǔ)-QR（Quick Response）碼2 QR碼的編碼碼的編碼 QR碼的解碼碼的解碼 綱綱 要要3 空白區(qū) 位置探測圖形 定位圖形 位置探測圖形 分 隔符 校正圖形 功能 圖形 數(shù)據(jù)和糾錯碼字 符號 格式信息 版本信息 編碼區(qū) 格式 數(shù)據(jù)信息及數(shù)據(jù)信息的數(shù)據(jù)信息及數(shù)據(jù)信息的糾錯碼糾錯碼包含版本信息，只有版本包含版本信息，只有版本740的符號有版本信息，的符號有版本信息，其余版本全為其余版本全為0 每個QR碼符號由名義上的正方形模塊構(gòu)成，組成一個正方形陣列，它由編碼區(qū)域和包括尋象圖形、分隔符、定位圖形和校正圖形在內(nèi)的功能圖形組成。功能圖形不能用于數(shù)據(jù)編碼。符號的四周由空白區(qū)

2、包圍。下圖為QR碼版本7符號的結(jié)構(gòu)圖。迅速地識別可能的迅速地識別可能的QR碼碼符號，明確地確定視場符號，明確地確定視場中符號的位置和方向中符號的位置和方向作用是確定符號的密度和作用是確定符號的密度和版本，提供決定模塊坐標(biāo)版本，提供決定模塊坐標(biāo)的基準(zhǔn)位置。的基準(zhǔn)位置。補正補正QR碼的歪斜。碼的歪斜。包含符號所使用的糾錯包含符號所使用的糾錯等級和掩模圖形信息。等級和掩模圖形信息。編碼編碼編碼：編碼：QR碼符號的結(jié)構(gòu)碼符號的結(jié)構(gòu)41.數(shù)據(jù)分析2.數(shù)據(jù)編碼3.糾錯編碼4.構(gòu)造最終信息5.在矩陣中布置模塊 6.掩模7.格式和版本信息確定要進行編碼的字符類型，選擇所需的版本信息和糾錯等級。確定要進行編碼的

3、字符類型，選擇所需的版本信息和糾錯等級。采用既定規(guī)則，數(shù)據(jù)字符轉(zhuǎn)換為位流，加必要符號，后將位流轉(zhuǎn)換為碼字。采用既定規(guī)則，數(shù)據(jù)字符轉(zhuǎn)換為位流，加必要符號，后將位流轉(zhuǎn)換為碼字。生成糾錯碼字加到數(shù)據(jù)碼字后。生成糾錯碼字加到數(shù)據(jù)碼字后。按規(guī)則將每一塊中置入數(shù)據(jù)和糾錯碼字，必要時加剩余位。按規(guī)則將每一塊中置入數(shù)據(jù)和糾錯碼字，必要時加剩余位。將尋像圖形、分隔符、矯正圖形與碼字，按規(guī)則排列，放入二維碼矩陣。將尋像圖形、分隔符、矯正圖形與碼字，按規(guī)則排列，放入二維碼矩陣。用八種掩模圖形依次對符號的編碼區(qū)域的位圖進行掩模處理，評價所得到用八種掩模圖形依次對符號的編碼區(qū)域的位圖進行掩模處理，評價所得到的的8種結(jié)果

4、，選擇最優(yōu)的一種。種結(jié)果，選擇最優(yōu)的一種。生成版本信息（如果需要）和格式信息，構(gòu)成符號。生成版本信息（如果需要）和格式信息，構(gòu)成符號。編碼編碼編碼：編碼：QR碼的編碼流程碼的編碼流程51.數(shù)據(jù)分析數(shù)據(jù)分析：確定要進行編碼的字符類型，選擇所需的版本信息和糾錯等級確定要進行編碼的字符類型，選擇所需的版本信息和糾錯等級編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。1.擴充解釋（ECI）模式，數(shù)字模式，字母數(shù)字模式，8位字節(jié)模式，中國漢字模式，日本漢字模式，混合模式，結(jié)構(gòu)鏈接模式，F(xiàn)NCI模式2.62.數(shù)據(jù)編碼數(shù)據(jù)編碼

5、：采用既定規(guī)則，數(shù)據(jù)字符轉(zhuǎn)換為位流，加必要符號，后將位流轉(zhuǎn)換為碼字采用既定規(guī)則，數(shù)據(jù)字符轉(zhuǎn)換為位流，加必要符號，后將位流轉(zhuǎn)換為碼字編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。分為分為3位一組：位一組：012 345 678 901 234 52) 將每組轉(zhuǎn)換為二進制：將每組轉(zhuǎn)換為二進制： 0120000001100 3450101011001 6781010100110 9011110000101 2340011101010 501013) 將二進制數(shù)連接為一個序列：將二進制數(shù)連接為一個序列：00000011

6、00 0101011001 1010100110 1110000101 0011101010 01014) 將字符計數(shù)指示符轉(zhuǎn)換為二進制（查表知版本將字符計數(shù)指示符轉(zhuǎn)換為二進制（查表知版本1-H為為10位）：位）： 字符數(shù)為：1600000100005) 加入模式指示符加入模式指示符0001（查表）以及字符計數(shù)指示符的二進制數(shù)據(jù)：（查表）以及字符計數(shù)指示符的二進制數(shù)據(jù)：0001 0000010000 0000001100 0101011001 1010100110 1110000101 0011101010 01016）數(shù)字模式中位流的長度計算公式：）數(shù)字模式中位流的長度計算公式：B=4+C+

7、10（D DIV 3）+R=4+10+50+4=6872.數(shù)據(jù)編碼數(shù)據(jù)編碼：采用既定規(guī)則，數(shù)據(jù)字符轉(zhuǎn)換為位流，加必要符號，后將位流轉(zhuǎn)換為碼字采用既定規(guī)則，數(shù)據(jù)字符轉(zhuǎn)換為位流，加必要符號，后將位流轉(zhuǎn)換為碼字編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。7）添加終止符：）添加終止符：查表可知版本1-H的數(shù)據(jù)位數(shù)應(yīng)為72，故需添加終止符序列0000，此時數(shù)據(jù)位流為72位，滿足版本要求。8）填充位和填充碼字：）填充位和填充碼字：本例中，數(shù)據(jù)位流長度為72位，滿足數(shù)據(jù)容量要求，無需添加填充位和填充碼字。9）位流到碼字的轉(zhuǎn)

8、換：）位流到碼字的轉(zhuǎn)換：所得的數(shù)據(jù)位流將被分為一個個碼字，所有的碼字長度都是8位。綜上，所得到的數(shù)據(jù)碼字序列為：綜上，所得到的數(shù)據(jù)碼字序列為：00010000 01000000 00001100 01010110 01101010 01101110 00010100 11101010 01010000（共9個碼字）83.糾錯編碼糾錯編碼：生成糾錯碼字加到數(shù)據(jù)碼字后生成糾錯碼字加到數(shù)據(jù)碼字后編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。000SSSccc11111 1)()()(161o251o400321625

9、21610ccc編碼碼字矩陣編碼碼字矩陣校驗矩陣校驗矩陣252522110)(xcxcxccxc編碼碼字多項式：編碼碼字多項式：前前9位為數(shù)據(jù)碼字位為數(shù)據(jù)碼字 后后17位為糾錯碼字位為糾錯碼字93.糾錯編碼糾錯編碼：生成糾錯碼字加到數(shù)據(jù)碼字后生成糾錯碼字加到數(shù)據(jù)碼字后編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。定義：在任何定義：在任何q階伽羅華域階伽羅華域GF（q）中都能找到一個）中都能找到一個，能用它的冪次表示，能用它的冪次表示q-1個非零元個非零元素。素。 QR碼的糾錯碼生成是通過碼的糾錯碼生成是通過GF

10、（28）來進行的，來進行的，GF（28）中的元素組成一個循環(huán)群：中的元素組成一個循環(huán)群：（ 1， 1 ，254 )， 其中其中255 = 0=1 ，則稱，則稱是是GF（28）的本原域元素。的本原域元素。0 254 可用可用0000 0001 1111 1111 來表示來表示同時，同時， 為為P（X）=0的根。其中，的根。其中， P（X）是以）是以GF（28）上上8次首一既約多項式，以次首一既約多項式，以P(X)為模的多項式剩余類環(huán)構(gòu)成為模的多項式剩余類環(huán)構(gòu)成28階伽羅華域。階伽羅華域。本例中，本原多項式為本例中，本原多項式為P(X)=X8+X4+X3+X2+1。用用i模模P（）可以得到域元素和

11、二進制比特串的對照表（如圖）。）可以得到域元素和二進制比特串的對照表（如圖）。103.糾錯編碼糾錯編碼：生成糾錯碼字加到數(shù)據(jù)碼字后生成糾錯碼字加到數(shù)據(jù)碼字后編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。113.糾錯編碼糾錯編碼：生成糾錯碼字加到數(shù)據(jù)碼字后生成糾錯碼字加到數(shù)據(jù)碼字后編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。(c, k, r): c =碼字總數(shù)碼字總數(shù)k =數(shù)據(jù)碼字數(shù)數(shù)據(jù)碼字數(shù)r =糾錯容量糾錯容量 糾錯容量小于

12、糾錯碼字數(shù)的糾錯容量小于糾錯碼字數(shù)的一半，以減少錯誤譯碼的可能一半，以減少錯誤譯碼的可能性性生成多項式：生成多項式：g(x)=(x-0)(x-1)(x-n-1) =(x-0)(x-1)(x-16)其中其中n為生成多項式的次數(shù)，為生成多項式的次數(shù)，也就是糾錯碼字數(shù)。本例中，也就是糾錯碼字數(shù)。本例中，糾錯碼字數(shù)為糾錯碼字數(shù)為17，生成多項，生成多項式如圖所示。式如圖所示。12（i=0,1,2,，16）3.糾錯編碼糾錯編碼：生成糾錯碼字加到數(shù)據(jù)碼字后生成糾錯碼字加到數(shù)據(jù)碼字后編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。

13、碼。數(shù)據(jù)碼字的多項式形式為數(shù)據(jù)碼字的多項式形式為：d(x)=d0+d1x+d2x2+d8x8 （有9個數(shù)據(jù)碼字） 生成多項式為：生成多項式為：g(x)=編碼后的表達式為：編碼后的表達式為：糾錯碼字多項式其中，糾錯碼字是數(shù)據(jù)碼字被糾錯碼多項式其中，糾錯碼字是數(shù)據(jù)碼字被糾錯碼多項式g(x)除得的余數(shù)。除得的余數(shù)。糾錯碼多項式求出后，將系數(shù)糾錯碼多項式求出后，將系數(shù)i按對照表轉(zhuǎn)換為位流，加到數(shù)據(jù)位流后面，即可求出整按對照表轉(zhuǎn)換為位流，加到數(shù)據(jù)位流后面，即可求出整個編碼數(shù)據(jù)位流。個編碼數(shù)據(jù)位流。C（X）C(i) = 0=g(x)q(x)( )(dx)(g）x（j）x（g mod )(dxdxdxdxd

14、)(dxt2t2011247258t2xqxxxx)()( j(x)j(x)q(x)g(x) j(x)(dx)(故t2xgxqxxc（數(shù)據(jù)碼字多項式）（糾錯碼字多項式）134.構(gòu)造最終信息構(gòu)造最終信息 ：按規(guī)則將每一塊中置入數(shù)據(jù)和糾錯碼字，必要時加剩余位按規(guī)則將每一塊中置入數(shù)據(jù)和糾錯碼字，必要時加剩余位編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。按如下步驟構(gòu)造最終的碼字序列（數(shù)據(jù)碼字加上糾錯碼字，必要時加上剩余碼字）。1）根據(jù)版本和糾錯等級將數(shù)據(jù)碼字序列分為n塊。2）對每一塊，計算相應(yīng)塊的糾錯碼字。3）依次將

15、每一塊的數(shù)據(jù)和糾錯碼字裝配成最終的序列：數(shù)據(jù)塊1的碼字1；數(shù)據(jù)塊2的碼字1；數(shù)據(jù)塊3的碼字1；以此類推至數(shù)據(jù)塊n-1的最后的碼字；數(shù)據(jù)塊n的最后的碼字；隨后，糾錯塊1的碼字1，糾錯塊2的碼字1，以此類推至糾錯塊n-1的最后的碼字；糾錯塊n的最后的碼字。查表可知，本例中查表可知，本例中1-H版本的數(shù)據(jù)碼字序列為版本的數(shù)據(jù)碼字序列為1塊，不需要分開，故無需構(gòu)造最終信息。塊，不需要分開，故無需構(gòu)造最終信息。145.在矩陣中布置模塊在矩陣中布置模塊：將尋像圖形、分隔符、校正圖形與碼字，按規(guī)則排列，放入二維碼矩陣將尋像圖形、分隔符、校正圖形與碼字，按規(guī)則排列，放入二維碼矩陣編碼編碼例：對數(shù)字例：對數(shù)字0

16、123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。圖形表示：圖形表示：00010000排列規(guī)則排列規(guī)則 數(shù)據(jù)碼字數(shù)據(jù)碼字9個，糾錯碼字個，糾錯碼字17個，共個，共26個碼字，就是個碼字，就是26塊碼字區(qū)。塊碼字區(qū)。 將碼字，尋像圖形，分隔符，校正圖形按規(guī)則排列，放入二維碼中即可將碼字，尋像圖形，分隔符，校正圖形按規(guī)則排列，放入二維碼中即可15掩模圖形參考條件000(i + j) mod 2 = 0001i mod 2 = 0010j mod 3 = 0011(i + j) mod 3 = 0100(i div 2) + (j div 3) mo

17、d 2 = 0101(i j) mod 2 + (i j) mod 3 = 0110(i j) mod 2 + (i j) mod 3) mod 2 = 0111(i j) mod 3 + (i+j) mod 2) mod 2 = 06.掩模掩模：依次對符號的編碼區(qū)域的位圖進行掩模處理，評價所得結(jié)果，選擇最優(yōu)一種。依次對符號的編碼區(qū)域的位圖進行掩模處理，評價所得結(jié)果，選擇最優(yōu)一種。編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。 為了QR碼閱讀的可靠性，最好均衡地安排深色與淺色模塊。應(yīng)盡可能避免位置探測圖形的位圖

18、1011101出現(xiàn)在符號的其他區(qū)域。為了滿足上述條件，應(yīng)按以下步驟進行掩模。1)掩模不用于功能圖形2)用多個矩陣圖形連續(xù)地對已知的編碼區(qū)域的模塊圖形（格式信息和版本信息除外）進行XOR操作。XOR操作將模塊圖形依次放在每個掩模圖形上，并將對應(yīng)于掩模圖形的深色模塊的模塊取反（淺色變成深色，或相反）。3)對每個結(jié)果圖形的不合要求的部分記分，以評估這些結(jié)果。4)選擇得分最低的圖形。 000 (i + j) mod 2 = 0 001 i mod 2 = 0 010 j mod 3 = 0 011 (i + j) mod 3 = 0 100 (i div 2 ) + (j div 3 ) mod 2

19、= 0 101 (i j) mod 2 + (i j) mod 3 = 0 110 ( (i j) mod 2 + (i j) mod 3) mod 2 = 0 110 ( (i j) mod 2 + (i j) mod 3) mod 2 = 0 功能模塊 掩模不用于功能模塊 i j 版本版本1符號的所有的掩模圖形，用掩模圖形符號的所有的掩模圖形，用掩模圖形參考參考000到到111的掩模結(jié)果。的掩模結(jié)果。 167.格式和版本信息格式和版本信息：生成版本信息（如果需要）和格式信息，構(gòu)成符號生成版本信息（如果需要）和格式信息，構(gòu)成符號編碼編碼例：對數(shù)字例：對數(shù)字0123456789012345（1

20、6個數(shù)字字符）進行編碼，生成個數(shù)字字符）進行編碼，生成QR碼。碼。 格式信息為格式信息為15位，其中有位，其中有5個數(shù)據(jù)位，個數(shù)據(jù)位，10個是用個是用BCH（15，5）編碼計算得到的）編碼計算得到的糾錯位。其中，數(shù)據(jù)位的第糾錯位。其中，數(shù)據(jù)位的第1,2位是符號的糾錯等級，第位是符號的糾錯等級，第3到第到第5位是掩模圖形參考。位是掩模圖形參考。 格式信息掩模是與格式信息掩模是與101010000010010進行進行XOR異或運算。異或運算。本例中糾錯等級為本例中糾錯等級為H，查表知，二進制指示符為，查表知，二進制指示符為10。掩模圖形參考根據(jù)上頁結(jié)果確定。掩模圖形參考根據(jù)上頁結(jié)果確定。 版本信息

21、為版本信息為18位，其中，位，其中，6位數(shù)據(jù)位，位數(shù)據(jù)位，12位通過位通過BCH（18,6）編碼計算出的）編碼計算出的糾錯位。只有版本糾錯位。只有版本7到版本到版本40的符號包含版本信息，沒有任何版本信息的結(jié)果全為的符號包含版本信息，沒有任何版本信息的結(jié)果全為0。糾錯等級二進制指示符L01M00Q11H1017解碼解碼 結(jié) 束 格 式 信 息 譯 碼 消 除 掩 模 識 別 深/淺 模 塊 用 糾 錯 碼 字 進行 錯 誤 檢 查 糾 錯 數(shù) 據(jù) 碼 字 譯 碼 輸 出 錯 誤 沒 有 錯 誤 開 始 確 定 版 本 恢 復(fù) 數(shù) 據(jù) 和 糾 錯 碼 字 1.計算伴隨多項式的值。計算伴隨多項式的

22、值。2.求錯誤位置多項式。求錯誤位置多項式。3.求錯誤位置多項式的根。求錯誤位置多項式的根。4.求錯誤值并對碼字進行錯誤求錯誤值并對碼字進行錯誤糾正。糾正。圖像處理方法圖像處理方法解碼：解碼：QR碼的解碼流程碼的解碼流程18解碼解碼編碼后的表達式為： =C25X25 + C24X24 + C1X1 + C0 =q(x)g(x)C（X）例：例：以版本以版本1-M為例，為例，GF（28）上有碼字）上有碼字26個，其中糾錯碼字個，其中糾錯碼字10個，可糾正個，可糾正4個碼字。個碼字。1.計算伴隨多項式的值計算伴隨多項式的值=ea1a1 + ea2a2 + ea3a3 + ea4a4 =ea1+ ea

23、2+ ea3+ ea4=ea1（7）a1 + ea2（7）a2 + ea3（7）a3 + ea4（7）a4 若若Si0 (i=0,1,2,3,4,5,6,7), 則接受到的碼字無錯誤。則接受到的碼字無錯誤。若若Si0 (i=0,1,2,3,4,5,6,7)，則接收到的碼字有誤，需先，則接收到的碼字有誤，需先找出錯誤碼字位置找出錯誤碼字位置，再，再算出算出錯誤值錯誤值，最后，最后進行糾錯進行糾錯，得到正確碼字。，得到正確碼字。432147372717432171o251o1751472521111SSSrrr11111 1aaaaaaaaaaaaeeee19解碼解碼例：例：以版本以版本1-M為例

24、，為例，GF（28）上有碼字）上有碼字26個，其中糾錯碼字個，其中糾錯碼字10個，可糾正個，可糾正4個碼個碼字。字。令ai為錯位碼字的位置（ai=0-25）。找到錯誤碼字位置ai 即可算出錯誤碼字eai。 故需先求出1,2,3,4。得到多項式(z)。將-ai依次帶入(z)，使(z)=0的項即為所求。）-1）（-1）（-1）（-1（)z(4321zzzzaaaa44332211zzzz2.找出錯誤碼字位置找出錯誤碼字位置是一個相對于是一個相對于的值，不是一個絕對值。有的值，不是一個絕對值。有4個錯誤和有個錯誤和有5個錯誤的個錯誤的 值是不一樣值是不一樣的。的。20解碼解碼例：例：以版本以版本1-

25、M為例，為例，GF（28）上有碼字）上有碼字26個，其中糾錯碼字個，其中糾錯碼字10個，可糾正個，可糾正4個碼個碼字。字。0)()()(1)(41-431-321-21-11-aaaaa0)()()(1)(42-432-322-22-12-aaaaa0)()()(1)(43-433-323-23-13-aaaaa0)()()(1)(44-434-324-24-14-aaaaa0)(14113121213111411411-aaaaaaaaaaaaeeeeee0)(24223222223212422422-aaaaaaaaaaaaeeeeee0)(34333323233313433433-aaa

26、aaaaaaaaaeeeeee0)(44443424243414444444-aaaaaaaaaaaaeeeeee0SSSSS)()()()(4031221344444-3433-2422-1411-aaaaaaaaaaaaeeee403122134SSSSS同理可得：2.找出錯誤碼字位置找出錯誤碼字位置433425167SSSSS423324156SSSSS413223145SSSSS21解碼解碼例：例：以版本以版本1-M為例，為例，GF（28）上有碼字）上有碼字26個，其中糾錯碼字個，其中糾錯碼字10個，可糾正個，可糾正4個碼個碼字。字。2.找出錯誤碼字位置找出錯誤碼字位置根據(jù)上式，確定錯誤位置矩陣為：根據(jù)上式，確定錯誤位置矩陣為