Berlekamp-Massey algoritması

[bullvar_katip]

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 Λ 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 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: 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 İ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. Ayrıca bakınız Reed-Solomon hata düzeltmesi Reeds–Sloane algoritması, tamsayılar modu üzerindeki diziler için bir uzantın Doğrusal olmayan geri besleme kaydırmalı yazmaç (NLFSR) Kaynakça Dış bağlantılar PlanetMath'te Berlekamp–Massey algoritması . Kategori:Hata tanılama ve düzeltme