[科普中国]-梅西解码程序

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

介绍梅西解码程序用来构造一个尽可能短的线性反馈移位寄存器（linear feedback shift register，LFSR）来产生一个有限二元序列，同时，该算法也给出了的线性复杂度。该算法是一个多项式时间的迭代算法，以N长二元序列为输入，输出产生给序列式的最短LFSR的特征多项式及该LFSR的线性复杂度。这一算法由埃尔温·伯利坎普与詹姆斯·梅西发明1。

Elwyn Berlekamp发明了一种解码Bose-Chaudhuri-Hocquenghem（BCH）码的算法。James Massey认识到它在线性反馈移位寄存器中的应用并简化了算法。 Massey将算法称为LFSR综合算法（Berlekamp迭代算法），但它称为Berlekamp-Massey算法。

代码示例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