QR码生成器中的Reed-Solomon算法

Question

在我的数据结构课程中，我想为我的期末项目创建一个QR码生成器。然而，我对“格式化错误校正”部分有些困惑。我想使用11（L）的错误校正和100（每隔一行）的掩膜模式。由于我是本科生，我想尽可能简单地处理版本1 QR码，并使用字节编码。

然后，我不明白如何在输出数据后计算出纠错盒。

- Isaac-Mick

Answer 1

在查看一些规范时，发现错误校正等级L（低级别，可以纠正7%）被识别为 01 这个两位比特模式，而不是11。以下是QR码格式字符串的链接，其中包括掩码和错误校正等级。 http://www.thonky.com/qr-code-tutorial/format-version-information 由于您选择了特定的错误校正等级和掩码模式，这与thonky.com网页中使用的相同，因此格式字符串将是15位固定的比特模式：“具有错误校正等级 L 和掩码模式 4 的代码的最终格式字符串为 110011000101111”，因此您无需计算它。

对于QR码，8比特字段GF（2^8）基于9位多项式。

    x^8 + x^4 + x^3 + x^2 + 1 = hex 11d
    the primitive   α = x + 0 = hex   2

请注意，二进制域的加法和减法与异或运算相同。

QR码版本1是一个由21x21个位（441位）组成的矩阵，用黑色或白色方块表示，其中208位（26字节）用于数据和纠错编码。

具有L级错误纠正水平的QR码具有152位（19字节）数据和56位（7字节）纠错编码，其中4字节用于纠正，3字节用于检测。用于纠正的4个字节可以纠正26个数据字节中的2个，约占7%。除了用于检测的3个字节之外，在解码期间，如果计算出的位置超出了26个数据字节的范围，则还会检测到无法纠正的错误。

生成多项式g(x)是一个8项多项式，其结果为7项余数。g(x)=0的7个根是α的连续幂，在这种情况下为α^0、α^1、...、α^6=hex 01、02、04、08、10、20、40。

g(x) = (x-1)(x-α)(x-α^2)(x-α^3)(x-α^4)(x-α^5)(x-α^6)

由于加法等于减法等于异或，因此可以用加号替换减号：

g(x) = (x+1)(x+α)(x+α^2)(x+α^3)(x+α^4)(x+α^5)(x+α^6)
g(x) = (x+01)(x+02)(x+04)(x+08)(x+10)(x+20)(x+40)
g(x) = 01 x^7 + 7f x^6 + 7a x^5 + 9a x^4 + a4 x^3 + 0b x^2 + 44 x + 75

将19字节的数据视为一个多项式m(x)(m代表消息)。通过乘以x^7，用7个零字节填充19个字节的数据。然后将26字节的多项式除以生成多项式，余数“减去”（异或或者由于填充产生了零，则余数仅替换填充字节）填充数据的低7字节。称余数为r(x)，编码结果为c(x):

r(x) = (m(x) x^7) % g(x)
c(x) = (m(x) x^7) - r(x)

请注意，减法是异或，与加法相同。维基百科有一篇不错的文章介绍了Reed Solomon：http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction，NASA也有一个教程：http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf。

- rcgldr