Berlekamp-Massey 算法不适用于 Syndrome 的最低有效符号为 0
Berlekamp-Massey Algorithm not working for Syndrome's Least significant Symbol being 0
我正在尝试在上图中实现这个算法。 Berlekamp-Massey 算法解决了 RS(n,k) 系统中的以下问题：给定一个综合多项式
S(z) = {S(n-k-1),........S(2),S(1),S(0)}
，求最小次数误差多项式。该算法适用于所有综合症，但当 S(0) 变为 0 时，误差多项式不正确。提到的算法中是否缺少任何内容？
什么时候失败了？它是否无法生成错误定位器多项式，或者它是否创建了一个没有正确根的多项式，或者它是否稍后失败，例如 Forney 算法？
我不确定你问题中的 S(0) 是不是真的。大多数文章将 S(j) 定义为元素乘以 (alpha^j) 的连续幂（位置）的总和。如果第一个连续的根 = FCR = alpha^0 = 1 (g(x) = (x-1)(x-alpha)(x -alpha^2)...)，使用 S(0) 到 S(n-k-1)，或者如果 FCR = alpha (g(x) = (x-alpha)(x-alpha^2)...) , 使用 S(1) 到 S(n-k).
任何 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 需要未反转的多项式。
我正在尝试在上图中实现这个算法。 Berlekamp-Massey 算法解决了 RS(n,k) 系统中的以下问题：给定一个综合多项式
S(z) = {S(n-k-1),........S(2),S(1),S(0)}
，求最小次数误差多项式。该算法适用于所有综合症，但当 S(0) 变为 0 时，误差多项式不正确。提到的算法中是否缺少任何内容？
什么时候失败了？它是否无法生成错误定位器多项式，或者它是否创建了一个没有正确根的多项式，或者它是否稍后失败，例如 Forney 算法？
我不确定你问题中的 S(0) 是不是真的。大多数文章将 S(j) 定义为元素乘以 (alpha^j) 的连续幂（位置）的总和。如果第一个连续的根 = FCR = alpha^0 = 1 (g(x) = (x-1)(x-alpha)(x -alpha^2)...)，使用 S(0) 到 S(n-k-1)，或者如果 FCR = alpha (g(x) = (x-alpha)(x-alpha^2)...) , 使用 S(1) 到 S(n-k).
任何 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 需要未反转的多项式。