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.

Algoritmanın açıklaması

değiştir

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:

 

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:

 
 

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

 

0'a eşit olması:

 

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 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:

 

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 = kj olur ve yeniden hesaplanan bir tutarsızlık şu şekilde gerçekleşecektir:

 

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

 

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

değiştir
 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

değiştir
  • 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)

Kaynakça

değiştir
  1. ^ Reeds & Sloane 1985
  2. ^ "Shift-Register Synthesis (Modulo n)" (PDF), SIAM Journal on Computing, 14 (3), 1985, ss. 505-513, doi:10.1137/0214038, 24 Şubat 2022 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 23 Mart 2022 
  3. ^ Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy, 1967 
  4. ^ Algebraic Coding Theory, Revised, Laguna Hills, CA: Aegean Park Press, 1984 [1968], ISBN 978-0-89412-063-3 . Previous publisher McGraw-Hill, New York, NY.
  5. ^ "Shift-register synthesis and BCH decoding" (PDF), IEEE Transactions on Information Theory, IT-15 (1), January 1969, ss. 122-127, doi:10.1109/TIT.1969.1054260, 27 Eylül 2011 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 23 Mart 2022 
  6. ^ "The Berlekamp–Massey Algorithm revisited", Applicable Algebra in Engineering, Communication and Computing, 17 (1), April 2006, ss. 75-82, doi:10.1007/s00200-005-0190-z, 20 Ocak 2022 tarihinde kaynağından arşivlendi, erişim tarihi: 23 Mart 2022 
  7. ^ Massey 1969

Dış bağlantılar

değiştir