1、二維碼基礎 -QR（Quick Response）碼,QR碼的編碼 QR碼的解碼,綱 要,數(shù)據(jù)信息及數(shù)據(jù)信息的糾錯碼,包含版本信息，只有版本740的符號有版本信息，其余版本全為0,每個QR碼符號由名義上的正方形模塊構成，組成一個正方形陣列，它由編碼區(qū)域和包括尋象圖形、分隔符、定位圖形和校正圖形在內(nèi)的功能圖形組成。功能圖形不能用于數(shù)據(jù)編碼。符號的四周由空白區(qū)包圍。下圖為QR碼版本7符號的結構圖。,迅速地識別可能的QR碼符號，明確地確定視場中符號的位置和方向,作用是確定符號的密度和版本，提供決定模塊坐標的基準位置。,補正QR碼的歪斜。,包含符號所使用的糾錯等級和掩模圖形信息。,編碼,編碼：QR碼符

2、號的結構,1.數(shù)據(jù)分析,2.數(shù)據(jù)編碼,3.糾錯編碼,4.構造最終信息,5.在矩陣中布置模塊,6.掩模,7.格式和版本信息,確定要進行編碼的字符類型，選擇所需的版本信息和糾錯等級。,采用既定規(guī)則，數(shù)據(jù)字符轉換為位流，加必要符號，后將位流轉換為碼字。,生成糾錯碼字加到數(shù)據(jù)碼字后。,按規(guī)則將每一塊中置入數(shù)據(jù)和糾錯碼字，必要時加剩余位。,將尋像圖形、分隔符、矯正圖形與碼字，按規(guī)則排列，放入二維碼矩陣。,用八種掩模圖形依次對符號的編碼區(qū)域的位圖進行掩模處理，評價所得到的8種結果，選擇最優(yōu)的一種。,生成版本信息（如果需要）和格式信息，構成符號。,編碼,編碼：QR碼的編碼流程,1.數(shù)據(jù)分析：確定要進行編碼的

3、字符類型，選擇所需的版本信息和糾錯等級,編碼,例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成QR碼。,1.擴充解釋（ECI）模式，數(shù)字模式，字母數(shù)字模式，8位字節(jié)模式，中國漢字模式，日本漢字模式，混合模式，結構鏈接模式，F(xiàn)NCI模式,2.,2.數(shù)據(jù)編碼：采用既定規(guī)則，數(shù)據(jù)字符轉換為位流，加必要符號，后將位流轉換為碼字,編碼,例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成QR碼。,分為3位一組：012 345 678 901 234 5 2) 將每組轉換為二進制： 0120000001100 3450101011001 6781010100

4、110 9011110000101 2340011101010 50101 3) 將二進制數(shù)連接為一個序列： 0000001100 0101011001 1010100110 1110000101 0011101010 0101 4) 將字符計數(shù)指示符轉換為二進制（查表知版本1-H為10位）： 字符數(shù)為：160000010000 5) 加入模式指示符0001（查表）以及字符計數(shù)指示符的二進制數(shù)據(jù)： 0001 0000010000 0000001100 0101011001 1010100110 1110000101 0011101010 0101 6）數(shù)字模式中位流的長度計算公式：B=4+C+

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

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

7、）來進行的，GF（28）中的元素組成一個循環(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)構成28階伽羅華域。 本例中，本原多項式為P(X)=X8+X4+X3+X2+1。 用i模P（）可以得到域元素和二進制比特串的對照表（如圖）。,3.糾錯編碼：生成糾錯碼字加到數(shù)據(jù)碼字后,編碼,例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成QR碼。,3.糾錯編

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

9、的多項式形式為：d(x)=d0+d1x+d2x2+d8x8 （有9個數(shù)據(jù)碼字） 生成多項式為：g(x)=,編碼后的表達式為：,糾錯碼字多項式,其中，糾錯碼字是數(shù)據(jù)碼字被糾錯碼多項式g(x)除得的余數(shù)。 糾錯碼多項式求出后，將系數(shù)i按對照表轉換為位流，加到數(shù)據(jù)位流后面，即可求出整個編碼數(shù)據(jù)位流。,C（X）,C(i) = 0,=g(x)q(x),（數(shù)據(jù)碼字多項式）,（糾錯碼字多項式）,4.構造最終信息 ：按規(guī)則將每一塊中置入數(shù)據(jù)和糾錯碼字，必要時加剩余位,編碼,例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成QR碼。,按如下步驟構造最終的碼字序列（數(shù)據(jù)碼字加上糾錯碼字，必

10、要時加上剩余碼字）。 1）根據(jù)版本和糾錯等級將數(shù)據(jù)碼字序列分為n塊。 2）對每一塊，計算相應塊的糾錯碼字。 3）依次將每一塊的數(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ù)碼字序列為1塊，不需要分開，故無需構造最終信息。,5.在矩陣中布置模塊：將尋像圖形、分隔符、校正圖形與碼字，按規(guī)則排列，放入二維碼矩陣,編碼,例：對數(shù)字0123456789012345（16個數(shù)字

11、字符）進行編碼，生成QR碼。,圖形表示：00010000,排列規(guī)則,數(shù)據(jù)碼字9個，糾錯碼字17個，共26個碼字，就是26塊碼字區(qū)。 將碼字，尋像圖形，分隔符，校正圖形按規(guī)則排列，放入二維碼中即可,6.掩模：依次對符號的編碼區(qū)域的位圖進行掩模處理，評價所得結果，選擇最優(yōu)一種。,編碼,例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成QR碼。,為了QR碼閱讀的可靠性，最好均衡地安排深色與淺色模塊。應盡可能避免位置探測圖形的位圖1011101出現(xiàn)在符號的其他區(qū)域。為了滿足上述條件，應按以下步驟進行掩模。 1)掩模不用于功能圖形 2)用多個矩陣圖形連續(xù)地對已知的編碼區(qū)域的模塊圖

12、形（格式信息和版本信息除外）進行XOR操作。XOR操作將模塊圖形依次放在每個掩模圖形上，并將對應于掩模圖形的深色模塊的模塊取反（淺色變成深色，或相反）。 3)對每個結果圖形的不合要求的部分記分，以評估這些結果。 4)選擇得分最低的圖形。,版本1符號的所有的掩模圖形，用掩模圖形參考000到111的掩模結果。,7.格式和版本信息：生成版本信息（如果需要）和格式信息，構成符號,編碼,例：對數(shù)字0123456789012345（16個數(shù)字字符）進行編碼，生成QR碼。,格式信息為15位，其中有5個數(shù)據(jù)位，10個是用BCH（15，5）編碼計算得到的糾錯位。其中，數(shù)據(jù)位的第1,2位是符號的糾錯等級，第3到第

13、5位是掩模圖形參考。 格式信息掩模是與101010000010010進行XOR異或運算。 本例中糾錯等級為H，查表知，二進制指示符為10。掩模圖形參考根據(jù)上頁結果確定。,版本信息為18位，其中，6位數(shù)據(jù)位，12位通過BCH（18,6）編碼計算出的糾錯位。只有版本7到版本40的符號包含版本信息，沒有任何版本信息的結果全為0。,解碼,1.計算伴隨多項式的值。 2.求錯誤位置多項式。 3.求錯誤位置多項式的根。 4.求錯誤值并對碼字進行錯誤糾正。,圖像處理方法,解碼：QR碼的解碼流程,解碼,編碼后的表達式為：,=C25X25 + C24X24 + C1X1 + C0 =q(x)g(x),C（X）,例

14、：以版本1-M為例，GF（28）上有碼字26個，其中糾錯碼字10個，可糾正4個碼字。,1.計算伴隨多項式的值,=ea1a1 + ea2a2 + ea3a3 + ea4a4,=ea1+ ea2+ 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)，則接收到的碼字有誤，需先找出錯誤碼字位置，再算出錯誤值，最后進行糾錯，得到正確碼字。,解碼,例：以版本1-M為例，GF（28）上有碼字26個，其中糾錯碼字10個，可糾正4個碼字

15、。,令,ai為錯位碼字的位置（ai=0-25）。 找到錯誤碼字位置ai 即可算出錯誤碼字eai。 故需先求出1,2,3,4。得到多項式(z)。 將-ai依次帶入(z)，使(z)=0的項即為所求。,2.找出錯誤碼字位置,是一個相對于的值，不是一個絕對值。有4個錯誤和有5個錯誤的 值是不一樣的。,解碼,例：以版本1-M為例，GF（28）上有碼字26個，其中糾錯碼字10個，可糾正4個碼字。,同理可得：,2.找出錯誤碼字位置,解碼,例：以版本1-M為例，GF（28）上有碼字26個，其中糾錯碼字10個，可糾正4個碼字。,2.找出錯誤碼字位置,根據(jù)上式，確定錯誤位置矩陣為：,將-ai依次帶入(z)，使(z)=0的項即為所求（只要是錯誤的-ai帶入后，結果都為0 ）。 ai即為錯誤碼字位置，接下來用錯誤碼字位置找到錯誤值進行糾錯。（注：若 ai 的個數(shù)多余4個，則無法進行糾錯。）,解此矩陣，即可求出1,2,3,4。 (z)即可求出：,解碼,例：以版本1-M為例，GF（28）上有碼字26個，其中糾錯碼字10個，