问QR码发生器的里德-所罗门算法

EN

从一些规范上看，纠错级别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

请注意，二进制字段的加法和减法都与xor相同。

QR码版本1是由21位乘21位= 441位表示为黑白方阵的矩阵，208个位== 26字节用于数据和ecc。

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

生成多项式g(x)是一个8项多项式，其结果为7项余数。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字节的数据与0的7字节相乘，乘以x^7。然后将26字节多项式除以生成器多项式，其余部分被“减去”(xor‘’ed或由于填充产生零，其余的只替换填充的字节)到填充数据的低7字节。调用剩余的r(x)和编码结果c(x)：

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

请再次注意，减法是xor，与加法相同。

Wiki有一篇关于里德·所罗门的像样文章：

correction

美国宇航局有一个教程：

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