Reed-Solomon kode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. december 2021; checks kræver 3 redigeringer .

Reed-Solomon kode
Opkaldt efter	Irving Reed [d] og Gustav Solomon [d]
Type	lineær blokkode polynomisk kode adskillelig kode med maksimal afstand
Blok længde	$n$
Beskedens længde	$k$
Afstand	$n-k+1$
Alfabet størrelse	$q=p^{m}\geqslant n$ for simpelt , ofte $s$ $q=n+1$
Betegnelse	${\displaystyle [n,k,n-k+1]_{q))$
Mediefiler på Wikimedia Commons

Reed -Solomon-koder ( eng. Reed-Solomon-koder ) er ikke-binære cykliske koder , der giver dig mulighed for at rette fejl i datablokke. Kodevektorens elementer er ikke bit, men grupper af bit (blokke). Reed-Solomon-koder er meget almindelige, der arbejder med bytes (oktetter).

Reed-Solomon-koden er et specialtilfælde af BCH-koden .

Det er i øjeblikket meget udbredt i datagendannelsessystemer fra cd'er , ved oprettelse af arkiver med information til gendannelse i tilfælde af skade, i støjkorrigerende kodning .

Historie

Solomon-koden blev opfundet i 1960 af Reid og Gustav Solomon Laboratory ved Massachusetts Institute of Ideen om at bruge denne kode blev præsenteret i artiklen "Polynomiale koder over visse endelige felter". Effektive afkodningsalgoritmer blev foreslået i 1969 af Alvin Berlekamp og James Massey ( Berlekamp-Massey algorithm ) og i 1977 af David Mandelbaum (metode ved hjælp af Euklid-algoritmen [1] ). Den første brug af Reed-Solomon-koden var i 1982 i serieproduktionen af cd'er.

Formel beskrivelse

Reed-Solomon-koder er et vigtigt specialtilfælde af en BCH-kode, hvis generatorpolynomiske rødder ligger i det samme felt , som koden er bygget over ( ). Lad være et element i ordensområdet . Hvis er et primitivt element, så er dets rækkefølge , dvs. Så er det normaliserede polynomium af minimumsgrad over feltet, hvis rødder er konsekutive potenser af elementet , det genererende polynomium af Reed-Solomon-koden over feltet : $m=1$ $\alfa$ $\tekststil GF(q)$ $\tekststil n$ $\alfa$ $q-1$ $\alpha ^{{q-1}}=1,\quad \alpha ^{i}\neq 1,0<i<q-1$ $g(x)$ $\tekststil GF(q)$ $d-1$ $\alpha ^{{l_{0}}},\alpha ^{{l_{0}+1}},...,\alpha ^{{l_{0}+d-2}}$ $\alfa$ $\tekststil GF(q)$

g(x)=(x-\alpha ^{l_{0)))(x-\alpha ^{l_{0}+1})\dots (x-\alpha ^{l_{0}+ d-2}),

hvor er et eller andet heltal (inklusive 0 og 1), ved hjælp af hvilket det nogle gange er muligt at forenkle indkoderen. Normalt skal det . Graden af polynomiet er . $l_{0}$ $l_{0}=1$ $\tekststil g(x)$ $d-1$

Længden af den resulterende kode , minimumsafstanden (er minimum af alle Hamming-afstande for alle par kodeord, se linjekode ). Koden indeholder check-symboler, hvor betegner graden af polynomiet; antal informationssymboler . Reed-Solomon-koden er således også en adskillelig kode med en maksimal afstand (den er optimal i betydningen Singleton bound ). $n$ $d$ $r=d-1=\deg(g(x))$ $\grader()$ $k=nr=n-d+1$ $\tekststil d=n-k+1$

Kodepolynomiet kan fås fra informationspolynomiet , , ved at multiplicere og : $c(x)$ $m(x)$ $\deg m(x)\leqslant k-1$ $m(x)$ $g(x)$

c(x)=m(x)g(x).

Egenskaber

Reed-Solomon-koden over , som retter fejl, kræver paritetssymboler og kan bruges til at rette vilkårlige fejlpakker af længde eller mindre. Ifølge Reiger-grænsesætningen er Reed-Solomon-koder optimale i forhold til forholdet mellem pakkelængden og muligheden for fejlkorrektion - ved hjælp af yderligere check-symboler korrigeres fejl (og færre). $\tekststil GF(q^{m})$ $t$ $2t$ $t$ $2t$ $t$

Sætning (Reiger bundet) . Hver lineær blokkode, der korrigerer alle bursts af længde eller mindre, skal mindst indeholde paritetssymboler. $t$ $2t$

En kode dual til en Reed-Solomon-kode er også en Reed-Solomon-kode. Den dobbelte kode for en cyklisk kode er den kode, der genereres af dens kontrolpolynomium.

En matrix genererer en Reed-Solomon-kode, hvis og kun hvis en mindre af matrixen ikke er nul. $G=[{\begin{array}{cc}I_{{k*k}}&P_{{k*(nk)}}\\\end{array}}]$ $P_{{k*(nk)}}$

Når man punkterer eller forkorter Reed-Solomon-koden, opnås Reed-Solomon-koden igen. Punktering er en operation, der fjerner ét afkrydsningstegn. Kodelængden reduceres med én, dimensionen bevares. Kodeafstanden skal mindskes med én, ellers ville det slettede tegn være ubrugeligt. Forkortning - vi fikserer en vilkårlig kodesøjle og vælger kun de vektorer, der indeholder 0 i denne kolonne. Dette sæt vektorer danner et underrum . $n$ $k$ $d$ $(n,k,d)$

Flere fejlrettelser

Reed-Solomon-koden er en af de mest kraftfulde koder til at korrigere flere fejludbrud. Det bruges i kanaler, hvor udbrud af fejl kan forekomme så hyppigt, at de ikke længere kan rettes ved hjælp af koder, der retter enkeltfejl.

En Reed-Solomon over-felt- kode med en kodeafstand kan opfattes som en -field-over-field- kode , der kan rette enhver kombination af fejl koncentreret i eller færre blokke af m tegn. Det største antal blokke af længde , der kan blive påvirket af en pakke af længde , hvor , ikke overstiger , så kode, der kan rette fejlblokke, kan altid rette enhver kombination af pakker af total længde, hvis . $(q^{m}-1,q^{m}-1-2t)$ $\tekststil GF(q^{m})$ $d=2t+1$ $((q^{m}-1)m,(q^{m}-1-2t)m)$ $\tekststil GF(q)$ $t$ $m$ $l_{i}$ $l_{i}\leqslant mt_{i}-(m-1)$ $t_{i}$ $t$ $s$ $l$ $l+(m-1)\leqslant mt$

Praktisk implementering

Reed-Solomon-kodning kan implementeres på to måder: systematisk og ikke-systematisk (se [1] for en beskrivelse af indkoderen).

Med ikke-systematisk kodning ganges informationsordet med et eller andet irreducerbart polynomium i Galois-feltet. Det resulterende kodede ord er helt anderledes end det originale, og for at udtrække informationsordet skal du udføre en afkodningsoperation, og først derefter kan du kontrollere dataene for fejl. Sådan kodning kræver kun mange ressourcer til at udtrække informationsdata, mens de kan være fejlfrie.

Ved systematisk kodning tildeles kontrolsymboler til en informationsblok af symboler; ved beregning af hvert kontrolsymbol bruges alle symboler i den oprindelige blok. I dette tilfælde er der ingen overhead ved udtrækning af den oprindelige blok, hvis informationsordet ikke indeholder fejl, men koderen/dekoderen skal udføre additions- og multiplikationsoperationer for at generere paritetssymboler. Da alle operationer udføres i Galois-feltet, kræver selve indkodnings-/afkodningsoperationerne mange ressourcer og tid. En hurtig afkodningsalgoritme baseret på Fast Fourier Transform kører i en tid af størrelsesordenen . $k$ $2t$ $k$ $k(nk)$ $O(ln^{2}{n})$

Kodning

Under indkodningsoperationen multipliceres informationspolynomiet med det genererende polynomium. Multiplikation af det oprindelige længdeord med et irreducerbart polynomium i systematisk kodning kan udføres som følger: $S$ $k$

Nuller føjes til det oprindelige ord , hvilket resulterer i et polynomium . $2t$ $\textstyle T=Sx^{{2t}}$
Dette polynomium divideres med det genererende polynomium , resten findes , , hvor er kvotienten. $G$ $R$ $\textstyle Sx^{{2t}}=QG+R$ $Q$
Denne rest vil være Reed-Solomon-korrektionskoden, den er tildelt den oprindelige blok af tegn. Modtaget kodeord . $\textstyle C=Sx^{{2t}}+R$

Encoderen er bygget af skifteregistre, addere og multiplikatorer. Skifteregisteret består af hukommelsesceller, som hver indeholder ét element i Galois-feltet.

Der er en anden kodningsprocedure (mere praktisk og enklere) . Lade være et primitivt element i feltet , og lad være en vektor af informationssymboler, og dermed et informationspolynomium. Så er vektoren Reed-Solomon-kodevektoren svarende til informationsvektoren . Denne kodningsmetode viser, at for PC-koden er det slet ikke nødvendigt at kende det genererende polynomium og kodens genererende matrix, det er nok at kende udvidelsen af feltet i form af det primitive element og kodens dimension (længden af koden er i dette tilfælde defineret som ). Sagen er, at det genererende polynomium og kodeafstanden er fuldstændig skjult bag forskellen. $a_{{i}}\i GF(q),(i=1,2,\ldots ,k-1),\alpha \i GF(q)$ $GF(q)$ $a=(a_{0},a_{1},\ldots,a_{{k-1}})$ $a(x)=a_{0}+a_{{1}}x+\ldots +a_{{k-1}}x^{{k-1}}$ $u=(a(1),a(\alpha ),\ldots ,a(\alpha ^{{q-2}}))$ $-en$ $GF(q)$ $\alfa$ $k$ $n=q-1$ $nk$ $g(x)$

Afkodning

Dekoderen, der arbejder i henhold til den autoregressive spektrale afkodningsmetode, udfører sekventielt følgende handlinger:

Beregner fejlsyndrom
Opbygger et fejlpolynomium
Finder rødderne af det givne polynomium
Specificerer arten af fejlen
Retter fejl

Beregning af fejlsyndrom

Beregningen af fejlsyndromet udføres af syndromdekoderen, som opdeler kodeordet i et generatorpolynomium. Hvis der er en rest under division, så er der en fejl i ordet. Resten af delingen er fejlsyndromet.

Konstruktion af fejlpolynomiet

Det beregnede fejlsyndrom angiver ikke fejlens position. Graden af syndrompolynomiet er , hvilket er meget mindre end graden af kodeordet . For at opnå en overensstemmelse mellem en fejl og dens position i meddelelsen konstrueres et fejlpolynomium. Fejlpolynomiet implementeres ved hjælp af Berlekamp-Massey- algoritmen eller ved hjælp af Euclid-algoritmen. Euclids algoritme har en simpel implementering, men er ressourcekrævende. Derfor bruges den mere komplekse, men mindre omkostningskrævende, Berlekamp-Massey-algoritme oftere. Koefficienterne for det fundne polynomium svarer direkte til koefficienterne for de fejlagtige symboler i kodeordet. $2t$ $n$

Find rødder

På dette trin søges der efter rødderne af fejlpolynomiet, som bestemmer placeringen af de forvrængede symboler i kodeordet. Det implementeres ved hjælp af Chens procedure, som svarer til udtømmende opregning. Alle mulige værdier substitueres sekventielt i fejlpolynomiet, når polynomiet forsvinder, findes rødderne.

Bestemmelse af fejlens art og dens rettelse

Baseret på fejlsyndromet og de fundne polynomiale rødder bestemmes fejlens art ved hjælp af Forney-algoritmen, og der bygges en maske af forvrængede symboler. For RS-koder er der dog en nemmere måde at finde fejlens art. Som vist i [2] for RS-koder med et vilkårligt sæt af på hinanden følgende nuller : $2t_{d}$ $\alpha ^{b},\alpha ^{{b+1}},\ldots ,\alpha ^{{b+\delta }},\delta =2t_{d}-1$

$e_{j_{l))={\frac {(\alpha ^{j_{l)))^{2-b}\Lambda (\alpha ^{-j_{l)))}{\sigma '(\alpha ^{-j_{l}})}},\quad \quad \quad (*)$

hvor er den formelle afledte med hensyn til fejlfinderpolynomiet , og $\sigma '(x)$ $x$ $\sigma (x)$ $\Lambda (x)=\sigma (x)S(x)\mod x^{2t_{d}+1}.$

Yderligere, efter at masken er fundet, overlejres den på kodeordet ved hjælp af XOR -operationen, og de forvrængede tegn gendannes. Derefter kasseres kontroltegnene, og det gendannede informationsord opnås.

Sudans algoritme

På dette tidspunkt er fundamentalt nye afkodningsmetoder blevet anvendt, for eksempel den algoritme, der blev foreslået i 1997 af Madhu Sudan [3] .

Udvidelse af RS-koder

RS-kodeforlængelse er en procedure, hvor kodens længde og afstand øges (mens koden stadig er på Singleton-grænsen , og kodealfabetet ikke ændres), og antallet af informationssymboler i koden ikke ændres [4] . Denne procedure øger kodens korrigerende evne . Overvej at forlænge RS-koden med ét symbol. Lade være en RS-kodevektor, hvis genererende polynomium er . Lad nu . Lad os vise, at tilføjelse af et symbol til vektoren vil øge dens vægt til , hvis . Polynomiet svarende til kodevektoren kan skrives som , men under hensyntagen til udtrykket for , får vi . , da 1 ikke hører til listen over rødder for det genererende polynomium. Men også , da i dette tilfælde , hvilket ville øge afstanden til koden i modsætning til betingelsen, betyder det, at kodens vægt er steget, på grund af tilføjelsen af et nyt tegn . Nye kodeparametre , forlænget vektor . Kontrolmatrixen for en ikke-strakt kode har formen $\upsilon =(c_{0},c_{1},\ldots ,c_{{q-2}})$ $g(x)=(x-\alpha )(x-\alpha ^{2})\ldots (x-\alpha ^{{d-1}}),\deg g(x)=d-1=r =nk,n=q-1$ $c_{{q-1}}=-\sum _{{i=1}}^{{q-2}}c_{{i}}$ $\upsilon$ $c_{{q-1}}$ $d+1$ $c_{{q-1}}\neq 0$ $\upsilon(x)=g(x)*z(x)$ $c_{{q-1}}$ $\upsilon(1)=g(1)z(1)=-c_{{q-1}}$ $g(1)\neq 0$ $z(1)\neq 0$ $(x-1)g(x)|\upsilon (x)$ $c_{{q-1}}\neq 0$ $c_{{q-1}}$ $n_{1}=n+1,k_{1}=k,d_{1}=d+1$ $v_{1}=(c_{0},c_{1},\ldots ,c_{q-2},c_{q-1})$

H={\begin{Vmatrix}1&\alpha &\alpha ^{2}&\cdots &\alpha ^{{q-2}}\\1&\alpha ^{2}&\alpha ^{4}&\ cdots &\alpha ^{{2(q-2)}}\\\cdots &\cdots &\cdots &\cdots &\cdots \\1&\alpha ^{{d-1}}&\alpha ^{{ 2(d-1)}}&\cdots &\alpha ^{{(d-1)(q-2)}}\end{Vmatrix}}

Så vil tjekmatrixen udvidet med ét symbol af pc-koden være

H_{1}={\begin{Vmatrix}1&1&1&\cdots &1&1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{{q-2}}&0\\1&\alpha ^{2 }&\alpha ^{4}&\cdots &\alpha ^{{2(q-2)}}&0\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\1&\alpha ^{{d-1}}&\alpha ^{{2(d-1)}}&\cdots &\alpha ^{{(d-1)(q-2)}}&0\end{Vmatrix}}

Ansøgning

Umiddelbart efter fremkomsten (60'erne af det XX århundrede) begyndte Reed-Solomon-koder at blive brugt som eksterne koder i kaskadestrukturer, der blev brugt i satellitkommunikation. I sådanne konstruktioner er de -th PC-symboler (der kan være flere af dem) kodet af interne foldningskoder . I den modtagende ende afkodes disse symboler med en blød Viterbi-algoritme (effektiv i AWGN -kanaler ). En sådan dekoder vil rette enkelte fejl i q-ary-symboler, men når burst-fejl opstår, og nogle pakker af q-ary-symboler er dekodet forkert, så vil den eksterne Reed-Solomon-dekoder rette bursts af disse fejl. Dermed vil den nødvendige pålidelighed af informationstransmission blive opnået ( [5] ). $q$

I øjeblikket har Reed-Solomon-koder et meget bredt anvendelsesområde på grund af deres evne til at finde og rette flere fejludbrud.

Registrering og lagring af information

Reed-Solomon-koden bruges ved skrivning og læsning i RAM-controllere, ved arkivering af data, skrivning af information til harddiske ( ECC ), skrivning til CD/DVD-diske. Selvom en betydelig mængde information er beskadiget, er flere sektorer af diskmediet beskadiget, så giver Reed-Solomon-koder dig mulighed for at gendanne det meste af den tabte information. Bruges også ved skrivning til medier såsom magnetbånd og stregkoder.

Brænder til cd-rom

Mulige fejl ved læsning fra en disk vises allerede på diskproduktionsstadiet, da det er umuligt at lave en ideel disk med moderne teknologier. Fejl kan også være forårsaget af ridser på diskens overflade, støv osv. Når man laver en læsbar cd, bruges CIRC-korrektionssystemet (Cross Interleaved Reed Solomon Code). Denne korrektion er implementeret i alle enheder, der tillader læsning af data fra cd'er i form af en chip med firmware. Fejldetektering og korrektion er baseret på redundans og interleaving . Redundans - cirka 25% af den oprindelige information.

Optagelse til lyd-cd'er bruger Red Book- standarden . Fejlretning sker på to niveauer, C1 og C2. Ved indkodning i det første trin tilføjes kontrolsymboler til de originale data, i det andet trin kodes informationen igen. Ud over kodning er bytes også interleaved ( interleaved ), så fejlblokke under korrektion brydes op i separate bits, der er nemmere at rette. På det første niveau bliver fejlagtige blokke på en og to bytes lange (henholdsvis et og to fejlagtige tegn) detekteret og rettet. Fejlblokke på tre bytes detekteres og sendes til næste lag. På det andet niveau detekteres og korrigeres 1 og 2 byte fejlblokke, der stammer fra C2. Detekteringen af tre fejlagtige tegn er en fatal fejl og kan ikke rettes.

Trådløs og mobil kommunikation

Denne kodningsalgoritme bruges i datatransmission over WiMAX -netværk , i optiske kommunikationslinjer , i satellit- og radiorelækommunikation . Metoden Forward Error Correction (FEC) er baseret på Reed-Solomon-koder.

Kodningseksempler

Hexadecimal (15,11) Reed-Solomon-kode

Lad . Derefter $t=2,l_{0}=1$

$g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)=x^4+\alpha^{13}x^3+ \alpha^{6}x^2+\alpha^{3}x+\alpha^{10}.$

Graden er 4, og . Hvert feltelement kan kortlægges til 4 bit. Informationspolynomiet er en sekvens på 11 tegn fra , hvilket svarer til 44 bit, og hele kodeordet er et sæt på 60 bit. $g(x)$ $nk=4$ $k=11$ ${\mathrm {GF}}(16)$ ${\mathrm {GF}}(16)$

8-ær (7,3) Reed-Solomon kode

Lad . Derefter $t=2,l_{0}=4$

$g(x)=(x-\alpha ^{4})(x-\alpha ^{5})(x-\alpha ^{6})(x-\alpha ^{0})=x ^{4}+\alpha ^{6}x^{3}+\alpha ^{6}x^{2}+\alpha ^{3}x+\alpha .$

Lad informationspolynomiet have formen:

$m(x)=\alpha ^{4}x^{2}+x+\alpha ^{3}.$

Kodeordet for en ikke-systematisk kode vil blive skrevet som:

$c(x)=m(x)g(x)=(\alpha ^{4}x^{2}+x+\alpha ^{3})(x^{4}+\alpha ^{6 }x^{3}+\alpha ^{6}x^{2}+\alpha ^{3}x+\alpha )=\alpha ^{4}x^{6}+\alpha x^{5}+ \alpha ^{6}x^{4}+0x^{3}+0x^{2}+\alpha ^{5}x+\alpha ^{4},$

som er en sekvens af syv oktale tegn.

En alternativ indkodningsmetode for den 9-årige (8,4) Reed-Solomon-kode

Lad os konstruere Galois-feltet modulo polynomiet . Lad dens rod, så , felttabellen ser sådan ud: $GF(3^{2})$ $x^{2}+x+2$ $\alfa$ $\alpha ^{2}+\alpha +2=0$

0=0=(00),

\alpha ^{0}=1=(10),

\alpha ^{1}=\alpha =(01),

\alpha ^{2}=1+2\alpha =(12),

\alpha ^{3}=2+2\alpha =(22),

\alpha ^{4}=2=(20),

\alpha ^{5}=2\alpha =(02),

\alpha ^{6}=2+\alpha =(21),

\alpha ^{7}=1+\alpha =(11).

Lad informationspolynomiet , og lav derefter de tilsvarende beregninger på det konstruerede felt, får vi: ${\displaystyle a(x)=1+\alpha x+\alpha ^{2}x^{2}+\alpha ^{3}x^{3))$ $a(1)=\alpha ^{2},\ a(\alpha )=0,\ a(\alpha ^{2})=\alpha ^{6},\ a(\alpha ^{3} })=0,\ a(\alpha ^{4})=\alpha ^{5},\ a(\alpha ^{5})=0,\ a(\alpha ^{6})=\alpha ^ {7},\ a(\alpha ^{7})=1.$

Som et resultat blev en RS-kodevektor med parametre konstrueret . Dette fuldender kodningen. Bemærk, at med denne metode behøvede vi ikke et genererende kodepolynomium [4] . $n=8,\ k=4,\ d=5$

Afkodningseksempler

Lad feltet være genereret af et primitivt element, hvis irreducible polynomium er . Så . Lad . Så er det genererende polynomium af PC-koden lig med . Lad nu polynomiet blive accepteret . Så . Derefter opnås nøglesystemet af ligninger i formen: $GF(2^{3})$ $p(x)=x^{3}+x+1$ $p(\alpha )=\alpha ^{3}+\alpha +1=0$ $b=0,\t_{d}=2$ $g(x)=(x+1)(x+\alpha )(x+\alpha ^{2})(x+\alpha ^{3})=x^{4}+\alpha ^{2}x ^{3}+\alpha ^{5}x^{2}+\alpha ^{5}x+\alpha ^{6}$ $r(x)=\alpha x^{2}+\alpha ^{5}x^{4}$ $S_{1}=r(1)=\alpha +\alpha ^{5}=\alpha ^{6},\ S_{2}=r(\alpha )=\alpha ^{5},\ S_{3}=\alpha ,\ S_{4}=\alpha$

${\begin{pmatrix}\alpha ^{6}&\alpha ^{5}\\\alpha ^{5}&\alpha \end{pmatrix)){\begin{pmatrix}\sigma _{2 }\\\sigma _{1}\end{pmatrix}}={\begin{pmatrix}\alpha \\\alpha \end{pmatrix}}.$

Overvej nu den euklidiske algoritme til løsning af dette ligningssystem.

Oprindelige forhold :

r_{0}(x)=x^{5},\ r1(x)=S(x)=1+\alpha ^{6}x+\alpha ^{5}x^{2}+\ alpha x^{3}+\alpha x^{4},

b_{0}(x)=0,\ b_{1}(x)=1;

$i=2$

x^{5}=(1+\alpha ^{6}x+\alpha ^{5}x^{2}+\alpha x^{3}+\alpha x^{4})(\alpha ^{6}x+\alpha ^{6})+\alpha ^{5}x+x^{2}+\alpha x+\alpha ^{6},

r_{2}(x)=\alpha ^{5}x^{3}+x^{2}+\alpha x+\alpha ^{6},

q_{2}(x)=\alpha ^{6}x+\alpha ^{6},

b_{2}(x)=0+(\alpha ^{6}x+\alpha ^{6})(1)=\alpha ^{6}x+\alpha ^{6};

$i=3$

$1+\alpha ^{6}x+\alpha ^{5}x^{2}+\alpha x^{3}+\alpha x^{4}=(\alpha ^{5}x^{ 3}+x^{2}+\alpha x+\alpha ^{6})(\alpha ^{3}x+\alpha ^{2})+\alpha ^{6}x^{2}+\alpha x+ \alpha ^{3},$

$\quad \quad ~r_{3}(x)=\alpha ^{6}x^{2}+\alpha x+\alpha ^{3},$

$\quad \quad ~q_{3}(x)=\alpha ^{3}x+\alpha ^{2},$

$\quad \quad ~b_{3}(x)=1+(\alpha ^{3}x+\alpha ^{2})(\alpha ^{6}x+\alpha ^{6})=\ alfa ^{3}+\alpha ^{4}x+\alpha ^{2}x^{2}.$

Algoritmen stopper fordi , derfor følger det ${\displaystyle \deg[r_{3}(x)]=2=t_{d))$ $\sigma (x)=\alpha ^{3}+\alpha ^{4}x+\alpha ^{2}x^{2}.$

Yderligere giver en komplet søgning ved hjælp af Cheney-algoritmen os placeringen af fejlene, dette er . Så ved formlen får vi det $j_{1}=2,\quad j_{2}=4$ $(*)$ $e_{2}=\alpha ,\ e_{4}=\alpha .$

Altså den afkodede vektor . Afkodning afsluttet, to fejl rettet [6] . $c(x)=r(x)+e(x)=0$

Ansøgning

Reed-Solomon-koden bruges i nogle lagringsapplikationer såsom RAID 6 ;

Se også

Noter

↑ Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse / pr. fra engelsk. V. B. Afanasiev . - M . : Technosfera, 2006. - S. 92-93. — (kommunikationens verden). - 2000 eksemplarer. — ISBN 5-94836-035-0 .
↑ Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse / pr. fra engelsk. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 s. — (kommunikationens verden). - 2000 eksemplarer. — ISBN 5-94836-035-0 .
↑ Sudans algoritme . Hentet 24. december 2018. Arkiveret fra originalen 24. december 2018. (ubestemt)
↑ 1 2 Sagalovich, 2007 , s. 212-213.
↑ M. Werner. Grundlæggende om kodning. - Technosphere, 2004. - S. 268-269. — ISBN 5-94836-019-9 .
↑ Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse / pr. fra engelsk. V. B. Afanasiev . - M . : Technosfera, 2006. - S. 116-119. — (kommunikationens verden). - 2000 eksemplarer. — ISBN 5-94836-035-0 .

Litteratur

Peterson W, Weldon E. Fejlretningskoder . - M . : Mir, 1976. - S. 596 .
Blahut R. Teori og praksis for fejlkontrolkoder. — M .: Mir , 1986. — 576 s.
Berlekamp E. Algebraisk kodningsteori = Algebraisk kodningsteori. - M . : Mir, 1971. - S. 478 .
Egorov S.I. Fejlrettelse i informationskanaler på computerperifere enheder. - Kursk: KurskGTU, 2008. - S. 252.
Sagalovich Yu. L. Introduktion til algebraiske koder - M. : MIPT , 2007. - 262 s. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse / pr. fra engelsk. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 s. — (kommunikationens verden). - 2000 eksemplarer. — ISBN 5-94836-035-0 .
M. Werner. Grundlæggende om kodning. - Technosphere, 2004. - 288 s. — ISBN 5-94836-019-9 .

Reed-Solomon kode

Historie

Formel beskrivelse

Egenskaber

Flere fejlrettelser

Praktisk implementering

Kodning

Afkodning

Udvidelse af RS-koder

Ansøgning

Registrering og lagring af information

Trådløs og mobil kommunikation

Kodningseksempler

Hexadecimal (15,11) Reed-Solomon-kode

8-ær (7,3) Reed-Solomon kode

En alternativ indkodningsmetode for den 9-årige (8,4) Reed-Solomon-kode

Afkodningseksempler

Ansøgning

Se også

Noter

Litteratur

Links