c++ - QR 码生成器的 Reed-Solomon 算法

Question

在我的数据结构类(class)中，我想为我的最终项目创建一个二维码生成器。但是，我在理解其中的“格式化错误更正”部分时遇到了一些麻烦。我想使用 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

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

QR 码版本 1 是一个 21 x 21 位 = 441 位的矩阵，表示为黑色或白色方 block ，其中 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 == 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，19 个字节的数据用 7 个字节的零填充。然后将 26 字节多项式除以生成多项式，并将余数“减去”(异或或因为填充产生零，余数只是替换填充字节)到填充数据的低 7 字节。调用余数r(x)，编码结果c(x):

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

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

Wiki 上有一篇关于 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