BCJR-Algorithmus

aus Wikipedia, der freien Enzyklopädie

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[1]. 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 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} das 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} -te Nachrichtenbit 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 \mathbf{y}} die Empfangssequenz (Beobachtung). Die a posteriori LLR für 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. 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 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} .

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 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 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_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 herleiten, wobei gilt: 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 \begin{align} \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{align}}

Die Berechnungsschritte des BCJR-Algorithmus sind folgende:

  1. Vorwärtsrekursion 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 \alpha_l(s) = \sum_{s'}\gamma_l(s',s)\alpha_{l-1}(s')} , beginnend mit
  2. Rückwärtsrekursion 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 \beta_{l-1}(s') = \sum_s \beta_l(s) \gamma_l (s',s)} , beginnend 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 \beta_L(s) =\begin{cases}1,&s=0\\0,&s\neq0\end{cases}} Hierbei geht man davon aus, dass der Encoder wieder in den Ausgangszustand "0" zurückkehrt.
  3. Berechnung der Verbundwahrscheinlichkeiten 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}) = \alpha_{l-1}(s')\gamma_l(s',s)\beta_l(s)} und daraus 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)} (siehe oben).

Die Werte 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 \gamma_l (s',s) = P(u_l) p(y_l|u_l)} berechnen sich direkt aus den a priori Wahrscheinlichkeiten (Auftrittshäufigkeiten) für und der Kanalübergangswahrscheinlichkeitsverteilung 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 \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[2]:

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 \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:[3]

  1. Vorwärtsrekursion 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 \tilde{\alpha}_l(s)=\operatorname{max*}_{s'} \left( \tilde{\alpha}_{l-1} (s') + \tilde{\gamma}_l (s',s) \right)} , beginnend 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 \tilde{\alpha}_0(s) =\begin{cases}0,&s=0\\-L_\mathrm{max},&s\neq0\end{cases}}
  2. Rückwärtsrekursion 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 \tilde{\beta}_{l-1} (s')=\operatorname{max*}_{s} \left( \tilde{\beta}_{l} (s) + \tilde{\gamma}_l (s',s) \right)} , beginnend 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 \tilde{\beta}_L(s) =\begin{cases}0,&s=0\\-L_\mathrm{max},&s\neq0\end{cases}}
  3. Berechnung der MAP-LLR 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 \begin{align}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{align}}

Hierbei ist 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 \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 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 \mathbf{y}} ergibt.

Einzelnachweise

  1. ↑ L. Bahl, J. Cocke, F. Jelinek, und J. Raviv: Optimal Decoding of Linear Codes for minimizing symbol error rate, erschienen in IEEE Transactions on Information Theory, Ausgabe IT-20(2), Seite 284 bis 287, März 1974.
  2. ↑ J. Hagenauer, E. Offer, L. Papke: Iterative decoding of binary block and convolutional codes. In: IEEE Transactions on Information Theory. Band 42, Nr. 2, März 1996, S. 429–445, doi:10.1109/18.485714 (ieee.org [abgerufen am 28. Oktober 2020]).
  3. ↑ S. Lin, W. E. Ryan: Channel codes: Classical and Modern. Cambridge University Press, Cambridge 2009, ISBN 978-0-521-84868-8.

Weblinks

Abgerufen von „https://de.wikiup.org/index.php?title=BCJR-Algorithmus&oldid=215188355“