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

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

基本介紹

• 中文名：伯利坎普－梅西算法
• 外文名：Berlekamp–Massey algorithm

演算法

伯利坎普－韋爾奇算法通常被用於解碼里德-所羅門碼。假使在有限體上有個數字，利用RS碼編為次多項式。如果已知傳輸信道會錯誤傳輸個值，那么RS碼可以傳輸上的個點。因此，解碼者的問題在於要辨認出哪個點是錯誤的。令解碼者接收到的點值為，可以看出對於且僅對於所有正確傳輸的點。

錯誤識別多項式

Burleigh-Welch算法引入了錯誤識別多項式的概念，也稱為多項式，其中值是所有誤差傳輸點的值（全部未知）。 因為，若且唯若一個點對應於錯誤傳輸時，可以看出，對於所有值，對於所有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 < N; n++)    {      /* step 2. calculate discrepancy */      field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};      if (d == 0)        {          /* step 3. discrepancy is zero; annihilation continues */          m = m + 1;        }      else if (2 * L <= n)        {          /* step 5. */          /* temporary copy of C(x) */          polynomial(field K) T(x) = C(x);          C(x) = C(x) - d b^{-1} x^m B(x);          L = n + 1 - L;          B(x) = T(x);          b = d;          m = 1;        }      else        {          /* step 4. */          C(x) = C(x) - d b^{-1} x^m B(x);          m = m + 1;        }    }  return L;