reed-solomon - 使用 Berlekamp-Massey 算法的错误检测能力

Question

我RS( n=1023,k=995 )在每个符号中实现了 10 位。为了找到误差多项式，我们使用 Berlekamp-Massey(BM) 算法。我们代码的错误检测能力应该是n-k = 1023-995 = 28. 纠错能力为(n-k)/2 = 14。BM 算法对于小于或等于 14 的错误非常有效。如果发生超过 14 个错误，如何确定错误的数量？？（因为如果错误大于 14，则纠正将失败）。我想知道这个算法是否有任何限制来查找错误的数量。根据理论，RS 码应该能够正确识别出发生了 14 个以上的错误。

Answer 1

对于 RS(n=1023,k=995)，距离为 n-k+1 = 29：每个有效码字与任何其他有效码字至少有 29 个符号不同。最大错误检测能力为 nk = 28。最大错误纠正能力为 (nk)/2 = 14。

根据理论，RS 码应该能够正确识别出发生了 14 个以上的错误。

这并不总是正确的。如果有超过 14 个错误，则错误纠正可能会导致有效的代码字，但与原始代码字相差 29 个或更多符号。

考虑接收到的码字有 15 个或更多错误符号的情况，那么尝试最大 (nk)/2 校正可能会产生额外的 14 个错误符号，产生看似有效的码字，但有一个与原始码字有 29 个或更多符号不同。只有当接收到的码字与有效码字相差 14 个或更少的符号时，才会发生错误纠正。对于 15 个错误情况，发生这种情况的概率非常低，但随着错误数量的增加而增加。使用哪种解码器方法（PGZ（矩阵）、BM（差异）或 YS（扩展 Euclid））不会产生显着差异。

可以通过减少已纠正错误的最大数量来降低错误纠正的概率。假设纠错被限制为 12 个符号而不是 14 个，那么除非有 17 个或更多符号错误，否则就没有错误纠正的机会。

如果使用缩短的码字，例如 RS(n=511, k=483)，错误更正的几率也会降低，其中错误计算的位置有 50% 的机会超出有效位置的范围（0 到 511）。