问里德·所罗门译码.误差校正.符号计算

EN

在查看QR代码引用后，对于版本1，级别H，使用生成器多项式g(x) =(x-1)(x-a)(x-a^2).(x-a^( 16 ))，你应该使用综合征S(i) = R(a^i)来表示i=0到16。在没有错误的情况下，所有17种综合征都应该是零。

里德·所罗门有一篇很好的wiki文章用于纠正错误：

correction

这篇wiki文章包含一个指向Nasa技术简介RSECC教程的链接：

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

链接到控制台程序的C源代码，该程序演示8位字段的RSECC方法(用户从29个可能的字段中选择)。我使用Microsoft编译器或Visual编译它，使用Windows运行它，但是它应该在大多数系统上工作。

注-我更新了ecc演示程序，以处理除错误之外的擦除，以防万一有用。在不使用欧几里得方法的情况下，还增加了计算误差值多项式欧米茄的代码。该链接与以前相同：

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，它将是底层(e/ 2)，其中e是纠错字节数(也称为奇偶字节或冗余字节)。如果行列式为零，则尝试t-1错误，如果为零，尝试t-2错误等等，直到行列式为非零或t被降为零。

欧几里德或Berlekamp Massey解码方法将自动确定错误的数量。

在所有情况下，如果有超过t个错误，就有可能出现错误校正，这取决于产生t个位置的概率，而这些位置中没有一个是超出范围的。如果从纠错中发现的任何t位置超出了范围，则检测到不可纠正的错误。

更新#2

我对ISO文档做了一个快速的概述。

生成多项式为(x - 1) (x - 2) (x - 2^2) .

ISO文档使用编码词来引用字节(或符号)，但在大多数ecc文章中，代码字一词指的是包括数据和纠错字节在内的字节数组，而纠错字节通常称为奇偶字节、冗余字节或剩余字节。因此，如果阅读其他ecc文章，请记住这一点。

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

如果你好奇，美国宇航局在RSECC上的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级，3p字节转换成1/(2^24)的错误校正概率，而位置范围多了(26/255)^2，大约为6.20E-10概率。对于H级，对于4.56E-11概率，1p字节转换为(1/2^8)的错误校正概率和(26/255)^8的位置范围。

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