0

我正在使用 C++ 为 QR 码解码实现 Reed Solomon 解码。到目前为止，我已经实现了解码和错误检测的主要部分。我已遵循 ISO/IEC 18004:2006 手册。正如我在附件 B 中看到的：纠错解码步骤，综合症 S(i) 计算为 S(i) = R(a^i)。假设我们有高纠错级别，所以我们有 9 个数据码字和 17 个纠错码字，当我们处于 QR 码版本 1 时，总共有 26 个码字。所以，我假设显示的多项式 R(x)在 ISO/IEC 18004:2006 手册的第 76 页中，将分别是具有正确 x 次方的数据码字和纠错码字序列。因此， S(i) = R(a^j) ，其中 i=0...15 和 j=0...25 表示高纠错级别。但是，当我运行我的代码并且我有一个没有错误的整个二维码矩阵时，我希望所有综合症都等于零，因此我认为非零综合症。我是否通过 Reed Solomon 解码对 Galois Field Arithmetic 下的 Syndromes 计算理解错误？

4

1 回答 1

1

查看 QR 代码参考后，对于版本 1，级别 H，具有 9 个数据字节和 17 个纠错字节，使用生成多项式 g(x) = (x-1)(xa)(xa^2)...(xa ^(16)) 对于 i = 0 到 16，您应该使用校正子 S(i) = R(a^i)。在没有错误的情况下，所有 17 个校正子都应该为零。

Reed Solomon 纠错有一篇不错的 wiki 文章：

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

wiki 文章包含指向美国宇航局技术简报 RSEC 教程的链接：

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

链接到控制台程序的 C 源代码，该程序演示 8 位字段的 RSCC 方法（用户从 29 个可能的字段中选择）。我使用 Microsoft 编译器或 Visual Studio 编译它并使用 Windows 运行它，但它应该适用于大多数系统。

注意 - 我更新了 ecc 演示程序以处理除错误之外的擦除，以防万一它有用。在不使用欧几里德方法的情况下，还添加了计算误差值多项式 Omega 的代码。链接和之前一样：

http://rcgldr.net/misc/eccdemo8.zip

根据评论中的问题更新：

我关于哪个 GF(2^8) 的问题：

GF(2^8) is based on 9 bit polynomial
        x^8 + x^4 + x^3 + x^2 + 1 = hex 11d
        primitive is x + 0 (hex 2)

查找 QR 码参考，根据校正级别使用不同的生成多项式：L（低）、M（中）、Q（质量）、H（高）。

关于使用矩阵解码的问题。Sklar 论文展示了使用线性方程和矩阵求逆进行解码。此过程必须假设最大错误情况t，它将是 floor(e / 2) 其中 e 是纠错字节（也称为奇偶校验字节或冗余字节）的数量。如果行列式为零，则尝试t -1 错误，如果为零，则尝试t -2 错误，依此类推，直到行列式非零或 t 减少到零。

Euclid 或 Berlekamp Massey 解码方法将自动确定错误的数量。

在所有情况下，如果有超过t个错误，则可能会发生错误校正，这取决于产生 t 个位置且其中没有一个超出范围的可能性。如果从纠错中找到的任何 t 个位置超出范围，则检测到不可纠正的错误。

更新#2

我快速浏览了 ISO 文档。

生成多项式是 (x - 1) (x - 2) (x - 2^2) ...，因此要检查的伴随式是 S(0) 到 S(n-1)，如您之前提到的，在如果错误为零，则所有校正子 S(0) 到 S(n-1) 都应为零。

ISO文档使用术语codewords来指代字节（或符号），但在大多数ecc文章中，术语codeword是指包含数据和纠错字节的字节数组，而纠错字节通常称为奇偶校验字节，冗余字节或剩余字节。因此，如果阅读其他 ecc 文章，请记住这一点。

ISO 文档的第 37 页提到了“擦除”和“错误”，这是 RSECC 术语。“擦除”是指在 RSECC 之外检测到的已知位置的错误（或潜在错误）数据字节。“错误”是指在 RSECC 之外未检测到的坏字节，仅在 RSECC 解码期间确定。该文件然后指出，没有无效的数据位模式，这意味着没有“擦除”检测。然后，它通过显示一个包含擦除和错误计数的等式来增加混乱。

如果您好奇，RSECC 上的 Nasa pdf 文件从第 86 页开始解释擦除处理，但我认为这不适用于 QR 码。

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

回到 ISO 文档，它使用p来记录用于误解码保护的数量或纠错字节，而不是用于纠正。这显示在第 38 页的表 9 中。对于似乎是您正在使用的版本 1，重新解释：

error correction level
|    number of data bytes
|    |    number of ecc bytes used for correction
|    |    |    number of ecc bytes used for misdecode protection (p)
|    |    |    |    correction capability
L   19    4    3    2/26 ~ 07.69%
M   16    8    2    4/26 ~ 15.38%
Q   13   12    1    6/26 ~ 23.08%
H    9   16    1    8/26 ~ 30.77%

鉴于此表显示在不使用擦除的情况下满足预期的校正能力，那么即使可以检测到擦除，也不需要它们。

使用 GF(2^8)，RSECC 解码可以生成 255 个（不是 256 个）可能的错误位置，但在版本 1 中，只有 26 个有效位置。26 个有效位置之外的任何生成位置都将检测到不可纠正的错误。因此，对于L级，3 p字节转换为误校正的几率为 1/(2^24)，而位置范围将其乘以 (26/255)^2，概率约为 6.20E-10。对于H级别，1 p字节转换为 (1/2^8) 的误校正几率和 (26/255)^8 的位置范围的几率，概率约为 4.56E-11。

请注意，对于版本 2，对于级别 M、Q、H， p = 0，依赖于位置范围 (44/255)^(8 或 11 或 14)，误校正概率为 7.87E-7、4.04E-9、2.07 E-11。

于 2017-01-11T17:04:48.617 回答