Reed Solomon解码-纠错-综合症计算
Reed Solomon Decoding - Error Correction - Syndromes Calculation
我正在使用 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 手册的 Pg.76 中将是一系列
分别具有正确的 x 次幂的数据码字和纠错码字。因此， S(i) = R(a^j) ，其中 i=0...15 和 j=0...25 对于高纠错级别。但是，当我 运行 我的代码并且我有一个没有错误的完整 QR 码矩阵时，我希望所有综合症都等于零，因此我认为非零综合症。我是否理解了通过 Reed Solomon 解码在 Galois Field Arithmetic 下进行 Syndromes 计算的错误？
查看 QR 码参考资料后，对于版本 1，H 级，具有 9 个数据字节和 17 个纠错字节，使用生成多项式 g(x) = (x-1)(x-a)(x-a^2) ...(x-a^(16)) 对于 i = 0 到 16，您应该使用校正子 S(i) = R(a^i)。在没有错误的情况下，所有 17 个校正子都应该为零。
Reed Solomon 纠错有一篇不错的 wiki 文章：
http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
维基文章包含 link 到 Nasa 技术简报 RSECC 教程：
http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf
Link 到控制台程序的 C 源代码，演示 8 位字段的 RSECC 方法（用户从 29 个可能的字段中选择）。我使用 Microsoft 编译器或 Visual Studio 来编译它，Windows 到 运行 它，但它应该适用于大多数系统。
注意 - 我更新了 ecc 演示程序以处理除错误之外的擦除，以防万一它可能有用。如果不使用 Euclid 方法，还添加了计算误差值多项式 Omega 的代码。 link 和之前一样：
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)
查找二维码参考，根据校正级别使用不同的生成多项式：L（低）、M（中）、Q（质量）、H（高）。
关于使用矩阵解码的问题。 Sklar 论文展示了使用线性方程和矩阵求逆进行解码。此过程必须假设最大错误情况 t，这将是 floor(e / 2)，其中 e 是纠错字节数（也称为奇偶校验字节或冗余字节）。如果行列式为零，则尝试 t-1 个错误，如果为零，则尝试 t-2 个错误，依此类推，直到行列式为非-零或 t 减为零。
Euclid 或 Berlekamp Massey 解码方法将自动确定错误数。
在所有情况下，如果有超过 t 个错误，则有可能会发生错误更正，这取决于产生 [=98] 的 t 个位置的几率=] 其中超出范围。如果从纠错中找到的任何 t 个位置超出范围，则检测到 uncorrectable 错误。
更新#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页提到了"erasures"和"errors"，这是RSECC术语。 "Erasures" 指的是在 RSECC 外部检测到的已知位置的坏（或潜在坏）数据字节。 "Errors" 指的是在 RSECC 之外未检测到的坏字节，仅在 RSECC 解码期间确定。然后文档指出没有无效数据位模式，这意味着没有 "erasure" 检测。然后，它通过显示包含擦除和错误计数的等式来增加混乱。
如果您好奇，RSECC 上的 Nasa pdf 文件从第 86 页开始解释了擦除处理，但我认为这不适用于 QR 码。
http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf
回到 ISO 文档，它使用 p 来记录用于错误解码保护的数字或纠错字节，而不是用于纠正。这在第38页的table 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%
鉴于这个table表明在不使用擦除的情况下达到了预期的校正能力，那么即使可以检测到擦除，也不需要它们。
对于 GF(2^8)，RSECC 解码可以产生 255（不是 256）个可能的错误位置，但在版本 1 中，只有 26 个有效位置。 26 个有效位置之外的任何生成位置都将检测到 uncorrectable 错误。因此，对于 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，p = 0 对于级别 M、Q、H，取决于位置范围 (44/255)^(8 or 11 or 14)对于 7.87E-7、4.04E-9、2.07E-11 的错误校正概率。
我正在使用 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 手册的 Pg.76 中将是一系列 分别具有正确的 x 次幂的数据码字和纠错码字。因此， S(i) = R(a^j) ，其中 i=0...15 和 j=0...25 对于高纠错级别。但是，当我 运行 我的代码并且我有一个没有错误的完整 QR 码矩阵时，我希望所有综合症都等于零，因此我认为非零综合症。我是否理解了通过 Reed Solomon 解码在 Galois Field Arithmetic 下进行 Syndromes 计算的错误？
查看 QR 码参考资料后，对于版本 1，H 级，具有 9 个数据字节和 17 个纠错字节，使用生成多项式 g(x) = (x-1)(x-a)(x-a^2) ...(x-a^(16)) 对于 i = 0 到 16，您应该使用校正子 S(i) = R(a^i)。在没有错误的情况下，所有 17 个校正子都应该为零。
Reed Solomon 纠错有一篇不错的 wiki 文章：
http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
维基文章包含 link 到 Nasa 技术简报 RSECC 教程：
http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf
Link 到控制台程序的 C 源代码，演示 8 位字段的 RSECC 方法（用户从 29 个可能的字段中选择）。我使用 Microsoft 编译器或 Visual Studio 来编译它，Windows 到 运行 它，但它应该适用于大多数系统。
注意 - 我更新了 ecc 演示程序以处理除错误之外的擦除，以防万一它可能有用。如果不使用 Euclid 方法，还添加了计算误差值多项式 Omega 的代码。 link 和之前一样：
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)
查找二维码参考，根据校正级别使用不同的生成多项式：L（低）、M（中）、Q（质量）、H（高）。
关于使用矩阵解码的问题。 Sklar 论文展示了使用线性方程和矩阵求逆进行解码。此过程必须假设最大错误情况 t，这将是 floor(e / 2)，其中 e 是纠错字节数（也称为奇偶校验字节或冗余字节）。如果行列式为零，则尝试 t-1 个错误，如果为零，则尝试 t-2 个错误，依此类推，直到行列式为非-零或 t 减为零。
Euclid 或 Berlekamp Massey 解码方法将自动确定错误数。
在所有情况下，如果有超过 t 个错误，则有可能会发生错误更正，这取决于产生 [=98] 的 t 个位置的几率=] 其中超出范围。如果从纠错中找到的任何 t 个位置超出范围，则检测到 uncorrectable 错误。
更新#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页提到了"erasures"和"errors"，这是RSECC术语。 "Erasures" 指的是在 RSECC 外部检测到的已知位置的坏（或潜在坏）数据字节。 "Errors" 指的是在 RSECC 之外未检测到的坏字节，仅在 RSECC 解码期间确定。然后文档指出没有无效数据位模式，这意味着没有 "erasure" 检测。然后，它通过显示包含擦除和错误计数的等式来增加混乱。
如果您好奇，RSECC 上的 Nasa pdf 文件从第 86 页开始解释了擦除处理，但我认为这不适用于 QR 码。
http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf
回到 ISO 文档，它使用 p 来记录用于错误解码保护的数字或纠错字节，而不是用于纠正。这在第38页的table 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%
鉴于这个table表明在不使用擦除的情况下达到了预期的校正能力，那么即使可以检测到擦除，也不需要它们。
对于 GF(2^8)，RSECC 解码可以产生 255（不是 256）个可能的错误位置，但在版本 1 中，只有 26 个有效位置。 26 个有效位置之外的任何生成位置都将检测到 uncorrectable 错误。因此，对于 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，p = 0 对于级别 M、Q、H，取决于位置范围 (44/255)^(8 or 11 or 14)对于 7.87E-7、4.04E-9、2.07E-11 的错误校正概率。