AlegsaOnline.com

Reed-Solomon foutcorrectie uitgelegd: werking en toepassingen

Leer Reed-Solomon foutcorrectie: hoe oversampling van polynomen werkt, voorbeelden en toepassingen in CD/DVD, DSL, DVB en meer — helder, praktisch en toepasbaar uitgelegd.

Schrijver: Leandro Alegsa Aanmaakdatum: 20 april 2021 Laatste update: 8 februari 2026

en.wikipedia.org · CC BY-SA 4.0

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.

Wat is een Reed-Solomon code?

Een Reed-Solomon-code is een type foutcorrectiecode die werkt op symbolen (meestal bytes) in plaats van op individuele bits. De code wordt vaak beschreven met parameters (n, k), waarbij k het aantal informatie-symbolen is en n het totale aantal symbolen na codering (informatie + pariteit). De extra pariteitsymbolen geven redundantie waarmee fouten kunnen worden opgespoord en gecorrigeerd.

Belangrijkste eigenschappen

Foutcorrectiecapaciteit: Een Reed-Solomon-code met parameters (n, k) kan maximaal t = (n − k) / 2 willekeurige symbolen corrigeren (fouten), of n − k gekende posities herstellen (erasures).
Veldstructuur: RS-codes werken meestal over eindige velden GF(2^m). Voor m = 8 werkt men vaak met bytes (256 elementen), wat veel praktische toepassingen mogelijk maakt.
Systematisch karakter: Veel implementaties zijn systematisch: de originele gegevens verschijnen ongewijzigd in de codewoord, met daaraan toegevoegd pariteitsymbolen.
Interleaving: Door codewoorden te interleaven kunnen RS-codes beter omgaan met lange burstfouten (aaneengesloten foutblokken).

Hoe codering en decodering werken (globale beschrijving)

Codering:

De informatie-symbolen worden geïnterpreteerd als coëfficiënten van een polynoom P(x) van graad < k.
De encoder evalueert P(x) op n verschillende punten in het veld en verstuurt die n waarden als het codewoord. Een alternatieve systematische methode is P(x) * x^(n−k) mod g(x) berekenen en de rest (pariteit) toevoegen.

Decodering (globaal):

De ontvanger meet het ontvangen codewoord; sommige symbolen kunnen corrupt zijn of ontbreken.
Een foutlokalisatie-algoritme vindt de posities met fouten (foutlocators) en bepaalt vervolgens de foutwaarden.
Veel gebruikte algoritmen zijn de Berlekamp–Massey-algoritme, het Euclidische algoritme voor polynoomgrootste gemene deler en Forney's algoritme voor foutwaarden.

Verschil tussen fouten en erasures

Een fout is een symbool met onbekende locatie en onbekende waarde; een erasure is een symbool waarvan de locatie bekend is maar de waarde ontbreekt (bijvoorbeeld vanwege detectie van een beschadigd blok). Erasures zijn gemakkelijker te corrigeren: een RS-code kan tot n − k erasures herstellen, of een combinatie van e erasures en f fouten zolang 2f + e ≤ n − k.

Decoderingstechnieken kort uitgelegd

Syndroomberekening: Bereken syndromen uit het ontvangen woord om te bepalen of en waar fouten zijn.
Foutlokatie: Gebruik Berlekamp–Massey of het Euclidische algoritme om het foutlokatorpolynoom te vinden.
Foutwaarde-berekening: Forney's algoritme berekent voor elk gevonden foutlocatie de juiste correctiewaarde.

Praktische voorbeelden en toepassingen

Reed-Solomon-codes worden veel toegepast in opslag en transmissie omdat ze robuust zijn tegen symbol- of blokfouten. Voorbeelden:

CD's gebruiken een vorm van interleaved Reed-Solomon-codering (CIRC) om krassen en fouten te corrigeren.
DVD's en Blu-ray Discs gebruiken uitgebreide foutcorrectieschema's waarin RS-codes een rol spelen (samen met andere technieken).
Datacommunicatieprotocollen zoals DSL en WiMAX gebruiken RS-codes in combinatie met andere codes of interleaving.
Omroepsystemen zoals DVB en ATSC gebruiken RS-codes als onderdeel van hun fysieke laag foutcorrectie.
QR-codes en veel barcodes gebruiken Reed-Solomon-codering om beschadigde of gedeeltelijk bedekte symbolen te herstellen.
In opslagsystemen en RAID-achtige constructies worden RS-achtige technieken gebruikt om dataverlies bij schijfuitval te beperken.

Praktische overwegingen

Symbolgrootte: De keuze van m (zodat het veld GF(2^m) grootte 2^m) bepaalt de maximale n (≤ 2^m − 1) en de symbolgrootte (bijv. m = 8 → byte-symbolen, n ≤ 255).
Complexiteit: Decodering vergt rekenkracht; voor realtime toepassingen zijn efficiënte implementaties en soms hardwareversnelling nodig.
Combinatie met andere codes: Moderne systemen combineren RS met convolutionele codes, turbo-codes of LDPC voor betere prestaties onder verschillende kanaalomstandigheden.

Kort voorbeeld

Een veelgebruikte code in praktijk is RS(255,223) over GF(256). Hier is n = 255, k = 223, dus n − k = 32 pariteitsymbolen; de code kan daarmee maximaal t = 16 willekeurige symbolen corrigeren. Zulke parameters zijn populair omdat ze werken op bytes en geschikt zijn voor veel storage- en transmissietoepassingen.

Samenvattend

Reed-Solomon-foutcorrectie gebruikt polynoomevaluaties over eindige velden om redundantie toe te voegen waarmee fouten en uitval van symbolen hersteld kunnen worden. Door de goede eigenschappen voor symbolfouten, de mogelijkheid om erasures efficiënt te verwerken en de flexibiliteit in parameters, zijn RS-codes wijdverspreid in media-opslag en communicatiesystemen. Voor implementaties is begrip van veldalgebra, syndromen en decoderingstechnieken zoals Berlekamp–Massey en Forney essentieel.

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 $k-1$ 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.

Schrijver

AlegsaOnline.com - Reed-Solomoncode - Leandro Alegsa

Aanmaakdatum: 20 april 2021
Laatste update: 8 februari 2026

URL: https://nl.alegsaonline.com/art/81778