BCJR-Algorithmus

Der BCJR-Algorithmus, die Bezeichnung leitet sich von den Initialen der Entwickler L. Bahl, J. Cocke, F. Jelinek und J. Raviv ab, wurde 1974 zur Dekodierung von Block- und Faltungscodes entwickelt. Im Gegensatz zum Viterbi-Algorithmus, der die wahrscheinlichste Sequenz (maximum likelihood sequence decoding, MLSD) berechnet, ist der BCJR-Algorithmus im Sinne der minimalen Symbolfehlerwahrscheinlichkeit optimale Dekodieralgorithmus (maximum a posteriori probability, MAP). Daher wird er insbesondere bei der iterativen Dekodierung von parallel oder seriell verketteten Faltungs- oder Blockcodes wie den Turbo-Codes eingesetzt. Er spielt daher eine wichtige Rolle in der Implementierung von Dekodierern für die Mobilfunkstandards UMTS und Long Term Evolution (LTE), die zur Fehlerschutzcodierung Turbo-Codes verwenden.

Der Vorteil des BCJR-Algorithmus zur Dekodierung von Faltungscodes mittels so genannter Soft-Decision besteht in der effizienten Ausnutzung der Information über die Verbundwahrscheinlichkeiten von aufeinander folgenden Codesymbolen (typischerweise Bits). Er kann ebenso wie der Viterbi-Algorithmus in Form eines Trellis-Diagrammes grafisch dargestellt werden. Neben der Anwendung in der Dekodierung kann der BCJR-Algorithmus auch in der Berechnung von allgemeinen Markow-Ketten verwendet werden.

Grundidee

Ziel der Berechnung ist eine a posteriori Log-Likelihood-Ratio (LLR) für jedes Nachrichtenbit, also das (log-)Verhältnis der Wahrscheinlichkeiten, dass das Bit am Empfänger zu 0 bzw. 1 entschieden wird. Sei $u_{l}$ das $l$-te Nachrichtenbit und $\mathbf {y}$ die Empfangssequenz (Beobachtung). Die a posteriori LLR für $u_{l}$ ist definiert als

$$L(u_{l})=\log \left({\frac {P(u_{l}=0|\mathbf {y} )}{P(u_{l}=1|\mathbf {y} )}}\right)$$

Die Maximum a posteriori (MAP) Entscheidung für $u_{l}$ am Empfänger ergibt sich als

$${\hat {u}}_{l}=\arg \max _{u_{l}}P(u_{l}|\mathbf {y} )={\begin{cases}0&{\text{wenn }}L(u_{l})\geq 0\\1&{\text{wenn }}L(u_{l})<0\end{cases}}$$

Im Allgemeinen müsste man zur Berechnung des Zählers bzw. Nenners der LLR nun jedes Codewort betrachten, bei dem $u_{l}=0$ bzw. $u_{l}=1$ ist. Dies ist für praktische Codes nicht realisierbar, da die Anzahl der Codeworte exponentiell mit der Codewortlänge skaliert. Der Trick des BCJR-Algorithmus liegt nun darin, auf dem Trellis des Codes zu operieren. Der Trellis berücksichtigt die Eigenschaft, dass Codeworte sich aus denselben Teilen zusammensetzen, also Kanten mehrfach benutzt werden. Dadurch reduziert sich der Berechnungsaufwand zu Zustands- und Zustandsübergangswahrscheinlichkeiten. Dies ist insbesondere bei Faltungscodes vorteilhaft, da hier die Anzahl der Zustände des Trellis direkt über die Länge des Schieberegisters festgelegt ist und daher unabhängig von der Codewortlänge ist. Die Komplexität des Algorithmus wächst daher linear mit der Nachrichtenlänge $L$.

Sei $s'=s_{l-1}$ der Ausgangszustand des Trellis vor dem Bit $u_{l}$ und $s=s_{l}$ der Folgezustand. Die Menge $U_{0}$ bezeichne nun alle Zustandsübergänge $(s',s)$, bei dem $u_{l}=0$ gilt, und $U_{1}$ entsprechend alle Zustandsübergänge $(s',s)$ mit $u_{l}=1$. Damit lässt sich die obige Formel folgendermaßen umschreiben:

$$L(u_{l})=\log \left({\frac {\sum _{(s',s)\in U_{0}}p(s_{l}=s',s_{l}=s,\mathbf {y} )}{\sum _{(s',s)\in U_{1}}p(s_{l}=s',s_{l}=s,\mathbf {y} )}}\right)$$

Durch eine Faktorisierung der auftretenden Wahrscheinlichkeitsdichtefunktion $p(s',s',\mathbf {y} )$ lässt sich die obige Gleichung effizient über eine Vorwärts- und eine Rückwärtsrekursion über den Trellis effizient berechnen. Daher wird der BCJR-Algorithmus auch Vorwärts-Rückwärts-Algorithmus genannt.

BCJR-Algorithmus mit Wahrscheinlichkeiten

Aus der Betrachtung des Trellis lässt sich die Faktorisierung $p(s',s,\mathbf {y} )=\alpha _{l-1}(s')\gamma _{l}(s',s)\beta _{l}(s)$ herleiten, wobei gilt:

$${\begin{aligned}\alpha _{l}(s)&=p(s_{l}=s,\mathbf {y} _{1:l})\\\gamma _{l}(s',s)&=p(s_{l}=s,y_{l}|s_{l-1}=s')\\\beta _{l}(s)&=p(\mathbf {y} _{l+1:L}|s_{l}=s)\\\end{aligned}}$$

Die Berechnungsschritte des BCJR-Algorithmus sind folgende:

1. Vorwärtsrekursion $\alpha _{l}(s)=\sum _{s'}\gamma _{l}(s',s)\alpha _{l-1}(s')$, beginnend mit $\alpha _{0}(s)={\begin{cases}1,&s=0\\0,&s\neq 0\end{cases}}$
2. Rückwärtsrekursion $\beta _{l-1}(s')=\sum _{s}\beta _{l}(s)\gamma _{l}(s',s)$, beginnend mit $\beta _{L}(s)={\begin{cases}1,&s=0\\0,&s\neq 0\end{cases}}$ Hierbei geht man davon aus, dass der Encoder wieder in den Ausgangszustand "0" zurückkehrt.
3. Berechnung der Verbundwahrscheinlichkeiten $p(s',s,\mathbf {y} )=\alpha _{l-1}(s')\gamma _{l}(s',s)\beta _{l}(s)$ und daraus $L(u_{l})$ (siehe oben).

Die Werte für $\gamma _{l}(s',s)=P(u_{l})p(y_{l}|u_{l})$ berechnen sich direkt aus den a priori Wahrscheinlichkeiten (Auftrittshäufigkeiten) für $u_{l}$ und der Kanalübergangswahrscheinlichkeitsverteilung als $\gamma _{l}(s',s)=P(u_{l})p(y_{l}|u_{l})$.

BCJR-Algorithmus mit Log-Wahrscheinlichkeiten

Berechnungen mit Wahrscheinlichkeiten können bei der Implementierung zu numerischer Instabilität führen, da die rekursiven Produkte nach wenigen Schritten zu Werten nahe 0 konvergieren. Ebenso sind Multiplikationen recht aufwändige Operationen, die in Hardware-Implementierungen von beispielsweise LTE-Modems auf Grund ihrer Komplexität vermieden werden. Aus diesen Grund wird der BCJR-Algorithmus meistens in der Log-Domäne implementiert, diese Variante wird auch als Log-MAP-Algorithmus bezeichnet. Multiplikationen werden zu den wesentlich einfacheren Additionen, während Additionen mit der sogenannten max-Star Operation berechnet werden. Diese lässt sich folgendermaßen formulieren:

$$\operatorname {max} ^{*}(x,y)=\log(e^{x}+e^{y})=\max(x,y)+\log(1+e^{-|x-y|})$$

Der BCJR-Algorithmus in der Log-Domäne berechnet sich also wie folgt:

1. Vorwärtsrekursion ${\tilde {\alpha }}_{l}(s)=\operatorname {max*} _{s'}\left({\tilde {\alpha }}_{l-1}(s')+{\tilde {\gamma }}_{l}(s',s)\right)$, beginnend mit ${\tilde {\alpha }}_{0}(s)={\begin{cases}0,&s=0\\-L_{\mathrm {max} },&s\neq 0\end{cases}}$
2. Rückwärtsrekursion ${\tilde {\beta }}_{l-1}(s')=\operatorname {max*} _{s}\left({\tilde {\beta }}_{l}(s)+{\tilde {\gamma }}_{l}(s',s)\right)$, beginnend mit ${\tilde {\beta }}_{L}(s)={\begin{cases}0,&s=0\\-L_{\mathrm {max} },&s\neq 0\end{cases}}$
3. Berechnung der MAP-LLR ${\begin{aligned}L(u_{l})=&\operatorname {max*} _{(s',s)\in U_{0}}\left({\tilde {\alpha }}_{l-1}(s')+{\tilde {\gamma }}_{l}(s',s)+{\tilde {\beta }}_{l}(s)\right)\\&-\operatorname {max*} _{(s',s)\in U_{1}}\left({\tilde {\alpha }}_{l-1}(s')+{\tilde {\gamma }}_{l}(s',s)+{\tilde {\beta }}_{l}(s)\right)\end{aligned}}$

Hierbei ist ${\tilde {\gamma }}_{l}(s',s)=\log P(u_{l})+\log p(y_{l}|u_{l})$ die sogenannte Kantenmetrik, die sich direkt aus der empfangenen Sequenz $\mathbf {y}$ ergibt.

Weblinks

• Online Lehrbuch: Information Theory, Inference, and Learning Algorithms, von David J. C. MacKay; Kapitel 25 (englisch)