Felkorrigeringskoder

Felkorrigeringskoder är metoder för att upptäcka och rätta fel som uppstår när data överförs eller lagras. Genom att lägga till redundans i data ökar de chanserna att återställa det ursprungliga budskapet utan ny överföring.

Grunden är att varje kodord består av k informationbitar och n-k kontrollbitar. Denna redundans gör att en mottagare kan upptäcka fel och ofta rätta dem upp till ett visst antal fel. Viktiga mått är minsta avstånd d_min mellan kodord, vilket bestämmer felkorrigerings- och felupptäcktsförmågan; t = floor((d_min-1)/2) antal fel som kan korrigeras; kodfaktorn eller kodningshastigheten R = k/n.

Vanliga typer inkluderar Hamming-koder, som oftast kan korrigera ett fel och upptäcka två; Reed-Solomon-koder, som arbetar över symboler och används i många lagringssystem samt QR-koder; BCH-koder, som erbjuder olika längder och felkapaciteter; samt mer moderna LDPC- och Turbo-koder som används i höghastighetskommunikation och mångsidig lagring.

Användningar omfattar datakommunikation och telekommunikation (till exempel satellitkommunikation och mobilnät), samt lagring och minnessystem (CD-, DVD- och Blu-ray-teknik, hårddiskar, SSD och ECC-minne). Felkorrigeringskoder är därmed centrala för att säkerställa tillförlitlig överföring och varaktig dataåtkomst.

Historiskt såg de första betydande koderna dagens ljus med Hamming på 1950-talet; Reed-Solomon och BCH-koder utvecklades senare och har blivit grundläggande i många praktiska system. LDPC och Turbo-koder har bidragit till förbättrad prestanda i modern kommunikation.