Reed-Solomon Code

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 december 2021; kontroller kräver 3 redigeringar .

Reed-Solomon Code
Döpt efter	Irving Reed [d] och Gustav Solomon [d]
Sorts	linjär blockkod polynomkod separerbar kod med maximalt avstånd
Blocklängd	$n$
Meddelandets längd	$k$
Distans	$n-k+1$
Alfabetets storlek	$q=p^{m}\geqslant n$ för enkelt , ofta $sid$ $q=n+1$
Beteckning	${\displaystyle [n,k,n-k+1]_{q))$
Mediafiler på Wikimedia Commons

Reed -Solomon-koder ( eng. Reed-Solomon-koder ) är icke-binära cykliska koder som låter dig korrigera fel i datablock. Elementen i kodvektorn är inte bitar, utan grupper av bitar (block). Reed-Solomon-koder är mycket vanliga och arbetar med bytes (oktetter).

Reed-Solomon-koden är ett specialfall av BCH-koden .

Det används för närvarande flitigt i dataåterställningssystem från CD- skivor , när man skapar arkiv med information för återställning vid skada, vid bruskorrigerande kodning .

Historik

-Solomon-koden uppfanns 1960 av Reid och Gustav Solomon Laboratory vid Massachusetts Institute of Idén att använda denna kod presenterades i artikeln "Polynomiala koder över vissa ändliga fält". Effektiva avkodningsalgoritmer föreslogs 1969 av Alvin Berlekamp och James Massey ( Berlekamp-Massey algorithm ) och 1977 av David Mandelbaum (metod som använder euklidalgoritmen [1] ). Den första användningen av Reed-Solomon-koden var 1982 i serieproduktionen av CD-skivor.

Formell beskrivning

Reed-Solomon-koder är ett viktigt specialfall av en BCH -kod vars generatorpolynomrötter ligger i samma fält som koden är uppbyggd över ( ). Låt vara en del av ordningsområdet . Om är ett primitivt element, då är dess ordning , det vill säga . Sedan är det normaliserade polynomet med minsta grad över fältet vars rötter är konsekutiva potenser av elementet det genererande polynomet för Reed-Solomon-koden över fältet : $m=1$ $\alfa$ $\textstil GF(q)$ $\textstil n$ $\alfa$ $q-1$ $\alpha ^{{q-1}}=1,\quad \alpha ^{i}\neq 1,0<i<q-1$ $g(x)$ $\textstil GF(q)$ $d-1$ $\alpha ^{{l_{0}}},\alpha ^{{l_{0}+1}},...,\alpha ^{{l_{0}+d-2}}$ $\alfa$ $\textstil GF(q)$

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

där är något heltal (inklusive 0 och 1), med hjälp av vilket det ibland är möjligt att förenkla kodaren. Vanligtvis ska det . Graden av polynomet är . $l_{0}$ $l_{0}=1$ $\textstil g(x)$ $d-1$

Längden på den resulterande koden , det minsta avståndet (är det minsta av alla Hamming-avstånd för alla par av kodord, se radkod ). Koden innehåller kontrollsymboler, där anger graden av polynomet; antal informationssymboler . Således är Reed-Solomon-koden också en separerbar kod med ett maximalt avstånd (den är optimal i betydelsen Singleton bound ). $n$ $d$ $r=d-1=\deg(g(x))$ $\deg()$ $k=nr=n-d+1$ $\textstil d=n-k+1$

Kodpolynomet kan erhållas från informationspolynomet , genom att multiplicera och : $c(x)$ $m(x)$ $\deg m(x)\leqslant k-1$ $m(x)$ $g(x)$

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

Egenskaper

Reed-Solomon-koden över , som korrigerar fel, kräver paritetssymboler och kan användas för att korrigera godtyckliga felpaket av längd eller mindre. Enligt Reigers gränssats är Reed-Solomon-koder optimala när det gäller förhållandet mellan paketlängden och möjligheten till felkorrigering - med hjälp av ytterligare kontrollsymboler korrigeras fel (och mindre). $\textstyle GF(q^{m})$ $t$ $2t$ $t$ $2t$ $t$

Sats (Reiger bunden) . Varje linjär blockkod som korrigerar alla skurar av längd eller mindre måste innehålla åtminstone paritetssymboler. $t$ $2t$

En kod dubbel till en Reed-Solomon-kod är också en Reed-Solomon-kod. Den dubbla koden för en cyklisk kod är den kod som genereras av dess kontrollpolynom.

En matris genererar en Reed-Solomon-kod om och bara om någon minor i matrisen inte är noll. $G=[{\begin{array}{cc}I_{{k*k}}&P_{{k*(nk)}}\\\end{array}}]$ $P_{{k*(nk)}}$

När du punkterar eller förkortar Reed-Solomon-koden erhålls Reed-Solomon-koden igen. Punktering är en operation som tar bort ett kontrolltecken. Kodlängden reduceras med en, dimensionen bevaras. Kodavståndet måste minska med ett, annars skulle det raderade tecknet vara värdelöst. Förkortning - vi fixar en godtycklig kodkolumn och väljer bara de vektorer som innehåller 0. Denna uppsättning vektorer bildar ett delrum . $n$ $k$ $d$ $(n,k,d)$

Flera buggfixar

Reed-Solomon-koden är en av de mest kraftfulla koderna för att korrigera flera felskurar. Det används i kanaler där felskurar kan uppstå så ofta att de inte längre kan korrigeras med koder som korrigerar enstaka fel.

En Reed-Solomon - överfältskod med ett kodavstånd kan ses som en -fält-över-fältkod som kan korrigera valfri kombination av fel koncentrerade i eller färre block med m tecken. Det största antalet längdblock som kan påverkas av ett paket med längd , där , inte överstiger , så kod som kan korrigera felblock kan alltid korrigera valfri kombination av paket med total längd om . $(q^{m}-1,q^{m}-1-2t)$ $\textstyle GF(q^{m})$ $d=2t+1$ $((q^{m}-1)m,(q^{m}-1-2t)m)$ $\textstil GF(q)$ $t$ $m$ $l_{i}$ $l_{i}\leqslant mt_{i}-(m-1)$ $t_{i}$ $t$ $sid$ $l$ $l+(m-1)\leqslant mt$

Praktisk implementering

Reed-Solomon-kodning kan implementeras på två sätt: systematisk och icke-systematisk (se [1] för en beskrivning av kodaren).

Med icke-systematisk kodning multipliceras informationsordet med något irreducerbart polynom i Galois-fältet. Det resulterande kodade ordet är helt annorlunda än det ursprungliga, och för att extrahera informationsordet måste du utföra en avkodningsoperation, och först då kan du kontrollera data för fel. Sådan kodning kräver mycket resurser endast för att extrahera informationsdata, medan de kan vara felfria.

Vid systematisk kodning tilldelas checksymboler till ett informationsblock av symboler, vid beräkning av varje checksymbol används alla symboler i originalblocket. I detta fall finns det ingen overhead vid extrahering av det ursprungliga blocket om informationsordet inte innehåller fel, men kodaren/avkodaren måste utföra additions- och multiplikationsoperationer för att generera paritetssymboler. Dessutom, eftersom alla operationer utförs i Galois-fältet, kräver själva kodnings-/avkodningsoperationerna mycket resurser och tid. En snabb avkodningsalgoritm baserad på Fast Fourier Transform körs i en tid av storleksordningen . $k$ $2t$ $k$ $k(nk)$ $O(ln^{2}{n})$

Kodning

Under kodningsoperationen multipliceras informationspolynomet med det genererande polynomet. Multiplikation av det ursprungliga längdordet med ett irreducerbart polynom i systematisk kodning kan göras på följande sätt: $S$ $k$

Nollor läggs till det ursprungliga ordet , vilket resulterar i ett polynom . $2t$ $\textstyle T=Sx^{{2t}}$
Detta polynom divideras med det genererande polynomet , resten finns , , där är kvoten. $G$ $R$ $\textstyle Sx^{{2t}}=QG+R$ $F$
Denna återstod kommer att vara Reed-Solomon-korrigeringskoden, den tilldelas det ursprungliga teckenblocket. Mottaget kodord . $\textstyle C=Sx^{{2t}}+R$

Kodaren är uppbyggd av skiftregister, adderare och multiplikatorer. Skiftregistret består av minnesceller, som var och en innehåller ett element i Galois-fältet.

Det finns ett annat kodningsförfarande (mer praktiskt och enklare). Låt vara ett primitivt element i fältet , och låt vara en vektor av informationssymboler, och därmed ett informationspolynom. Då är vektorn Reed-Solomon-kodvektorn som motsvarar informationsvektorn . Denna kodningsmetod visar att för PC-koden är det inte nödvändigt att känna till det genererande polynomet och den genererande matrisen för koden alls, det räcker att känna till fältets expansion i termer av det primitiva elementet och kodens dimension (kodens längd i detta fall definieras som ). Saken är den att det genererande polynomet och kodavståndet är helt dolda bakom skillnaden. $a_{{i}}\i GF(q),(i=1,2,\ldots ,k-1),\alpha \in 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}}))$ $a$ $GF(q)$ $\alfa$ $k$ $n=q-1$ $nk$ $g(x)$

Avkodning

Avkodaren, som arbetar enligt den autoregressiva spektrala avkodningsmetoden, utför sekventiellt följande åtgärder:

Beräknar felsyndrom
Bygger ett felpolynom
Hittar rötterna till det givna polynomet
Anger felets karaktär
Fixar buggar

Beräkning av felsyndrom

Beräkningen av felsyndromet utförs av syndromavkodaren, som delar upp kodordet i ett generatorpolynom. Om det finns en rest under division, så finns det ett fel i ordet. Resten av divisionen är felsyndromet.

Konstruktion av felpolynomet

Det beräknade felsyndromet indikerar inte felens position. Graden av syndrompolynomet är , vilket är mycket mindre än graden av kodordet . För att få en överensstämmelse mellan ett fel och dess position i meddelandet konstrueras ett felpolynom. Felpolynomet implementeras med Berlekamp-Massey- algoritmen eller med Euklid-algoritmen. Euclids algoritm har en enkel implementering, men är resurskrävande. Därför används den mer komplexa, men mindre kostsamma Berlekamp-Massey-algoritmen oftare. Koefficienterna för det hittade polynomet motsvarar direkt koefficienterna för de felaktiga symbolerna i kodordet. $2t$ $n$

Hitta rötter

I detta skede söker man efter rötterna till felpolynomet, vilka bestämmer positionen för de förvrängda symbolerna i kodordet. Det implementeras med Chens procedur, vilket motsvarar en uttömmande uppräkning. Alla möjliga värden ersätts sekventiellt i felpolynomet, när polynomet försvinner hittas rötterna.

Fastställande av felets natur och dess korrigering

Baserat på felsyndromet och de hittade polynomrötterna bestäms felets natur med hjälp av Forney-algoritmen och en mask av förvrängda symboler byggs upp. Men för RS-koder finns det ett enklare sätt att hitta felens natur. Som visas i [2] för RS-koder med en godtycklig uppsättning av på varandra följande nollor : $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 (*)$

där är den formella derivatan med avseende på fellokaliseringspolynomet , och $\sigma '(x)$ $x$ $\sigma (x)$ $\Lambda (x)=\sigma (x)S(x)\mod x^{2t_{d}+1}.$

Vidare, efter det att masken har hittats, överlagras den på kodordet med användning av XOR -operationen och de förvrängda tecknen återställs. Därefter kasseras kontrolltecknen och det återvunna informationsordet erhålls.

Sudans algoritm

Vid denna tidpunkt har fundamentalt nya avkodningsmetoder tillämpats, till exempel den algoritm som föreslogs 1997 av Madhu Sudan [3] .

Förlängning av RS-koder

RS-kodförlängning är en procedur där kodens längd och avstånd ökar (medan koden fortfarande är på Singleton-gränsen och kodalfabetet inte ändras), och antalet informationssymboler för koden inte ändras [4] . Denna procedur ökar kodens korrigeringsförmåga . Överväg att förlänga RS-koden med en symbol. Låta vara en RS-kodvektor vars genererande polynom är . Låt nu . Låt oss visa att om du lägger till en symbol i vektorn ökar dess vikt till , om . Polynomet som motsvarar kodvektorn kan skrivas som , men då, med hänsyn till uttrycket för , får vi . , eftersom 1 inte hör till listan över rötter för det genererande polynomet. Men också , eftersom i det här fallet , vilket skulle öka kodens avstånd i motsats till villkoret, betyder detta att kodens vikt har ökat, på grund av att ett nytt tecken lagts till . Nya kodparametrar , förlängd vektor . Kontrollmatrisen för en icke-sträckt kod 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}}=-\summa _{{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}}

Då blir kontrollmatrisen utökad med en symbol för PC-koden

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}}

Applikation

Omedelbart efter uppkomsten (60-talet av XX-talet) började Reed-Solomon-koder användas som externa koder i kaskadstrukturer som används i satellitkommunikation. I sådana konstruktioner kodas de -e PC-symbolerna (det kan finnas flera av dem) av interna faltningskoder . I den mottagande sidan avkodas dessa symboler med en mjuk Viterbi-algoritm (effektiv i AWGN -kanaler ). En sådan avkodare kommer att korrigera enstaka fel i q-ary-symboler, men när skurfel uppstår och vissa paket med q-ary-symboler avkodas felaktigt, kommer den externa Reed-Solomon-avkodaren att korrigera skurarna av dessa fel. Därmed kommer den erforderliga tillförlitligheten för informationsöverföring att uppnås ( [5] ). $q$

För närvarande har Reed-Solomon-koder ett mycket brett räckvidd på grund av deras förmåga att hitta och korrigera flera skurar av fel.

Registrering och lagring av information

Reed-Solomon-koden används vid skrivning och läsning i RAM-kontroller, vid arkivering av data, skrivning av information till hårddiskar ( ECC ), skrivning till CD/DVD-skivor. Även om en betydande mängd information är skadad, skadas flera sektorer av diskmediet, då låter Reed-Solomon-koder dig återställa det mesta av den förlorade informationen. Används även när du skriver till media som magnetband och streckkoder.

Bränna till CD-ROM

Möjliga fel när du läser från en disk visas redan vid diskproduktionsstadiet, eftersom det är omöjligt att göra en idealisk disk med modern teknik. Fel kan också orsakas av repor på skivans yta, damm etc. När du gör en läsbar CD används därför CIRC (Cross Interleaved Reed Solomon Code) korrigeringssystemet. Denna korrigering är implementerad i alla enheter som tillåter läsning av data från CD-skivor i form av ett chip med firmware. Feldetektering och korrigering baseras på redundans och interfoliering . Redundans - cirka 25% av den ursprungliga informationen.

Inspelning till ljud-CD-skivor använder Red Book -standarden . Felkorrigering sker på två nivåer, C1 och C2. Vid kodning i det första steget läggs kontrollsymboler till originaldatan, i det andra steget kodas informationen igen. Förutom kodning interfolieras även bytes ( interfolierade ) så att felblock under korrigering bryts upp i separata bitar som är lättare att korrigera. På den första nivån upptäcks och korrigeras felaktiga block på en och två byte långa (ett respektive två felaktiga tecken). Felblock på tre byte upptäcks och skickas till nästa lager. På den andra nivån detekteras och korrigeras 1 och 2 byte felblock som har sitt ursprung i C2. Upptäckten av tre felaktiga tecken är ett allvarligt fel och kan inte korrigeras.

Trådlös och mobil kommunikation

Denna kodningsalgoritm används vid dataöverföring över WiMAX -nätverk , i optiska kommunikationslinjer , i satellit- och radioreläkommunikation . Metoden Forward Error Correction (FEC) är baserad på Reed-Solomon-koder.

Kodningsexempel

Hexadecimal (15,11) Reed-Solomon-kod

Låt . Sedan $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 är 4, och . Varje fältelement kan mappas till 4 bitar. Informationspolynomet är en sekvens av 11 tecken från , vilket motsvarar 44 bitar, och hela kodordet är en uppsättning av 60 bitar. $g(x)$ $nk=4$ $k=11$ ${\mathrm {GF}}(16)$ ${\mathrm {GF}}(16)$

8-ary (7,3) Reed-Solomon-kod

Låt . Sedan $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 .$

Låt informationspolynomet ha formen:

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

Kodordet för en icke-systematisk kod kommer att skrivas 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 är en sekvens av sju oktala tecken.

En alternativ kodningsmetod för den 9-åriga (8,4) Reed-Solomon-koden

Låt oss konstruera Galois-fältet modulo polynomet . Låt dess rot, då ser fälttabellen ut så här: $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).

Låt informationspolynomet och sedan göra motsvarande beräkningar på det konstruerade fältet 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 ett resultat konstruerades en RS-kodvektor med parametrar . Detta avslutar kodningen. Observera att med denna metod behövde vi inte ett genererande kodpolynom [4] . $n=8,\ k=4,\ d=5$

Avkodningsexempel

Låt fältet genereras av ett primitivt element vars irreducible polynom är . Sedan . Låt . Då är det genererande polynomet för PC-koden lika med . Låt nu polynomet accepteras . Sedan . Då erhålls nyckelsystemet av ekvationer 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}}.$

Betrakta nu den euklidiska algoritmen för att lösa detta ekvationssystem.

Inledande villkor :

r_{0}(x)=x^{5},\ r1(x)=S(x)=1+\alpha ^{6}x+\alpha ^{5}x^{2}+\ alfa x^{3}+\alfa 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}+\alfa ^{4}x+\alpha ^{2}x^{2}.$

Algoritmen stannar eftersom , därför följer det det ${\displaystyle \deg[r_{3}(x)]=2=t_{d))$ $\sigma (x)=\alpha ^{3}+\alpha ^{4}x+\alpha ^{2}x^{2}.$

Vidare ger en fullständig sökning med Cheney-algoritmen oss positionerna för felen, det här är . Sedan får vi det genom formeln $j_{1}=2,\quad j_{2}=4$ $(*)$ $e_{2}=\alpha ,\ e_{4}=\alpha .$

Alltså den avkodade vektorn . Avkodning klar, två buggar fixade [6] . $c(x)=r(x)+e(x)=0$

Applikation

Reed-Solomon-koden används i vissa lagringsapplikationer som RAID 6 ;

Se även

Anteckningar

↑ Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - S. 92-93. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .
↑ Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 sid. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .
↑ Sudans algoritm . Hämtad 24 december 2018. Arkiverad från originalet 24 december 2018. (obestämd)
↑ 1 2 Sagalovich, 2007 , sid. 212-213.
↑ M. Werner. Grunderna i kodning. - Technosphere, 2004. - S. 268-269. — ISBN 5-94836-019-9 .
↑ Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - S. 116-119. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .

Litteratur

Peterson W, Weldon E. Felkorrigeringskoder . - M . : Mir, 1976. - S. 596 .
Blahut R. Teori och praktik av felkontrollkoder. — M .: Mir , 1986. — 576 sid.
Berlekamp E. Algebraisk kodningsteori = Algebraisk kodningsteori. - M . : Mir, 1971. - S. 478 .
Egorov S.I. Felkorrigering i informationskanaler för kringutrustning för datorer. - Kursk: KurskGTU, 2008. - S. 252.
Sagalovich Yu. L. Introduktion till algebraiska koder - M. : MIPT , 2007. - 262 sid. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 sid. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .
M. Werner. Grunderna i kodning. - Technosphere, 2004. - 288 sid. — ISBN 5-94836-019-9 .

Länkar

The Power of Reed-Solomon Codes or Information Risen from the Ashes (artikel av Chris Kaspersky)
Bruskorrigerande kodning i paketnätverk (artikel av V. Vargauzin)
Felkorrigeringskod (ECC)
CD-R-skivor, teknik från insidan
CD-format
Reed-Solomon-koder
wiki.linuxformat.ru/wiki/LXF134:par2 - med par2 , ett filåterställningsverktyg som använder Reed-Solomon Code-metoden (ryska)