Forney algoritm

I kodningsteori beräknar Forney -algoritmen (eller Forneys algoritm ) felvärdena vid kända felplatser. Den används som ett av stegen för att avkoda BCH-koder och Reed–Solomon-koder (en underklass av BCH-koder). George David Forney Jr. utvecklade algoritmen.

Procedur

Behöver introducera terminologi och inställningarna...

Kodord ser ut som polynom. Genom designen har generatorpolynomet på varandra följande rötter α ^c , α ^{c +1} , ..., α ^{c + d −2} .

Syndrom

Felplaceringspolynom

\Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\summa _{i=1}^{\nu }\lambda _{i}\,x^{i}

Nollorna för Λ( x ) är X ₁⁻¹ , ..., X _ν⁻¹ . Nollorna är de reciproka felplatserna $X_{j}=\alpha ^{i_{j}}$ .

När felplatserna väl är kända är nästa steg att fastställa felvärdena på dessa platser. Felvärdena används sedan för att korrigera de mottagna värdena på dessa platser för att återställa det ursprungliga kodordet.

I det mer allmänna fallet kan felvikterna $e j$ bestämmas genom att lösa det linjära systemet

s_{0}=e_{1}\alpha ^{(c+0)\,i_{1} }+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,

s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{ 2}}+\cdots \,

\cdots \,

Det finns dock en mer effektiv metod som kallas Forney-algoritmen, som är baserad på Lagrange-interpolation . Beräkna först felutvärderarens polynom

\Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}} \,

Där $S (x)$ är det partiella syndrompolynomet:

S(x)=s_{0}x^{0}+s_{1}x^{1}+s_{2}x^{2}+\cdots +s_{2t-1}x^{ 2t-1}.

Utvärdera sedan felvärdena:

e_{j}=-{\frac {X_{j}^{1-c}\,\ Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,

Värdet $c$ kallas ofta "första roten i följd" eller "fcr". Vissa koder väljer $c = 1$ , så uttrycket förenklas till:

e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda ' (X_{j}^{-1})}}

Formell derivata

Λ'( x ) är den formella derivatan av fellokaliseringspolynomet Λ( x ):

\Lambda '(x)=\summa _{i=1}^{\nu }i\,\cdot \,\ lambda _{i}\,x^{i-1}

I uttrycket ovan, notera att i är ett heltal och λ _i skulle vara ett element i det finita fältet. Operatorn · representerar vanlig multiplikation (upprepad addition i det finita fältet) och inte det finita fältets multiplikationsoperator.

Härledning

Lagrange interpolation

Gill (nd , s. 52–54) ger en härledning av Forney-algoritmen.

Raderingar

Definiera raderingslokaliseringspolynomet

\Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})

Där raderingsplatserna anges av j _i . Använd proceduren som beskrivs ovan och ersätt Γ med Γ.

Om både fel och raderingar förekommer, använd polynomet för lokalisering av fel och radering

\Psi (x)=\Lambda (x)\,\Gamma (x)

Se även

Forney, G. (oktober 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory , 11 (4): 549–557, doi : 10.1109/TIT.1965.1053825 , ISSN 0018-9448
Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, s. 42–45, arkiverad från originalet (PDF) den 30 juni 2014 , hämtad 21 april 2010
W. Wesley Petersons bok