Der BCJR-Algorithmus, die Bezeichnung leitet sich von den Initialen der Entwickler L. Bahl, J. Cocke, F. Jelinek und J. Raviv ab, wurde 1974 in der Nachrichtentechnik 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

Bearbeiten

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   das  -te Nachrichtenbit und   die Empfangssequenz (Beobachtung). Die a posteriori LLR für   ist definiert als

 

Die Maximum a posteriori (MAP) Entscheidung für   am Empfänger ergibt sich als

 

Im Allgemeinen müsste man zur Berechnung des Zählers bzw. Nenners der LLR nun jedes Codewort betrachten, bei dem   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  .

Sei   der Ausgangszustand des Trellis vor dem Bit   und   der Folgezustand. Die Menge   bezeichne nun alle Zustandsübergänge  , bei dem   gilt, und   entsprechend alle Zustandsübergänge   mit  . Damit lässt sich die obige Formel folgendermaßen umschreiben:

 

Durch eine Faktorisierung der auftretenden Wahrscheinlichkeitsdichtefunktion   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

Bearbeiten

Aus der Betrachtung des Trellis lässt sich die Faktorisierung   herleiten, wobei gilt:  

Die Berechnungsschritte des BCJR-Algorithmus sind folgende:

  1. Vorwärtsrekursion  , beginnend mit  
  2. Rückwärtsrekursion  , beginnend mit   Hierbei geht man davon aus, dass der Encoder wieder in den Ausgangszustand "0" zurückkehrt.
  3. Berechnung der Verbundwahrscheinlichkeiten   und daraus   (siehe oben).

Die Werte für   berechnen sich direkt aus den a priori Wahrscheinlichkeiten (Auftrittshäufigkeiten) für   und der Kanalübergangswahrscheinlichkeitsverteilung als  .

BCJR-Algorithmus mit Log-Wahrscheinlichkeiten

Bearbeiten

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]:

 

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

  1. Vorwärtsrekursion  , beginnend mit  
  2. Rückwärtsrekursion  , beginnend mit  
  3. Berechnung der MAP-LLR  

Hierbei ist   die sogenannte Kantenmetrik, die sich direkt aus der empfangenen Sequenz   ergibt.

Einzelnachweise

Bearbeiten
  1. L. Bahl, J. Cocke, F. Jelinek, J. Raviv: Optimal Decoding of Linear Codes for minimizing symbol error rate. In: IEEE Transactions on Information Theory. Band 20, Nr. 2, März 1974, S. 284–287.
  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.
Bearbeiten