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ı

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 }+\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:

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

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:

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:

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:

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

^ Reeds & Sloane 1985
^ "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
^ Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy, 1967
^ 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.
^ "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
^ "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
^ Massey 1969

Dış bağlantılar

PlanetMath'te Berlekamp–Massey algoritması .

[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

[1]

[2]

[3]

[4]

[5]

[6]

[7]