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 .
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ä.
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 ;