梅西解碼程式

梅西解碼程式是一種算法，可以找到給定二進制輸出序列的最短線性反饋移位暫存器（LFSR）。 該算法還將在任意場中找到線性遞歸序列的最小多項式。 欄位要求意味著Berlekamp-Massey算法要求所有非零元素都具有乘法逆。

介紹

梅西解碼程式

梅西解碼程式

梅西解碼程式

梅西解碼程式

梅西解碼程式

梅西解碼程式用來構造一個儘可能短的線性反饋移位暫存器（linear feedback shift register，LFSR）來產生一個有限二元序列 ，同時，該算法也給出了 的線性複雜度。該算法是一個多項式時間的疊代算法，以N長二元序列 為輸入，輸出產生給序列式的最短LFSR的特徵多項式 及該LFSR的線性複雜度 。這一算法由埃爾溫·伯利坎普與詹姆斯·梅西發明。

Elwyn Berlekamp發明了一種解碼Bose-Chaudhuri-Hocquenghem（BCH）碼的算法。James Massey認識到它線上性反饋移位暫存器中的套用並簡化了算法。 Massey將算法稱為LFSR綜合算法（Berlekamp疊代算法），但它稱為Berlekamp-Massey算法。

代碼示例

Massey（1969，p.124）中任意欄位的算法：