Feiloppdagingskoder

Feiloppdagingskoder er metoder for å oppdage utilsiktede endringer i digital data som sendes eller lagres. De legger til redundant informasjon slik at mottakeren kan verifisere integriteten og oppdage feil forårsaket av støy eller maskinfeil.

Slik fungerer det: en kode beregner en verifiseringsverdi fra dataene, som sendes sammen med dem. Ved mottak beregnes verdien på nytt og sammenlignes med den mottatte. Forskjellige koder gir ulik evne til å oppdage feil og ulik kostnad i form av ekstra data og beregninger.

Hovedtyper: Paritetskontroll – enkel og kan oppdage en enkelt bitfeil, men ikke alle feiltyper. Checksums – en sum av dataene som gir bedre dekning, men kan fortsatt la enkelte feil passere. CRC – cyclic redundancy check; bruker polynomielt divisjon og oppdager de fleste burst-feil; utbredt i nettverk og lagring. Hamming-koder – oppdager og korrigerer enkeltbitesfeil, og kan oppdage visse to-bitesfeil. Reed-Solomon-koder – tåler burst-feil og brukes i optiske medier, lagringssystemer og QR-koder.

Anvendelser: dataoverføring, lagring og RAM-minne med ECC. ECC-minne bruker avanserte koder for å oppdage og korrigere feil i minneblokker.

Begrensninger: ingen kode gir absolutt feilfrihet; overhead og beregninger varierer. Noen feiltyper kan fortsatt passere uoppdaget, avhengig av kode og implementering.

Historie: ideen stammer fra paritetskontroll, mens Hamming-koder ble utviklet av Richard Hamming på 1950-tallet. CRC og andre koder ble videreutviklet og er nå standarder i mange systemer.