AlegsaOnline.com

Reed–Solomon-felkorrigering

Reed–Solomon-felkorrigering är en blockkod baserad på polynom över ändliga kroppar. Den kan återställa förlorade eller korrupta symboler och används i lagring och digital överföring som CD, DVD, QR och satellit.

Författare: Leandro Alegsa Skapandedatum: 20 april 2022 Senast uppdaterad: 26 april 2026

en.wikipedia.org · CC BY-SA 4.0

Reed–Solomon-felkorrigering är en kraftfull och allmänt använd metod för att upptäcka och rätta fel i digital information. Tekniken bygger på att data representeras som koefficienter i ett polynom över en ändlig kropp, och att polynomet utvärderas i flera punkter för att skapa redundans. När en mottagare får ett tillräckligt antal korrekta utvärderingsvärden kan ursprungsmeddelandet rekonstrueras även om några av värdena är felaktiga eller saknas.

Översikt

Reed–Solomon (RS) är en typ av blockkod som arbetar med symboler (vanligtvis bytes) istället för enskilda bitar. En RS-kod anges ofta som (n,k) där k är antalet informationssymboler och n det totala antalet symboler efter tillsatt redundans. Antalet redundanta symboler n−k bestämmer hur många symbolfel eller bortfall som kan korrigeras.

Princip och egenskaper

Polynomrepresentation: ursprungsdata tolkas som koefficienter i ett polynom; polynomet utvärderas i många punkter för att skapa kodord. Se exempel på polynom och konstruktion.
Fel- och utplåningskorrigering: upp till (n−k)/2 slumpmässiga symbolfel eller upp till n−k kända utplåningar kan återställas.
Arbetsfält: RS-koder definieras över ändliga kroppar GF(2^m), där symboler är element i dessa kroppar; detta gör dem särskilt lämpade för byte-baserad lagring.
Systematisk form: det är vanligt att koden konstrueras så att originaldata syns oförändrade följt av paritetssymboler.

Historia och utveckling

Reed–Solomon-koder introducerades av Irving S. Reed och Gustave Solomon 1960. Sedan dess har de blivit en grundpelare i kodningsteori och praktiska system tack vare sin flexibilitet och starka egenskaper mot klusterskador (burst errors). Kombinationer med andra tekniker, till exempel konkatenerade koder och interleaving, har förbättrat prestandan i brusiga kanaler.

Tillämpningar och exempel

RS-felkorrigering används brett både i lagring och kommunikation. Vanliga exempel:

Optisk media: CD (läs mer), DVD (läs mer) och Blu-ray (läs mer) använder RS-baserade scheman för att korrigera repor och defekter.
Datakommunikation: DSL (mer om DSL) och trådlösa system som WiMAX använder RS eller derivat för robust överföring.
Broadcast och satellit: standarder som DVB (DVB-info) och ATSC använder RS-koder i sina felkorrigeringslager.
Andra tillämpningar: arkivlagring, RAID-varianter, QR-koder och satellitkommunikation förlitar sig på RS för att rädda data vid partiella fel.

Viktiga skillnader och tekniska aspekter

Till skillnad från enkla bitpariteter hanterar RS-koder hela symboler, vilket ger bra skydd mot både slumpmässiga och sammanhängande fel. Dekodning kräver algoritmer för att hitta felpositioner och -värden; kända effektiva metoder är Berlekamp–Massey, Euclidisk algoritm och Forneys formel för feletablering. Förfallande eller kända utplåningar (erasures) är enklare att rätta än okända fel, och många praktiska system kombinerar RS med interleaving för att omvandla burstfel till individuella symbolfel som koden kan hantera.

För den som vill fördjupa sig finns introduktioner till kodteori och praktiska implementationer med fler exempel och mattespecifika detaljer på grundläggande resurser, samt exempel på hur data mappas via symbolrepresentation i praktiska system.

Ö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} $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.