Berlekamp-Massey algoritması

Berlekamp-Massey algoritması, belirli bir ikili çıkış dizisi için en kısa doğrusal geri besleme kaydırmalı yazmacı (LFSR) bulan bir algoritmadır . Algoritma ayrıca rastgele bir alanda lineer olarak yinelenen bir dizinin minimum polinomunu da bulacaktır. Alan gereksinimi, Berlekamp-Massey algoritmasının sıfır olmayan tüm öğelerin çarpımsal bir tersi olmasını gerektirdiği anlamına gelir.^[1] Reeds ve Sloane, bir yüzüğü işlemek için bir uzantı sunar.^[2]

Elwyn Berlekamp, Bose–Chaudhuri–Hocquenghem (BCH) kodlarını çözmek için bir algoritma icat etti.^[3][4] James Massey, lineer geri besleme kaydırmalı yazmaçlara uygulanmasını fark etti ve algoritmayı basitleştirdi.^[5][6] Massey, algoritmayı LFSR Sentez Algoritması (Berlekamp Yinelemeli Algoritma) olarak adlandırıldı,^[7] ancak şimdi Berlekamp-Massey algoritması olarak biliniyor.

Berlekamp-Massey algoritması, lineer denklem setini çözmek için Reed-Solomon Peterson kod çözücüye bir alternatiftir. Bu, bir Λ(x) polinomunun Λ _j katsayılarının bulunması olarak özetlenebilir, böylece bir S girdi akışındaki tüm i konumları için:

${\displaystyle S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.}$

Aşağıdaki kod örneklerinde, C (x), potansiyel bir Λ (x) örneğidir. L hataları için hata bulucu polinomu C (x) şu şekilde tanımlanır:

${\displaystyle C(x)=C_{L}x^{L}+C_{L-1}x^{L-1}+\cdots +C_{2}x^{2}+C_{1}x+1}$

${\displaystyle C(x)=1+C_{1}x+C_{2}x^{2}+\cdots +C_{L-1}x^{L-1}+C_{L}x^{L}.}$

Algoritmanın amacı, tüm sendromlarla sonuçlanan minimum L ve C (x) derecesini belirlemektir.

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}}$

0'a eşit olması:

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=0,\qquad L\leq n\leq N-1.}$

Algoritma: C (x) 1 olarak başlatılır, L mevcut varsayılan hata sayısıdır ve sıfır olarak başlatılır. N, toplam sendrom sayısıdır. n, ana yineleyici olarak ve 0'dan N -1'e kadar olan sendromları indekslemek için kullanılır. B (x), L güncellendiğinden ve 1 olarak başlatıldığından beri son C'nin (x) bir kopyasıdır . L, B (x) ve b'den beri yinelemeler güncellendi ve 1 olarak başlatıldı.

Algoritmanın her yinelemesi bir tutarsızlık hesaplar d . k yinelemesinde bu şu şekilde olur:

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.}$

d sıfır ise, algoritma C (x) ve L' nin o an için doğru olduğunu varsayar, m'yi artırır ve devam eder.

d sıfır değilse, algoritma C'yi (x) d' nin yeniden hesaplanması sıfır olacak şekilde ayarlar:

${\displaystyle C(x)\gets C(x)-(d/b)x^{m}B(x).}$

x ^m terimi B(x)'i kaydırır, böylece b'ye karşılık gelen sendromları takip eder. L' nin önceki güncellemesi j yinelemesinde gerçekleşmişse, o zaman m = k − j olur ve yeniden hesaplanan bir tutarsızlık şu şekilde gerçekleşecektir:

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}S_{j-1}+\cdots ).}$

Bu, yeniden hesaplanan bir tutarsızlığı şu şekilde değiştirir:

${\displaystyle d=d-(d/b)b=d-d=0.}$

Algoritmanın, ayrıca L'yi (hata sayısını) gerektiği gibi artırması gereklidir. L, gerçek hata sayısına eşitse, yineleme işlemi sırasında, n, 2 L'ye eşit veya daha büyük hale gelmeden önce, tutarsızlıklar sıfır olacaktır. Aksi takdirde L güncellenir ve algoritma B (x), b 'yi günceller, L 'yi artırır ve m = 1'i sıfırlar. L = (n + 1 − L) formülü, L'yi tutarsızlıkları hesaplamak için kullanılan mevcut sendromların sayısıyla sınırlar ve ayrıca L' nin 1'den fazla arttığı durumu ele alır.

 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;

İkili GF(2) BCH kodu durumunda, tüm tek adımlarda d farkı sıfır olacaktır, bu nedenle hesaplamayı önlemek için bir kontrol eklenebilir.

/* ... */
 for (n = 0; n < N; n++) {
   /* if odd step number, discrepancy == 0, no need to calculate it */
   if ((n&1) != 0) {
     m = m + 1;
     continue;
   }
/* ... */

• Reed-Solomon hata düzeltmesi
• Reeds–Sloane algoritması, tam sayılar modu üzerindeki diziler için bir uzantı n
• Doğrusal olmayan geri besleme kaydırmalı yazmaç (NLFSR)

• PlanetMath'te Berlekamp–Massey algoritması .