Berlekamp-Massey-algoritmi

Berlekamp-Massey-  algoritmi on algoritmi, jolla etsitään lyhin siirtorekisteri lineaarisella takaisinkytkennällä syötteenä annetulle binäärisekvenssille. Algoritmin avulla voit myös löytää syötetyn lineaarisen toistuvan sekvenssin minimipolynomin mielivaltaisen kentän yli .

Alvin Berlekamp löysi algoritmin vuonna 1968 [1] . James Massey löysi seuraavana vuonna algoritmin soveltamisen lineaarisiin koodeihin [2] . Tästä tuli avain Reed-Solomon-koodien käytännön soveltamiseen .

Algoritmin kuvaus

Algoritmi B.M. on vaihtoehtoinen menetelmä SLAE:n ratkaisemiseksi, joka voidaan kuvata seuraavasti:

Alla olevissa koodiesimerkeissä C(x) on Λ(x). Virheen paikannus C(x) L - virheille määritellään seuraavasti:

tai taaksepäin eteen:

Algoritmin tarkoituksena on määrittää minimi L ja sitä vastaava C(x), joka antaa virheitä koko oireyhtymässä

tuloksena nolla:

Algoritmi: C(x) alustetaan 1:ksi, L tarkoittaa tähän mennessä löydettyjen virheiden nykyistä määrää ja alustetaan nollaan. N on virheoireyhtymän elementtien kokonaismäärä. n on päälaskuri, se on myös oireyhtymän elementtien indeksi nollasta ( N -1). B(x) on kopio viimeisestä C(x):stä päivityksen L ajankohtana , ja se on alustettu 1:ksi. b on kopio viimeisestä poikkeamasta d (katso alla), jälleen päivityksen L ja on alustettu 1:ksi. m on iteraatioiden lukumäärä, jotka ovat kuluneet päivityksen L , B(x) ja b jälkeen ja jotka on myös alustettu yhdeksi.

Jokaisessa iteraatiossa lasketaan ero d . K : nnessä iteraatiossa se on:

Jos d on nolla, se tarkoittaa, että C(x) ja L ovat toistaiseksi oikein, riittää, että lisäät m ja jatkat iteraatiota.

Jos d on muu kuin nolla, algoritmi korjaa C(x):n asettamaan d :n nollaan :

Kertominen x m :llä on olennaisesti B(x)-kertoimien siirtymä m:llä, ts. jokainen kerroin on m korkeampi vastaamaan b :n oireyhtymää . Jos viimeksi L päivitettiin iteraatiossa j (ja nyt meillä on k :s iteraatio), niin m = k - j , ja uudelleen laskettu poikkeama on:

Eli korvaamalla näemme sen katoavan:

Myös L :n arvoa (löytyneiden virheiden määrä) on joskus korjattava. Jos L on yhtä suuri kuin virheellisten symbolien todellinen lukumäärä, niin iteraatioiden aikana erot nollataan ennen kuin n : stä tulee suurempi tai yhtä suuri kuin (2 L ). Muussa tapauksessa L päivitetään ja algoritmi päivittää B(x):n, b:n, L:n itsensä (lisäyksiä), ja m nollataan 1:ksi. Lauseke L = (n + 1 - L) rajoittaa L:n käytettävissä olevien oireyhtymäelementtien lukumäärään. laskea erot ja samalla ratkaisee L:n lisäämisen useammalla kuin yhdellä.

Esimerkkikoodi

Masseyn algoritmi (1969 , s. 124):

polynomi ( kenttä K ) s ( x ) = ... /* kertoimet ovat s_j; lähtösekvenssi N-1 asteen polynomina) */ /* yhteyspolynomi */ polynomi ( kenttä K ) C ( x ) = 1 ; /* kertoimet ovat c_j */ polynomi ( kenttä K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; kenttä Kb = 1 ; _ int n ; /* vaiheet 2. ja 6. */ for ( n = 0 ; n < N ; n ++ ) { /* vaihe 2. laske ristiriita */ kenttä K d = s_n + \ Sigma_ { i = 1 } ^ L c_i * s_ { n - i }; jos ( d == 0 ) { /* vaihe 3. poikkeama on nolla; tuhoaminen jatkuu */ m = m + 1 _ } muuten jos ( 2 * L <= n ) { /* vaihe 5. */ /* väliaikainen kopio C(x):stä */ polynomi ( kenttä K ) T ( x ) = C ( x ); C ( x ) = C ( x ) -db ^ { - 1 } x ^ mB ( x ) ; _ L = n + 1 - L ; B ( x ) = T ( x ); b = d ; m = 1 ; } muu { /* vaihe 4. */ C ( x ) = C ( x ) -db ^ { - 1 } x ^ mB ( x ) ; _ m = m + 1 _ } } paluu L ;

Algoritmi binäärisekvensseille

  • Aseta tarvittava bittisekvenssi .
  • Luo taulukoita , , pituudet , aseta alkuarvot , , , , .
  • Heippa :
    1. Laske .
    2. Jos , niin nykyinen funktio luo valitun osan sekvenssistä; jätä toiminto ennalleen.
    3. Jos :
      • Tallenna kopio taulukosta kohteeseen .
      • Laske uudet arvot .
      • Jos , aseta arvot ja kopioi tiedostoon .
    4. .
  • Tämän seurauksena matriisi  on palautefunktio, eli mille tahansa .

Muistiinpanot

  1. Elwyn R. Berlekamp , ​​Algebraic Coding Theory, New York: McGraw-Hill, 1968. Tarkistettu painos, Aegean Park Press, 1984, ISBN 0-89412-063-8 .
  2. JL Massey , Shift-rekisterin synteesi ja BCH-dekoodaus Arkistoitu 27. syyskuuta 2011 Wayback Machinessa , IEEE Trans. Information Theory, IT-15 (1969), 122-127.

Kirjallisuus

  • Blahut R. Virheenhallintakoodien teoria ja käytäntö. — M .: Mir , 1986. — 576 s.
  • VL Kurakin, AS Kuzmin, AV Mikhalev, AA Nechaev. Lineaariset toistuvat sekvenssit renkaiden ja moduulien yli. // I. of Math. Tiede. Nykyajan matematiikka. ja se on Appl. Temaattiset tutkimukset, vol. 10, 1994, I. of Math. Sciences, voi. 76, nro 6, 1995. MR : 1365809

Linkit

Toteutus