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:

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

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)

Kaynakça

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 (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  . 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 (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 , erişim tarihi: 23 Mart 2022 
7. ^ Massey 1969

Dış bağlantılar

• PlanetMath'te .