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. Reeds ve Sloane, bir yüzüğü işlemek için bir uzantı sunar.

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

Algoritmanın açıklaması

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:

$S_{i+\nu }+{\mathrm{\Lambda }}_1{S}_{i+\nu -1}+\cdots +{\mathrm{\Lambda }}_{\nu -1}{S}_{i+1}+{\mathrm{\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:

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

$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.

$S_n+C_1{S}_{n-1}+\cdots +C_L{S}_{n-L}$

0'a eşit olması:

$S_n+C_1{S}_{n-1}+\cdots +C_L{S}_{n-L}=0,L\le n\le 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:

$d\leftarrow 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:

$C(x)\leftarrow 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:

$d\leftarrow 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:

$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.

Kod örneği

 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;
   }
/* ... */

Ayrıca bakınız

• 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)

Dış bağlantılar

• PlanetMath'te Berlekamp–Massey algoritması .