reed-solomon - Berlekamp-Massey 算法不适用于综合征的最低有效符号为 0

Question

我正在尝试在上图中实现此算法。Berlekamp-Massey 算法解决了RS(n,k)系统中的以下问题： 给定一个校正子多项式

S(z) = {S(nk-1),........S(2),S(1),S(0)}

, 找到最小次误差多项式。该算法适用于所有综合征，但当 S(0) 变为 0 时，误差多项式不正确。提到的算法有什么遗漏吗？

Answer 1

它在什么时候失败？它是无法生成错误定位多项式，还是创建了一个没有正确根的多项式，或者它后来失败了，例如 Forney 算法？

我不确定你的问题是否真的是 S(0)。大多数文章将 S(j) 定义为元素的总和乘以 (alpha^j) 的连续幂（位置）。重要的是，解码器使用的校正子基于生成多项式的根，如果第一个连续根 = FCR = alpha^0 = 1 (g(x) = (x-1)(x-alpha)(x -alpha^2)...)，使用 S(0) 到 S(nk-1)，或者如果 FCR = alpha (g(x) = (x-alpha)(x-alpha^2)...) ，使用 S(1) 到 S(nk)。

任何 RS 解码器都应该工作，尽管有零综合症，只要没有太多零综合症（这将表明一个不可纠正的错误）。

wiki 文章通过示例代码对算法进行了更简单的描述。请注意，它使用 lambda (Λ) 而不是 sigma (σ) 来表示错误定位器多项式。描述是针对示例代码的，在这种情况下，S[0] 可能表示 S(0) 或 S(1)，具体取决于 FCR（未提及）。

https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm

我还为 4 位和 8 位字段编写了交互式 RS 程序，其中包括 Berlekamp Massey 作为程序中实现的三个解码器之一。程序允许用户将 FCR 指定为 1 或 2，除非选择自倒数多项式（用于简化硬件编码器的非流行选项）。在这些示例程序中，多项式通常首先存储最重要的项（遗留问题），因此代码会移动数组来处理这个问题。

http://rcgldr.net/misc/eccdemo4.zip

http://rcgldr.net/misc/eccdemo8.zip

---

我修改了我的一个 ecc 演示程序以使用 GF(2^10)。我运行了你的测试用例：

S[...] = {0000 0596 0302 0897}   (S[0] = 0)

这些是我为 BM 解码器得到的迭代和多项式：

k      d    σ

0   0000    0001
1   0596    0596 x^2 + 0000 x + 0001
2   0302    0596 x^2 + 1006 x + 0001
3   0147    0585 x^2 + 1006 x + 0001

根是：

383 = 1/(2^526) and 699 = 1/(2^527)

琐事，通过反转系数，你得到定位器而不是它们的逆：

 0001 x^2 + 1006 x + 0585 : roots are 346 = 2^526 and 692 = 2^527

请注意，如果使用 Forney 计算误差值，则 Forney 需要不可逆多项式。