Reed-Solomon felkorrigering
Reed-Solomon-felkorrigering är en framåtriktad felkorrigeringskod. Den fungerar genom att man översamplar ett polynom som konstruerats utifrån data. Polynomet utvärderas i flera punkter och dessa värden skickas eller registreras. Genom att provta polynomet oftare än nödvändigt blir polynomet överbestämt. Så länge mottagaren tar emot "många" av punkterna korrekt kan den återskapa det ursprungliga polynomet även om det finns "några" dåliga punkter.
Reed-Solomon-koder används i många olika kommersiella tillämpningar, till exempel i CD-skivor, DVD-skivor och Blu-ray-skivor, i dataöverföringstekniker som DSL och WiMAX och i sändningssystem som DVB och ATSC.
Översikt
Reed-Solomon-koder är blockkoder. Det innebär att ett fast block av indata bearbetas till ett fast block av utdata. I fallet med den vanligaste R-S-koden (255, 223) - 223 Reed-Solomon-inmatningssymboler (var och en åtta bitar lång) kodas till 255 utmatningssymboler.
- De flesta R-S ECC-system är systematiska. Detta innebär att en del av det utgående kodordet innehåller de ingående uppgifterna i sin ursprungliga form.
- En Reed-Solomon-symbolstorlek på åtta bitar valdes eftersom avkodare för större symbolstorlekar skulle vara svåra att genomföra med nuvarande teknik. Detta val tvingar den längsta kodordslängden att vara 255 symboler.
- Reed-Solomon-standardkoden (255, 223) kan korrigera upp till 16 Reed-Solomon-symbolfel i varje kodord. Eftersom varje symbol egentligen består av åtta bitar innebär detta att koden kan korrigera upp till 16 korta fel som beror på den inre konvolutionella avkodaren.
Reed-Solomon-koden, liksom konvolutionskoden, är en transparent kod. Detta innebär att om kanalsymbolerna har inverterats någonstans längs linjen fungerar avkodarna fortfarande. Resultatet blir komplementet till de ursprungliga uppgifterna. Reed-Solomon-koden förlorar dock sin transparens om virtuell nollfyllning används. Av denna anledning är det obligatoriskt att datans betydelse (dvs. sant eller kompletterat) måste lösas innan Reed-Solomon avkodning påbörjas.
När det gäller Voyager-programmet uppnår R-S-koder nästan optimal prestanda när de kombineras med den inre (7, 1/2) konvolutionskoden (Viterbi). Eftersom det krävs två kontrollsymboler för varje fel som skall korrigeras, resulterar detta i totalt 32 kontrollsymboler och 223 informationssymboler per kodord.
Dessutom kan Reed-Solomon-kodorden interleavas på symbolbasis innan de konvolutionskodas. Eftersom detta separerar symbolerna i ett kodord blir det mindre sannolikt att en burst från Viterbi-dekodern stör mer än en Reed-Solomon-symbol i ett kodord.
Grundläggande idé
Huvudidén bakom en Reed-Solomon-kod är att de kodade uppgifterna först visualiseras som ett polynom. Koden bygger på en sats från algebra som säger att k olika punkter unikt bestämmer ett polynom av graden högst k-1.
Avsändaren bestämmer ett polynom av grad k - 1 {\displaystyle k-1}
över ett ändligt fält som representerar de k {\displaystyle k}
datapunkterna. Polynomet "kodas" sedan genom att det utvärderas i olika punkter, och dessa värden är det som faktiskt sänds. Under överföringen kan vissa av dessa värden bli skadade. Därför skickas fler än k punkter. Så länge tillräckligt många värden tas emot korrekt kan mottagaren härleda vad det ursprungliga polynomet var och avkoda de ursprungliga uppgifterna.
På samma sätt som man kan korrigera en kurva genom att interpolera förbi en lucka, kan en Reed-Solomon-kod överbrygga en rad fel i ett datablock för att återskapa koefficienterna i det polynom som ritade den ursprungliga kurvan.
Historia
Koden uppfanns 1960 av Irving S. Reed och Gustave Solomon, som då arbetade vid MIT Lincoln Laboratory. Deras banbrytande artikel hade titeln "Polynomial Codes over Certain Finite Fields". När artikeln skrevs var den digitala tekniken inte tillräckligt avancerad för att genomföra konceptet. Den första tillämpningen, 1982, av RS-koder i massproducerade produkter var CD-skivan, där två RS-koder används. En effektiv avkodningsalgoritm för RS-koder med stora avstånd utvecklades av Elwyn Berlekamp och James Massey 1969. I dag används RS-koder i hårddiskar, DVD-skivor, telekommunikationer och digitala sändningsprotokoll.
