QR 码详解（下）（qrspeed词库）

书接上回，继续下半场。

纠错码

QR 码采用纠错算法生成一系列纠错码字，添加在数据码字序列之后，使得符号可以在遇到损坏时可以恢复。这就是为什么二维码即使有残缺也可以扫出来。没有残缺创造残缺也要把它扫出来，相信大家见过很多中间带图标的二维码吧。

纠错码字可以纠正两种类型的错误，拒读错误（错误码字的位置已知）和替代错误（错误码字位置未知）。一个拒读错误是一个没扫描到或无法译码的符号字符，一个替代错误是错误译码的符号字符。如果一个缺陷使深色模块变成浅色模块，或将浅色模块变成深色模块，将符号字符错误地译码为是另一个不同的码字，造成替代错误，这种数据替代错误需要两个纠错码字来纠正。

纠错等级

纠错共有 4 个等级，对应 4 种纠错容量，如下表所示。

纠错等级

L

M

Q

H

纠错容量，%（近似值）

7

15

25

30

用户应确定合适的纠错等级来满足应用需求。从 L 到 H 四个不同等级所提供的检测和纠错的容量逐渐增加，其代价是对表示给定长度数据的符号的尺寸逐渐增加。例如，一个版本为 20-Q 的符号能包含 485 个数据码字，如果可以接受一个较低的纠错等级，则同样的数据也可用版本 15-L 的符号表示（准确数据容量为 523 个码字）。

纠错等级的选择与下列因素相关：

预计的符号质量水平：预计的符号质量等级越低，应用的纠错等级就应越高。

首读率的重要性。

在扫描误读失败后，再次扫描的机会。

印刷符号的空间限制了使用较高的纠错等级。

纠错等级【L】适用于具有高质量的符号以及/或者要求使表示给定数据的符号尽可能最小的情况。等级【M】被认为是“标准”等级，它具有较小尺寸和较高的可靠性。等级【Q】是具有“高可靠性”的等级，适用于一些重要的或符号印刷质量差的场合，等级【H】提供可实现的最高的可靠性。

纠错码字的生成

QR 码的纠错使用 Reed–Solomon 编码，有关 Reed–Solomon 码，可以参考这篇文章：http://article.iotxfd.cn/RFID/Reed%20Solomon%20Codes。这里我只大概介绍一下计算过程。

纠错码字的生成多项式

纠错码字是用数据码字除纠错码多项式所得到的余数。纠错码多项式我们可以查表得出，首先查下表 3：QR码符号各版本的纠错特性。这里我仅列出小部分，完整表数据请查看 GB/T 18284-2000 中的表 9。

表 3：QR码符号各版本的纠错特性

其中（c，k，r)：c=码字总数；k=数据码字数；r=纠错容量。

之前【例 1 续 1】确定使用的是版本1-H，查表得到纠错码字数为：17（上表红框部分）。码字总数为 26 表示此版本 QR 码可容纳的总数据量，其中数据码字占 9 个，纠错码字占 17 个。接下来根据纠错码字数 17 来查找多项式。可在 GB/T 18284-2000 附录 A 的纠错码字的生成多项式表中查找，也可使用生成多项式工具创建它，下表 4 只列出小部分内容：

表 4：QR码符号各版本的纠错特性

Reed–Solomon 码的 C# 实现

大家可能会问了，之前生成的纠错码字怎么跟这个多项式除啊？直接除肯定是不行的，首先要把查到的多项式转化为对应的一组数字。上表查到 17 所对应的生成多项式可转化为：[1, 119, 66, 83, 120, 119, 22, 197, 83, 249, 41, 143, 134, 85, 53, 125, 99, 79]。用数据码字除这组数字所得余数，就是我们的纠错码字了。当然，这个过程是使用程序来完成的。Reed–Solomon 编码这篇文章详细讲述了如何使用 Python 实现这个功能。我将需要用到的代码翻译成了 C#：

using System;

namespace QRHelper

{

class ECC

{

const int PRIM = 0x11d;

private static byte[] gfExp = new byte[512]; //逆对数(指数)表

private static byte[] gfLog = new byte[256]; //对数表

static ECC()

{

byte x = 1;

for (int i = 0; i <= 255; i++)

{

gfExp[i] = x;

gfLog[x] = (byte)i;

x = Gf_MultNoLUT(x, 2);

}

for (int i = 255; i < 512; i++)

{

gfExp[i] = gfExp[i - 255];

}

}

//伽罗华域乘法

private static byte Gf_MultNoLUT(int x, int y)

{

int r = 0;

while (y != 0)

{

if ((y & 1) != 0)

{

r ^= x;

}

y >>= 1;

x <<= 1;

if ((x & 256) != 0)

{

x ^= PRIM;

}

}

return (byte)r;

}

//伽罗华域乘法

private static byte GfMul(byte x, byte y)

{

if (x == 0 || y == 0)

{

return 0;

}

return gfExp[gfLog[x] + gfLog[y]];

}

//伽罗华域幂

private static byte GfPow(byte x, int power)

{

return gfExp[(gfLog[x] * power) % 255];

}

//多项式 乘法

private static byte[] GfPolyMul(byte[] p, byte[] q)

{

byte[] r = new byte[p.Length + q.Length - 1];

for (int j = 0; j < q.Length; j++)

{

for (int i = 0; i < p.Length; i++)

{

r[i + j] ^= GfMul(p[i], q[j]);

}

}

return r;

}

///

/// 获取纠错码字的生成多项式

///

/// 纠错码字数

/// 由一组数字表示的生成多项式

public static byte[] RsGeneratorPoly(int nsym)

{

byte[] g = { 1 };

for (int i = 0; i < nsym; i++)

{

g = GfPolyMul(g, new byte[] { 1, GfPow(2, i) });

}

return g;

}

///

/// 生成纠错码，并添加在数据码字之后

///

/// 数据码字

/// 纠错码字数

/// 数据码字+纠错码字

public static byte[] RsEncodeMsg(byte[] msgIn, int nsym)

{

if (msgIn.Length + nsym > 255)

{

throw new ArgumentException("数组长度超过 255！");

}

//byte[] gen = generators[(byte)nsym];

byte[] gen = RsGeneratorPoly(nsym);

byte[] msgOut = new byte[msgIn.Length + gen.Length - 1];

Array.Copy(msgIn, 0, msgOut, 0, msgIn.Length);

for (int i = 0; i < msgIn.Length; i++)

{

byte coef = msgOut[i];

if (coef != 0)

{

for (int j = 1; j < gen.Length; j++)

{

msgOut[i + j] ^= GfMul(gen[j], coef);

}

}

}

Array.Copy(msgIn, 0, msgOut, 0, msgIn.Length);

return msgOut;

}

}

}

代码量是相当少啊！根据不用上网找算法包。在实际开发中，如果需要绘制大量 QR 码，完全可以将所有 31 个生成多项式转化结果存放在集合中，使用时直接查询即可得出，这样可以大大加快生成速度。上述代码中的RsGeneratorPoly()方法用于生成多项式，它会产生大量临时数组。有了代码，可以继续我们之前的例子了。

【例 1 续 2】：生成完整码字

之前在【例 1 续 1】中，我们已经生成了数据码字：

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

16 进制表示形式为：0x10, 0x20, 0x0C, 0x56, 0x61, 0x80, 0xEC, 0x11, 0xEC

接下来使用如下代码生成完整码字：

byte[] msgin = { 0x10, 0x20, 0x0C, 0x56, 0x61, 0x80, 0xEC, 0x11, 0xEC };

byte[] msg = ECC.RsEncodeMsg(msgin, 17);

得到结果：0x10 0x20 0x0C 0x56 0x61 0x80 0xEC 0x11 0xEC 0x0E 0x9D 0x02 0xC8 0xC2 0x94 0xF3 0xA7 0xAD 0x8D 0xE2 0x0A 0xF4 0xA5 0x2B 0xAC 0xDF

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。