二维条码QR Code编码原理及实现

摘要：在二维码编码的实现过程中，分析了QR Code二维条码的结构、编码步骤、编码原理和Reed-Solomon算法，并以数字模式为实例按照QR Code编码原理直观的描述了实现二维码QR Code的编码、纠错等功能。采用VC++的编程环境，通过对二维码编码程序反复测试，实现了二维码QR Code的编码程序设计。

关键词：QR Code；二维码；编码；VC++；纠错

中图分类号：TP319 文献标识码：A 文章编号：1009-3044（2013）12-2904-05

条码是采用二进制概念的一种可印刷机器语言，具体地就是以“1”和“0”表示编码的特定单元组合，以排列规则的图形符号表示数据。条码技术是在20世纪70年代初快速发展并得到广泛应用的一门技术，早期的条码称为一维条码，仅仅只是一种商品的标识，不含商品的任何描述。随着现代高新技术和资料自动收集技术的发展，最初的一维条码技术已不能满足人们的需求。于是在1987年David Allais博士提出了Code49的二维码[1]，这实际是把一维条码的高度截短并按行堆积的一种多行连续型长度可变条码。如今常用的二维码有：PDF417码、QR Code码、DataMatrix码等等。

1 二维码QR Code编码原理

1.1 QR Code简述

1994年9月日本Denso公司开发了一种矩阵式二维条码符号，即QR Code（Quick Response Code）快速响应矩阵码。QR Code除具有一维条码及其它二维条码所具有的优点外，还具有识读速度快、数据密度大、占用空间小的优势。QR Code基本结构如图1所示。

其中，位置探测图形、位置探测图形分隔符、定位图形：用于对二维码的定位，对每个QR码来说，位置都是固定存在的，只是大小规格会有所差异；

校正图形：规格确定，校正图形的数量和位置也就确定了；

格式信息：表示改二维码的纠错级别，分为L、M、Q、H；

版本信息：即二维码的规格，QR码符号共有40种规格的矩阵（一般为黑白色），从21×21（版本1）如图2，到177×177（版本40），每一版本符号比前一版本的每边增加4个模块。

数据和纠错码字：实际保存的二维码信息，和纠错码字（用于修正二维码损坏带来的错误）。

1.2 QR Code编码

1.2.1 QR Code编码步骤

QR Code编码的主要步骤如下：

1）数据分析：确定编码的字符类型，按相应的字符集转换成符号字符； 选择纠错等级，在规格一定的条件下，纠错等级越高其真实数据的容量越小。

2）数据编码：将数据字符转换为位流，每8位一个码字，整体构成一个数据的码字序列。其实知道这个数据码字序列就知道了二维码的数据内容。

3）纠错编码：按需要将上面的码字序列分块，并根据纠错等级和分块的码字，产生纠错码字，并把纠错码字加入到数据码字序列后面，成为一个新的序列。

4）构造最终数据信息：在规格确定的条件下，将上面产生的序列按次序放入分块中。

5）构造矩阵：将探测图形、分隔符、定位图形、校正图形和码字模块放入矩阵中。

6）掩摸：将掩摸图形用于符号的编码区域，使得二维码图形中的深色和浅色（黑色和白色）区域能够比率最优的分布，提高阅读的可靠性。

7）格式和版本信息：生成格式和版本信息放入相应区域内。

1.2.2 Reed-Solomon算法

1960年Reed和Solomon共同提出了一种纠正随机错误和突发错误的编码，及Reed-Solomon（简称RS）码。RS码是循环码的一种，在伽罗华域GF（2m）中对数据位进行编码。若a∈GF（2m）对于纠正r个错误符号的RS码生成多项式[2]可表示为：

g（x）=（x+a）（x+a2）（x+a3）……（x+a2r） （1）

若原始信息的多项式为：m（x）=（a0+a1x+a2x2+……+ak-1xk-1），进行RS编码后的表达式[2]为：

d（x）=x2rm（x）+x2rm（x） mod g（x） （2）

其中：x2rm（x）是原始数据码；x2rm（x） mod g（x）是纠错码字部分。

1.2.3 编码实例

为了能使QR Code生成有个直观了解，下面举例进行说明。

例如：以“01234567”这8个字符为例，采用数字模式，编码一个版本号为1-M纠错等级的QR Code。

1）将输入字符分为3个一组，剩下的2个或1个一组，且将每一组都转换为10位或7位二进制数；

012：0000001100

345：0101011001

67 ：1000011

得到二进制序列为：0000001100 0101011001 1000011

2）将模式指示符和字符数依次放到上述序列前，并在最后放入结束符0000结果为：0001 0000001000 0000001100 0101011001 1000011 0000

3）将上述得到的二进制数分为8位一组的码字，并加入所需的填充位后得到的序列为：

00010000 00100000 00001100 01010110 01100001 10000000

4）因为版本1-M数据码字容量为16个码字，因此上面序列还需10个填充码字，故用填充码11101100和00010001依次进行填充，结果为：

00010000 00100000 00001100 01010110 01100001 10000000 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001 11101100 00010001

5）根据版本1-M需要10个纠错码字对应的生成多项式g（x）为：

g（x）=x10+a251x9+a67x8+a46x7+a61x6+a118x5+a70x4+a64x3+a94x2+a32x+a45

6.纠错等级M其掩膜图形参考为：101，二进制字符串为：00101，生成多项式为：x2+1.

QR码中用BCH（15，5）码纠错，故将多项式次数提升（15-5）次方后为：x12+x10 被G（x）除后的结果是：（x10+x8+x5+x4+x2+x+1）x2+（x7+x6+x4+x3+x2）

把上面剩余多项式的系数字符串：001010011011100附加至格式信息数据串即可。

2 二维码QR Code编码实现

2.1 二维编码对话框设计

在VC++中建立好工程后，就可以设计操作界面，类，变量，映射消息及及成员函数等。下图是设计好的二维编码对话框。

使用上面对话框，用户可以选择不同的纠错级别，掩膜号，版本信息，并在二维条码输入区输入不同信息后，在二维条码显示区就能显示相应的二维码形状，若输入“01234567”显示为图4，若输入“四川长江职业学院”显示为图5。

2.2 二维编码算法实现

根据前面的描述，下面给出了二维编码程序流程示意图。

图6 二维编码程序流程示意图

根据上面的程序流程示意图，下面是编码算法实现的主要代码。

EncodeData（int nLevel， int nVersion， BOOL bAutoExtent， int nMaskingNo， LPCSTR lpsSource， int ncSource）

{ int i， j；

m_nLevel = nLevel；//纠错级别

m_nMaskingNo = nMaskingNo；//掩膜号

int ncLength = ncSource > 0 ？ ncSource ： lstrlen（lpsSource）；

if （ncLength == 0）

return FALSE；

// 获取版本号

int nEncodeVersion = GetEncodeVersion（nVersion， lpsSource， ncLength）；

if （nEncodeVersion == 0）

return FALSE；

if （nVersion == 0）

{m_nVersion = nEncodeVersion；}

else

{if （nEncodeVersion <= nVersion）

{m_nVersion = nVersion；}

else

{if （bAutoExtent）

m_nVersion = nEncodeVersion；

else

return FALSE； }}

// "0000" 加入终止符号

int ncDataCodeWord = QR_VersonInfo[m_nVersion].ncDataCodeWord[nLevel]；

int ncTerminater = min（4， （ncDataCodeWord * 8） - m_ncDataCodeWordBit）；

if （ncTerminater > 0）

m_ncDataCodeWordBit = SetBitStream（m_ncDataCodeWordBit， 0， ncTerminater）；

//"11101100， 00010001"增加数据码字

BYTE byPaddingCode = 0xec；

for （i = （m_ncDataCodeWordBit + 7） / 8； i < ncDataCodeWord； ++i）

{ m_byDataCodeWord[i] = byPaddingCode；

byPaddingCode = （BYTE）（byPaddingCode == 0xec ？ 0x11 ： 0xec）；}

m_ncAllCodeWord = QR_VersonInfo[m_nVersion].ncAllCodeWord；

ZeroMemory（m_byAllCodeWord， m_ncAllCodeWord）；

int nDataCwIndex = 0；

int ncBlock1 = QR_VersonInfo[m_nVersion].RS_BlockInfo1[nLevel].ncRSBlock；

int ncBlock2 = QR_VersonInfo[m_nVersion].RS_BlockInfo2[nLevel].ncRSBlock；

int ncBlockSum = ncBlock1 + ncBlock2；

int nBlockNo = 0；

//信息块输入

int ncDataCw1 = QR_VersonInfo[m_nVersion].RS_BlockInfo1[nLevel].ncDataCodeWord；

int ncDataCw2 = QR_VersonInfo[m_nVersion].RS_BlockInfo2[nLevel].ncDataCodeWord；

for （i = 0； i < ncBlock1； ++i）

{for （j = 0； j < ncDataCw1； ++j）

{m_byAllCodeWord[（ncBlockSum * j） + nBlockNo] = m_byDataCodeWord[nDataCwIndex++]；}

++nBlockNo；}

for （i = 0； i < ncBlock2； ++i）

{for （j = 0； j < ncDataCw2； ++j）

{if （j < ncDataCw1）

{m_byAllCodeWord[（ncBlockSum * j） + nBlockNo] = m_byDataCodeWord[nDataCwIndex++]；}

else

{m_byAllCodeWord[（ncBlockSum * ncDataCw1） + i] = m_byDataCodeWord[nDataCwIndex++]；}}

++nBlockNo；}

// 纠错块输入

int ncRSCw1 = QR_VersonInfo[m_nVersion].RS_BlockInfo1[nLevel].ncAllCodeWord - ncDataCw1；

int ncRSCw2 = QR_VersonInfo[m_nVersion].RS_BlockInfo2[nLevel].ncAllCodeWord - ncDataCw2；

nDataCwIndex = 0；

nBlockNo = 0；

for （i = 0； i < ncBlock1； ++i）

{ZeroMemory（m_byRSWork， sizeof（m_byRSWork））；

memmove（m_byRSWork， m_byDataCodeWord + nDataCwIndex， ncDataCw1）；

GetRSCodeWord（m_byRSWork， ncDataCw1， ncRSCw1）；//调用reed_solomon算法进行纠错

for （j = 0； j < ncRSCw1； ++j）

{m_byAllCodeWord[ncDataCodeWord + （ncBlockSum * j） + nBlockNo] = m_byRSWork[j]；}

nDataCwIndex += ncDataCw1；

++nBlockNo；}

for （i = 0； i < ncBlock2； ++i）

{ZeroMemory（m_byRSWork， sizeof（m_byRSWork））；

memmove（m_byRSWork， m_byDataCodeWord + nDataCwIndex， ncDataCw2）；

GetRSCodeWord（m_byRSWork， ncDataCw2， ncRSCw2）； //调用reed_solomon算法进行纠错

for （j = 0； j < ncRSCw2； ++j）

{m_byAllCodeWord[ncDataCodeWord + （ncBlockSum * j） + nBlockNo] = m_byRSWork[j]；}

nDataCwIndex += ncDataCw2；

++nBlockNo；}

m_nSymbleSize = m_nVersion * 4 + 17；

FormatModule（）；

return TRUE；}

3 结论

实验实现了在录入数据时，能根据不同版本，纠错级别，掩膜号生成QR Code二维条码。因二维条码具有储存量大、保密性高、追踪性高、抗损性强、备援性大、成本便宜等特性，这些特性特别适用于表单如进出口报单、安全保密如商业情报、追踪如生产线零件自动追踪、证照如身份证、存货盘点如物流中心等方面。

参考文献：

[1] 刘苇娜.QR Code二维条码的编码与图像处理技术的研究[D].湖北大学，2007.

[2] 冯汉禄，黄颍为，牛晓娇，钱银超.QR码纠错码原理及实现[J].计算机应用，2011（6）：40-42.

[3] 黄宏博，肖峻岭，佟俐鹃.基于Reed-Solomon算法的QR码纠错编码[J].计算机工程，2003，29（1）：93-95.

[4] 宋作玲，刘志海.基于VC++的QR Code条码编程实现[J].山东科技大学学报：自然科学版，2010，29（6）：80-84.

[5] 曾子剑.基于QR二维码编码技术的研究与实现[D].电子科技大学，2007.

[6] 许统.手机二维码在国内的发展及应用[J]，电脑与信息技术，2011，19（3）：62-63.

[7] 杨平.QR Code条码编解码及应用的研究[D].五邑大学，2009.

[8] 蔡文婷.移动端二维条码图像增强及应用研究[D].浙江工业大学，2008.