[科普中国]-伯利坎普－梅西算法

Berlekamp-Massey算法是一种算法，可以找到给定二进制输出序列的最短线性反馈移位寄存器（LFSR）。 该算法还将在任意场中找到线性递归序列的最小多项式。 字段要求意味着Berlekamp-Massey算法要求所有非零元素都具有乘法逆。 Reeds和Sloane提供延伸处理戒指。

演算法伯利坎普－韦尔奇算法通常被用于解码里德-所罗门码。假使在有限体上有个数字，利用RS码编为次多项式。如果已知传输信道会错误传输个值，那么RS码可以传输上的个点。因此，解码者的问题在于要辨认出哪个点是错误的。令解码者接收到的点值为，可以看出对于且仅对于所有正确传输的点。

错误识别多项式Burleigh-Welch算法引入了错误识别多项式的概念，也称为多项式，其中值是所有误差传输点的值（全部未知）。 因为，当且仅当一个点对应于错误传输时1，可以看出，对于所有值，对于所有i都知道常数。让我们看左边是一个阶的多项式，右边是一阶的多项式，但最高阶系数是1。因此，整个线性系统有一个方程和一个未知数，可以是 通过线性代数求解，可以求解原始编码多项式，并可以读出编码值。

代码示例Massey（1969，p.124）中任意字段的算法：

polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */ /* connection polynomial */ polynomial(field K) C(x) = 1; /* coeffs are c_j */ polynomial(field K) B(x) = 1; int L = 0; int m = 1; field K b = 1; int n; /* steps 2. and 6. */ for (n = 0; n