Berlekamp-Massey algoritm

Berlekamp-Massey- algoritmen är en algoritm för att hitta det kortaste skiftregistret med linjär återkoppling för en binär sekvens som ges som ingång. Algoritmen låter dig också hitta minimipolynomet för den ingående linjära återkommande sekvensen över ett godtyckligt fält .

Algoritmen upptäcktes av Alvin Berlekamp 1968 [1] . En tillämpning av algoritmen på linjära koder hittades av James Massey följande år [2] . Detta blev nyckeln till den praktiska tillämpningen av Reed-Solomon-koder .

Beskrivning av algoritmen

Algoritm B.M. är en alternativ metod för att lösa SLAE, som kan beskrivas enligt följande:

S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.

I kodexemplen nedan representerar C(x) Λ(x). Fellokaliseraren C(x) för L -fel definieras som:

C(x)=C_{L}\ x^{L}+C_{L-1}\ x^{L-1}+\cdots +C_{2}\ x^{2}+C_{ 1}\x+1

eller bakifrån:

C(x)=1+C_{1}\ x+C_{2}\ x^{2}+\cdots +C_{L-1}\ x^{L-1}+C_{L} \x^{L}.

Syftet med algoritmen är att bestämma minimum L och motsvarande C(x), vilket ger fel i hela syndromet

{\displaystyle S_{n}+C_{1}\ S_{n-1}+\cdots +C_{L}\ S_{nL))

resulterar i noll:

S_{n}+C_{1}\ S_{n-1}+\cdots +C_{L}\ S_{nL}=0,\qquad L\leq n\leq N-1.

Algoritm: C(x) initieras till 1, L betecknar det aktuella antalet fel som hittills hittats och initieras till noll. N är det totala antalet felsyndromelement. n är huvudräknaren, det är också indexet för syndromelementen från 0 till ( N -1). B(x) är en kopia av den sista C(x) vid tidpunkten för uppdateringen av L , och initieras till 1. b är en kopia av den senaste avvikelsen d (se nedan), återigen, vid tidpunkten för uppdateringen av L och initieras till 1. m är antalet iterationer som har passerat sedan uppdateringen L , B(x) och b och som också initierats till en.

Vid varje iteration beräknas diskrepansen d . Vid den k: te iterationen blir det:

d=S_{k}+C_{1}\ S_{k-1}+\cdots +C_{L}\ S_{kL}.

Om d är noll betyder det att C(x) och L är korrekta för närvarande, det räcker med att öka m och fortsätta iterationen.

Om d inte är noll, korrigerar algoritmen C(x) för att sätta d till noll :

C(x)=C(x)\ -\ (d/b)\ x^{m}\ B(x).

Multiplicering med x m är i huvudsak en förskjutning av B(x)-koefficienterna med m, dvs varje koefficient sker m högre för att matcha syndromet för b . Om senaste gången L uppdaterades vid iteration j (och nu har vi den k: te iterationen), då är m = k - j , och den omräknade avvikelsen är:

d=S_{k}+C_{1}\ S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}\ S_{j-1}+\cdots ).

Det vill säga, genom att ersätta, ser vi att det försvinner:

d=d-(d/b)b=dd=0.\

Dessutom måste värdet på L (antalet fel hittade) ibland korrigeras. Om L är lika med det faktiska antalet felaktiga symboler, så nollställs avvikelserna under iterationerna innan n blir större än eller lika med (2 L ). Annars uppdateras L och algoritmen uppdaterar B(x), b, L själv (ökar) och m återställs till 1. Uttrycket L = (n + 1 - L) begränsar L till antalet tillgängliga syndromelement som används för att beräkna avvikelserna, och löser samtidigt problemet med att öka L med mer än ett.

Exempelkod

Algoritm från Massey (1969 , s. 124):

polynom ( fält K ) s ( x ) = ... /* koeffs är s_j; utdatasekvens som N-1 grads polynom) */ /* anslutningspolynom */ polynom ( fält K ) C ( x ) = 1 ; /* koeffs är c_j */ polynom ( fält K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; fält Kb = 1 ; _ int n ; /* steg 2. och 6. */ för ( n = 0 ; n < N ; n ++ ) { /* steg 2. beräkna avvikelse */ fält Kd = s_n + \ Sigma_ { i = 1 } ^ L c_i * s_ { n - i } ; om ( d == 0 ) { /* steg 3. avvikelsen är noll; förintelsen fortsätter */ m = m + 1 _ } annat om ( 2 * L <= n ) { /* steg 5. */ /* tillfällig kopia av C(x) */ polynom ( fält 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 ; } annan { /* steg 4. */ C ( x ) = C ( x ) -db ^ { - 1 } x ^ mB ( x ) ; _ m = m + 1 _ } } retur L ;

Algoritm för binära sekvenser

Ställ in önskad bitsekvens . ${\displaystyle s_{0},s_{1},...,s_{n-1))$
Skapa arrayer , , längder , ställ in initiala värden , , , , . $b$ $t$ $c$ $n$ $b_{0}\leftarrow 1$ $c_{0}\leftarrow 1$ $N\leftarrow 0$ $L\leftarrow 0$ $m\leftarrow -1$
Hejdå : $N<n$
1. Beräkna . ${\displaystyle d\leftarrow s_{N}\oplus c_{1}s_{N-1}\oplus c_{2}s_{N-2}\oplus ...\oplus c_{L}s_{NL))$
2. Om , då genererar den aktuella funktionen den valda delen av sekvensen; lämna funktionen densamma. $d=0$ ${\displaystyle s_{NL},s_{N-L+1},...,s_{N))$
3. Om : $d\not=0$
  - Spara en kopia av arrayen i . $c$ $t$
  - Beräkna nya värden . $c_{Nm}\leftarrow c_{Nm}\oplus b_{0},c_{N-m+1}\leftarrow c_{N-m+1}\oplus b_{1},...,c_ {n-1}\leftarrow c_{n-1}\oplus b_{n-N+m-1}$
  - Om , ställ in värden och kopiera till . $2L\leqslant N$ $L\leftarrow N+1-L$ $m\leftarrow N$ $t$ $b$
4. $N\leftarrow N+1$ .
Som ett resultat är matrisen en återkopplingsfunktion, det vill säga för alla . $c$ $c_{L}s_{i}\oplus c_{L-1}s_{i+1}\oplus c_{L-2}s_{i+2}\oplus ...\oplus c_{0} s_{i+L}=0$ $i$

Anteckningar

↑ Elwyn R. Berlekamp , Algebraic Coding Theory, New York: McGraw-Hill, 1968. Reviderad upplaga, Aegean Park Press, 1984, ISBN 0-89412-063-8 .
↑ JL Massey , Shift-register syntes och BCH-avkodning Arkiverad 27 september 2011 på Wayback Machine , IEEE Trans. Information Theory, IT-15 (1969), 122-127.

Litteratur

Blahut R. Teori och praktik av felkontrollkoder. — M .: Mir , 1986. — 576 sid.
VL Kurakin, AS Kuzmin, AV Mikhalev, AA Nechaev. Linjära återkommande sekvenser över ringar och moduler. // I. of Math. Vetenskap. Samtida matematik. och det är Appl. Tematiska undersökningar, vol. 10, 1994, I. of Math. Sciences, vol. 76, nr 6, 1995. MR : 1365809

Länkar

Berlekamp-Massey-algoritmen (engelska) på PlanetMath-webbplatsen .
Weisstein, Eric W. Berlekamp-Massey Algorithm - MathWorld .

Implementering

Onlineimplementering av Reed-Sloane och Berlekamp-Massey över GF(P) -algoritmer (otillgänglig länk) på SignalsLab
GF(2 ) implementering i Mathematica