Felrättande kod
From Wikipedia, the free encyclopedia
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.
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. |
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.