Viterbi Receiver

From LNTwww

Blockschaltbild und Voraussetzungen für Kapitel 3.8 (1)


Der Korrelationsempfänger ist im Sinne der Maximum–Likelihood–Entscheidungsregel optimal, das heißt, er führt bei gleichwahrscheinlichen Quellensymbolen zur minimalen Fehlerwahrscheinlichkeit. Nachteilig ist:

  • Der Realisierungsaufwand steigt exponentiell mit der Länge N der zu detektierenden Symbolfolge.
  • Da die Folge gemeinsam entschieden wird, kommt es bei großem N zu langen Verzögerungen.

In den 1970er Jahren hat Andrew J. Viterbi einen ML–Empfänger vorgeschlagen, der die Detektion von Teilen der empfangenen Nachricht erlaubt und bei dem sich der Realisierungsaufwand auch bei unendlich langen Folgen in Grenzen hält.

Blockschaltbild des Viterbi-Empfängers

Zu den einzelnen Komponenten des Blockschaltbildes ist anzumerken:

  • Das an den Empfangsgrundimpuls und die Störung angepasste Matched–Filter HMF(f) dient der Störleistungsbegrenzung. Das MF–Ausgangssignal m(t) bzw. die Folge 〈mν〉 der äquidistanten Signalwerte nach der Abtastung besitzt das bestmögliche Signal–zu–Stör–Leistungsverhältnis.
  • Aufgabe des Dekorrelationsfilters HDF(f) ist es, aus der Folge 〈mν〉 die Detektionsabtastwerte dν = d + d zu gewinnen, deren Störanteile d unkorreliert sind. Dieses Filter wird deshalb auch Whitening–Filter genannt.
  • Der Viterbi–Entscheider, der im Mittelpunkt der folgenden Betrachtungen steht, gewinnt aus der Folge 〈dν〉 seiner wertkontinuierlichen Eingangswerte die binäre Ausgangsfolge 〈υν〉 entsprechend der Maximum–Likelihood–Regel mit der kleinstmöglichen Fehlerwahrscheinlichkeit Pr(υνqν).

Die Beschreibung wird auf der nächsten Seite fortgesetzt.

Blockschaltbild und Voraussetzungen für Kapitel 3.8 (2)


Um den Viterbi–Algorithmus möglichst einfach beschreiben und veranschaulichen zu können, werden hier einige vereinfachende Voraussetzungen getroffen:

  • Die Amplitudenkoeffizienten seien unipolar  ⇒  aν ∈ {0, 1}. Anzumerken ist, dass es bei der Verwendung bipolarer Koeffizienten aν ∈ {–1, +1} nur weniger Modifikationen bedarf.
  • Der Grundimpuls gd(t) besteht nur aus dem Hauptwert g0 = gd(t = TD) und einem Vorläufer g–1 = gd(t = TDT).
  • Damit ergeben sich für die wertkontinuierlichen Detektionsabtastwerte
\[d_{\nu} = a_{\nu}\cdot g_{0} + a_{\nu+1}\cdot g_{-1}+d_{{\rm N}\nu} \hspace{0.05cm},\]
wobei die Rauschkomponente dNν als gaußverteilt angenommen wird (Streuung σd).

Bei bipolarer Signalisierung ist der Algorithmus nicht aufwändiger. Dagegen steigt der Rechenaufwand, wenn der Detektionsgrundimpuls breiter wird und mehr als nur einen Vorläufer g–1 aufweist. Die Vernachlässigung von Nachläufern stellt keine grundlegende Einschränkung dar, weil jeder Impuls gd(t) diese Bedingung durch geeignete Wahl des Detektionszeitpunktes TD erfüllen kann. Anzumerken ist weiter, dass im Folgenden alle Signalwerte auf 1 normiert werden.

: In der Grafik sind die Detektionsnutzabtastwerte d als (blaue) Kreuze eingetragen, wobei die zugehörigen Amplitudenkoeffizienten a1 = 1, a2 = 1, a3 = 0, ... aus dem grün eingezeichneten Quellensignal q(t) abgelesen werden können. Die Grundimpulswerte sind in diesem Beispiel zu g0 = 0.7 und g–1 = 0.3 angenommen. Aus der Grafik ist weiter zu erkennen, dass dSν nur vier verschiedene Werte, nämlich 0, g0, g–1 und

g0 + g–1, annehmen kann.

Abtastwerte zur Verdeutlichung des Viterbi-Algorithmus

Die am Viterbi–Entscheider anstehenden Abtastwerte (rote Punkte) sind d0 = 0.2, d1 = 0.7, d2 = 0.5, d3 = 0, ... , wobei die Differenzen dNν = dνdSν von einer AWGN–Rauschquelle herrühren.

Ein Schwellenwertentscheider (mit der Schwelle bei E = 0.5) würde bei diesen dargestellten zehn Bit mindestens eine Fehlentscheidung treffen (bei ν = 4), und eventuell eine weitere bei ν = 2, falls d2 geringfügig kleiner ist als der Schwellenwert E = 0.5. Dagegen wird der Viterbi–Empfänger diese Folge der Länge 10 richtig entscheiden, wie auf den nächsten Seiten gezeigt werden wird.


Fehlergrößen und Gesamtfehlergrößen (1)


Wie in Kapitel 3.7 gibt Q ∈ {Qi} die begrenzte, aus N Binärsymbolen bestehende Quellensymbolfolge an. Die Anzahl der möglichen Symbolfolgen Qi ist somit 2N. V bezeichnet wieder die Sinkensymbolfolge der Länge N, die vom Viterbi–Entscheider gleich der wahrscheinlichsten Folge Qj gesetzt wird.

: Definition: Die Fehlergröße bezeichnet die quadratische Abweichung zwischen dem tatsächlichen, verrauschten Abtastwert dν und dem zur Folge Qi gehörenden Nutzabtastwert dSν(i):

\[\varepsilon_{\nu}(i) = |d_{\nu} - d_{{\rm S}\nu}(i)|^2 \hspace{0.05cm}.\]

Die Gesamtfehlergröße γν(i) kennzeichnet die Summe aller Fehlergrößen bis zum Zeitpunkt ν:

\[\gamma_{\nu}(i)= \sum_{k=0}^{\nu}\varepsilon_{k}(i) \hspace{0.05cm}.\]


Man bezeichnet γν(i) auch als Metrik. Anzumerken ist, dass diese Definitionen an einem Grundimpuls mit Hauptwert g0 und nur einem Vorläufer g–1 angepasst sind. Bei υ Vorläufern müsste die obige Summe bei k = 1 – υ beginnen. Der Parameter i ∈ {0, ... , 2N+1–1} wird meist binär dargestellt, so dass i gleichzeitig die Amplitudenkoeffizienten a1, ... , aν+1 (jeweils entweder 0 oder 1) angibt.

Darstellung der Fehlergrößen im Baumdiagramm

Die Grafik verdeutlicht die oben definierten Größen in einer Baumstruktur, woraus zu erkennen ist, dass die Gesamtfehlergrößen iterativ berechnet werden können:

\[\gamma_{\nu}(i)= \gamma_{\nu-1}(i')+\varepsilon_{k}(i'') \hspace{0.05cm}.\]

i, i' und i sind unterschiedliche Laufvariable. Die Bildbeschreibung folgt auf der nächsten Seite.

Fehlergrößen und Gesamtfehlergrößen (2)


Zu dieser Grafik, die hier nochmals eingeblendet werden kann, ist Folgendes anzumerken:

  • Die Knoten des Baumdiagramms stehen für die Gesamtfehlergrößen γν(i); deren Anzahl wird mit jedem Iterationsschritt verdoppelt. Zum Zeitpunkt ν gibt es 2ν+1 solcher Knoten. Beispielsweise sind für ν = 3 genau 24 = 16 Knoten zu erkennen.
  • Die zu den Gesamtfehlergrößen γν(i) gehörigen Amplitudenkoeffizienten ergeben sich, wenn man den Weg vom Anfangsknoten bis zum betrachteten Knoten verfolgt. Es wird vereinbart, dass einem nach oben gerichteten Zweig der Amplitudenkoeffizient 1 und einem nach unten gerichteten Zweig eine 0 zugeordnet wird.
  • Beispielsweise kennzeichnet der grün hinterlegte Knoten γ3(1100) die Gesamtfehlergröße unter der hypothetischen Annahme, dass die Symbole a1 = 1, a2 = 1, a3 = 0, a4 = 0 gesendet wurden. Diese Zuordnung kann auch aus den Richtungen der Pfeile im Baumdiagramm abgelesen werden: zunächst zweimal nach oben, dann zweimal nach unten.
  • Aufgrund des Vorläufers muss bereits zum Zeitpunkt ν = 3 der Koeffizient a4 mitberücksichtigt werden. Alle Knoten γν(i), die unter der Voraussetzung aν+1 = 1 berechnet werden, sind im Baumdiagramm durch Rechtecke dargestellt, während die Hypothese aν+1 = 0 jeweils durch ein abgerundetes Rechteck symbolisiert ist, z. B. γ2 (110) oder γ3 (1100).
  • Die Zweige im Baumdiagramm sind den Fehlergrößen εν(i) zugeordnet. Beim vorausgesetzten Grundimpuls (nur g0 und g–1 sind ungleich 0) gibt es zu jedem Zeitpunkt mit Ausnahme des Startzustandes (ν = 0) genau vier unterschiedliche Größen:
\[\varepsilon_{\nu}(00) = |d_{\nu}|^2\hspace{0.05cm},\hspace{0.5cm}\varepsilon_{\nu}(01) = |d_{\nu}-g_{-1}|^2\hspace{0.05cm},\]
\[\varepsilon_{\nu}(10) = |d_{\nu}-g_{0}|^2\hspace{0.05cm},\hspace{0.2cm}\varepsilon_{\nu}(11) = |d_{\nu}-g_{0}-g_{-1}|^2\hspace{0.05cm}.\]
  • Die Gesamtfehlergröße γν ist gleich der Summe aus dem vorausgegangenen Knoten γν–1 und dem dazwischenliegenden Zweig εν. Beispielsweise gilt für die hervorgehobenen Knoten:
\[\gamma_{1}(11)=\gamma_{0}(1)+\varepsilon_{1}(11) ,\hspace{0.05cm} \gamma_{2}(110)=\gamma_{1}(11)+\varepsilon_{2}(10) ,\hspace{0.05cm} \gamma_{3}(1100)=\gamma_{2}(110)+\varepsilon_{3}(00) .\]
  • Bei den ersten Knoten γ0(0) und γ0(1) wird berücksichtigt, dass vor der eigentlichen Übertragung (a1, a2, ...) vereinbarungsgemäß stets das Symbol a0 = 0 übertragen wird. Daraus folgt:
\[\gamma_{0}(0)=\varepsilon_{0}(00)= |d_{0}|^2 \hspace{0.05cm},\hspace{0.2cm} \gamma_{0}(1)=\varepsilon_{0}(01)=|d_{0}-g_{-1}|^2 \hspace{0.05cm}.\]

Das nachfolgende Beispiel wird hoffentlich diese etwas ermüdenden Aussagen verdeutlichen.

Fehlergrößen und Gesamtfehlergrößen (3)


: Wir betrachten wie im letzten Beispiel die unipolare Quellensymbolfolge der Länge N = 3, mit den Amplitudenkoeffizienten a1 = 1, a2 = 1, a3 = 0 und die weiteren Parameterwerte

\[g_{0}=0.7 \hspace{0.05cm},\hspace{0.2cm} g_{-1}=0.3 \hspace{0.05cm},\hspace{0.2cm} d_{0}=0.2 \hspace{0.05cm},\hspace{0.2cm} d_{1}=0.7 \hspace{0.05cm},\hspace{0.2cm} d_{2}=0.5 \hspace{0.05cm},\hspace{0.2cm} d_{3}=0 \hspace{0.05cm} \hspace{0.05cm}.\]

Nachfolgend ist das Baumdiagramm mit den Knoten γν(i) für die Zeitpunkte ν = 0 bis ν = 3 dargestellt. Die Berechnung der sich ergebenden Fehlergrößen εν(i) folgt auf der nächsten Seite.

Iterative Berechnung der Gesamtfehlergrößen (Beispiel)

Die minimale Gesamtfehlergröße γ3(1100) ist gleich 0.14. Daraus ergeben sich die Koeffizienten der nach den vorliegenden Signalwerten d0, d1, d2, d3 mit größter Wahrscheinlichkeit gesendeten Folge zu a1 = 1, a2 = 1 und a3 = 0 (grün eingezeichneter Pfad). Weiter ist zu sagen:

  • Ist die Folgenlänge N = 3 (das heißt: nur drei Symbole werden durch den Viterbi–Empfänger gemeinsam entschieden), so ist auch die Entscheidung a4 = 0 mit Sicherheit die richtige, da alle Koeffizienten aν>3 als 0 vorausgesetzt wurden.
  • Bei längerer Folge (N > 3) kann aus dem minimalen Wert γ3(1100) nicht unbedingt geschlossen werden, dass a1 = 1, a2 = 1, a3 = 0 Teil der wahrscheinlichsten Folge ist. Bei Berücksichtigung weiterer Abtastwerte (d4, d5, ...) könnte sich dieses vorläufige Ergebnis durchaus noch ändern.

Die Berechnung der Fehlergrößen für ν = 0 bis ν = 3 wird auf der nächsten Zeile gezeigt.

Nachzutragen ist die Berechnung der Fehlergrößen für die Zeitpunkte ν = 0 bis ν = 3. Die unipolare Quellensymbolfolge hat die Länge N = 3. Die Amplitudenkoeffizienten seien a1 = 1, a2 = 1, a3 = 0. Weiterhin gilt:

\[g_{0}=0.7 \hspace{0.05cm},\hspace{0.2cm} g_{-1}=0.3 \hspace{0.05cm},\hspace{0.2cm} d_{0}=0.2 \hspace{0.05cm},\hspace{0.2cm} d_{1}=0.7 \hspace{0.05cm},\hspace{0.2cm} d_{2}=0.5 \hspace{0.05cm},\hspace{0.2cm} d_{3}=0 \hspace{0.05cm} \hspace{0.05cm}.\]

Das Baumdiagramm mit den Knoten γν(i) ist unten dargestellt. Für die Zeitpunkte ν = 0 bis ν = 3 gilt:

\[\nu = 0 : \hspace{0.2cm}\varepsilon_{0}(00) = [0.2- (0 \cdot 0.7 + 0 \cdot 0.3)]^2=0.04 \hspace{0.05cm},\]

\[\hspace{0.4cm} \varepsilon_{0}(01) = [0.2- (0 \cdot 0.7 + 1 \cdot 0.3)]^2=0.01 \hspace{0.05cm},\]

\[\nu = 1 : \hspace{0.2cm}\varepsilon_{1}(00) = [0.7- (0 \cdot 0.7 + 0 \cdot 0.3)]^2=0.49 \hspace{0.05cm},\]

\[\hspace{0.4cm} \varepsilon_{1}(01) = [0.7- (0 \cdot 0.7 + 1 \cdot 0.3)]^2=0.16 \hspace{0.05cm},\]
\[\hspace{0.4cm}\varepsilon_{1}(10) = [0.7- (1 \cdot 0.7 + 0 \cdot 0.3)]^2=0.00 \hspace{0.05cm}\]
\[\hspace{0.4cm}\varepsilon_{1}(11) = [0.7- (1 \cdot 0.7 + 1 \cdot 0.3)]^2=0.09 \hspace{0.05cm},\]

\[\nu = 2 : \hspace{0.2cm}\varepsilon_{2}(00) = [0.5- (0 \cdot 0.7 + 0 \cdot 0.3)]^2=0.25 \hspace{0.05cm},\]

\[\hspace{0.4cm}\varepsilon_{2}(01) = [0.5- (0 \cdot 0.7 + 1 \cdot 0.3)]^2=0.04 \hspace{0.05cm},\]
\[\hspace{0.4cm}\varepsilon_{2}(10) = [0.5- (1 \cdot 0.7 + 0 \cdot 0.3)]^2=0.04 \hspace{0.05cm},\]
\[\hspace{0.4cm}\varepsilon_{2}(11) = [0.5- (1 \cdot 0.7 + 1 \cdot 0.3)]^2=0.25 \hspace{0.05cm},\]

\[ \nu = 3 : \hspace{0.2cm}\varepsilon_{3}(00) = [0.0- (0 \cdot 0.7 + 0 \cdot 0.3)]^2=0.00 \hspace{0.05cm},\]

\[\hspace{0.4cm}\varepsilon_{3}(01) = [0.0- (0 \cdot 0.7 + 1 \cdot 0.3)]^2=0.09 \hspace{0.05cm},\]
\[\hspace{0.4cm}\varepsilon_{3}(10) = [0.0- (1 \cdot 0.7 + 0 \cdot 0.3)]^2=0.49 \hspace{0.05cm},\]
\[\hspace{0.4cm}\varepsilon_{3}(11) = [0.0- (1 \cdot 0.7 + 1 \cdot 0.3)]^2=1.00 \hspace{0.05cm}.\]

Iterative Berechnung der Gesamtfehlergrößen (Beispiel)


Minimale Gesamtfehlergröße und Trellisdiagramm (1)


Wir gehen weiterhin von den Zahlenwerten des letzten Beispiels aus.

Vereinfachung des Baumdiagramms nach Viterbi

Wichtige Eigenschaften des optimalen Entscheiders (Maximum–Likelihood) lassen sich aus obiger Grafik anhand des Zeitpunktes ν = 2 erkennen:

  • Die minimale Gesamtfehlergröße ist γ2(101) = 0.05 (braun hervorgehoben). Das bedeutet: Eine Entscheidung zu diesem Zeitpunkt – basierend auf den Werten d0, d1 und d2 – wäre zugunsten der Folge „101” anstelle der gesendeten Folge „110” ausgegangen.
  • Daraus folgt: Für eine optimale Entscheidung sollte eine zu frühe endgültige Festlegung unbedingt vermieden werden. Allerdings kann man zu jedem Zeitpunkt ν bereits mehrere Teilsymbolfolgen ausschließen, die zu späteren Zeitpunkten nicht mehr berücksichtigt werden müssen.
  • Zu γ2(001), γ2(011) und γ2(111) werden jeweils genau die gleichen Fehlergrößen hinzuaddiert. Da diese drei Metriken alle größer sind als γ2(101) = 0.05, steht bereits bei ν = 2 fest, dass „001”, „011” sowie „111” nicht Bestandteil der wahrscheinlichsten Folge sein können. Diese Knoten und alle ihre Nachfahren müssen deshalb nicht weiter beachtet werden (braune Überdeckungen).
  • Gleiches gilt für die abgerundeten Knoten: γ2(000), γ2(010) und γ2(100) sind größer als der grün markierte Knoten γ2(110) = 0.14, so dass auch diese und ihre Nachfahren ab dem Zeitpunkt ν = 3 nicht mehr berücksichtigt werden müssen (grüne Überdeckungen).
  • Man stellt fest: Von den acht Knoten bei ν = 2 müssen nur zwei weiterverfolgt werden, nämlich das abgerundete Rechteck γ2(110) = 0.14 und das Rechteck γ2(101) = 0.05. Diese beschreiben die minimalen Gesamtfehlergrößen unter der Annahme, dass a3 = 0 bzw. a3 = 1 sein wird.

Die Beschreibung wird auf der nächsten Seite fortgesetzt.