二进制QR码的一个简化查表译码算法

包小敏，瞿云云，武登杰，袁治华，刘 旭，李 梅



二进制QR码的一个简化查表译码算法

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

(1. 西南大学数学与统计学院 重庆北碚区 400715；2. 贵州师范大学数学科学学院 贵阳 550001)

基于QR码的特点和伴随式的重量，给出了二进制QR码的一个新的简化查表译码算法。译码表的行是形如(,)的向量，其中是错误仅出现在信息部分且错误个数不超过码的纠错能力一半的错误模式，是的伴随式。该算法适用于所有的二进制QR码。其译码表的行数在目前已知的二进制QR码的查表译码算法中是最小的。因此该算法不仅有一定的理论意义，也有一定的实用价值。

错误模式; Hamming 重量; QR码; 伴随式; 查表译码

QR码是在1958年被提出的[3]。从那时起，人们对QR码的研究就一直没有停止过[4-8]。

QR码是一类译码比较困难的“好”码[9]；而对于Q译R码的码，文献[10]认为QR码类的译码算法通常不具有规范的结构，针对不同的QR码，采用不同的译码算法[10]。因此对QR码的译码算法研究具有一定的理论意义和实际意义。

本文针对所有二进制QR码给出一个通用的简化查表译码算法。目前已有的二进制QR码的查表译码算法一般都是针对特定的QR码，本文给出的算法不仅具有适用性广的特点，而且译码表的行数也是最小的。

1 QR码及QR码的查表译码算法

QR码的译码分为两类：代数译码[13-14]和查表译码。查表译码的大致过程如下：

事先构造一个译码表，该表中一个错误模式与一个伴随式对应。对接收到的向量，按下面的步骤进行译码：

3) 通过错误模式进行纠错，然后将纠错后的向量输出。

查表译码最直接的做法是在译码表中将纠错能力范围内的所有错误模式和其对应的伴随式一一全部列出，这时译码表的行数为。由于译码表的大小直接影响查表译码算法的效率和实用性，所以长期以来有很多学者都致力于减少译码表的行数的研究。

以上这些算法大多数都是针对单个具体的QR码来给出的，且译码表的行数都大于。

通过研究，本文发现了QR码的一些性质，利用这些性质，给出一个针对所有二进制QR码的通用的查表译码算法，译码表的行数都为。该算法不仅能纠正小于或等于个的错误，而且还可以检测出部分多于个的错误。

2 循环码的生成矩阵和一致校验矩阵

则矩阵：

具有这种结构的码称为系统码。在系统码的情况下，将一个二进制维向量的前个分量称为信息部分，后个分量称为校验部分。

3 主要定理及证明

为了得到一个适用于所有QR码的通用算法，本文对QR进行研究，发现QR码都具有一些性质，利用这些性质可以得到一个通用的简化查表译码算法。将结果用6个定理的形式给出。

由定理2和定理3可得：

定理4给出了一个如何判别错误只出现在校验部分的方法及如何确定错误模式的方法。因此当错误只出现在校验部分时就可统一处理，而不必将每个错误模式和其对应的伴随式一一列出。下面只须考虑信息部分一定有错误出现的情形。

由定理5可知，在错误向量的伴随式及其信息部分对应的伴随式已知的情况下可以得到错误向量的校验部分。

其对应的伴随式分别为：

表1 MPSET表

在实际译码时并不知道错误向量的信息部分，所以定理5的结果不具可操作性。定理6则从理论上保证由错误向量的伴随式和表MPSET，通过比较向量的汉明重量就可确定错误向量。因为错误向量的伴随式可通过接收到的向量得到，而表MPSET可事先做好，所以定理6的结果可实际操作。

实际上由定理1可得：

4 新的译码算法

然后计算SMPSET。

Algorithm：SimplifiedTLD

{

else {

}

}

if testedNo = 2

if testedNo = 3

}

output (“failure”);

else

}

当算法输出“failure”时，表明在SMPSET中没有找到对应的错误模式，即错误个数超出了纠错能力，因此算法此时实际上相当于检测到纠错能力范围之外的一个错误模式。

5 结束语

本文利用QR码的特点及伴随式的重量，给出了QR码的一个简化译码算法。该译码算法简单明了，容易理解和实现。其译码表的行数为，是目前QR码的查表译码算法中最少的。

从本文的讨论可以看出，这个数目还可进一步减少。在SMPSET中，错误模式经过循环移位可以得到的所有错误模式中只需保留一个，其他的均可删去。比如对Golay码，SMPSET的12行可以只保留第一行，这个行数是最小的。

参 考 文 献

[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] 肖国镇, 卿斯汉. 编码理论[M]. 北京: 国防工业出版社, 1993. XIAO Guo-zhen, QING Si-han. Coding theory[M]. Beijing: National Defense Industry Press, 1993.

[10] 赵晓群. 现代编码理论[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)；贵州省科学技术基金(黔科合J字[2014]2125号)

包小敏(1959-)，男，博士，教授，主要从事编码理论和密码学方面的研究.