Berlekamp-Massey algoritme

Berlekamp-Massey- algoritmen er en algoritme til at finde det korteste skifteregister med lineær feedback for en binær sekvens givet som input. Algoritmen giver dig også mulighed for at finde minimumspolynomiet for den lineære tilbagevendende inputsekvens over et vilkårligt felt .

Algoritmen blev opdaget af Alvin Berlekamp i 1968 [1] . En anvendelse af algoritmen til lineære koder blev fundet af James Massey året efter [2] . Dette blev nøglen til den praktiske anvendelse af Reed-Solomon-koder .

Beskrivelse af algoritmen

Algoritme B.M. er en alternativ metode til at løse SLAE, som kan beskrives som følger:

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

I kodeeksemplerne nedenfor repræsenterer C(x) Λ(x). Fejlfinderen C(x) for L -fejl er defineret som:

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

eller bagfra:

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

Formålet med algoritmen er at bestemme minimum L og den tilsvarende C(x), som giver fejl i hele syndromet

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

resulterer i nul:

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

Algoritme: C(x) initialiseres til 1, L angiver det aktuelle antal fejl fundet indtil nu, og initialiseres til nul. N er det samlede antal fejlsyndromelementer. n er hovedtælleren, det er også indekset for syndromelementerne fra 0 til ( N -1). B(x) er en kopi af den sidste C(x) på tidspunktet for opdatering af L og initialiseres til 1. b er en kopi af den sidste uoverensstemmelse d (se nedenfor), igen, på tidspunktet for opdatering af L og initialiseres til 1. m er antallet af iterationer, der er gået siden opdateringen L , B(x) og b og også initialiseret til én.

Ved hver iteration beregnes uoverensstemmelsen d . Ved den kth iteration vil det være:

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

Hvis d er nul, betyder det, at C(x) og L er korrekte for nu, det er nok at øge m og fortsætte iterationen.

Hvis d ikke er nul, korrigerer algoritmen C(x) for at sætte d til nul :

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

Multiplikation med x m er i det væsentlige en forskydning af B(x)-koefficienterne med m, dvs. hver koefficient finder sted m højere for at matche syndromet for b . Hvis sidste gang L blev opdateret ved iteration j (og nu har vi den kth iteration), så er m = k - j , og den genberegnede uoverensstemmelse er:

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

Det vil sige, at erstatte, ser vi, at det forsvinder:

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

Værdien af L (antallet af fundne fejl) skal nogle gange også rettes. Hvis L er lig med det faktiske antal fejlagtige symboler, så vil uoverensstemmelserne i løbet af iterationer blive nulstillet, før n bliver større end eller lig med (2 L ). Ellers opdateres L, og algoritmen opdaterer B(x), b, L selv (inkrementer), og m nulstilles til 1. Udtrykket L = (n + 1 - L) begrænser L til antallet af tilgængelige syndromelementer, der anvendes at beregne uoverensstemmelserne, og løser samtidig problemet med at øge L med mere end én.

Eksempelkode

Algoritme fra Massey (1969 , s. 124):

polynomium ( felt K ) s ( x ) = ... /* koefficienter er s_j; outputsekvens som N-1 grads polynomium) */ /* forbindelsespolynomium */ polynomium ( felt K ) C ( x ) = 1 ; /* koeffs er c_j */ polynomium ( felt K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; felt Kb = 1 ; _ int n ; /* trin 2. og 6. */ for ( n = 0 ; n < N ; n ++ ) { /* trin 2. beregn uoverensstemmelse */ felt Kd = s_n + \ Sigma_ { i = 1 } ^ L c_i * s_ { n - i } ; hvis ( d == 0 ) { /* trin 3. uoverensstemmelsen er nul; udslettelse fortsætter */ m = m + 1 _ } andet hvis ( 2 * L <= n ) { /* trin 5. */ /* midlertidig kopi af C(x) */ polynomium ( felt 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 ; } andet { /* trin 4. */ C ( x ) = C ( x ) -db ^ { - 1 } x ^ mB ( x ) ; _ m = m + 1 _ } } retur L ;

Algoritme for binære sekvenser

Indstil den ønskede bitsekvens . ${\displaystyle s_{0},s_{1},...,s_{n-1))$
Opret arrays , , længder , sæt startværdier , , , , . $b$ $t$ $c$ $n$ $b_{0}\leftarrow 1$ $c_{0}\leftarrow 1$ $N\leftarrow 0$ $L\leftarrow 0$ $m\leftarrow -1$
farvel : $N<n$
1. Beregn . ${\displaystyle d\leftarrow s_{N}\oplus c_{1}s_{N-1}\oplus c_{2}s_{N-2}\oplus ...\oplus c_{L}s_{NL))$
2. Hvis , så genererer den aktuelle funktion den valgte sektion af sekvensen; lad funktionen være den samme. $d=0$ ${\displaystyle s_{NL},s_{N-L+1},...,s_{N))$
3. Hvis : $d\not=0$
  - Gem en kopi af arrayet i . $c$ $t$
  - Beregn nye værdier . $c_{Nm}\leftarrow c_{Nm}\oplus b_{0},c_{N-m+1}\leftarrow c_{N-m+1}\oplus b_{1},...,c_ {n-1}\venstrepil c_{n-1}\oplus b_{n-N+m-1}$
  - Hvis , indstil værdier og kopier til . $2L\leqslant N$ $L\leftarrow N+1-L$ $m\leftarrow N$ $t$ $b$
4. $N\leftarrow N+1$ .
Som et resultat er arrayet en feedbackfunktion, det vil sige for enhver . $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$ $jeg$

Noter

↑ Elwyn R. Berlekamp , Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revideret udgave, Aegean Park Press, 1984, ISBN 0-89412-063-8 .
↑ JL Massey , Skiftregistersyntese og BCH-afkodning Arkiveret 27. september 2011 på Wayback Machine , IEEE Trans. Information Theory, IT-15 (1969), 122-127.

Litteratur

Blahut R. Teori og praksis for fejlkontrolkoder. — M .: Mir , 1986. — 576 s.
VL Kurakin, AS Kuzmin, AV Mikhalev, AA Nechaev. Lineære tilbagevendende sekvenser over ringe og moduler. // I. af Math. Videnskab. Nutidig matematik. og det er Appl. Tematiske undersøgelser, vol. 10, 1994, I. of Math. Sciences, vol. 76, nr. 6, 1995. MR : 1365809

Implementering

Online implementering af Reed-Sloane og Berlekamp-Massey over GF(P) algoritmer (utilgængeligt link) på SignalsLab
GF(2 ) implementering i Mathematica