Decoding of Convolutional Codes

Blockschaltbild und Voraussetzungen

Ein wesentlicher Vorteil der Faltungscodierung ist, dass es hierfür mit dem Viterbi–Algorithmus ein sehr effizientes Decodierverfahren gibt. Dieser von Andrew J. Viterbi entwickelte Algorithmus wurde bereits im Kapitel 3.8 des Buches „Digitalsignalübertragung” im Hinblick auf seinen Einsatz zur Entzerrung im Detail beschrieben. Für seinen Einsatz als Faltungsdecodierer gehen wir von folgendem Blockschaltbild und den folgenden Voraussetzungen aus:

Die Informationssequenz u = (u₁, u₂, ...) ist hier im Gegensatz zur Beschreibung der linearen Blockcodes ⇒ Kapitel 1.5 oder von Reed–Solomon–Codes ⇒ Kapitel 2.4 im allgemeinen unendlich lang („semi–infinite”). Für die Informationssymbole gilt stets u_i ∈ {0, 1}.

Die Codesequenz x = (x₁, x₂, ...) mit x_i ∈ {0, 1} hängt außer von u auch noch von der Coderate R = 1/n, dem Gedächtnis m und der Übertragungsfunktionsmatrix G(D) ab. Bei endlicher Anzahl L an Informationsbits sollte der Faltungscode durch Anfügen von m Nullen terminiert werden:

\[\underline{u}= (u_1,\hspace{0.05cm} u_2,\hspace{0.05cm} ... \hspace{0.1cm}, u_L, \hspace{0.05cm} 0 \hspace{0.05cm},\hspace{0.05cm} ... \hspace{0.1cm}, 0 ) \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x}= (x_1,\hspace{0.05cm} x_2,\hspace{0.05cm} ... \hspace{0.1cm}, x_{2L}, \hspace{0.05cm} x_{2L+1} ,\hspace{0.05cm} ... \hspace{0.1cm}, \hspace{0.05cm} x_{2L+2m} ) \hspace{0.05cm}.\]

Die Empfangssequenz y = (y₁, y₂, ...) ergibt sich entsprechend dem angenommenen Kanalmodell. Bei einem digitalen Modell wie dem Binary Symmetric Channel (BSC) gilt y_i ∈ {0, 1}, so dass die Verfälschung von x auf y mit der Hamming–Distanz d_H (x, y) quantifiziert werden kann. Die erforderlichen Modifikationen für den AWGN–Kanal folgen auf Seite 6 dieses Kapitels.

Der nachfolgend beschriebene Viterbi–Algorithmus liefert eine Schätzung z für die Codesequenz x und eine weitere Schätzung υ für die Informationssequenz u. Dabei gilt:

\[{\rm Pr}(\underline{z} \ne \underline{x})\stackrel{!}{=}{\rm Minimum} \hspace{0.25cm}\Rightarrow \hspace{0.25cm} {\rm Pr}(\underline{\upsilon} \ne \underline{u})\stackrel{!}{=}{\rm Minimum} \hspace{0.05cm}.\]

Zusammenfassung : Der Viterbi–Algorithmus sucht bei einem digitalen Kanalmodell (zum Beispiel BSC) von allen möglichen Codesequenzen x' diejenige Sequenz z mit der minimalen Hamming–Distanz d_H(x', y) zur Empfangssequenz y:

\[\underline{z} = {\rm arg} \min_{\underline{x}' \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} d_{\rm H}( \underline{x}'\hspace{0.02cm},\hspace{0.02cm} \underline{y} ) = {\rm arg} \max_{\underline{x}' \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{y} \hspace{0.05cm}|\hspace{0.05cm} \underline{x}')\hspace{0.05cm}.\]

Das bedeutet auch: Der Viterbi–Algorithmus erfüllt das Maximum–Likelihood–Kriterium.

Vorbemerkungen zu den nachfolgenden Decodierbeispielen (1)

In den Beispielen dieses Kapitels wird stets von unserem Standard–Faltungscodierer der Rate R = 1/2, mit dem Gedächtnis m = 2 sowie der Übertragungsfunktionsmatrix G(D) = (1 + D + D², 1 + D²) ausgegangen. Die Länge der Informationssequenz sei L = 5 und unter Berücksichtigung der Terminierung L′ = 7. Die betrachteten Codesequenzen x und auch die Empfangssequenzen y setzen sich somit jeweils aus 14 Bit zusammen. Durch Aufteilung entsprechend y = ( y₁, y₂, ... , y₇) ergeben sich die Bitpaare y_i ∈ {00, 01, 10, 11}.

Die Viterbi–Decodierung erfolgt mit Hilfe des dargestellten Trellisdiagramms. Ein roter Pfeil steht für die Hypothese u_i = 0, ein blauer für u_i = 1. Um Verwechslungen zu vermeiden, versehen wir hypothetische Größen mit Apostroph. Auch dann, wenn wir sicher wissen, dass das Informationsbit u_i = 1 ist, gilt u_i' ∈ {0, 1}. Neben den Pfeilen steht die jeweilige hypothetische Codesequenz x_i' ∈ {00, 01, 10, 11}.

Wir gehen auf dieser und den nachfolgenden Seiten davon aus, dass die Viterbi–Decodierung auf der Hamming–Distanz d_H(x_i', y_i) zwischen dem Empfangswort y_i und den vier möglichen Codeworten x_i' ∈ {00, 01, 10, 11} basiert. Dann gehen wir wie folgt vor:

In den noch leeren Kreisen werden die Fehlergrößen Γ_i(S_μ) der Zustände S_μ (0 ≤ μ ≤ 3) zu den Zeitpunkten i eingetragen. Der Startwert ist stets Γ₀(S₀) = 0.

Die Fehlergrößen für i = 1 und i = 2 ergeben sich zu

\[{\it \Gamma}_1(S_0) \hspace{-0.15cm} = \hspace{-0.15cm} d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big ) \hspace{0.05cm}, \hspace{2.13cm}{\it \Gamma}_1(S_1) = d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_1 \big ) \hspace{0.05cm},\]

\[{\it \Gamma}_2(S_0) \hspace{-0.15cm} = \hspace{-0.15cm}{\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.4cm}{\it \Gamma}_2(S_1) = {\it \Gamma}_1(S_0)+ d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big ) \hspace{0.05cm},\]

\[{\it \Gamma}_2(S_2) \hspace{-0.15cm} = \hspace{-0.15cm}{\it \Gamma}_1(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big )\hspace{0.05cm}, \hspace{0.4cm}{\it \Gamma}_2(S_3) = {\it \Gamma}_1(S_1)+ d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_2 \big ) \hspace{0.05cm}.\]

Die Beschreibung wird auf der nächsten Seite fortgesetzt.

Vorbemerkungen zu den nachfolgenden Decodierbeispielen (2)

Fortsetzung der allgemeinen Viterbi–Beschreibung:

Ab dem Zeitpunkt i = 3 hat das Trellisdiagramm seine Grundform erreicht, und zur Berechnung aller Γ_i(S_μ) muss jeweils das Minimum zwischen zwei Summen ermittelt werden:

\[{\it \Gamma}_i(S_0) \hspace{-0.15cm} = \hspace{-0.15cm}{\rm Min} \left [{\it \Gamma}_{i-1}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},\]

\[{\it \Gamma}_i(S_1) \hspace{-0.15cm} = \hspace{-0.15cm}{\rm Min} \left [{\it \Gamma}_{i-1}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_2) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},\]

\[{\it \Gamma}_i(S_2) \hspace{-0.15cm} = \hspace{-0.15cm}{\rm Min} \left [{\it \Gamma}_{i-1}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_3) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm},\]

\[{\it \Gamma}_i(S_3) \hspace{-0.15cm} = \hspace{-0.15cm}{\rm Min} \left [{\it \Gamma}_{i-1}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{i-1}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} \underline{y}_i \big ) \right ] \hspace{0.05cm}.\]

Von den zwei an einem Knoten Γ_i(S_μ) ankommenden Zweigen wird der schlechtere (der zu einem größeren Γ_i(S_μ) geführt hätte) eliminiert. Zu jedem Knoten führt dann nur noch ein einziger Zweig.

Sind alle Fehlergrößen bis einschließlich i = 7 ermittelt, so kann der Viterbi–Algotithmus mit der Suche das zusammenhängenden Pfades vom Ende des Trellis ⇒ Γ₇(S₀) bis zum Anfang ⇒ Γ₀(S₀) abgeschlossen werden.

Durch diesen Pfad liegen dann die am wahrscheinlichsten erscheinende Codesequenz z und die wahrscheinlichste Informationssequenz υ fest. Nicht für alle Empfangssequenzen y gilt aber z = x und υ = u. Das heißt: Bei zu vielen Übertragungsfehlern versagt auch der Viterbi–Algorithmus.

Decodierbeispiel für den fehlerfreien Fall (1)

Zunächst gehen wir von der Empfangssequenz y = (11, 01, 01, 11, 11, 10, 11) aus, die hier – wegen der Codewortlänge n = 2 – bereits in Bitpaare y₁, ... , y₇ unterteilt ist.

Die eingetragenen Zahlenwerte und die verschiedenen Stricharten werden im folgenden Text erklärt:

Ausgehend vom Initialwert Γ₀(S₀) = 0 kommt man mit y₁ = (11) durch Addition der Hamming-Distanzen d_H ((00), y₁) = 2 bzw. d_H ((11), y₁) = 0 zu den Fehlergrößen Γ₁(S₀) = 2, Γ₁(S₁) = 0.

Im zweiten Decodierschritt gibt es Fehlergrößen für alle vier Zustände: Mit y₂ = (01) erhält man:

\[{\it \Gamma}_2(S_0) \hspace{-0.15cm} = \hspace{-0.15cm} {\it \Gamma}_1(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 2+1 = 3 \hspace{0.05cm},\]

\[{\it \Gamma}_2(S_1) \hspace{-0.15cm} = \hspace{-0.15cm} {\it \Gamma}_1(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 2+1 = 3 \hspace{0.05cm},\]

\[{\it \Gamma}_2(S_2) \hspace{-0.15cm} = \hspace{-0.15cm} {\it \Gamma}_1(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 0+2=2 \hspace{0.05cm},\]

\[{\it \Gamma}_2(S_3) \hspace{-0.15cm} = \hspace{-0.15cm} {\it \Gamma}_1(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) = 0+0=0 \hspace{0.05cm}.\]

In allen weiteren Decodierschritten müssen jeweils zwei Werte verglichen werden, wobei dem Knoten Γ_i(S_μ) stets der kleinere Wert zugewiesen wird. Beispielsweise gilt für i = 3 mit y₃ = (01):

\[{\it \Gamma}_3(S_0) \hspace{-0.15cm} = \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{2}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =\]

\[ \hspace{1.2cm} = \hspace{-0.15cm}{\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] = 3\hspace{0.05cm},\]

\[{\it \Gamma}_3(S_3) \hspace{-0.15cm} = \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{2}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm}, \hspace{0.2cm}{\it \Gamma}_{2}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] =\]

\[ \hspace{1.2cm} = \hspace{-0.15cm}{\rm min} \left [ 3+0\hspace{0.05cm},\hspace{0.05cm} 0+2 \right ] = 2\hspace{0.05cm}.\]

Ab i = 6 wird im betrachteten Beispiel die Terminierung des Faltungscodes wirksam. Hier sind nur noch zwei Vergleiche zur Bestimmung von Γ₆(S₀) und Γ₆(S₂) anzustellen, und für i = 7 nur noch ein Vergleich mit dem Endergebnis Γ₇(S₀).

Von den jeweils zwei an einem Knoten ankommenden Zweigen wird stets nur derjenige bei der abschließenden Pfadsuche herangezogen, der zur minimalen Fehlergröße Γ_i(S_μ) geführt hat. Die „schlechten” Zweige werden verworfen. Sie sind in obiger Grafik jeweils punktiert dargestellt.