Algoritmus Berlekamp-Massey

Algoritmus Berlekamp-Massey je algoritmus pro nalezení nejkratšího posuvného registru s lineární zpětnou vazbou pro binární sekvenci zadanou jako vstup. Algoritmus také umožňuje najít minimální polynom vstupní lineární rekurentní sekvence v libovolném poli .

Algoritmus objevil Alvin Berlekamp v roce 1968 [1] . Aplikaci algoritmu na lineární kódy našel následující rok James Massey [2] . To se stalo klíčem k praktické aplikaci Reed-Solomonových kódů .

Popis algoritmu

Algoritmus B.M. je alternativní metoda pro řešení SLAE, kterou lze popsat následovně:

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

V níže uvedených příkladech kódu C(x) představuje Λ(x). Lokátor chyb C(x) pro chyby L je definován jako:

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

nebo zezadu dopředu:

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

Účelem algoritmu je určit minimum L a odpovídající C(x), což dává chyby v celém syndromu

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

nula na konci:

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

Algoritmus: C(x) je inicializováno na 1, L označuje aktuální počet dosud nalezených chyb a inicializováno na nulu. N je celkový počet prvků chybového syndromu. n je hlavní čítač, je to také index prvků syndromu od 0 do ( N -1). B(x) je kopie posledního C(x) v době aktualizace L a je inicializována na 1. b je kopie poslední nesrovnalosti d (viz níže), opět v době aktualizace L a je inicializováno na 1. m je počet iterací, které prošly od aktualizace L , B(x) a b a také inicializovány na jednu.

Při každé iteraci se vypočítá diskrepance d . V k-té iteraci to bude:

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

Pokud je d nula, znamená to, že C(x) a L jsou prozatím správné, stačí ma inkrementovat a pokračovat v iteraci.

Pokud je d nenulové, algoritmus opraví C(x) tak, aby d bylo nastaveno na nulu :

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

Násobení x m je v podstatě posunem B(x) koeficientů o m, tj. každý koeficient je o m vyšší, aby odpovídal syndromu pro b . Pokud byl L naposledy aktualizován v iteraci j (a nyní máme k -tou iteraci), pak m = k - j a přepočítaný nesoulad je:

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

To znamená, že nahrazením vidíme, že zmizí:

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

Také hodnotu L (počet nalezených chyb) je někdy potřeba opravit. Pokud se L rovná skutečnému počtu chybných symbolů, pak v průběhu iterací budou nesrovnalosti vynulovány, než bude n větší nebo rovno (2 L ). V opačném případě se L aktualizuje a algoritmus aktualizuje B(x), b, samotné L (přírůstky) a m je resetováno na 1. Výraz L = (n + 1 - L) omezuje L na počet použitých dostupných prvků syndromu. vypočítat nesrovnalosti a zároveň řeší problém zvýšení L o více než jednu.

Ukázkový kód

Algorithm from Massey (1969 , str. 124):

polynom ( pole K ) s ( x ) = ... /* koeficienty jsou s_j; výstupní sekvence jako polynom N-1 stupně) */ /* spojovací polynom */ polynom ( pole K ) C ( x ) = 1 ; /* koeficienty jsou c_j */ polynom ( pole K ) B ( x ) = 1 ; int L = 0 ; int m = 1 ; pole Kb = 1 ; _ int n ; /* kroky 2. a 6. */ pro ( n = 0 ; n < N ; n ++ ) { /* krok 2. výpočet nesrovnalosti */ pole K d = s_n + \ Sigma_ { i = 1 } ^ L c_i * s_ { n - i }; if ( d == 0 ) { /* krok 3. nesoulad je nula; ničení pokračuje */ m = m + 1 _ } jinak if ( 2 * L <= n ) { /* krok 5. */ /* dočasná kopie C(x) */ polynom ( pole 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 ; } jiný { /* krok 4. */ C ( x ) = C ( x ) -db ^ { - 1 } x ^ mB ( x ) ; _ m = m + 1 _ } } návrat L ;

Algoritmus pro binární posloupnosti

Nastavte požadovanou bitovou sekvenci . ${\displaystyle s_{0},s_{1},...,s_{n-1))$
Vytvořte pole , , lengths , nastavte počáteční hodnoty , , , , . $b$ $t$ $C$ $n$ $b_{0}\leftarrow 1$ $c_{0}\leftarrow 1$ $N\leftarrow 0$ $L\leftarrow 0$ $m\leftarrow -1$
ahoj : $N<n$
1. Vypočítejte . ${\displaystyle d\leftarrow s_{N}\oplus c_{1}s_{N-1}\oplus c_{2}s_{N-2}\oplus ...\oplus c_{L}s_{NL))$
2. Jestliže , pak aktuální funkce vygeneruje vybranou část sekvence; funkci nechte stejnou. $d=0$ ${\displaystyle s_{NL},s_{N-L+1},...,s_{N))$
3. Pokud : $d\not=0$
  - Uložte kopii pole ve formátu . $C$ $t$
  - Vypočítejte nové hodnoty . $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}$
  - Pokud , nastavte hodnoty a zkopírujte do . $2L\leqslant N$ $L\leftarrow N+1-L$ $m\leftarrow N$ $t$ $b$
4. $N\leftarrow N+1$ .
V důsledku toho je pole zpětnovazební funkcí, tedy pro libovolný . $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$

Poznámky

↑ Elwyn R. Berlekamp , Teorie algebraického kódování, New York: McGraw-Hill, 1968. Revidované vydání, Aegean Park Press, 1984, ISBN 0-89412-063-8 .
↑ JL Massey , syntéza Shift-registru a dekódování BCH Archivováno 27. září 2011 na Wayback Machine , IEEE Trans. Teorie informace, IT-15 (1969), 122-127.

Literatura

Blahut R. Teorie a praxe kódů kontroly chyb. — M .: Mir , 1986. — 576 s.
VL Kurakin, AS Kuzmin, AV Michalev, AA Něčajev. Lineární opakující se sekvence přes kroužky a moduly. // I. matematiky. Věda. Současná matematika. a je to Appl. Tematické průzkumy, sv. 10, 1994, I. of Math. Sciences, sv. 76, č. 6, 1995. MR : 1365809

Odkazy

Algoritmus Berlekamp-Massey (anglicky) na webu PlanetMath .
Weisstein, Eric W. Berlekamp-Massey Algorithm - MathWorld .

Implementace

Online implementace Reed-Sloane a Berlekamp-Massey přes GF(P) algoritmy (nedostupný odkaz) na SignalsLab
Implementace GF(2 ) v Mathematica