二進(jìn)制QR碼的一個(gè)簡(jiǎn)化查表譯碼算法

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

?

二進(jìn)制QR碼的一個(gè)簡(jiǎn)化查表譯碼算法

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

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

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

錯(cuò)誤模式; Hamming 重量; QR碼; 伴隨式; 查表譯碼

QR碼是在1958年被提出的[3]。從那時(shí)起，人們對(duì)QR碼的研究就一直沒(méi)有停止過(guò)[4-8]。

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

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

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

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

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

3) 通過(guò)錯(cuò)誤模式進(jìn)行糾錯(cuò)，然后將糾錯(cuò)后的向量輸出。

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

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

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

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

則矩陣：

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

3 主要定理及證明

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

由定理2和定理3可得：

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

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

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

表1 MPSET表

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

實(shí)際上由定理1可得：

4 新的譯碼算法

然后計(jì)算SMPSET。

Algorithm：SimplifiedTLD

{

else {

}

}

if testedNo = 2

if testedNo = 3

}

output (“failure”);

else

}

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

5 結(jié)束語(yǔ)

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

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

參 考 文 獻(xiàn)

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

[10] 趙曉群. 現(xiàn)代編碼理論[M]. 武漢: 華中科技大學(xué)出版社, 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

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

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