Felrättande kod

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2011-04) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

En felrättande kod används vid lagring eller överföring av digitala data för att identifiera bitfel och med stor sannolikhet rätta ("gissa") felen. Således kan man minska bitfel (bit error rate). Tillämpningsexempel vid protokoll för forward error correction (FEC) vid trådlös kommunikation, särskilt broadcasting där en backkanal saknas, och vid bredbandsmodem, där bitfel är vanligt förekommande. Den är särskilt användbar vid broadcasting, där backkanal och omsändning inte är möjlig, samt vid lagringsmedia såsom CD-ROM. Ett exempel på felrättande kodning är hammingkoden.

Felrättande koder skall inte sammanblandas med felupptäckande koder, som kan användas vid protokoll för automatisk omsändning (automatic repeat request, ARQ), exempelvis i TCP-protokollet, men även används i protokoll som ignorerar felaktiga datapaket, exempelvis Ethernet, IP och UDP. Automatisk omsändning kan inte användas om backkanal saknas, exempelvis vid broadcasting och lagringsmedia såsom CD-ROM, varför felrättande koder då är vanliga. Vid kommunikation där bitfel är vanligt förekommande, såsom trådlös kommunikation och bredbandsmodem, är ARQ ineffektivt, varför felrättande koder är att föredra.

Om antalet bitfel blir stort kan man inte använda den felrättande koden för att rätta fel, men man kan använda den som felupptäckande kod, det vill säga man kan med stor sannolikhet detektera att ett antal fel har uppstått i ett block av data men inte säga exakt vilka bitar som är felaktiga och vad det korrekta värdet skulle vara.

I ett vanligt förekommande skolexempel på felrättande kod bygger man på antagandet att ett enda fel i en datamängd av en given storlek kan uppstå någorlunda ofta, medan två fel i samma datamängd är mycket ovanligt och sannolikheten att tre fel skall uppstå samtidigt är försumbar.

Flera kontroll- och paritetsbitar

En mycket enkel och gammal teknik för lägga till redundanta bitar i syfte att upptäcka felaktig data är användande av en paritetsbit. Detta är en bit som visar om antalet ettor i ett ord (en sekvens binära bitar) är jämnt eller udda. En paritetsbit kan användas som felupptäckande kod av udda antal bitfel, men inte som felrättade kod. Tekniken kan dock vidareutvecklas till en mycket enkel felrättande kod genom att använda flera bitar. Exempelvis kan man införa flerdimensionell redundans i de data som skall lagras eller överföras, exempelvis en paritetsbit för varje rad och en för varje kolumn i ett block av bitar (tvådimensionell paritetskontroll). På så sätt kan man identifiera vilka bitar som sannolikt är fel och rätta dem (invertera dem), vid litet antal bitfel. Vid ett större antal bitfel kan man inte rätta fel, men man kan med hög sannolikhet detektera bitfel.

Moderna felupptäckande och felrättande koder är emellertid avsevärt mer avancerade, och baseras på diskret matematik.

Exempel på användning

En del RAM-minnen är av typen "Error-Correcting Code (ECC) memory", vilket innebär att de undersöker och korrigerar fel automatiskt. Särskilda kretsar genererar kontrollsummor som korrigerar fel som är större än en bit.

Felrättande koder förekommer också i enheter för läsning och skrivning av optiska lagringsmedium, exempelvis i dvd- och cd-spelare.