Feilkorrigeringskoding

Feilkorrigeringskoding er en del av feilkontroll i kommunikasjons- og lagringssystemer som bruker redundant informasjon for å oppdage og ofte rette feil som oppstår under overføring eller lagring. Gjennom forward error correction (FEC) blir en del av feilinformasjonen lagt inn i datastrukturen slik at mottakeren kan korrigere feil uten å be om ny sending. Dette øker påliteligheten i støyfulle kanaler og i miljøer med begrenset båndbredde.

Koder bygges som blokker eller strømmer. For lineære blokkoder brukes en generator- og en parity-check-matrise; koden har lengde n og informasjonslengde k, og forholdet R = k/n. Minimum avstand d_min bestemmer hvor mange feil som kan rettes eller oppdages. Dekoding bruker metoder som syndromdekoding, Viterbi-dekoding for konvolusjonelle koder, eller belief propagation for LDPC-koder.

Vanlige koder inkluderer Hamming-koder (enkle, effektive for små feil), Reed-Solomon-koder (robuste mot burstfeil i lagringsmedier), BCH-koder (generelle blokkoder) og moderne koder som LDPC og turbo-koder. LDPC-koder bruker sparse grafiske representasjoner og iterativ melding-propagasjon; Turbo-koder kombinerer konvolusjonelle koder med iterativ dekoding for svært høy ytelse og nær Shannon-grensen.

Bruksområder inkluderer datakommunikasjon (satellitt- og mobilnettverk, Wi-Fi, fiber), lagring (CD/DVD/Blu-ray, harddisker, SSD-er, RAID), og visuelle koder som QR-koder. Utviklingen av feilkorrigeringskoding har vært central for å gjøre digital kommunikasjon og lagring mer pålitelig, med historiske bidrag fra Hamming på 1950-tallet, Reed-Solomon på 1960-tallet, CIRC i optiske medier, og senere LDPC- og turbo-koder i moderne standarder.