伯利坎普-梅西算法(伯利坎普-梅西算法)

簡介

伯利坎普－梅西算法（英語：Berlekamp-Massey algorithm，簡稱B-M算法）用來構造一個儘可能短的線性反饋移位暫存器（linear feedback shift register，LFSR）來產生一個有限二元序列

，同時，該算法也給出了

的線性複雜度。該算法是一個多項式時間的疊代算法，以N長二元序列

為輸入，輸出產生給序列式的最短LFSR的特徵多項式

及該LFSR的線性複雜度

。

這一算法由埃爾溫·伯利坎普與詹姆斯·梅西發明。.

埃爾溫·拉爾夫·伯利坎普（英語：Elwyn Ralph Berlekamp），美國的數學家與計算機科學家，現任伯克利加州大學榮譽教授。他對現代編碼理論和組合博弈論做出了很大貢獻。

線性反饋移位暫存器（英語：Linear feedback shift register，LFSR）是指給定前一狀態的輸出，將該輸出的線性函式再用作輸入的移位暫存器。異或運算是最常見的單比特線性函式：對暫存器的某些位進行異或操作後作為輸入，再對暫存器中的各比特進行整體移位。

賦給暫存器的初始值叫做“種子”，因為線性反饋移位暫存器的運算是確定性的，所以，由暫存器所生成的數據流完全決定於暫存器當時或者之前的狀態。而且，由於暫存器的狀態是有限的，它最終肯定會是一個重複的循環。然而，通過本原多項式，線性反饋移位暫存器可以生成看起來是隨機的且循環周期非常長的序列。

線性反饋移位暫存器的套用包括生成偽隨機數，偽隨機噪聲序列，快速數字計數器，還有擾頻器。線性反饋移位暫存器在硬體和軟體方面的套用都非常得普遍。

循環冗餘校驗中用於快速校驗傳輸錯誤的數學原理，就與線性反饋移位暫存器密切相關。