QR二維碼糾錯改進算法

康偉慈，曹 民

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

?

QR二維碼糾錯改進算法

康偉慈，曹 民

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

二維條碼與一維條碼相比，其無需依賴數(shù)據(jù)庫，存儲信息量大，可表達多種多媒體及文字信息，具有糾錯能力。針對傳統(tǒng)QR碼的糾錯能力有限，文中提出了將糾錯碼LDPC碼替換RS碼生成新的QR碼方案，即利用新的糾錯技術(shù)生成QR碼。通過對糾錯碼LDPC碼的編碼原理和性能仿真進行研究，與RS碼進行仿真對比。實驗結(jié)果表明，相比原RS糾錯碼，新糾錯碼LDPC碼的糾錯能力有所提高。

QR碼；二維碼；RS碼；LDPC碼

二維碼是將特定的圖形按照一定規(guī)律在平面上形成的黑白相間的圖形，儲藏著所要傳達的信息；常見的二維碼有QR Code、PDF417、DataMatrix等[1]。QR(Quick Response Code)碼是由日本豐田公司Denso Wave于1994年9月研制的一種矩陣二維碼符號，其擁有一維碼和所有二維碼信息容量大、可靠性高、可表示漢字和圖像等多種信息[2]。

1 QR二維碼

1.1 QR碼符號結(jié)構(gòu)

QR碼[3]是包括編碼區(qū)域和功能區(qū)域，功能區(qū)域不用于數(shù)據(jù)編碼，包括尋像圖形、分隔符、定位圖形和校正圖形[4]。QR碼符號共有40個版本[5]，圖1為版本7的結(jié)構(gòu)。

A：3模塊 B：5模塊 C：7模塊

圖1 QR Code的符號結(jié)構(gòu)(版本7)

1.2 QR碼編碼

QR碼的編碼要經(jīng)過以下步驟：數(shù)據(jù)分析、數(shù)據(jù)編碼、糾錯編碼、數(shù)據(jù)及糾錯信息整合、陣列的構(gòu)造、掩模、添加格式和版本信息。

2 RS碼糾錯算法

QR碼有4個不同的糾錯等級，糾錯能力最大為30%。

2.1 Reed-Solomon編碼原理

RS(Reed-Solomon)[6]碼又稱里德-所羅門碼，是一種糾錯能力很強的非二進制BCH碼。RS編碼運算在有限域中進行。

RS碼的多項式為c(x)=m(x)+r(x)，m(x)為信息多項式，r(x)為校驗多項式,m(x)=c2tx2t+c2t+1x2t+1+…cn-1xn-1,r(x)=c0+c1x+…c2t-1x2t-1。

若c(x)為一個碼字，則它必須是生成多項式g(x)的倍數(shù)，且通過除法算法可獲得p(x)。c(x)=q(x)g(x),m(x)=q(x)g(x)+p(x)。

2.2 仿真實驗

對RS編碼理論分析在仿真平臺上進行實驗比較，實驗給出了誤比特率BER為參考的性能曲線。實驗采用AWGN信道，BPSK調(diào)制，仿真軟件為Matlab7.1。

圖2 RS信噪比和誤碼率曲線圖

由圖2可知，RS的誤碼率隨著信噪比的增加而降低，當信噪比相同時，誤碼率隨信息位K的增加而降低。

3 LDPC碼編碼算法

3.1 LDPC碼

LDPC碼[7]是一種(n,k)的線性分組碼，通過校驗矩陣H獲得，H的大小為m×n，一列代表碼字的一位，一行代表一個校驗方程。

上式代表5×10的校驗矩陣和對應(yīng)的校驗方程，滿足H×cT=0，其中

c=(c1,c2,c3,c4,c5,c6,c7,c8,c9,c10)∈C

當校驗矩陣H是滿秩時,m=n-k，碼率r=(n-m)/n=1-m/n。若H的秩小于m，即m>n-k，碼率是r>1-m/n。

構(gòu)造維數(shù)為m×n的校驗矩陣H，利用高斯消元法將其轉(zhuǎn)化為

(1)

3.2 LDPC碼算法

利用生成矩陣編碼方法是最基礎(chǔ)的，但這種方法在碼長較長的情況下復(fù)雜度O(n)2將是嚴重的制約因素。因此，需要采取新方法使得生成矩陣中含有大量的“1”元素，為此提出了運用近似下三角矩陣的編碼算法[8]。

若H為m×n的行滿秩矩陣，通過交換行列轉(zhuǎn)化成近似下三角矩陣[9]如圖3所示，并保持了矩陣的稀疏性。

圖3 稀疏校驗矩陣的近似下三角矩陣

(2)

假設(shè)編碼碼字S=(t,p1,p2)，表示信息比特序列，p1和p2表示校驗比特序列。根據(jù)HST=0，可得

若矩陣(-ET-1B+D)可逆，則可得

(3)

(4)

這種編碼算法的復(fù)雜度為 。研究主要集中在如何利用校驗矩陣的稀疏性來有效的進行編碼，目的是使編碼的復(fù)雜度隨著碼字長度呈線性增長。

3.3 仿真實驗

對LDPC碼的編碼理論在仿真平臺上進行了實驗，研究影響LDPC碼性能的因素。

圖4 LDPC不同迭代次數(shù)的性能比較

圖4表示的是不同迭代次數(shù)對LDPC碼性能的影響。由圖可知，迭代次數(shù)越大，LDPC碼的性能越好。

圖5 比特錯誤率與信噪比和迭代次數(shù)關(guān)系

圖5表示了比特錯誤率與信噪比和迭代次數(shù)的關(guān)系曲線，由圖可知，在信噪比>3dB時，BER快速減小，信噪比比較小時BER變化較慢。

4 LDPC與RS仿真對比

在Matlab實驗平臺上，以碼長512為界限[10]，文中選擇信噪比和比特誤碼率這一對參數(shù)進行對比分析，當比特誤碼率較小時可判斷它其糾錯性能較好。

圖6 信噪比與比特誤碼率之間的關(guān)系

從仿真結(jié)果可以看出，LDPC譯碼的性能優(yōu)于RS碼，RS碼在信躁較低時性能該變量較少，而LDPC碼快速降低比特誤碼率，這樣可糾正更多錯誤。

影響糾錯碼性能的另一個因素是碼率，因此選擇在相同碼率的情況下進行仿真實驗，如圖7所示。

圖7 LDPC與RS在具有相同碼率時的曲線

由圖7可知，LDPC碼的性能要優(yōu)于RS，在信噪比較小時LDPC碼的誤碼率就已經(jīng)降到較低水平，而RS碼在信噪比較大時才較為明顯。

5 結(jié)束語

對LDPC碼和RS碼的性能進行了分析比較，從仿真結(jié)果可知，LDPC碼的性能優(yōu)于RS碼。因此使用糾錯碼LDPC輸出新的QR碼，提高了糾錯能力。

[1] 劉志海,萬麗榮,宋作玲.條碼技術(shù)及程序設(shè)計案例[M].北京:化學(xué)工業(yè)出版社,2009.

[2]LiuYue,LiuMingye.Researchondataencodingoftwo-dimensionalQRcodebarcode[J].JournalofBeijingInstituteofTechnology,2005,25(4)：352-355.

[3] 全國信息技術(shù)標準化技術(shù)委員會.GB/T18284-2000.快速響應(yīng)矩陣碼[S]. 北京：中國標準出版社，2000.

[4] 黃宏博.QR二維條碼的糾錯編碼算法研究及實現(xiàn)[J].微計算機信息,2010,26(30):36-38.

[5] 張興華.矩陣式快速Q(mào)R碼的研究和應(yīng)用[D].成都:電子科技大學(xué),2009.

[6] 吳祖義.RS碼軟判譯碼技術(shù)的研究[D].南京:南京郵電大學(xué),2010.

[7] 袁東風(fēng),張海剛.LDPC碼理論與應(yīng)用[M].北京:人民郵電出版社,2008.

[8] 張麗麗.LDPC碼構(gòu)造及其應(yīng)用研究[D].杭州：杭州電子科技大學(xué),2011.

[9] 賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用[M].北京:人民郵電出版社,2009.

[10]XiaoYouan,LuoChunling,YangChao.ThecomparativeanalysisofLDPCandRScode[C].Hangzhou:InternationalConferenceonConsumerElectronics,CommunicationsandNetworks,2011.

Error Correction Improvement Algorithms of QR Code

KANG Weici，CAO Min

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology, Shanghai 200093, China)

Compared two dimensional barcode with one dimensional barcode, the former does not need to rely on database, and it can store large amount of information and express a variety of multimedia and text information, having error correction ability. For traditional QR code the error correction ability is limited, this paper proposes a solution that error correcting codes LDPC codes will replace RS code to the QR image, it means that use the new correction technology to generate QR code. It gives a study of the error correction code LDPC codes encoding thinking and performance simulation, and then puts it with the RS code simulation contrast. The result shows that compared with the original RS error correcting code, the error correcting capability of the new error correcting LDPC code is improved.

QR code; two-dimensional code; RS code; LDPC code

10.16180/j.cnki.issn1007-7820.2016.12.028

2016- 02- 14

康偉慈(1993-)， 女，碩士研究生。研究方向：軟件開發(fā)及測試。

TP391.41

A

1007-7820(2016)12-101-03