Berlekamp-Massey algoritmus

A Berlekamp-Massey algoritmus egy olyan algoritmus, amely a legrövidebb lineáris visszacsatolású eltolási regisztert keresi egy bemenetként megadott bináris sorozathoz. Az algoritmus azt is lehetővé teszi, hogy megtalálja a bemeneti lineáris ismétlődő sorozat minimális polinomját egy tetszőleges mezőn .

Az algoritmust Alvin Berlekamp fedezte fel 1968-ban [1] . Az algoritmus lineáris kódokra való alkalmazását James Massey találta meg a következő évben [2] . Ez lett a kulcs a Reed-Solomon kódexek gyakorlati alkalmazásához .

Az algoritmus leírása

Algoritmus B.M. egy alternatív módszer az SLAE megoldására, amely a következőképpen írható le:

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

Az alábbi kódpéldákban C(x) jelentése Λ(x). A C(x) hibakereső L hiba esetén a következőképpen definiálható:

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

vagy hátulról előre:

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

Az algoritmus célja a minimum L és a hozzá tartozó C(x) meghatározása, ami a teljes szindrómában hibákat ad.

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

nullát eredményez:

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

Algoritmus: C(x) inicializálása 1, L az eddig talált hibák aktuális számát jelöli, és nullára inicializálva. N a hibaszindróma elemek teljes száma. n a fő számláló, egyben a szindrómaelemek indexe 0-tól ( N -1-ig). B(x) az utolsó C(x) másolata L frissítése idején , és 1-re van inicializálva. b az utolsó d eltérés másolata (lásd alább), ismét az L frissítése idején, és m az L , B(x) és b frissítés óta eltelt iterációk száma, és szintén eggyel inicializálva van .

Minden iterációnál kiszámítjuk a d eltérést . A k- adik iterációnál ez lesz:

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

Ha d nulla, az azt jelenti, hogy C(x) és L egyenlőre helyes, elegendő m -et növelni és folytatni az iterációt.

Ha d értéke nem nulla, az algoritmus korrigálja a C(x)-et, és d -t nullára állítja :

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

Az x m -rel való szorzás lényegében a B(x) együtthatók m-rel való eltolását jelenti, azaz minden együttható m-rel magasabban helyezkedik el, hogy megfeleljen a b szindrómának . Ha legutóbb a j iterációnál frissítették az L-t (és most megvan a k -edik iteráció), akkor m = k - j , és az újraszámított eltérés a következő:

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

Vagyis helyettesítve azt látjuk, hogy eltűnik:

{\megjelenítési stílus d=d-(d/b)b=dd=0.\ }

Ezenkívül az L értékét (a talált hibák száma) néha javítani kell. Ha L egyenlő a hibás szimbólumok tényleges számával, akkor az iterációk során az eltérések nullázódnak, mielőtt n nagyobb vagy egyenlő lesz, mint (2 L ). Ellenkező esetben az L frissítésre kerül, és az algoritmus frissíti a B(x), b-t, magát az L-t (növekmény), és m visszaáll 1-re. Az L = (n + 1 - L) kifejezés korlátozza az L-t a felhasznált elérhető szindrómaelemek számára. az eltérések kiszámításához, és egyúttal megoldja az L eggyel növelésének problémáját.

Mintakód

Massey algoritmusa (1969 , 124. o.):

polinom ( K mező ) s ( x ) = ... /* együtthatók s_j; kimeneti sorozat N-1 fokos polinomként) */ /* kapcsolati polinom */ polinom ( K mező ) C ( x ) = 1 ; /* a koefficiensek c_j */ polinom ( K mező ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; mező K b = 1 ; int n ; /* 2. és 6. lépés. */ for ( n = 0 ; n < N ; n ++ ) { /* 2. lépés: eltérés kiszámítása */ mező K d = s_n + \ Sigma_ { i = 1 } ^ L c_i * s_ { n - i }; ha ( d == 0 ) { /* lépés 3. az eltérés nulla; a megsemmisítés folytatódik */ m = m + 1_ _ } különben ha ( 2 * L <= n ) { /* 5. lépés. */ /* a C(x) ideiglenes másolata */ polinom ( K mező ) 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 ; } más { /* 4. lépés. */ C ( x ) = C ( x ) -db ^ { - 1 } x ^ mB ( x ) ; _ m = m + 1_ _ } } vissza L ;

Algoritmus bináris sorozatokhoz

Állítsa be a kívánt bitsorozatot . ${\displaystyle s_{0},s_{1},...,s_{n-1))$
Hozzon létre , , hosszúságú tömböket , állítsa be a kezdeti értékeket , , , , . $b$ $t$ $c$ $n$ $b_{0}\leftarrow 1$ $c_{0}\leftarrow 1$ $N\leftarrow 0$ $L\leftarrow 0$ $m\leftarrow -1$
Viszlát : $N<n$
1. Számolja ki . ${\displaystyle d\leftarrow s_{N}\oplus c_{1}s_{N-1}\oplus c_{2}s_{N-2}\oplus ...\oplus c_{L}s_{NL))$
2. Ha , akkor az aktuális függvény generálja a sorozat kiválasztott szakaszát; hagyja a funkciót változatlan. $d=0$ ${\displaystyle s_{NL},s_{N-L+1},...,s_{N))$
3. Ha : $d\not=0$
  - Mentse el a tömb másolatát ide : . $c$ $t$
  - Számítsa ki az új értékeket . $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}$
  - Ha , állítsa be az értékeket , és másolja ide . $2L\leqslant N$ $L\leftarrow N+1-L$ $m\leftarrow N$ $t$ $b$
4. $N\leftarrow N+1$ .
Ennek eredményeként a tömb visszacsatolási függvény, azaz bármely . $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$ $én$

Jegyzetek

↑ Elwyn R. Berlekamp , Algebraic Coding Theory, New York: McGraw-Hill, 1968. Átdolgozott kiadás, Aegean Park Press, 1984, ISBN 0-89412-063-8 .
↑ JL Massey , Shift-register szintézis és BCH dekódolás Archiválva : 2011. szeptember 27., a Wayback Machine , IEEE Trans. Információelmélet, IT-15 (1969), 122-127.

Irodalom

Blahut R. A hibaellenőrző kódok elmélete és gyakorlata. — M .: Mir , 1986. — 576 p.
VL Kurakin, AS Kuzmin, AV Mikhalev, AA Nechaev. Lineáris ismétlődő sorozatok gyűrűk és modulok felett. // I. of Math. Tudomány. Kortárs matematika. és ez az Appl. Tematikus felmérések, vol. 10, 1994, I. of Math. Sciences, vol. 76, 6. szám, 1995. MR : 1365809

Linkek

Berlekamp-Massey algoritmus (angol) a PlanetMath weboldalán .
Weisstein, Eric W. Berlekamp-Massey algoritmus - MathWorld .

Megvalósítás

Reed-Sloane és Berlekamp-Massey GF(P) algoritmusok online megvalósítása (nem elérhető hivatkozás) a SignalsLabon
GF(2 ) implementáció a Mathematicában