BCH -kode - BCH code

I kodningsteorien danner BCH-koderne eller Bose-Chaudhuri-Hocquenghem-koderne en klasse af cykliske fejlkorrigerende koder, der er konstrueret ved hjælp af polynom over et begrænset felt (også kaldet Galois-felt ). BCH-koder blev opfundet i 1959 af den franske matematiker Alexis Hocquenghem og uafhængigt i 1960 af Raj Bose og DK Ray-Chaudhuri . Navnet Bose – Chaudhuri – Hocquenghem (og akronymet BCH ) stammer fra initialerne til opfindernes efternavne (fejlagtigt i tilfældet Ray-Chaudhuri).

En af nøglefunktionerne i BCH -koder er, at der under kodedesign er en præcis kontrol over antallet af symbolfejl, der kan korrigeres af koden. Især er det muligt at designe binære BCH -koder, der kan korrigere flere bitfejl. En anden fordel ved BCH -koder er den lethed, hvormed de kan afkodes, nemlig via en algebraisk metode kendt som syndromdekodning . Dette forenkler designet af dekoderen til disse koder ved hjælp af lille elektronisk hardware med lav effekt.

BCH-koder bruges i applikationer såsom satellitkommunikation, cd- afspillere, dvd'er , diskdrev , solid-state-drev , kvantebestandig kryptografi og todimensionale stregkoder .

Definition og illustration

Primitive BCH-koder med smal sans

I betragtning af et primtal q og primær kraft q ^m med positive heltal m og d sådan, at d ≤ q ^m -1 , en primitiv BCH-kode med snæver sans over det endelige felt (eller Galois-felt) GF ( q ) med kodelængde n = q ^m - 1 og afstanden mindst d konstrueres ved følgende metode.

Lad α være et primitivt element i GF ( q ^m ) . For ethvert positivt heltal i , lad m _i ( x ) være det minimale polynom med koefficienter i GF ( q ) af α ⁱ . Den generatorpolynomium af BCH-koden defineres som den mindste fælles multiplum g ( x ) = lcm ( m ₁ ( x ), ..., m _{d - 1} ( x )) . Det kan ses, at g ( x ) er et polynom med koefficienter i GF ( q ) og deler x ⁿ - 1 . Derfor er den polynomiske kode defineret af g ( x ) en cyklisk kode.

Eksempel

Lad q = 2 og m = 4 (derfor n = 15 ). Vi vil overveje forskellige værdier af d for GF (16) = GF (2 ⁴ ) baseret på det reducerende polynom z ⁴ + z + 1 ved hjælp af primitivt element α ( z ) = z . Der er fjorten minimumspolynomer m _i ( x ) med tilfredsstillende koefficienter i GF (2)

${\ displaystyle m_ {i} \ venstre (\ alpha ^{i} \ højre) {\ bmod {\ venstre (z ^{4}+z+1 \ højre)}} = 0.}$

De minimale polynomer er

${\ displaystyle {\ begin {justeret} m_ {1} (x) & = m_ {2} (x) = m_ {4} (x) = m_ {8} (x) = x^{4}+x+ 1, \\ m_ {3} (x) & = m_ {6} (x) = m_ {9} (x) = m_ {12} (x) = x^{4}+x^{3}+x ^{2}+x+1, \\ m_ {5} (x) & = m_ {10} (x) = x^{2}+x+1, \\ m_ {7} (x) & = m_ {11} (x) = m_ {13} (x) = m_ {14} (x) = x^{4}+x^{3} +1. \ End {align}}}$

BCH -koden med har generatorpolynom ${\ displaystyle d = 2,3}$

${\ displaystyle g (x) = {\ rm {lcm}} (m_ {1} (x), m_ {2} (x)) = m_ {1} (x) = x^{4}+x+1 . \,}$

Den har minimal Hamming -afstand mindst 3 og retter op til en fejl. Da generatorpolynomet er af grad 4, har denne kode 11 databit og 4 checksum -bits.

BCH -koden med har generatorpolynom ${\ displaystyle d = 4,5}$

${\ displaystyle {\ begin {justeret} g (x) & = {\ rm {lcm}} (m_ {1} (x), m_ {2} (x), m_ {3} (x), m_ {4 } (x)) = m_ {1} (x) m_ {3} (x) \\ & = \ venstre (x^{4}+x+1 \ højre) \ venstre (x^{4}+x^ {3}+x^{2}+x+1 \ højre) = x^{8}+x^{7}+x^{6}+x^{4} +1. \ End {align}}}$

Den har minimal Hamming -afstand mindst 5 og retter op til to fejl. Da generatorpolynomet er af grad 8, har denne kode 7 databit og 8 checksum -bits.

BCH -koden med har generatorpolynom ${\ displaystyle d = 6,7}$

${\ displaystyle {\ begin {justeret} g (x) & = {\ rm {lcm}} (m_ {1} (x), m_ {2} (x), m_ {3} (x), m_ {4 } (x), m_ {5} (x), m_ {6} (x)) = m_ {1} (x) m_ {3} (x) m_ {5} (x) \\ & = \ venstre ( x^{4}+x+1 \ højre) \ venstre (x^{4}+x^{3}+x^{2}+x+1 \ højre) \ venstre (x^{2}+x+ 1 \ højre) = x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1. \ End {align}}}$

Den har minimal Hamming -afstand mindst 7 og retter op til tre fejl. Da generatorpolynomet har en grad 10, har denne kode 5 databit og 10 checksum -bits. (Denne særlige generatorpolynom har en applikation i den virkelige verden i QR-kodens formatmønstre .)

BCH -koden med og højere har generatorpolynom ${\ displaystyle d = 8}$

${\ displaystyle {\ begin {justeret} g (x) & = {\ rm {lcm}} (m_ {1} (x), m_ {2} (x), ..., m_ {14} (x) ) = m_ {1} (x) m_ {3} (x) m_ {5} (x) m_ {7} (x) \\ & = \ venstre (x^{4}+x+1 \ højre) \ venstre (x^{4}+x^{3}+x^{2}+x+1 \ højre) \ venstre (x^{2}+x+1 \ højre) \ venstre (x^{4}+ x^{3} +1 \ højre) = x^{14}+x^{13}+x^{12}+\ cdots+x^{2}+x+1. \ slut {justeret}}}$

Denne kode har minimal Hamming -afstand 15 og retter 7 fejl. Den har 1 databit og 14 checksum -bits. Faktisk har denne kode kun to kodeord: 000000000000000 og 111111111111111.

Generelle BCH -koder

Generelle BCH-koder adskiller sig fra primitive smalle sansede BCH-koder i to henseender.

For det første kan kravet om at være et primitivt element i lempes. Ved at slappe dette krav, koden længde ændrer sig fra at den rækkefølge af elementet${\ displaystyle \ alpha}$${\ displaystyle \ mathrm {GF} (q^{m})}$${\ displaystyle q^{m} -1}$${\ displaystyle \ mathrm {ord} (\ alpha),}$${\ displaystyle \ alpha.}$

For det andet kan de på hinanden følgende rødder af generatorpolynomet løbe fra i stedet for${\ displaystyle \ alpha ^{c}, \ ldots, \ alpha ^{c+d-2}}$${\ displaystyle \ alpha, \ ldots, \ alpha ^{d-1}.}$

Definition. Fix et begrænset felt, hvor der er en primær effekt. Vælg positive heltal sådan og er multiplikative rækkefølgen af modulo${\ displaystyle GF (q),}$${\ displaystyle q}$${\ displaystyle m, n, d, c}$${\ displaystyle 2 \ leq d \ leq n,}$ ${\ displaystyle {\ rm {gcd}} (n, q) = 1,}$${\ displaystyle m}$${\ displaystyle q}$${\ displaystyle n.}$

Som før, så lad være en primitiv th roden af enhed i , og lad være det minimale polynomium løbet af for alle Generatoren polynomium af BCH-koden er defineret som den mindste fælles multiplum${\ displaystyle \ alpha}$${\ displaystyle n}$${\ displaystyle GF (q^{m}),}$${\ displaystyle m_ {i} (x)}$${\ displaystyle GF (q)}$${\ displaystyle \ alpha ^{i}}$${\ displaystyle i.}$ ${\ displaystyle g (x) = {\ rm {lcm}} (m_ {c} (x), \ ldots, m_ {c+d-2} (x)).}$

Bemærk: hvis som i den forenklede definition, så er 1, og rækkefølgen af modulo er Derfor er den forenklede definition faktisk et specielt tilfælde af den generelle. ${\ displaystyle n = q^{m} -1}$${\ displaystyle {\ rm {gcd}} (n, q)}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle m.}$

Særlige tilfælde

• En BCH-kode med kaldes en smalfølsom BCH-kode .${\ displaystyle c = 1}$
• En BCH -kode med kaldes primitiv .${\ displaystyle n = q^{m} -1}$

Generatorpolynomet for en BCH -kode har koefficienter fra Generelt kaldes en cyklisk kode med som generatorpolynomet en BCH -kode over BCH -koden over og generatorpolynom med successive beføjelser som rødder er en type Reed -Solomon -kode, hvor dekoder (syndromer) alfabet er det samme som kanal (data og generator polynom) alfabet, alle elementer af . Den anden type Reed Solomon -kode er en original visning af Reed Solomon -kode, som ikke er en BCH -kode. ${\ displaystyle g (x)}$${\ displaystyle \ mathrm {GF} (q).}$${\ displaystyle \ mathrm {GF} (q^{p})}$${\ displaystyle g (x)}$${\ displaystyle \ mathrm {GF} (q^{p}).}$${\ displaystyle \ mathrm {GF} (q^{m})}$${\ displaystyle g (x)}$${\ displaystyle \ alpha}$${\ displaystyle \ mathrm {GF} (q^{m})}$

Ejendomme

Generatorpolynomet for en BCH -kode har højst grad . Desuden, hvis og , har generatorpolynomet højst grad . ${\ displaystyle (d-1) m}$${\ displaystyle q = 2}$${\ displaystyle c = 1}$${\ displaystyle dm/2}$

En BCH -kode har mindst Hamming -afstand mindst . ${\ displaystyle d}$

En BCH -kode er cyklisk.

Indkodning

Fordi ethvert polynom, der er et multiplum af generatorpolynomet, er et gyldigt BCH -kodeord, er BCH -kodning blot processen med at finde et polynom, der har generatoren som en faktor.

Selve BCH -koden er ikke foreskrivende for betydningen af ​​koefficienterne i polynomet; konceptuelt er en BCH -afkodingsalgoritme eneste bekymring at finde det gyldige kodeord med den minimale Hamming -afstand til det modtagne kodeord. Derfor kan BCH -koden implementeres enten som en systematisk kode eller ej, afhængigt af hvordan implementøren vælger at integrere meddelelsen i det kodede polynom.

Ikke-systematisk kodning: Beskeden som faktor

Den mest enkle måde at finde et polynom, der er et multiplum af generatoren, er at beregne produktet af et vilkårligt polynom og generatoren. I dette tilfælde kan det vilkårlige polynom vælges ved hjælp af meddelelsens symboler som koefficienter.

${\ displaystyle s (x) = p (x) g (x)}$

Som et eksempel kan du overveje generatorpolynomet , valgt til brug i den (31, 21) binære BCH -kode, der bruges af POCSAG og andre. For at kode 21-bit beskeden {101101110111101111101} repræsenterer vi den først som et polynom over : ${\ displaystyle g (x) = x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3} +1}$${\ displaystyle GF (2)}$

${\ displaystyle p (x) = x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+ x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2} +1}$

Beregn derefter (også over ): ${\ displaystyle GF (2)}$

${\ displaystyle {\ begin {justeret} s (x) & = p (x) g (x) \\ & = \ venstre (x^{20}+x^{18}+x^{17}+x^ {15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5 }+x^{4}+x^{3}+x^{2} +1 \ højre) \ venstre (x^{10}+x^{9}+x^{8}+x^{6} +x^{5}+x^{3} +1 \ højre) \\ & = x^{30}+x^{29}+x^{26}+x^{25}+x^{24} +x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x ^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2} +1 \ slut {justeret}}}$

Således er det transmitterede kodeord {1100111010010111101011101110101}.

Modtageren kan bruge disse bits som koefficienter i og, efter fejlkorrektion for at sikre et gyldigt kodeord, kan genberegne${\ displaystyle s (x)}$${\ displaystyle p (x) = s (x)/g (x)}$

Systematisk kodning: Beskeden som et præfiks

En systematisk kode er en, hvor meddelelsen vises ordret et sted i kodeordet. Derfor involverer systematisk BCH-kodning først at integrere meddelelsespolynomet i kodeordpolynomet og derefter justere koefficienterne for de resterende (ikke-besked) vilkår for at sikre, at det kan deles med . ${\ displaystyle s (x)}$${\ displaystyle g (x)}$

Denne kodningsmetode udnytter det faktum, at det at trække resten fra et udbytte resulterer i et multiplum af divisoren. Derfor, hvis vi tager vores budskabspolynom som før og multiplicerer det med (for at "flytte" budskabet væk fra resten), kan vi derefter bruge euklidisk opdeling af polynomier til at give: ${\ displaystyle p (x)}$${\ displaystyle x^{nk}}$

${\ displaystyle p (x) x^{nk} = q (x) g (x)+r (x)}$

Her ser vi, at det er et gyldigt kodeord. Som det altid er grad mindre end (hvilket er graden af ), kan vi roligt trække det fra uden at ændre nogen af ​​beskedkoefficienterne, derfor har vi vores som ${\ displaystyle q (x) g (x)}$${\ displaystyle r (x)}$${\ displaystyle nk}$${\ displaystyle g (x)}$${\ displaystyle p (x) x^{nk}}$${\ displaystyle s (x)}$

${\ displaystyle s (x) = q (x) g (x) = p (x) x^{nk} -r (x)}$

Over (dvs. med binære BCH-koder) kan denne proces ikke skelnes fra at tilføje en cyklisk redundanskontrol , og hvis en systematisk binær BCH-kode kun bruges til fejldetekteringsformål, ser vi, at BCH-koder kun er en generalisering af cykliske matematik redundans kontrol . ${\ displaystyle GF (2)}$

Fordelen ved den systematiske kodning er, at modtageren kan gendanne den originale meddelelse ved at kassere alt efter de første koefficienter efter at have udført fejlkorrektion. ${\ displaystyle k}$

Afkodning

Der er mange algoritmer til afkodning af BCH -koder. De mest almindelige følger denne generelle oversigt:

1. Beregn syndromerne s _j for den modtagne vektor
2. Bestem antallet af fejl t og fejllokatorens polynom Λ (x) fra syndromerne
3. Beregn rødderne til fejlplaceringspolynomet for at finde fejlplaceringerne X _i
4. Beregn fejlværdierne Y _i på disse fejlsteder
5. Ret fejlene

Under nogle af disse trin kan dekoderingsalgoritmen bestemme, at den modtagne vektor har for mange fejl og ikke kan rettes. For eksempel, hvis en passende værdi af t ikke findes, ville korrektionen mislykkes. I en afkortet (ikke primitiv) kode kan en fejlplacering være uden for området. Hvis den modtagne vektor har flere fejl, end koden kan rette, kan dekoderen ubevidst frembringe en tilsyneladende gyldig meddelelse, der ikke er den, der blev sendt.

Beregn syndromerne

Den modtagne vektor er summen af ​​det korrekte kodeord og en ukendt fejlvektor Syndromværdierne dannes ved at betragte det som et polynom og evaluere det på Således er syndromerne ${\ displaystyle R}$${\ displaystyle C}$${\ displaystyle E.}$${\ displaystyle R}$${\ displaystyle \ alpha ^{c}, \ ldots, \ alpha ^{c+d-2}.}$

${\ displaystyle s_ {j} = R \ venstre (\ alpha ^{j} \ højre) = C \ venstre (\ alpha ^{j} \ højre)+E \ venstre (\ alpha ^{j} \ højre)}$

for at${\ displaystyle j = c}$${\ displaystyle c+d-2.}$

Da nuller heraf er et multiplum, isolerer undersøgelse af syndromværdierne således fejlvektoren, så man kan begynde at løse for det. ${\ displaystyle \ alpha ^{j}}$${\ displaystyle g (x),}$${\ displaystyle C (x)}$${\ displaystyle C \ venstre (\ alpha ^{j} \ højre) = 0.}$

Hvis der ikke er nogen fejl, for alle Hvis syndromerne alle er nul, er afkodningen udført. ${\ displaystyle s_ {j} = 0}$${\ displaystyle j.}$

Beregn fejlplaceringspolynomet

Hvis der er nul -syndromer, er der fejl. Dekoderen skal finde ud af, hvor mange fejl og placeringen af ​​disse fejl.

Hvis der er en enkelt fejl, skal du skrive dette som hvor er placeringen af ​​fejlen og dens størrelse. Så er de to første syndromer ${\ displaystyle E (x) = e \, x^{i},}$${\ displaystyle i}$${\ displaystyle e}$

${\ displaystyle {\ begin {align} s_ {c} & = e \, \ alpha ^{c \, i} \\ s_ {c+1} & = e \, \ alpha ^{(c+1) \ , i} = \ alpha ^{i} s_ {c} \ end {align}}}$

så sammen giver de os mulighed for at beregne og give nogle oplysninger om (fuldstændig bestemmelse af det i tilfælde af Reed -Solomon -koder). ${\ displaystyle e}$${\ displaystyle i}$

Hvis der er to eller flere fejl,

${\ displaystyle E (x) = e_ {1} x^{i_ {1}}+e_ {2} x^{i_ {2}}+\ cdots \,}$

Det er ikke umiddelbart indlysende, hvordan man begynder at løse de resulterende syndromer for de ukendte og${\ displaystyle e_ {k}}$${\ displaystyle i_ {k}.}$

Det første trin er at finde, kompatibelt med computersyndromer og med minimalt muligt lokaliseringspolynom: ${\ displaystyle t,}$

${\ displaystyle \ Lambda (x) = \ prod _ {j = 1} ^{t} \ venstre (x \ alpha ^{i_ {j}}-1 \ højre)}$

Tre populære algoritmer til denne opgave er:

1. Peterson – Gorenstein – Zierler algoritme
2. Berlekamp – Massey algoritme
3. Sugiyama euklidisk algoritme

Peterson – Gorenstein – Zierler algoritme

Petersons algoritme er trin 2 i den generaliserede BCH -afkodningsprocedure. Petersons algoritme bruges til at beregne fejllokatorens polynomkoefficienter for et polynom ${\ displaystyle \ lambda _ {1}, \ lambda _ {2}, \ dots, \ lambda _ {v}}$

${\ displaystyle \ Lambda (x) = 1+\ lambda _ {1} x+\ lambda _ {2} x^{2}+\ cdots+\ lambda _ {v} x^{v}.}$

Nu er proceduren for Peterson – Gorenstein – Zierler -algoritmen. Forvent, at vi har mindst 2 t syndromer s _c ,…, s _{c +2 t −1} . Lad v  =  t .

Faktorfejl lokaliseringspolynom

Nu hvor du har polynomet, kan dets rødder findes i formen ved brutal kraft, for eksempel ved hjælp af Chien -søge -algoritmen. Det primitive elements eksponentielle kræfter vil give de positioner, hvor der opstår fejl i det modtagne ord; deraf navnet 'fejlfinder' polynom. ${\ displaystyle \ Lambda (x)}$${\ displaystyle \ Lambda (x) = \ left (\ alpha ^{i_ {1}} x-1 \ right) \ left (\ alpha ^{i_ {2}} x-1 \ right) \ cdots \ left ( \ alpha ^{i_ {v}} x-1 \ højre)}$${\ displaystyle \ alpha}$

Nullerne på Λ ( x ) er α ^{- i ₁} ,…, α ^{- i _v} .

Beregn fejlværdier

Når fejlplaceringerne er kendt, er det næste trin at bestemme fejlværdierne på disse steder. Fejlværdierne bruges derefter til at rette de modtagne værdier på disse steder for at gendanne det originale kodeord.

I tilfælde af binær BCH (med alle læsbare tegn) er dette trivielt; bare vend bitene for det modtagne ord på disse positioner, og vi har det korrigerede kodeord. I det mere generelle tilfælde kan fejlvægtene bestemmes ved at løse det lineære system ${\ displaystyle e_ {j}}$

${\ displaystyle {\ begin {align} s_ {c} & = e_ {1} \ alpha ^{c \, i_ {1}}+e_ {2} \ alpha ^{c \, i_ {2}}+\ cdots \\ s_ {c+1} & = e_ {1} \ alpha ^{(c+1) \, i_ {1}}+e_ {2} \ alpha ^{(c+1) \, i_ {2 }}+\ cdots \\ & {} \ \ vdots \ end {align}}}$

Forney algoritme

Der er imidlertid en mere effektiv metode kendt som Forney -algoritmen .

Lade

${\ displaystyle S (x) = s_ {c}+s_ {c+1} x+s_ {c+2} x^{2}+\ cdots+s_ {c+d-2} x^{d-2 }.}$

${\ displaystyle v \ leqslant d-1, \ lambda _ {0} \ neq 0 \ qquad \ Lambda (x) = \ sum _ {i = 0}^{v} \ lambda _ {i} x^{i} = \ lambda _ {0} \ prod _ {k = 0} ^{v} \ venstre (\ alpha ^{-i_ {k}} x-1 \ højre).}$

Og fejlvurderingspolynomet

${\ displaystyle \ Omega (x) \ equiv S (x) \ Lambda (x) {\ bmod {x^{d-1}}}}}$

Endelig:

${\ displaystyle \ Lambda '(x) = \ sum _ {i = 1}^{v} i \ cdot \ lambda _ {i} x^{i-1},}$

hvor

${\ displaystyle i \ cdot x: = \ sum _ {k = 1}^{i} x.}$

End hvis syndromer kunne forklares med et fejlord, der kun kunne være nul på positioner , er fejlværdierne ${\ displaystyle i_ {k}}$

${\ displaystyle e_ {k} =-{\ alpha ^{i_ {k}} \ Omega \ venstre (\ alpha ^{-i_ {k}} \ højre) \ over \ alpha ^{c \ cdot i_ {k} } \ Lambda '\ venstre (\ alpha ^{-i_ {k}} \ højre)}.}$

For BCH-koder med smal sans, c = 1, så udtrykket forenkles til:

${\ displaystyle e_ {k} =-{\ Omega \ venstre (\ alpha ^{-i_ {k}} \ højre) \ over \ Lambda '\ venstre (\ alpha ^{-i_ {k}} \ højre)} .}$

Forklaring af Forney -algoritmeberegning

Det er baseret på Lagrange -interpolation og teknikker til generering af funktioner .

Overvej og for enkelthedens skyld antag for og for derefter ${\ displaystyle S (x) \ Lambda (x),}$${\ displaystyle \ lambda _ {k} = 0}$${\ displaystyle k> v,}$${\ displaystyle s_ {k} = 0}$${\ displaystyle k> c+d-2.}$

${\ displaystyle S (x) \ Lambda (x) = \ sum _ {j = 0}^{\ infty} \ sum _ {i = 0}^{j} s_ {j-i+1} \ lambda _ { i} x^{j}.}$

${\ displaystyle {\ begin {align} S (x) \ Lambda (x) & = S (x) \ left \ {\ lambda _ {0} \ prod _ {\ ell = 1}^{v} \ left ( \ alpha ^{i _ {\ ell}} x-1 \ højre) \ højre \} \\ & = \ venstre \ {\ sum _ {i = 0} ^{d-2} \ sum _ {j = 1} ^{v} e_ {j} \ alpha ^{(c+i) \ cdot i_ {j}} x ^{i} \ højre \} \ venstre \ {\ lambda _ {0} \ prod _ {\ ell = 1}^{v} \ venstre (\ alpha^{i _ {\ ell}} x-1 \ højre) \ højre \} \\ & = \ venstre \ {\ sum _ {j = 1}^{v} e_ {j} \ alpha^{ci_ {j}} \ sum _ {i = 0}^{d-2} \ venstre (\ alpha^{i_ {j}} \ højre)^{i} x^{i} \ højre \} \ venstre \ {\ lambda _ {0} \ prod _ {\ ell = 1} ^{v} \ venstre (\ alpha ^{i _ {\ ell}} x-1 \ højre) \ højre \} \\ & = \ venstre \ {\ sum _ {j = 1} ^{v} e_ {j} \ alpha ^{ci_ {j}} {\ frac {\ venstre (x \ alpha ^{i_ {j}} \ højre) ^{d-1} -1} {x \ alpha ^{i_ {j}}-1}} \ højre \} \ venstre \ {\ lambda _ {0} \ prod _ {\ ell = 1} ^{v} \ venstre (\ alpha ^{i _ {\ ell}} x-1 \ højre) \ højre \} \\ & = \ lambda _ {0} \ sum _ {j = 1} ^{v} e_ {j} \ alpha ^{ci_ {j}} {\ frac {\ left (x \ alpha ^{i_ {j}} \ right) ^{d-1} -1} {x \ alpha ^{i_ {j }}-1}} \ prod _ {\ ell = 1} ^{v} \ venstre (\ alpha ^{i _ {\ ell}} x-1 \ højre) \\ & = \ lambda _ {0} \ sum _ {j = 1} ^{v} e_ {j} \ alpha ^{ci_ {j}} \ venstre (\ venstre (x \ alpha ^{i_ {j}} \ højre) ^{d-1} -1 \ højre) \ prod _ {\ ell \ in \ {1, \ cdot s, v \} \ setminus \ {j \}} \ venstre (\ alpha ^{i _ {\ ell}} x-1 \ højre) \ end {justeret}}}$

Vi vil beregne ubekendte, og vi kunne forenkle konteksten ved at fjerne vilkårene. Dette fører til fejlevalueringspolynomet ${\ displaystyle e_ {j},}$${\ displaystyle \ venstre (x \ alpha ^{i_ {j}} \ højre) ^{d-1}}$

${\ displaystyle \ Omega (x) \ equiv S (x) \ Lambda (x) {\ bmod {x^{d-1}}}.}$

Takket være det har vi ${\ displaystyle v \ leqslant d-1}$

${\ displaystyle \ Omega (x) =-\ lambda _ {0} \ sum _ {j = 1} ^{v} e_ {j} \ alpha ^{ci_ {j}} \ prod _ {\ ell \ in \ {1, \ cdots, v \} \ setminus \ {j \}} \ venstre (\ alpha ^{i _ {\ ell}} x-1 \ højre).}$

Takket være (Lagrange -interpolationstricket) degenereres summen til kun én summen for${\ displaystyle \ Lambda}$${\ displaystyle x = \ alpha ^{-i_ {k}}}$

${\ displaystyle \ Omega \ venstre (\ alpha ^{-i_ {k}} \ right) =-\ lambda _ {0} e_ {k} \ alpha ^{c \ cdot i_ {k}} \ prod _ {\ ell \ in \ {1, \ cdots, v \} \ setminus \ {k \}} \ venstre (\ alpha ^{i _ {\ ell}} \ alpha ^{-i_ {k}}-1 \ højre). }$

For at få det skal vi bare slippe af med produktet. Vi kunne beregne produktet direkte fra allerede beregnede rødder af, men vi kunne bruge enklere form. ${\ displaystyle e_ {k}}$${\ displaystyle \ alpha ^{-i_ {j}}}$${\ displaystyle \ Lambda,}$

Som formel afledt

${\ displaystyle \ Lambda '(x) = \ lambda _ {0} \ sum _ {j = 1} ^{v} \ alpha ^{i_ {j}} \ prod _ {\ ell \ in \ {1, \ cdots, v \} \ setminus \ {j \}} \ venstre (\ alpha ^{i _ {\ ell}} x-1 \ højre),}$

vi får igen kun en summen ind

${\ displaystyle \ Lambda '\ venstre (\ alpha ^{-i_ {k}} \ right) = \ lambda _ {0} \ alpha ^{i_ {k}} \ prod _ {\ ell \ in \ {1, \ cdots, v \} \ setminus \ {k \}} \ venstre (\ alpha ^{i _ {\ ell}} \ alpha ^{-i_ {k}}-1 \ højre).}$

Så endelig

${\ displaystyle e_ {k} =-{\ frac {\ alpha ^{i_ {k}} \ Omega \ venstre (\ alpha ^{-i_ {k}} \ right)} {\ alpha ^{c \ cdot i_ {k}} \ Lambda '\ venstre (\ alpha ^{-i_ {k}} \ højre)}}.}$

Denne formel er fordelagtig, når man beregner det formelle derivat af form ${\ displaystyle \ Lambda}$

${\ displaystyle \ Lambda (x) = \ sum _ {i = 1}^{v} \ lambda _ {i} x^{i}}$

hvilket giver:

${\ displaystyle \ Lambda '(x) = \ sum _ {i = 1}^{v} i \ cdot \ lambda _ {i} x^{i-1},}$

hvor

${\ displaystyle i \ cdot x: = \ sum _ {k = 1}^{i} x.}$

Afkodning baseret på udvidet euklidisk algoritme

En alternativ proces med at finde både polynomet Λ og fejllokatorpolynomet er baseret på Yasuo Sugiyamas tilpasning af den udvidede euklidiske algoritme . Korrektion af ulæselige tegn kan også let indarbejdes i algoritmen.

Lad være positioner med ulæselige tegn. Man opretter polynom lokalisering af disse positioner Indstil værdier på ulæselige positioner til 0 og beregne syndromerne. ${\ displaystyle k_ {1}, ..., k_ {k}}$${\ displaystyle \ Gamma (x) = \ prod _ {i = 1} ^{k} \ venstre (x \ alpha ^{k_ {i}}-1 \ højre).}$

Som vi allerede har defineret for Forney -formlen lad ${\ displaystyle S (x) = \ sum _ {i = 0}^{d-2} s_ {c+i} x^{i}.}$

Lad os køre en udvidet euklidisk algoritme til lokalisering af den mindst fælles divisor af polynomier og Målet er ikke at finde den mindst fælles divisor, men højst et polynom og polynomer således, at Lav grad af garantier, der ville tilfredsstille udvidede (ved ) definerende betingelser til${\ displaystyle S (x) \ Gamma (x)}$${\ displaystyle x^{d-1}.}$${\ displaystyle r (x)}$${\ displaystyle \ lfloor (d+k-3)/2 \ rfloor}$${\ displaystyle a (x), b (x)}$${\ displaystyle r (x) = a (x) S (x) \ Gamma (x)+b (x) x^{d-1}.}$${\ displaystyle r (x)}$${\ displaystyle a (x)}$${\ displaystyle \ Gamma}$${\ displaystyle \ Lambda.}$

At definere og bruge på stedet for i Fourney -formlen vil give os fejlværdier. ${\ displaystyle \ Xi (x) = a (x) \ Gamma (x)}$${\ displaystyle \ Xi}$${\ displaystyle \ Lambda (x)}$

Den største fordel ved algoritmen er, at den i mellemtiden beregner nødvendige i Forney -formlen. ${\ displaystyle \ Omega (x) = S (x) \ Xi (x) {\ bmod {x}}^{d-1} = r (x)}$

Forklaring af afkodningsprocessen

Målet er at finde et kodeord, der adskiller sig fra det modtagne ord minimalt som muligt på læsbare positioner. Når vi udtrykker det modtagne ord som en sum af nærmeste kodeord og fejlord, forsøger vi at finde fejlord med et minimalt antal ikke-nuller på læsbare positioner. Syndrom begrænser fejl ord efter tilstand ${\ displaystyle s_ {i}}$

${\ displaystyle s_ {i} = \ sum _ {j = 0} ^{n-1} e_ {j} \ alpha ^{ij}.}$

Vi kunne skrive disse betingelser separat eller vi kunne skabe polynom

${\ displaystyle S (x) = \ sum _ {i = 0}^{d-2} s_ {c+i} x^{i}}$

og sammenligne koefficienter nær beføjelser til${\ displaystyle 0}$${\ displaystyle d-2.}$

${\ displaystyle S (x) {\ stackrel {\ {0, \ cdots, \, d-2 \}} {=}} E (x) = \ sum _ {i = 0}^{d-2} \ sum _ {j = 0} ^{n-1} e_ {j} \ alpha ^{ij} \ alpha ^{cj} x ^{i}.}$

Antag, at der er et ulæseligt bogstav om position, vi kunne erstatte sæt syndromer med sæt af syndromer defineret ved ligning Antag for et fejlord, at alle begrænsninger ved det originale sæt syndromer holder, end ${\ displaystyle k_ {1},}$${\ displaystyle \ {s_ {c}, \ cdots, s_ {c+d-2} \}}$${\ displaystyle \ {t_ {c}, \ cdots, t_ {c+d-3} \}}$${\ displaystyle t_ {i} = \ alpha ^{k_ {1}} s_ {i} -s_ {i+1}.}$${\ displaystyle \ {s_ {c}, \ cdots, s_ {c+d-2} \}}$

${\ displaystyle t_ {i} = \ alpha ^{k_ {1}} s_ {i} -s_ {i+1} = \ alpha ^{k_ {1}} \ sum _ {j = 0} ^{n- 1} e_ {j} \ alpha ^{ij}-\ sum _ {j = 0} ^{n-1} e_ {j} \ alpha ^{j} \ alpha ^{ij} = \ sum _ {j = 0} ^{n-1} e_ {j} \ venstre (\ alpha ^{k_ {1}}-\ alpha ^{j} \ højre) \ alpha ^{ij}.}$

Nyt sæt syndromer begrænser fejlvektoren

${\ displaystyle f_ {j} = e_ {j} \ venstre (\ alpha ^{k_ {1}}-\ alpha ^{j} \ right)}$

på samme måde begrænsede det originale sæt syndromer fejlvektoren Bortset fra koordinaten, hvor vi har en, er nul, hvis For målet om at lokalisere fejlpositioner kunne vi ændre sættet med syndromer på lignende måde for at afspejle alle ulæselige tegn. Dette forkorter sæt af syndromer med${\ displaystyle e_ {j}.}$${\ displaystyle k_ {1},}$${\ displaystyle f_ {k_ {1}} = 0,}$${\ displaystyle f_ {j}}$${\ displaystyle e_ {j} = 0.}$${\ displaystyle k.}$

I polynomformulering fører udskiftning af syndromer sat med syndromesæt til ${\ displaystyle \ {s_ {c}, \ cdots, s_ {c+d-2} \}}$${\ displaystyle \ {t_ {c}, \ cdots, t_ {c+d-3} \}}$

${\ displaystyle T (x) = \ sum _ {i = 0}^{d-3} t_ {c+i} x^{i} = \ alpha^{k_ {1}} \ sum _ {i = 0 }^{d-3} s_ {c+i} x^{i}-\ sum _ {i = 1}^{d-2} s_ {c+i} x^{i-1}.}$

Derfor,

${\ displaystyle xT (x) {\ stackrel {\ {1, \ cdots, \, d-2 \}} {=}} \ venstre (x \ alpha ^{k_ {1}}-1 \ højre) S ( x).}$

Efter udskiftning af med ville man kræve ligning for koefficienter nær kræfter${\ displaystyle S (x)}$${\ displaystyle S (x) \ Gamma (x)}$${\ displaystyle k, \ cdots, d-2.}$

Man kunne overveje at kigge efter fejlpositioner fra det synspunkt at eliminere indflydelse fra givne positioner på samme måde som for ulæselige tegn. Hvis vi fandt positioner, så eliminering af deres indflydelse fører til at få et sæt syndromer, der består af alle nuller, end der findes fejlvektor med fejl kun på disse koordinater. Hvis betegner det polynom, der eliminerer påvirkningen af ​​disse koordinater, opnår vi ${\ displaystyle v}$${\ displaystyle \ Lambda (x)}$

${\ displaystyle S (x) \ Gamma (x) \ Lambda (x) {\ stackrel {\ {k+v, \ cdots, d-2 \}} {=}} 0.}$

I den euklidiske algoritme forsøger vi højst at rette fejl (på læsbare positioner), fordi med større fejltælling kan der være flere kodeord i samme afstand fra det modtagne ord. Derfor, for vi leder efter, skal ligningen holde for koefficienter nær kræfter, der starter fra ${\ displaystyle {\ tfrac {1} {2}} (d-1-k)}$${\ displaystyle \ Lambda (x)}$

${\ displaystyle k+\ left \ lfloor {\ frac {1} {2}} (d-1-k) \ right \ rfloor.}$

I Forney -formlen kan den ganges med en skalar, der giver det samme resultat. ${\ displaystyle \ Lambda (x)}$

Det kan ske, at den euklidiske algoritme finder en grad højere end at have et antal forskellige rødder svarende til dens grad, hvor Fourney -formlen ville være i stand til at rette fejl i alle dens rødder, men alligevel kunne det være risikabelt at rette så mange fejl (især uden andre begrænsninger på modtaget ord). Normalt efter at have fået en højere grad, beslutter vi os for ikke at rette fejlene. Korrektion kan mislykkes, hvis der er rødder med større multiplicitet, eller antallet af rødder er mindre end dets grad. Fejl kan også opdages ved at Forney -formel returnerer fejl uden for det transmitterede alfabet. ${\ displaystyle \ Lambda (x)}$${\ displaystyle {\ tfrac {1} {2}} (d-1-k)}$${\ displaystyle \ Lambda (x)}$${\ displaystyle \ Lambda (x)}$

Ret fejlene

Brug fejlværdierne og fejlplaceringen til at rette fejlene og danne en korrigeret kodevektor ved at trække fejlværdier fra ved fejlplaceringer.

Afkodningseksempler

Afkodning af binær kode uden ulæselige tegn

Overvej en BCH -kode i GF (2 ⁴ ) med og . (Dette bruges i QR -koder .) Lad meddelelsen, der skal transmitteres, være [1 1 0 1 1], eller i polynomnotation, "checksum" -symbolerne beregnes ved at dividere med og tage resten, hvilket resulterer i eller [1 0 0 0 0 1 0 1 0 0]. Disse er vedhæftet meddelelsen, så det overførte kodeord er [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]. ${\ displaystyle d = 7}$${\ displaystyle g (x) = x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$${\ displaystyle M (x) = x^{4}+x^{3}+x+1.}$${\ displaystyle x^{10} M (x)}$${\ displaystyle g (x)}$${\ displaystyle x^{9}+x^{4}+x^{2}}$

Forestil dig nu, at der er to bitfejl i transmissionen, så det modtagne kodeord er [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. I polynom notation:

${\ displaystyle R (x) = C (x)+x^{13}+x^{5} = x^{14}+x^{11}+x^{10}+x^{9}+x ^{5}+x^{4}+x^{2}}$

For at rette fejlene skal du først beregne syndromerne. Når vi tager og derefter anvender vi Peterson-proceduren ved at reducere følgende forstørrede matrix i række. ${\ displaystyle \ alpha = 0010,}$${\ displaystyle s_ {1} = R (\ alpha ^{1}) = 1011,}$ ${\ displaystyle s_ {2} = 1001,}$ ${\ displaystyle s_ {3} = 1011,}$ ${\ displaystyle s_ {4} = 1101,}$ ${\ displaystyle s_ {5} = 0001,}$${\ displaystyle s_ {6} = 1001.}$

${\ displaystyle \ left [S_ {3 \ times 3} | C_ {3 \ times 1} \ right] = {\ begin {bmatrix} s_ {1} & s_ {2} & s_ {3} & s_ {4} \\ s_ {2} & s_ {3} & s_ {4} & s_ {5} \\ s_ {3} & s_ {4} & s_ {5} & s_ {6} \ end {bmatrix}} = {\ begin {bmatrix} 1011 & 1001 & 1011 & 1101 \\ 1001 & 1011 & 1101 & 0001 \\ 1011 & 1101 & 0001 & 1001 \ end {bmatrix}} \ Højre pil {\ begin {bmatrix} 0001 & 0000 & 1000 & 0111 \\ 0000 & 0001 & 1011 & 0001 \\ 0000 & 0000 & 0000 & 0000 \ end {bmatrix}}}$

På grund af nulrækken er S _{3 × 3} ental, hvilket ikke er nogen overraskelse, da kun to fejl blev introduceret i kodeordet. Matrixens øverste venstre hjørne er imidlertid identisk med [ S _{2 × 2} | C _{2 × 1} ] , som giver anledning til løsningen Det resulterende fejllokaliseringspolynom er som har nuller på og Eksponenterne svarer til fejlplaceringerne. Det er ikke nødvendigt at beregne fejlværdierne i dette eksempel, da den eneste mulige værdi er 1. ${\ displaystyle \ lambda _ {2} = 1000,}$ ${\ displaystyle \ lambda _ {1} = 1011.}$${\ displaystyle \ Lambda (x) = 1000x^{2}+1011x+0001,}$${\ displaystyle 0100 = \ alpha ^{-13}}$${\ displaystyle 0111 = \ alpha ^{-5}.}$${\ displaystyle \ alpha}$

Afkodning med ulæselige tegn

Antag det samme scenario, men det modtagne ord har to ulæselige tegn [1 0 0? 11 1? 0 0 1 1 0 1 0 0]. Vi erstatter de ulæselige tegn med nuller, mens vi opretter polynomet, der afspejler deres positioner Vi beregner syndromerne og (Ved hjælp af lognotation, der er uafhængig af GF (2 ⁴ ) isomorfier. Til beregningskontrol kan vi bruge den samme repræsentation til tilføjelse som blev brugt i tidligere Hexadecimal beskrivelse af beføjelserne er i rækkefølge 1,2,4,8,3,6, C, B, 5, A, 7, E, F, D, 9 med tilføjelsen baseret på bitvis xor.) ${\ displaystyle \ Gamma (x) = \ left (\ alpha ^{8} x-1 \ right) \ left (\ alpha ^{11} x-1 \ right).}$${\ displaystyle s_ {1} = \ alpha ^{-7}, s_ {2} = \ alpha ^{1}, s_ {3} = \ alpha ^{4}, s_ {4} = \ alpha ^{2 }, s_ {5} = \ alpha ^{5},}$${\ displaystyle s_ {6} = \ alpha ^{-7}.}$${\ displaystyle \ alpha}$

Lad os gøre syndrom polynomt

${\ displaystyle S (x) = \ alpha ^{-7}+\ alpha ^{1} x+\ alpha ^{4} x ^{2}+\ alpha ^{2} x ^{3}+\ alpha ^ {5} x^{4}+\ alpha^{-7} x^{5},}$

beregne

${\ displaystyle S (x) \ Gamma (x) = \ alpha ^{-7}+\ alpha ^{4} x+\ alpha ^{-1} x ^{2}+\ alpha ^{6} x ^{ 3}+\ alpha ^{-1} x ^{4}+\ alpha ^{5} x ^{5}+\ alpha ^{7} x ^{6}+\ alpha ^{-3} x ^{ 7}.}$

Kør den udvidede euklidiske algoritme:

${\ displaystyle {\ begin {align} & {\ begin {pmatrix} S (x) \ Gamma (x) \\ x^{6} \ end {pmatrix}} \\ [6pt] = {} & {\ begin {pmatrix} \ alpha ^{-7}+\ alpha ^{4} x+\ alpha ^{-1} x ^{2}+\ alpha ^{6} x ^{3}+\ alpha ^{-1} x^{4}+\ alpha^{5} x^{5}+\ alpha^{7} x^{6}+\ alpha^{-3} x^{7} \\ x^{6} \ slut {pmatrix}} \\ [6pt] = {} & {\ begin {pmatrix} \ alpha ^{7}+\ alpha ^{-3} x & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} x ^{6} \\\ alpha ^{-7}+\ alpha ^{4} x+\ alpha ^{-1} x ^{2}+\ alpha ^{6} x ^{3}+\ alpha ^ {-1} x^{4}+\ alpha^{5} x^{5} +2 \ alpha^{7} x^{6} +2 \ alpha^{-3} x^{7} \ end {pmatrix}} \\ [6pt] = {} & {\ begin {pmatrix} \ alpha ^{7}+\ alpha ^{-3} x & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{4}+\ alpha ^{-5} x & 1 \\ 1 & 0 \ end {pmatrix}} \\ & \ qquad {\ begin {pmatrix} \ alpha ^{-7}+\ alpha ^{4} x+\ alpha ^{-1} x ^{2}+\ alpha ^{6} x ^{3}+\ alpha ^{-1} x ^{4}+\ alpha ^{5} x ^{5} \\ \ alpha ^{-3}+\ venstre (\ alpha ^{-7}+\ alpha ^{3} \ højre) x+\ venstre (\ alpha ^{3}+\ alpha ^{-1} \ højre) x ^{2}+\ venstre (\ alpha ^{-5}+\ alpha ^{-6} \ højre) x ^{3}+\ venstre (\ alpha ^{3}+\ alpha ^{1} \ højre ) x^{4} +2 \ alpha^{-6} x^{5}+2x^{6} \ end {pmatrix}} \\ [6pt] = {} & {\ begin { pmatrix} \ venstre (1+ \ alpha ^{-4} \ højre)+\ venstre (\ alpha ^{1}+\ alpha ^{2} \ højre) x+\ alpha ^{7} x ^{2} & \ alpha ^{7}+\ alpha ^{-3} x \\\ alpha ^{4}+\ alpha ^{-5} x & 1 \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{-7 }+\ alpha ^{4} x+\ alpha ^{-1} x ^{2}+\ alpha ^{6} x ^{3}+\ alpha ^{-1} x ^{4}+\ alpha ^ {5} x ^{5} \\\ alpha ^{-3}+\ alpha ^{-2} x+\ alpha ^{0} x ^{2}+\ alpha ^{-2} x ^{3} +\ alpha ^{-6} x ^{4} \ end {pmatrix}} \\ [6pt] = {} & {\ begin {pmatrix} \ alpha ^{-3}+\ alpha ^{5} x+\ alpha ^{7} x ^{2} & \ alpha ^{7}+\ alpha ^{-3} x \\\ alpha ^{4}+\ alpha ^{-5} x & 1 \ end {pmatrix}} { \ begin {pmatrix} \ alpha ^{-5}+\ alpha ^{-4} x & 1 \\ 1 & 0 \ end {pmatrix}} \\ & \ qquad {\ begin {pmatrix} \ alpha ^{-3}+\ alpha ^{-2} x+\ alpha ^{0} x ^{2}+\ alpha ^{-2} x ^{3}+\ alpha ^{-6} x ^{4} \\\ venstre (\ alpha ^{7}+\ alpha ^{-7} \ right)+\ left (2 \ alpha ^{-7}+\ alpha ^{4} \ right) x+\ left (\ alpha ^{-5}+ \ alpha ^{-6}+\ alpha ^{-1} \ højre) x ^{2}+\ venstre (\ alpha ^{-7}+\ alpha ^{-4}+\ alpha ^{6} \ højre) x ^{3}+\ venstre (\ alpha ^{4}+\ alpha ^{-6}+\ alpha ^{-1} \ højre) x ^{4} +2 \ alpha ^{5} x ^{5} \ end {pmatrix}} \\ [6pt] = {} & {\ begin {pmatrix} \ alpha ^{7} x+\ alpha ^{ 5} x ^{2}+\ alpha ^{3} x ^{3} & \ alpha ^{-3}+\ alpha ^{5} x+\ alpha ^{7} x ^{2} \\\ alpha ^{3}+\ alpha ^{-5} x+\ alpha ^{6} x ^{2} & \ alpha ^{4}+\ alpha ^{-5} x \ end {pmatrix}} {\ begin { pmatrix} \ alpha ^{-3}+\ alpha ^{-2} x+\ alpha ^{0} x ^{2}+\ alpha ^{-2} x ^{3}+\ alpha ^{-6} x ^{4} \\\ alpha ^{-4}+\ alpha ^{4} x+\ alpha ^{2} x ^{2}+\ alpha ^{-5} x ^{3} \ end {pmatrix }}. \ end {align}}}$

Vi har højst nået polynom af grad 3, og som

${\ displaystyle {\ begin {pmatrix}-\ venstre (\ alpha ^{4}+\ alpha ^{-5} x \ right) & \ alpha ^{-3}+\ alpha ^{5} x+\ alpha ^ {7} x ^{2} \\\ alpha ^{3}+\ alpha ^{-5} x+\ alpha ^{6} x ^{2} &-\ venstre (\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3} \ right) \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3} & \ alpha ^{-3}+\ alpha ^{5} x+\ alpha ^{7} x ^{2} \\\ alpha ^{3 }+\ alpha ^{-5} x+\ alpha ^{6} x ^{2} & \ alpha ^{4}+\ alpha ^{-5} x \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 \\ 0 & 1 \ slut {pmatrix}},}$

vi får

${\ displaystyle {\ begin {pmatrix}-\ venstre (\ alpha ^{4}+\ alpha ^{-5} x \ right) & \ alpha ^{-3}+\ alpha ^{5} x+\ alpha ^ {7} x ^{2} \\\ alpha ^{3}+\ alpha ^{-5} x+\ alpha ^{6} x ^{2} &-\ venstre (\ alpha ^{7} x+\ alpha ^{5} x^{2}+\ alpha^{3} x^{3} \ right) \ end {pmatrix}} {\ begin {pmatrix} S (x) \ Gamma (x) \\ x^{ 6} \ end {pmatrix}} = {\ begin {pmatrix} \ alpha ^{-3}+\ alpha ^{-2} x+\ alpha ^{0} x ^{2}+\ alpha ^{-2} x ^{3}+\ alpha ^{-6} x ^{4} \\\ alpha ^{-4}+\ alpha ^{4} x+\ alpha ^{2} x ^{2}+\ alpha ^ {-5} x^{3} \ end {pmatrix}}.}$

Derfor,

${\ displaystyle S (x) \ Gamma (x) \ venstre (\ alpha ^{3}+\ alpha ^{-5} x+\ alpha ^{6} x ^{2} \ right)-\ left (\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3} \ højre) x ^{6} = \ alpha ^{-4}+\ alpha ^{4 } x+\ alfa ^{2} x ^{2}+\ alpha ^{-5} x ^{3}.}$

Lad dig ikke bekymre dig om, at Find ved brutal kraft en rod til Rødderne er og (efter at have fundet for eksempel kan vi dividere med tilsvarende monom, og roden til den resulterende monom kan let findes). ${\ displaystyle \ Lambda (x) = \ alpha ^{3}+\ alpha ^{-5} x+\ alpha ^{6} x ^{2}.}$${\ displaystyle \ lambda _ {0} \ neq 1.}$${\ displaystyle \ Lambda.}$${\ displaystyle \ alpha ^{2},}$${\ displaystyle \ alpha ^{10}}$${\ displaystyle \ alpha ^{2}}$${\ displaystyle \ Lambda}$${\ displaystyle \ venstre (x- \ alpha ^{2} \ højre)}$

Lade

${\ displaystyle {\ begin {justeret} \ Xi (x) & = \ Gamma (x) \ Lambda (x) = \ alpha ^{3}+\ alpha ^{4} x ^{2}+\ alpha ^{ 2} x ^{3}+\ alpha ^{-5} x ^{4} \\\ Omega (x) & = S (x) \ Xi (x) \ equiv \ alpha ^{-4}+\ alpha ^{4} x+\ alpha^{2} x^{2}+\ alpha^{-5} x^{3} {\ bmod {x^{6}}} \ end {justeret}}}$

Lad os se efter fejlværdier ved hjælp af formel

${\ displaystyle e_ {j} =-{\ frac {\ Omega \ left (\ alpha ^{-i_ {j}} \ right)} {\ Xi '\ left (\ alpha ^{-i_ {j}} \ ret)}},}$

hvor er rødderne til Vi kommer ${\ displaystyle \ alpha ^{-i_ {j}}}$${\ displaystyle \ Xi (x).}$ ${\ displaystyle \ Xi '(x) = \ alpha ^{2} x ^{2}.}$

${\ displaystyle {\ begin {align} e_ {1} & =-{\ frac {\ Omega (\ alpha ^{4})} {\ Xi '(\ alpha ^{4})}}} = {\ frac { \ alpha ^{-4}+\ alpha ^{-7}+\ alpha ^{-5}+\ alpha ^{7}} {\ alpha ^{-5}}} = {\ frac {\ alpha ^{ -5}} {\ alpha ^{-5}}} = 1 \\ e_ {2} & =-{\ frac {\ Omega (\ alpha ^{7})} {\ Xi '(\ alpha ^{7 })}} = {\ frac {\ alpha ^{-4}+\ alpha ^{-4}+\ alpha ^{1}+\ alpha ^{1}} {\ alpha ^{1}}} = 0 \\ e_ {3} & =-{\ frac {\ Omega (\ alpha ^{10})} {\ Xi '(\ alpha ^{10})}}} = {\ frac {\ alpha ^{-4} +\ alpha ^{-1}+\ alpha ^{7}+\ alpha ^{-5}} {\ alpha ^{7}}} = {\ frac {\ alpha ^{7}} {\ alpha ^{ 7}}} = 1 \\ e_ {4} & =-{\ frac {\ Omega (\ alpha ^{2})} {\ Xi '(\ alpha ^{2})}} = {\ frac {\ alpha ^{-4}+\ alpha ^{6}+\ alpha ^{6}+\ alpha ^{1}} {\ alpha ^{6}}} = {\ frac {\ alpha ^{6}} { \ alpha ^{6}}} = 1 \ slut {justeret}}}$

Faktum, det burde ikke være overraskende. ${\ displaystyle e_ {3} = e_ {4} = 1,}$

Korrigeret kode er derfor [1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0].

Afkodning med ulæselige tegn med et lille antal fejl

Lad os vise algoritmens adfærd for sagen med et lille antal fejl. Lad det modtagne ord være [1 0 0? 11 1? 0 0 0 1 0 1 0 0].

Igen skal du erstatte de ulæselige tegn med nuller, mens du opretter polynomet, der afspejler deres positioner Beregn syndromerne og Opret syndromspolynom ${\ displaystyle \ Gamma (x) = \ left (\ alpha ^{8} x-1 \ right) \ left (\ alpha ^{11} x-1 \ right).}$${\ displaystyle s_ {1} = \ alpha ^{4}, s_ {2} = \ alpha ^{-7}, s_ {3} = \ alpha ^{1}, s_ {4} = \ alpha ^{1 }, s_ {5} = \ alpha ^{0},}$${\ displaystyle s_ {6} = \ alpha ^{2}.}$

${\ displaystyle {\ begin {align} S (x) & = \ alpha ^{4}+\ alpha ^{-7} x+\ alpha ^{1} x ^{2}+\ alpha ^{1} x ^ {3}+\ alpha ^{0} x ^{4}+\ alpha ^{2} x ^{5}, \\ S (x) \ Gamma (x) & = \ alpha ^{4}+\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3}+\ alpha ^{1} x ^{4}+\ alpha ^{-1} x ^ {5}+\ alpha ^{-1} x ^{6}+\ alpha ^{6} x ^{7}. \ End {align}}}$

Lad os køre den udvidede euklidiske algoritme:

${\ displaystyle {\ begin {align} {\ begin {pmatrix} S (x) \ Gamma (x) \\ x ^{6} \ end {pmatrix}} & = {\ begin {pmatrix} \ alpha ^{4 }+\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3}+\ alpha ^{1} x ^{4}+\ alpha ^{- 1} x^{5}+\ alpha^{-1} x^{6}+\ alpha^{6} x^{7} \\ x^{6} \ end {pmatrix}} \\ & = { \ begin {pmatrix} \ alpha ^{-1}+\ alpha ^{6} x & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} x ^{6} \\\ alpha ^{4}+\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3}+\ alpha ^{1} x ^{4}+\ alpha ^{-1} x ^{5} +2 \ alpha ^{-1} x ^{6} +2 \ alpha ^{6} x ^{7} \ end {pmatrix}} \\ & = {\ begin {pmatrix} \ alpha ^ {-1}+\ alpha ^{6} x & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{3}+\ alpha ^{1} x & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{4}+\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^{3}+\ alpha ^{1} x ^{4}+\ alpha ^{-1} x ^{5} \\\ alpha ^{7}+\ venstre (\ alpha ^{-5}+\ alpha ^{5} \ højre) x+2 \ alpha ^{-7} x ^{2} +2 \ alpha ^{6} x ^{3} +2 \ alpha ^{4} x ^{4} +2 \ alpha ^{2} x ^{5 }+2x ^{6} \ end {pmatrix}} \\ & = {\ begin {pmatrix} \ venstre (1+ \ alpha ^{2} \ højre)+\ venstre (\ alpha ^{0}+\ alpha ^{-6} \ højre) x+\ alpha ^{7} x ^{2} & \ alpha ^{-1}+\ alpha ^{6} x \\\ alpha ^{3}+\ alpha ^{1} x & 1 \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{4}+\ alpha ^{7} x+\ alpha ^{5} x ^{2}+ \ alpha ^{3} x ^{3}+\ alpha ^{1} x ^{4}+\ alpha ^{-1} x ^{5} \\\ alpha ^{7}+\ alpha ^{0 } x \ end {pmatrix}} \ end {align}}}$

Vi har højst nået polynom af grad 3, og som

${\ displaystyle {\ begin {pmatrix} -1 & \ alpha ^{-1}+\ alpha ^{6} x \\\ alpha ^{3}+\ alpha ^{1} x &-\ left (\ alpha ^{ -7}+\ alpha ^{7} x+\ alpha ^{7} x ^{2} \ right) \ end {pmatrix}} {\ begin {pmatrix} \ alpha ^{-7}+\ alpha ^{7 } x+\ alpha ^{7} x ^{2} & \ alpha ^{-1}+\ alpha ^{6} x \\\ alpha ^{3}+\ alpha ^{1} x & 1 \ end {pmatrix} } = {\ begin {pmatrix} 1 & 0 \\ 0 & 1 \ end {pmatrix}},}$

vi får

${\ displaystyle {\ begin {pmatrix} -1 & \ alpha ^{-1}+\ alpha ^{6} x \\\ alpha ^{3}+\ alpha ^{1} x &-\ left (\ alpha ^{ -7}+\ alpha ^{7} x+\ alpha ^{7} x ^{2} \ right) \ end {pmatrix}} {\ begin {pmatrix} S (x) \ Gamma (x) \\ x ^ {6} \ end {pmatrix}} = {\ begin {pmatrix} \ alpha ^{4}+\ alpha ^{7} x+\ alpha ^{5} x ^{2}+\ alpha ^{3} x ^ {3}+\ alpha ^{1} x ^{4}+\ alpha ^{-1} x ^{5} \\\ alpha ^{7}+\ alpha ^{0} x \ end {pmatrix}} .}$

Derfor,

${\ displaystyle S (x) \ Gamma (x) \ venstre (\ alpha ^{3}+\ alpha ^{1} x \ right)-\ left (\ alpha ^{-7}+\ alpha ^{7} x+\ alpha ^{7} x ^{2} \ right) x ^{6} = \ alpha ^{7}+\ alpha ^{0} x.}$

Lad dig ikke bekymre dig om, at roden til er${\ displaystyle \ Lambda (x) = \ alpha ^{3}+\ alpha ^{1} x.}$${\ displaystyle \ lambda _ {0} \ neq 1.}$${\ displaystyle \ Lambda (x)}$${\ displaystyle \ alpha ^{3-1}.}$

Lade

${\ displaystyle {\ begin {justeret} \ Xi (x) & = \ Gamma (x) \ Lambda (x) = \ alpha ^{3}+\ alpha ^{-7} x+\ alpha ^{-4} x ^{2}+\ alpha ^{5} x ^{3}, \\\ Omega (x) & = S (x) \ Xi (x) \ equiv \ alpha ^{7}+\ alpha ^{0} x {\ bmod {x^{6}}} \ end {justeret}}}$

Lad os lede efter fejlværdier ved hjælp af formel, hvor er polynomets rødder${\ displaystyle e_ {j} =-\ Omega \ venstre (\ alpha ^{-i_ {j}} \ højre)/\ Xi '\ venstre (\ alpha ^{-i_ {j}} \ højre),}$${\ displaystyle \ alpha ^{-i_ {j}}}$${\ displaystyle \ Xi (x).}$

${\ displaystyle \ Xi '(x) = \ alpha ^{-7}+\ alpha ^{5} x ^{2}.}$

Vi får

${\ displaystyle {\ begin {align} e_ {1} & =-{\ frac {\ Omega \ left (\ alpha ^{4} \ right)} {\ Xi '\ left (\ alpha ^{4} \ right )}} = {\ frac {\ alpha ^{7}+\ alpha ^{4}} {\ alpha ^{-7}+\ alpha ^{-2}}} = {\ frac {\ alpha ^{3 }} {\ alpha ^{3}}} = 1 \\ e_ {2} & =-{\ frac {\ Omega \ venstre (\ alpha ^{7} \ højre)} {\ Xi '\ venstre (\ alpha ^{7} \ right)}} = {\ frac {\ alpha ^{7}+\ alpha ^{7}} {\ alpha ^{-7}+\ alpha ^{4}}} = 0 \\ e_ {3} & =-{\ frac {\ Omega \ left (\ alpha ^{2} \ right)} {\ Xi '\ left (\ alpha ^{2} \ right)}} = {\ frac {\ alpha ^{7}+\ alpha ^{2}} {\ alpha ^{-7}+\ alpha ^{-6}}} = {\ frac {\ alpha ^{-3}} {\ alpha ^{-3 }}} = 1 \ slut {justeret}}}$

Det skulle ikke være overraskende. ${\ displaystyle e_ {3} = 1}$

Korrigeret kode er derfor [1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0].

Citater

Referencer

Primære kilder

• Hocquenghem, A. (september 1959), "Codes correcteurs d'erreurs", Chiffres (på fransk), Paris, 2 : 147–156
• Bose, RC ; Ray-Chaudhuri, DK (marts 1960), "On A Class of Error Correcting Binary Group Codes" (PDF) , Information and Control , 3 (1): 68–79, doi : 10.1016/s0019-9958 (60) 90287- 4 , ISSN  0890-5401

Sekundære kilder

• Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, s. 42–45 , hentet 21. april 2010Kursusnotater bliver tilsyneladende lavet om i 2012: http://www.stanford.edu/class/ee387/
• Gorenstein, Daniel ; Peterson, W. Wesley ; Zierler, Neal (1960), "Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect", Information and Control , 3 (3): 291–294, doi : 10.1016/s0019-9958 (60) 90877-9
• Lidl, Rudolf; Pilz, Günter (1999), Applied Abstract Algebra (2. udgave), John Wiley
• Reed, Irving S .; Chen, Xuemin (1999), Error-Control Coding for Data Networks , Boston, MA: Kluwer Academic Publishers , ISBN 0-7923-8528-4

Yderligere læsning

• Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (2. udgave), Cambridge University Press , ISBN 0-521-55374-1
• Gilbert, WJ; Nicholson, WK (2004), Modern Algebra with Applications (2. udgave), John Wiley
• Lin, S .; Costello, D. (2004), Error Control Coding: Fundamentals and Applications , Englewood Cliffs, NJ: Prentice-Hall
• MacWilliams, FJ; Sloane, NJA (1977), Theory of Error-Correcting Codes , New York, NY: North-Holland Publishing Company
• Rudra, Atri, CSE 545, Fejlrettelseskoder: Combinatorics, Algorithms and Applications , University at Buffalo, arkiveret fra originalen 2010-07-02 , hentet 21. april 2010