BCJRAlgorithmus

Der BCJR-Algorithmus (benannt nach Bahl, Cocke, Jelinek und Raviv) ist ein Soft-Output-Decoder für konvolutionale Codes. Er berechnet die a posteriori Wahrscheinlichkeit (APP) jeder symbolischen Übertragung gegeben das gesamte empfangene Signal Y. Im Gegensatz zum Viterbi-Algorithmus liefert BCJR vollständige Wahrscheinlichkeitsverteilungen statt eines einzelnen Pfades, wodurch Soft-Entscheidungen möglich sind und sich der Decoder in iterativen Verfahren einsetzen lässt.

Grundlage ist die Trellisdarstellung des Codes mit Zuständen S_k und Übergängen zwischen aufeinanderfolgenden Zeiten. Es werden drei Typen von Wahrscheinlichkeiten eingeführt: α_k(s) als Vorwärtsmaß (P(S_k = s, Y_1^k)), β_k(s) als Rückwärtsmaß (P(Y_{k+1}^N | S_k = s)) und γ_k(s, s') als Grenz-/Branch-Wahrscheinlichkeit des Übergangs von S_{k-1} = s nach S_k = s' unter Berücksichtigung des beobachteten Signals. Die Vorwärtsrekursion lautet α_k(s') = Σ_s α_{k-1}(s) γ_k(s, s'), die Rückwärtsrekursion β_k(s) = Σ_{s'} γ_k(s, s') β_{k+1}(s'). Die a-posteriori-Wahrscheinlichkeit für ein Symbol X_k lässt sich aus α, γ und β ableiten: P(X_k = x | Y) ∝ Σ_{s,s'} α_{k-1}(s) γ_k(s, s') β_k(s'), wobei für binäre Quellen typischerweise der LLR-Löser verwendet wird.

Komplexität und Anwendung: Der Algorithmus arbeitet typischerweise mit O(N S^2) Zeit und O(S) Speicher pro Stufe, wobei N die Sequenzlänge und S die Anzahl der Zustände des Trellis ist. BCJR liefert Soft-Outputs, ist zentral in Turbo-Decodern (mit Interleaving) und wird auch in Soft-Input-Soft-Output-Verarbeitung von Kanälen und in der MAP-Entzerrung eingesetzt. Historisch ist er eine MAP-Variante des Baum-Welch-Frameworks für Hidden-Markov-Modelle.