用于QR码生成器的Reed-Solomon算法

Question

在我的数据结构类中，我想为我的最终项目创建一个QR码生成器。不过，我在理解“格式化错误修正”部分时遇到了一些麻烦。我想使用11（L）的错误校正和100（每隔一行）的掩蔽模式。由于我是一名本科生，因此我想尝试使用版本1 QR代码并使用字节编码来保持它非常简单。

然后我不明白如何在数据输出后提出错误更正框。

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是由21位= 441位表示的矩阵，表示为黑色或白色方块，其中208位== 26字节用于数据和ecc。

具有纠错等级L的QR码具有152位== 19个字节的数据和56位== 7个字节的ecc，4个用于校正，3个用于检测。用于校正的4个字节可以校正26个字节中的2个，约26个数据字节的7％。除了用于检测的3个字节外，如果在解码期间，计算出的任何一个位置都在26个字节的数据范围之外，也会检测到不可纠正的错误。

生成多项式g（x）是导致7项余数的8项多项式。 g（x）= 0的7个根是α的连续幂，在这种情况下，α^ 0，α^ 1，...α^ 6 ==十六进制01,02,04,08,10,20,40。

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

由于除了==减法== XOR，所述弊可以用加号代替：

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表示消息） 。 19个字节的数据用7个字节的零填充x^7。然后，26字节多项式被生成多项式除并且余数被“减”（异或因为填充产生零，余数仅替换填充的字节）到填充数据的低7字节。调用余数r（x）和编码结果C（X）：

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

再次注意减法是异或，相同的加法。

Wiki有关于里德 - 所罗门像样的文章：

http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

和美国航天局有一个教程：

http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf