Code Description with State and Trellis Diagram

Zustandsdefinition für ein Speicherregister (1)

Ein Faltungscodierer kann auch als Automat mit endlicher Anzahl von Zuständen aufgefasst werden. Die Zustandsanzahl ergibt sich dabei aus der Zahl der Speicherelemente ⇒ Gedächtnis m zu 2^m.

Im Kapitel 3.3 gehen wir meist vom gezeichneten Faltungscodierer aus, der durch folgende Kenngrößen charakterisiert wird:

k = 1, n = 2 ⇒ Coderate R = 1/2,

Gedächtnis m = 2 ⇒ Einflusslänge ν = 3,

Übertragungsfunktionsmatrix in Oktalform (7, 5) ⇒ G(D) =(1 + D + D², 1 + D²).

Die Codesequenz zum Zeitpunkt i ⇒ x_i = (x_i⁽¹⁾, x_i⁽²⁾) hängt außer vom Informationsbit u_i auch vom Inhalt (u_i_–1, u_i_–2) des Speichers ab. Hierfür gibt es 2^m = 4 Möglichkeiten, die man als die Zustände S₀, S₁, S₂ und S₃ bezeichnet. Der Registerzustand S_μ sei dabei über den Index definiert:

\[\mu = u_{i-1} + 2 \cdot u_{i-2}\hspace{0.05cm}, \hspace{0.5cm}{\rm allgemein\hspace{-0.1cm}:}\hspace{0.15cm} \mu = \sum_{l = 1}^{m} \hspace{0.1cm}2\hspace{0.03cm}^{l-1} \cdot u_{i-l} \hspace{0.05cm}.\]

Im Englischen verwendet man für „Zustand” den Begriff State. Entsprechend ist auch im deutschen Text manchmal vom Registerstatus die Rede.

Um Verwechslungen zu vermeiden, unterscheiden wir im Weiteren durch Groß– bzw. Kleinbuchstaben:

die möglichen Zustände S_μ mit den Indizes 0 ≤ μ ≤ 2^m – 1,

die aktuellen Zustände s_i zu den Zeitpunkten i = 1, 2, 3, ....

Auf der nächsten Seite verdeutlichen wir die Zustände an einem Beispiel.

Zustandsdefinition für ein Speicherregister (2)

: Die folgende Grafik zeigt für obigen Faltungscodierer jeweils den Beginn (i ≤ 15)

der Informationssequenz u ⇒ Informationsbits u_i,

der aktuellen Zustände s_i ∈ {S₀, S₁, S₂, S₃} zu den Zeitpunkten i, sowie

der jeweiligen Codesequenzen x_i = (x_i⁽¹⁾, x_i⁽²⁾).

Die Farbkennzeichnungen sollen den Übergang zu den nachfolgenden Grafiken auf den nächsten Seiten erleichtern. Man erkennt aus obiger Darstellung beispielsweise:

Zum Zeitpunkt i = 5 gilt u_i_–1 = u₄ = 0, u_i_–2 = u₃ = 1. Das heißt, der Automat befindet sich im Zustand s₅ = S₂. Mit dem Informationsbit u_i = u₅ = 0 erhält man die Codesequenz x₅ = (11).

Der Zustand für den Zeitpunkt i = 6 ergibt sich aus u_i_–1 = u₅ = 0 und u_i_–2 = u₄ = 0 zu s₆ = S₀. Wegen u₆ = 0 wird nun x₆ = (00) ausgegeben und der neue Zustand s₇ ist wiederum S₀.

Auch zum Zeitpunkt i = 12 wird wegen u₁₂ = 0 die Codesequenz x₁₂ = (11) ausgegeben und man geht vom Zustand s₁₂ = S₂ in den Zustand s₁₃ = S₀ über.

Dagegen wird zum Zeitpunkt i = 9 die Codesequenz (00) ausgegeben und auf s₉ = S₂ folgt s₁₀ = S₁. Gleiches gilt auch für i = 15. In beiden Fällen lautet das aktuelle Informationsbit u_i = 1.

Aus diesem Beispiel ist zu erkennen, dass die Codesequenz x_i zum Zeitpunkt i allein

vom aktuellen Zustand s_i = S_μ (0 ≤ μ ≤ 2^m – 1), sowie

vom aktuellen Informationsbit u_i

abhängt. Ebenso wird der Nachfolgezustand s_i₊₁ allein durch s_i und u_i bestimmt. Diese Eigenschaften werden im so genannten Zustandsübergangsdiagramm auf der nächsten Seite berücksichtigt.

Darstellung im Zustandsübergangsdiagramm (1)

Die Grafik zeigt das Zustandsübergangsdiagramm (englisch: State Transition Diagram) für unseren Standardcodierer. Dieses liefert alle Informationen über den (n = 2, k = 1, m = 2)–Faltungscodierer in kompakter Form. Die Farbgebung ist mit der sequenziellen Darstellung auf der vorherigen Seite abgestimmt. Der Vollständigkeit halber ist auch die Herleitungstabelle nochmals angegeben.

Die 2^m⁺^k Übergänge sind mit „u_i | x_i” beschriftet. Beispielsweise ist abzulesen:

Durch das Informationsbit u_i = 0 (gekennzeichnet durch eine rote Beschriftung) gelangt man vom Zustand s_i = S₁ zum Zustand s_i₊₁ = S₂ und die beiden Codebits lauten x_i⁽¹⁾ = 1, x_i⁽²⁾ = 0.

Mit dem Informationsbit u_i = 1 (blaue Beschriftung) im Zustand s_i = S₁ ergeben sich dagegen die Codebits zu x_i⁽¹⁾ = 0, x_i⁽²⁾ = 1, und man kommt zum neuen Zustand s_i₊₁ = S₃.

Die Struktur des Zustandsübergangsdiagramms ist allein durch die Parameter m und k festgelegt:

Die Anzahl der Zustände ist 2^{m · k}.

Von jedem Zustand gehen 2^k Pfeile ab.

Ein weiteres Beispiel folgt auf der nächsten Seite.

Darstellung im Zustandsübergangsdiagramm (2)

Die obere Grafik zeigt nochmals das Zustandsübergangsdiagramm für unseren Standardcodierer. Dieses dient lediglich als Vergleichsgrundlage für das nachfolgende Beispiel.

Die untere Grafik gilt für einen systematischen Code, ebenfalls mit den Kenngrößen n = 2, k = 1, m = 2. Es handelt sich um die äquivalente systematische Repräsentation des obigen Codierers. Man bezeichnet diesen auch als RSC–Codierer (englisch: Recursive Systematic Convolutional Encoder).

Gegenüber dem oberen Zustandsübergangsdiagramm erkennt man folgende Unterschiede:

Da die früheren Informationsbits u_i_–1 und u_i_–2 nicht abgespeichert werden, beziehen sich hier die Zustände s_i = S_μ auf die verarbeiteten Größen w_i_–1 und w_i_–2, wobei w_i = u_i + w_i_–1 + w_i_–2 gilt.

Da dieser Code systematisch ist, gilt x_i⁽¹⁾ = u_i. Die Herleitung der zweiten Codebits x_i⁽²⁾ finden Sie in Aufgabe A3.5. Es handelt sich um ein rekursives Filter, wie in Kapitel 3.2 beschrieben.

Der Bildervergleich zeigt, dass sich für beide Codierer ein ähnliches Zustandsübergangsdiagramm ergibt:

Man gelangt von jedem Zustand s_i ∈ {S₀, S₁, S₂,S₃} zu den gleichen Nachfolgezuständen s_i₊₁.

Ein Unterschied besteht hinsichtlich der ausgegebenen Codesequenzen x_i ∈ {00, 01, 10, 11}.

Darstellung im Trellisdiagramm (1)

Man kommt vom Zustandsübergangsdiagramm zum so genannten Trellisdiagramm (oder kurz: Trellis), indem man zusätzlich eine Zeitkomponente ⇒ Laufvariable i berücksichtigt. Die folgende Grafik stellt die beiden Diagramme für unseren Standardcodierer (n = 2, k = 1, m = 2) gegenüber.

Die untere Darstellung hat Ähnlichkeit mit einem Gartenspalier – etwas Phantasie vorausgesetzt. Die englische Übersetzung hierfür ist „Trellis”. Weiter ist anhand dieser Grafik zu erkennen:

Da alle Speicherregister mit Nullen vorbelegt sind, startet das Trellis stets vom Zustand s₁ = S₀. Zum nächsten Zeitpunkt (i = 2) sind dann nur die beiden Zustände S₀ und S₁ möglich.

Ab dem Zeitpunkt i = m + 1 = 3 hat das Trellis für jeden Übergang von s_i nach s_i₊₁ genau das gleiche Aussehen. Jeder Zustand S_μ ist durch einen roten Pfeil (u_i = 0) und einen blauen Pfeil (u_i = 1) mit einem Nachfolgezustand verbunden.

Gegenüber einem Codebaum, der mit jedem Zeitschritt i exponentiell anwächst – siehe zum Beispiel Kapitel 3.8, Seite 2a im Buch „Digitalsignalübertragung” – ist hier die Zahl der Knoten (also der möglichen Zustände) auf 2^m begrenzt.

Diese erfreuliche Eigenschaft eines jeden Trellisdiagramms nutzt auch der Viterbi–Algorithmus zur effizienten Maximum–Likelihood–Decodierung von Faltungscodes.

Darstellung im Trellisdiagramm (2)

Das folgende Beispiel soll zeigen, dass zwischen der Aneinanderreihung der Codesequenzen x_i und den Pfaden durch das Trellisdiagramm eine 1:1–Zuordnung besteht. Auch die Informationssequenz u ist aus dem ausgewählten Trellispfad anhand der Farben der einzelnen Zweige ablesbar. Ein roter Zweig steht für das Informationsbit u_i = 0, ein blauer für u_i = 1.

: Auf der ersten Seite dieses Abschnitts wurde für unseren Rate–1/2–Standardcodierer mit Gedächtnis m = 2 sowie die Informationssequenz u = (1, 1, 1, 0, 0, 0, 1, 0, 1, ...) die Codesequenz x hergeleitet, die in nachfolgender Tabelle für i ≤ 9 nochmals angegeben ist.

Darunter gezeichnet ist das Trellisdiagramm. Man erkennt:

Der ausgewählte Pfad durch das Trellis ergibt sich durch die Aneinanderreihung roter und blauer Pfeile, die für die möglichen Informationsbits u_i = 0 bzw. u_i = 1 stehen. Diese Aussage gilt für jeden Rate–1/n–Faltungscode. Bei einem Code mit k > 1 gäbe es 2^k verschiedenfarbige Pfeile.

Bei einem Rate–1/n–Faltungscode sind die Pfeile mit den Codeworten x_i = (x_i⁽¹⁾, ... , (x_i⁽ⁿ⁾) beschriftet, die sich aus dem Informationsbit u_i und den aktuellen Registerzuständen s_i ergeben. Für n = 2 gibt es nur vier mögliche Codeworte, nämlich 00, 01, 10 und 11.

In vertikaler Richtung erkennt man aus dem Trellis die möglichen Registerzustände S_μ. Bei einem Rate–k/n–Faltungscode mit der Gedächtnisordnung m gibt es 2^{k · m} verschiedene Zustände. Im vorliegenden Beispiel (k = 1, m = 2) sind dies nur die Zustände S₀, S₁, S₂ und S₃.