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

Berlekamp-Massey算法是一種算法，可以找到給定二進(jìn)制輸出序列的最短線性反饋移位寄存器（LFSR）。 該算法還將在任意場中找到線性遞歸序列的最小多項(xiàng)式。 字段要求意味著Berlekamp-Massey算法要求所有非零元素都具有乘法逆。 Reeds和Sloane提供延伸處理戒指。

演算法伯利坎普－韋爾奇算法通常被用于解碼里德-所羅門碼。假使在有限體上有個(gè)數(shù)字，利用RS碼編為次多項(xiàng)式。如果已知傳輸信道會(huì)錯(cuò)誤傳輸個(gè)值，那么RS碼可以傳輸上的個(gè)點(diǎn)。因此，解碼者的問題在于要辨認(rèn)出哪個(gè)點(diǎn)是錯(cuò)誤的。令解碼者接收到的點(diǎn)值為，可以看出對于且僅對于所有正確傳輸?shù)狞c(diǎn)。

錯(cuò)誤識別多項(xiàng)式Burleigh-Welch算法引入了錯(cuò)誤識別多項(xiàng)式的概念，也稱為多項(xiàng)式，其中值是所有誤差傳輸點(diǎn)的值（全部未知）。 因?yàn)?，?dāng)且僅當(dāng)一個(gè)點(diǎn)對應(yīng)于錯(cuò)誤傳輸時(shí)1，可以看出，對于所有值，對于所有i都知道常數(shù)。讓我們看左邊是一個(gè)階的多項(xiàng)式，右邊是一階的多項(xiàng)式，但最高階系數(shù)是1。因此，整個(gè)線性系統(tǒng)有一個(gè)方程和一個(gè)未知數(shù)，可以是 通過線性代數(shù)求解，可以求解原始編碼多項(xiàng)式，并可以讀出編碼值。

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