Dekodningsalgoritmer

Dekodningsalgoritmer er metoder til at rekonstruere oprindelig data fra en kode eller fra data, der er udsat for støj og fejl. De anvendes inden for telekommunikation, lagring og datakompression og kan omfatte både fejlfinding og dekodning af kompakt eller omkodet information. Formålet er at opnå korrekt eller højst sandsynlig original besked.

I fejlkorrektionskoder anvendes dekodningsalgoritmer til at bestemme den mest sandsynlige oprindelige besked fra de modtagne symboler. Eksempelvis anvendes Viterbi-dekodning for konvolutionelle koder, BCJR-algoritmen til MAP-dekodning og iterativ dekodning baseret på belief propagation til LDPC- og turbo-koder. Disse metoder afvejer sandsynlighed, kompleksitet og latenstid og kan arbejde med soft-decision-informationer fra modtagelsen.

I datakompression dekoder dekodningsalgoritmerne det modtagne kodedata tilbage til ufortrængt information. Almindelige teknikker er Huffman-dekodning, aritmetisk dekodning og LZ77/LZ78-dekodning. Disse metoder kræver ofte kendskab til den anvendte kodning og træk ved datastrukturen for at rekonstruere den oprindelige bitstrøm.

I lagrings- og transmissionsmiljøer anvendes også fejlkorrektionskoder som Reed-Solomon-dekodning og BCH-dekodning for at rette fejl i fysiske medier og datafiler. Reed-Solomon-dekodning kan benytte Berlekamp–Madde-algoritmen og beslægtede teknikker til at identificere og korrigere fejl inden for et bestemt antal symboler.

Praktiske overvejelser omfatter beregningskompleksitet, latens og implementeringsmiljøer (hardware versus software). Valget af algoritme afhænger af kodenype, kanalens støjprofil, krav til ydeevne og rammebetingelser som realtid og strømforbrug.