0

我有一个关于本文“通用集成交错代码”中的陈述的问题。论文提到，Reed-Solomon（RS）码的纠删码不会产生误纠，但是如果纠错能力太低，RS码的纯误码解码会产生很高的误码率。

根据我的理解，我认为擦除解码和仅错误解码之间的区别在于擦除解码不需要计算错误位置。另一方面，仅错误解码需要知道错误位置，这可以通过 Berlekamp-Massey 算法计算。我想知道仅错误解码的错误纠正是否来自计算错误的错误位置？如果是，为什么误纠率与RS码的纠错能力有关？

4

1 回答 1

0

仅错误解码的错误纠正来自计算错误的错误位置

是的。例如，考虑一个具有 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视图Reed Solomon：PGZ（Peterson Gorenstein Zierler）矩阵解码器、BKM（Berlekamp Massey）差异解码器和Sugiyama的扩展Euclid解码器。PGZ 的时间复杂度 O((nk)^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 + ax^2 + bx + c 的 3 个错误情况。如果消息中有超过 3 个错误，则生成的多项式可能具有少于 3 个不同的根，例如双根、零根或 ...无法纠正。

于 2020-09-28T08:55:55.890 回答