Reed-Solomoncode
Reed-Solomon foutcorrectie is een voorwaartse foutcorrectiecode. Het werkt door oversampling van een polynoom die uit de gegevens is geconstrueerd. De polynoom wordt op verschillende punten geëvalueerd, en deze waarden worden verzonden of opgenomen. Door de polynoom vaker te bemonsteren dan nodig is, wordt de polynoom overgedetermineerd. Zolang de ontvanger "veel" punten correct ontvangt, kan hij de oorspronkelijke polynoom herstellen, zelfs in aanwezigheid van "enkele" slechte punten.
Reed-Solomon codes worden in veel verschillende commerciële toepassingen gebruikt, bijvoorbeeld in CD's, DVD's en Blu-ray Discs, in datatransmissietechnologieën zoals DSL en WiMAX, en in omroepsystemen zoals DVB en ATSC.
Overzicht
Reed-Solomon codes zijn blokcodes. Dit betekent dat een vast blok van invoergegevens wordt verwerkt tot een vast blok van uitvoergegevens. In het geval van de meest gebruikte R-S code (255, 223) - worden 223 Reed-Solomon ingangssymbolen (elk acht bits lang) gecodeerd in 255 uitgangssymbolen.
- De meeste R-S ECC-schema's zijn systematisch. Dit betekent dat een deel van het codewoord de oorspronkelijke invoergegevens bevat.
- Er is gekozen voor een Reed-Solomon symboolgrootte van acht bits, omdat de decoders voor grotere symboolgroottes moeilijk te implementeren zouden zijn met de huidige technologie. Deze ontwerpkeuze dwingt de langste codewoordlengte op 255 symbolen.
- De standaard (255, 223) Reed-Solomon code kan tot 16 Reed-Solomon symboolfouten in elk codewoord corrigeren. Aangezien elk symbool in feite acht bits is, betekent dit dat de code tot 16 korte foutuitbarstingen kan corrigeren die te wijten zijn aan de binnenste convolutionele decoder.
De Reed-Solomon code is, evenals de convolutionele code, een transparante code. Dit betekent dat indien de kanaalsymbolen ergens langs de lijn zijn geïnverteerd, de decoders nog steeds zullen werken. Het resultaat zal het complement zijn van de oorspronkelijke gegevens. De Reed-Solomon code verliest echter zijn transparantie indien virtuele nulvulling wordt gebruikt. Om deze reden is het verplicht dat de betekenis van de gegevens (d.w.z. waar of aangevuld) wordt bepaald voordat Reed-Solomon decodering plaatsvindt.
In het geval van het Voyager-programma bereiken R-S-codes bijna optimale prestaties wanneer zij worden samengevoegd met de (7, 1/2) convolutionele (Viterbi) binnencode. Aangezien er twee controlesymbolen nodig zijn voor elke te corrigeren fout, resulteert dit in een totaal van 32 controlesymbolen en 223 informatiesymbolen per codewoord.
Bovendien kunnen de Reed-Solomon codewoorden op symboolbasis worden doorverbonden voordat ze convolutiegecodeerd worden. Aangezien hierdoor de symbolen in een codewoord worden gescheiden, wordt het minder waarschijnlijk dat een burst van de Viterbi decoder meer dan één Reed-Solomon symbool in een codewoord verstoort.
Basisidee
Het kernidee achter een Reed-Solomon code is dat de gecodeerde gegevens eerst worden gevisualiseerd als een polynoom. De code berust op een stelling uit de algebra die stelt dat elk van de k verschillende punten op unieke wijze een polynoom van hoogstens k-1 bepaalt.
De verzender bepaalt een 
polynoom van graad k - 1 over een eindig veld, die de k 
gegevenspunten weergeeft. De polynoom wordt dan "gecodeerd" door zijn evaluatie op verschillende punten, en deze waarden zijn wat werkelijk wordt verzonden. Tijdens de transmissie kunnen sommige van deze waarden beschadigd raken. Daarom worden in feite meer dan k punten verzonden. Zolang voldoende waarden correct worden ontvangen, kan de ontvanger afleiden wat de oorspronkelijke polynoom was, en de oorspronkelijke gegevens decoderen.
Net zoals men een curve kan corrigeren door langs een gat te interpoleren, kan een Reed-Solomon code een reeks fouten in een blok gegevens overbruggen om de coëfficiënten van de polynoom die de oorspronkelijke curve tekende, terug te krijgen.
Geschiedenis
De code werd in 1960 uitgevonden door Irving S. Reed en Gustave Solomon, die toen lid waren van het MIT Lincoln Laboratory. Hun baanbrekende artikel was getiteld "Polynomial Codes over Certain Finite Fields." Toen het artikel werd geschreven, was de digitale technologie nog niet ver genoeg gevorderd om het concept toe te passen. De eerste toepassing, in 1982, van RS-codes in massaprodukten was de compact disc, waar twee interleaved RS-codes worden gebruikt. In 1969 werd door Elwyn Berlekamp en James Massey een efficiënt decoderingsalgoritme voor RS-codes met grote afstand ontwikkeld. Tegenwoordig worden RS-codes gebruikt in harde schijven, DVD's, telecommunicatie en digitale omroepprotocollen.
