为什么只差错解码对小奇偶校验误纠率高？
Why error-only decoding has high miscorrection rate for small parity?
我对本文中的陈述“广义集成交错码”有疑问。论文中提到RS码的擦除解码不会产生误纠，而RS码的只错解码在纠错能力太低的情况下会导致较高的误纠率。
根据我的理解，我认为擦除解码和仅错误解码之间的区别在于擦除解码不需要计算错误位置。另一方面，仅错误解码需要知道错误位置，这可以通过 Berlekamp-Massey 算法计算。我想知道错误解码的错误纠正是否来自计算错误的错误位置？如果是，为什么误纠率与RS码的纠错能力有关？
miscorrection for error-only decoding comes from computing the wrong error locations
是的。例如，考虑一个具有 6 个奇偶校验位的 RS 码，它可以纠正 3 个错误。假设发生了 4 个错误，并且第 3 个错误更正尝试又产生了 3 个错误，总共有 7 个错误。它会产生一个有效的代码字，但是错误的代码字。
有些情况下可以降低错误纠正的可能性。如果消息是缩短的消息，比如 64 字节的数据和 6 个奇偶校验，总共 70 字节，那么如果 3 错误情况产生无效位置，则可以避免错误更正。在这种情况下，3 个随机位置有效的几率为 (70/255)^3 ~= .02 (2%)。
另一种避免错误校正的方法是不使用所有奇偶校验进行校正。对于 6 个奇偶校验，可以将校正限制为 2 个错误，留下 2 个奇偶校验用于检测目的。或者使用7个校验位，用于3个纠错，1个校验位用于检测。
根据评论跟进：
首先要注意的是，有3种解码器可以用于BCH view Reed Solomon：PGZ（Peterson Gorenstein Zierler）矩阵解码器，BKM（Berlekamp Massey）差异解码器，以及Sugiyama的扩展Euclid解码器。 PGZ 的时间复杂度 O((n-k)^3) 比 BKM 或 Euclid 大，所以大多数实现都使用 BKM 或 Euclid。您可以在这里阅读更多关于这些解码器的信息：
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
回到 6 个奇偶校验，4 个错误。所有有效的 RS(n+6, n) 码字彼此至少有 7 个元素不同。如果消息的 4 个元素有误，则可能有一个有效代码字与具有 4 个错误元素的消息仅相差 3 个元素，在这种情况下，所有 3 个解码器都会发现该消息与有效代码字不同由 3 个元素组成的代码字，并“更正”这 3 个元素以生成有效代码字，但在这种情况下，错误的有效代码字将与原始代码字相差 7 个元素。有 5 个元素错误，可能会发生 2 或 3 个错误错误纠正，而有 6 个或更多
错误的元素，可能会出现 1 或 2 或 3 错误错误更正。
无效位置 - 考虑基于 GF(2^8) 的 RS 代码，它允许消息大小最大为 255 字节。 255 字节消息的有效位置为 0 到 254。如果消息大小小于 255 字节，例如 64 数据 + 6 奇偶校验 = 70 字节，则位置 0 到 69 有效，而位置 70 到 254 无效。在错误校正的情况下，如果计算出的位置超出范围，则解码器检测到无法校正的消息，而不是错误校正它。假设一条乱码消息，解码器生成 0 到 254 范围内的 3 个随机位置，所有 3 个都在 0 到 69 范围内的概率是 (70/255)^3.
另一种避免错误校正的情况是当错误定位器多项式的不同根的数量与多项式的次数不匹配时。考虑生成错误定位器多项式 x^3 + a x^2 + b x + c 的 3 个错误情况。如果消息中有超过 3 个错误，则生成的多项式可能具有少于 3 个不同的根，例如双根、零根或 ...，在这种情况下，可以避免错误纠正，并且消息被检测为无法纠正。
我对本文中的陈述“广义集成交错码”有疑问。论文中提到RS码的擦除解码不会产生误纠，而RS码的只错解码在纠错能力太低的情况下会导致较高的误纠率。
根据我的理解，我认为擦除解码和仅错误解码之间的区别在于擦除解码不需要计算错误位置。另一方面，仅错误解码需要知道错误位置，这可以通过 Berlekamp-Massey 算法计算。我想知道错误解码的错误纠正是否来自计算错误的错误位置？如果是，为什么误纠率与RS码的纠错能力有关？
miscorrection for error-only decoding comes from computing the wrong error locations
是的。例如，考虑一个具有 6 个奇偶校验位的 RS 码，它可以纠正 3 个错误。假设发生了 4 个错误，并且第 3 个错误更正尝试又产生了 3 个错误，总共有 7 个错误。它会产生一个有效的代码字，但是错误的代码字。
有些情况下可以降低错误纠正的可能性。如果消息是缩短的消息，比如 64 字节的数据和 6 个奇偶校验，总共 70 字节，那么如果 3 错误情况产生无效位置，则可以避免错误更正。在这种情况下，3 个随机位置有效的几率为 (70/255)^3 ~= .02 (2%)。
另一种避免错误校正的方法是不使用所有奇偶校验进行校正。对于 6 个奇偶校验，可以将校正限制为 2 个错误，留下 2 个奇偶校验用于检测目的。或者使用7个校验位，用于3个纠错，1个校验位用于检测。
根据评论跟进：
首先要注意的是，有3种解码器可以用于BCH view Reed Solomon：PGZ（Peterson Gorenstein Zierler）矩阵解码器，BKM（Berlekamp Massey）差异解码器，以及Sugiyama的扩展Euclid解码器。 PGZ 的时间复杂度 O((n-k)^3) 比 BKM 或 Euclid 大，所以大多数实现都使用 BKM 或 Euclid。您可以在这里阅读更多关于这些解码器的信息：
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
回到 6 个奇偶校验，4 个错误。所有有效的 RS(n+6, n) 码字彼此至少有 7 个元素不同。如果消息的 4 个元素有误，则可能有一个有效代码字与具有 4 个错误元素的消息仅相差 3 个元素，在这种情况下，所有 3 个解码器都会发现该消息与有效代码字不同由 3 个元素组成的代码字，并“更正”这 3 个元素以生成有效代码字，但在这种情况下，错误的有效代码字将与原始代码字相差 7 个元素。有 5 个元素错误，可能会发生 2 或 3 个错误错误纠正，而有 6 个或更多 错误的元素，可能会出现 1 或 2 或 3 错误错误更正。
无效位置 - 考虑基于 GF(2^8) 的 RS 代码，它允许消息大小最大为 255 字节。 255 字节消息的有效位置为 0 到 254。如果消息大小小于 255 字节，例如 64 数据 + 6 奇偶校验 = 70 字节，则位置 0 到 69 有效，而位置 70 到 254 无效。在错误校正的情况下，如果计算出的位置超出范围，则解码器检测到无法校正的消息，而不是错误校正它。假设一条乱码消息，解码器生成 0 到 254 范围内的 3 个随机位置，所有 3 个都在 0 到 69 范围内的概率是 (70/255)^3.
另一种避免错误校正的情况是当错误定位器多项式的不同根的数量与多项式的次数不匹配时。考虑生成错误定位器多项式 x^3 + a x^2 + b x + c 的 3 个错误情况。如果消息中有超过 3 个错误，则生成的多项式可能具有少于 3 个不同的根，例如双根、零根或 ...，在这种情况下，可以避免错误纠正，并且消息被检测为无法纠正。