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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l} ist definiert als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l} am Empfänger ergibt sich als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{u}_l = \arg \max_{u_l} P(u_l|\mathbf{y})=\begin{cases}0 &\text{wenn }L(u_l)\ge0\\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l=0} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s' = s_{l-1}} der Ausgangszustand des Trellis vor dem Bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s=s_l} der Folgezustand. Die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U_0 } bezeichne nun alle Zustandsübergänge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (s',s)} , bei dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l=0} gilt, und $U_{1}$ entsprechend alle Zustandsübergänge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (s',s)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l=1} . Damit lässt sich die obige Formel folgendermaßen umschreiben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle p(s',s,\mathbf {y} )=\alpha _{l-1}(s')\gamma _{l}(s',s)\beta _{l}(s)} herleiten, wobei gilt: Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \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)