Avkodningsalgoritm

Avkodningsalgoritm är en metod för att återvinna det ursprungliga meddelandet från en kodad eller felaktigt överförd representation. Inom informations- och kommunikationsteori handlar avkodning om att rekonstruera data givet en kodbok och en sannolikhetsmodell för hur fel uppstår. Avkodningsalgoritmer används bland annat för felrättande kodning, där målet är att rätta fel som uppstår i överföringen eller lagringen, samt vid avkodning av komprimerade data och i vissa kryptografiska processer där dekryptering betraktas som en särskild form av avkodning.

Inom felrättning finns flera tekniker. Konventionella metoder inkluderar maximal-likelihood- eller minimum-distance-avkodning. Särskilda algoritmer används beroende på kodtyp: Viterbi-algoritmen för konvolutionella koder; BCJR-algoritmen för sannolikhetbaserad avkodning; belif propagation eller liknande iterativa metoder för LDPC-koder. Reed-Solomon-avkodning används i CDs, DVDs och vissa lagringsmedier. För binära eller textbaserade komprimeringsformat används ofta avkodningstekniker som Huffman eller LZ77.

Praktiska tillämpningar finns i mobil- och satellitkommunikation, digital TV, lagring och optiska medier, samt i moderna video- och ljuddekodare enligt relevanta standarder (till exempel MPEG och H.264). Effektiviteten hos en avkodningsalgoritm avgörs av felmodellen, krav på beräkningskomplexitet och den förväntade felhastigheten.

Se även: felrättande kodning, dekomprimering, dekryptering.