包小敏，瞿云云，武登杰，袁治華，劉 旭，李 梅

?

二進制QR碼的一個簡化查表譯碼算法

包小敏1，瞿云云2，武登杰1，袁治華1，劉 旭1，李 梅1

(1. 西南大學數(shù)學與統(tǒng)計學院 重慶北碚區(qū) 400715；2. 貴州師范大學數(shù)學科學學院 貴陽 550001)

基于QR碼的特點和伴隨式的重量，給出了二進制QR碼的一個新的簡化查表譯碼算法。譯碼表的行是形如(,)的向量，其中是錯誤僅出現(xiàn)在信息部分且錯誤個數(shù)不超過碼的糾錯能力一半的錯誤模式，是的伴隨式。該算法適用于所有的二進制QR碼。其譯碼表的行數(shù)在目前已知的二進制QR碼的查表譯碼算法中是最小的。因此該算法不僅有一定的理論意義，也有一定的實用價值。

錯誤模式; Hamming 重量; QR碼; 伴隨式; 查表譯碼

QR碼是在1958年被提出的[3]。從那時起，人們對QR碼的研究就一直沒有停止過[4-8]。

QR碼是一類譯碼比較困難的“好”碼[9]；而對于Q譯R碼的碼，文獻[10]認為QR碼類的譯碼算法通常不具有規(guī)范的結(jié)構(gòu)，針對不同的QR碼，采用不同的譯碼算法[10]。因此對QR碼的譯碼算法研究具有一定的理論意義和實際意義。

本文針對所有二進制QR碼給出一個通用的簡化查表譯碼算法。目前已有的二進制QR碼的查表譯碼算法一般都是針對特定的QR碼，本文給出的算法不僅具有適用性廣的特點，而且譯碼表的行數(shù)也是最小的。

1 QR碼及QR碼的查表譯碼算法

QR碼的譯碼分為兩類：代數(shù)譯碼[13-14]和查表譯碼。查表譯碼的大致過程如下：

事先構(gòu)造一個譯碼表，該表中一個錯誤模式與一個伴隨式對應(yīng)。對接收到的向量，按下面的步驟進行譯碼：

3) 通過錯誤模式進行糾錯，然后將糾錯后的向量輸出。

查表譯碼最直接的做法是在譯碼表中將糾錯能力范圍內(nèi)的所有錯誤模式和其對應(yīng)的伴隨式一一全部列出，這時譯碼表的行數(shù)為。由于譯碼表的大小直接影響查表譯碼算法的效率和實用性，所以長期以來有很多學者都致力于減少譯碼表的行數(shù)的研究。

以上這些算法大多數(shù)都是針對單個具體的QR碼來給出的，且譯碼表的行數(shù)都大于。

通過研究，本文發(fā)現(xiàn)了QR碼的一些性質(zhì)，利用這些性質(zhì)，給出一個針對所有二進制QR碼的通用的查表譯碼算法，譯碼表的行數(shù)都為。該算法不僅能糾正小于或等于個的錯誤，而且還可以檢測出部分多于個的錯誤。

2 循環(huán)碼的生成矩陣和一致校驗矩陣

則矩陣：

具有這種結(jié)構(gòu)的碼稱為系統(tǒng)碼。在系統(tǒng)碼的情況下，將一個二進制維向量的前個分量稱為信息部分，后個分量稱為校驗部分。

3 主要定理及證明

為了得到一個適用于所有QR碼的通用算法，本文對QR進行研究，發(fā)現(xiàn)QR碼都具有一些性質(zhì)，利用這些性質(zhì)可以得到一個通用的簡化查表譯碼算法。將結(jié)果用6個定理的形式給出。

由定理2和定理3可得：

定理4給出了一個如何判別錯誤只出現(xiàn)在校驗部分的方法及如何確定錯誤模式的方法。因此當錯誤只出現(xiàn)在校驗部分時就可統(tǒng)一處理，而不必將每個錯誤模式和其對應(yīng)的伴隨式一一列出。下面只須考慮信息部分一定有錯誤出現(xiàn)的情形。

由定理5可知，在錯誤向量的伴隨式及其信息部分對應(yīng)的伴隨式已知的情況下可以得到錯誤向量的校驗部分。

其對應(yīng)的伴隨式分別為：

表1 MPSET表

在實際譯碼時并不知道錯誤向量的信息部分，所以定理5的結(jié)果不具可操作性。定理6則從理論上保證由錯誤向量的伴隨式和表MPSET，通過比較向量的漢明重量就可確定錯誤向量。因為錯誤向量的伴隨式可通過接收到的向量得到，而表MPSET可事先做好，所以定理6的結(jié)果可實際操作。

實際上由定理1可得：

4 新的譯碼算法

然后計算SMPSET。

Algorithm：SimplifiedTLD

{

else {

}

}

if testedNo = 2

if testedNo = 3

}

output (“failure”);

else

}

當算法輸出“failure”時，表明在SMPSET中沒有找到對應(yīng)的錯誤模式，即錯誤個數(shù)超出了糾錯能力，因此算法此時實際上相當于檢測到糾錯能力范圍之外的一個錯誤模式。

5 結(jié)束語

本文利用QR碼的特點及伴隨式的重量，給出了QR碼的一個簡化譯碼算法。該譯碼算法簡單明了，容易理解和實現(xiàn)。其譯碼表的行數(shù)為，是目前QR碼的查表譯碼算法中最少的。

從本文的討論可以看出，這個數(shù)目還可進一步減少。在SMPSET中，錯誤模式經(jīng)過循環(huán)移位可以得到的所有錯誤模式中只需保留一個，其他的均可刪去。比如對Golay碼，SMPSET的12行可以只保留第一行，這個行數(shù)是最小的。

參 考 文 獻

[1] MIL-STD-188-141B. Interoperability and performance standards for medium and high frequency radio equipment[S]. Washington DC, USA: Army Information Systems Engineering Command, 1988.

[2] FED-STD-1045. Telecommunications: HF radio automatic link establishment[S]. Washington DC, USA: General Services Administration, 1990.

[3] PRANGE E. Some cyclic error-correcting codes with simple decoding algorithms[R]. Cambridge, MA: Tech Rep of Air Force Cambridge Research Center, AFCRC-TN-58-156, 1958.

[4] LEE H P, CHANG H C. An efficient decoding algorithm for the (73,37,13) quadratic residue code[C]//CSE 2011, Part I. Qingdao, China: Springer, 2011.

[5] LEE H P, CHANG H C. A memory improvement on decoding of the (41,21,9) quadratic residue code[J]. International Journal of Computer Theory and Engineering, 2012, 4(4): 590-594.

[6] LIN T C, LEE H P, CHANG H C, et al. A cyclic weight algorithm of decoding the (47,24,11) quadratic residue code[J]. Information Sciences, 2012, 197: 215-222.

[7] LEE H P, CHANG C H, CHU S I. High-speed decoding of the binary golay code[J]. Journal of Applied Research and Technology, 2013, 11: 331-337.

[8] WANG L, LI Y, TRUONG T K, et al. On decoding of the (89,45,17) quadratic residue code[J]. IEEE Trans Commun, 2013, 61(3): 832-841.

[9] 肖國鎮(zhèn), 卿斯?jié)h. 編碼理論[M]. 北京: 國防工業(yè)出版社, 1993. XIAO Guo-zhen, QING Si-han. Coding theory[M]. Beijing: National Defense Industry Press, 1993.

[10] 趙曉群. 現(xiàn)代編碼理論[M]. 武漢: 華中科技大學出版社, 2008. ZHAO Xiao-qun. Modern coding theory[M]. Wuhan：Huazhong University of Science and Technology Press, 2008.

[11] MCELIECE R J. The theory of information and coding [M]. 2nd ed. Beijin: Publishing House of Electronics Industry, 2002.

[12] MACWILLIAMS F J, SLOANE N J A. The theory of error-correcting codes[M]. Amsterdam: North-Holland Publishing Company, 1977.

[13] CHANG Y, TRUONG T K, REED I S, et al. Algebraic decoding of (71,36,11), (79,40,15), and(97,49,15)quadratic residue codes[J]. IEEE Transactions on Communications, 2003, 51(9): 1463-1473.

[14] REED I S, YIN X, TRUONG T K. Algebraic decoding of the (32,16, 8) quadratic residue code[J]. IEEE Trans Inform Theory, 1990, 36: 876-880.

[15] WICKER S B. Error control systems for digital communication and storage[M]. Englewood Cliffs NJ: Prentice-Hall, 1995.

[16] CHEN Y H, TRUONG T K, HUANG C H, et al. A lookup table decoding of systematic (47,24,11) quadratic residue code[J]. Information Sciences, 2009, 179: 2470-2477.

[17] CHEN Y H, CHIEN C H, HUANG C H, et al. Efficient decoding of systematic (23,12,7) and (41,21,9) quadratic residue codes[J]. Journal of Information Science and Engineering, 2010, 26(5): 1831-1843.

[18] LIN T C, LEE H P, CHANG H C, et al. High speed decoding of the binary (47,24,11) quadratic residue code[J]. Information Sciences, 2010,180: 4060-4068.

[19] CHANG H C, LEE H P, LIN T C, et al. A weight method of decoding the (23,12,7) Golay code using reduced table lookup[C]//2008 International Conference on Communication, Circuits and Systems (ICCCAS 2008). Xiamen: IEEE, 2008.

編 輯 稅 紅

A Simplified Table Lookup Decoding Algorithm for Binary QR Codes

BAO Xiao-min1, QU Yun-yun2, WU Deng-jie1, YUAN Zhi-hua1, LIU Xu1, and LI Mei1

(1. School of Mathematics and Statistics, Southwest University Beibei Chongqing 400715; 2. School of Mathematics Science, Guizhou Normal University Guiyang 550001)

A new simplified table lookup algorithm for decoding binary QR codes is presented. The algorithm is based on the properties of QR codes and the weights of syndromes. The decoding table is composed of the vectors of the form (,), whereis an error pattern, of which the error bits are located only in the information part and the number of errors is no more than half of the error-correcting capability of the code, andis the syndrome of. The algorithm can be applied to decoding any binary QR code. Moreover, the number of rows of the lookup table in this algorithm is the smallest one among all known lookup table decoding algorithms for binary QR codes.So this algorithm not only has certain theoretical significance, but also has certain practical value.

error pattern; Hamming weight; QR codes; syndrome; table lookup decoding

TP391

A

10.3969/j.issn.1001-0548.2016.05.014

2014-07-21；

2016-03-21

國家自然科學基金(61462016)；貴州省科學技術(shù)基金(黔科合J字[2014]2125號)

包小敏(1959-)，男，博士，教授，主要從事編碼理論和密碼學方面的研究.