BCJRalgoritmen

BCJR-algoritmen, opkaldt efter Bahl, Cocke, Jelinek og Raviv, er en forward-backward algoritme til beregning af a posteriori sandsynligheder for transmitterede symboler i digitale kommunikationssystemer, der anvender en trellis, som konvolutionskoder og turbo-koder. Den giver soft outputs og er optimal i MAP-sammenhæng for en given trellis.

Algoritmen deles i tre dele: en fremadrettet rekursion (alpha), en bagudrettet rekursion (beta) og en gren-metrik (gamma) der beskriver overgang mellem tilstande og den tilhørende emission. Alpha beregner sandsynligheden for at nå en tilstand ved et bestemt tidspunkt givet tidligere symboler; beta beregner sandsynligheden for resten af koden givet den nuværende tilstand. Gamma beskriver overgangssandsynligheden sammen med den observerede emissionssymbol. Ved slutningen kombineres alpha, beta og gamma til posterior sandsynligheder for hvert bit eller symbol, og log-likelihood-ratioer (LLR) beregnes som ratioen mellem posterior sandsynligheder for bit 1 og bit 0.

Anvendelser omfatter SISO-dekodning af konvolutionskoder og turbo-decoding, hvor BCJR producerer soft outputs til iterative decodere. Algoritmen bruges også i forlængelse af kanalekvilisering og generel iterativ dekoding, hvor informationen flyder mellem komponentdecodere.

Kompleksitet og variantor: beregningerne skalerer med antallet af tilstande og symboler og er ofte O(n S^2) pr. trin, hvor S er antal tilstande. For numerisk stabilitet anvendes log-domain-implementering, og max-log-MAP er en tilnærmingsvariant der reducerer beregningen ved at erstatte summeringer med max-operationer.

Historie: BCJR-algoritmen blev publiceret i 1974 af Bahl, Cocke, Jelinek og Raviv og har været central i udviklingen af effektive decodere for konvolutionskoder og turbo-koder.