Felkorrigeringsalgoritmer

Felkorrigeringsalgoritmer är algoritmer som används för att upptäcka och korrigera fel som uppstår när data lagras eller överförs. De bygger på felkorrigerande koder som tillför redundans till originaldata för att möjliggöra återvinning av information även om delar av bitarna har blivit felaktiga på vägen.

Koderna kan delas in i blockkoder och konvolutionskoder. Blockkoder används på fasta datablock och inkluderar exempel som Hamming-koder och Reed-Solomon-koder. Konvolutionskoder används i flerdemade strömmar och avkodas med metoder som Viterbi-algoritmen. Modernare varianter som LDPC- och turbo-koder används i höghastighetskommunikation.

Avkodningstekniker baseras ofta på algebraisk felberäkning eller probabilistisk sannolikhetsberäkning. Många avkodningar strävar efter att minimera feluppskattningen genom att maximera sannolikheten att rätt data återvinns (maximum likelihood). Tekniker som soft-decode och iterativ decoding används särskilt för LDPC- och turbo-koder.

Användningsområden omfattar telekommunikation, lagring av digital information och nätverksstandarder. Felkorrigeringsalgoritmer används i mobil- och satellitkommunikation, i lagringsmedia som CD-, DVD- och Blu-ray, i hårddiskar och SSD-enheter, samt i QR-koder och RAID-lösningar.

Prestanda och designval beror på kodens ränta (redundans), felmodell och avkodningskomplexitet. En högre redundans förbättrar felkorrigering men kräver mer utrymme eller bandbredd och kan öka latens och energianvändning.

Historiskt utvecklades felkorrigeringskoder under 1950-talet med Hamming-koden. Reed-Solomon-koder används i optisk media och många lagringssystem. LDPC- och turbo-koder utvecklades på 1990-talet och används i moderna kommunikationsstandarder som Wi‑Fi, 4G/5G och DVB.