Viterbidekodning

Viterbidekodning är en felkorrigerande kodningsteknik som används inom digital kommunikation. Den bygger på konvolutionella koder där varje ingående bit blandas med tidigare bitar i ett minne för att producera flera utgående kodbitar. Kodens egenskaper bestäms av minneslängden och generatorpolynom; vanliga upplägg är koder med kodhastighet cirka 1/2 eller 1/3, där minneslängden är K = m+1. Koden kan beskrivas med polynom i modul-2 aritmetik via shift-register.

Avkodningen av Viterbidekodade signaler görs med Viterbi-algoritmen, som uppnår maximal chans att återge den sanna bitsekvensen. Algoritmen bygger en trellis över kodens tillstånd (antalet tillstånd är 2^m där m är minneslängden). Varje övergång mellan tillstånd associeras med en grenmetrik baserad på de mottagna symbolerna. Genom dynamisk programmering uppdateras vägmetrikerna och de överlevande vägarna sparas. Efter bearbetning av hela sekvensen rekonstrueras den mest sannolikt sända bitsekvensen via backtrace eller genom att följa pointers. Detta gör Viterbi-avkodningen optimal i betydelsen maximal sannolikhet under antaget vattenfalls-aktiga brusmiljöer.

Kompakthet och prestanda kräver balansering mellan minneslängd, kodhastighet och beräkningsresurser. Complexiteten ökar med minneslängden, vilket påverkar både hårdvaru- och mjukvaruimplementationer. I praktiken används ofta interleaving och kombinationer med andra felkorrigeringsstrukturer för att hantera burstfel i kanalen.

Historia och användning: Algoritmen introducerades av Andrew Viterbi 1967 och har sedan dess varit en grundläggande del av många kommunikationsstandarder och modem, särskilt där konvolutionella koder används för felkorrigering. Viterbidekodning har fortsatt att spela en roll även när nya kodningsscheman utvecklats, ofta som en robust och välbeprövad del av felkorrigering i olika länkar och system.