Schwerpunktlabor Nachrichtentechnik Viterbi-Algorithmus ... · 1 EINFUHRUNG¨ 1 1 Einfu¨hrung 1.1 Motivation In diesem Versuch wird mit dem Viterbi Algorithmus (VA) ein fundamentaler

Schwerpunktlabor Nachrichtentechnik

Viterbi-Algorithmus

– SoSe 2013 –

Florian LenkeitNW1, Raum N 2390, Tel.: 0421/218-62395

E-mail: [email protected]

Universitat Bremen, FB1Institut fur Hochfrequenz- und Nachrichtentechnik

Arbeitsbereich NachrichtentechnikProf. Dr.-Ing. A. Dekorsy

Postfach 33 04 40D–28334 Bremen

WWW-Server: http://www.ant.uni-bremen.de

Version vom Mai 2013

INHALTSVERZEICHNIS I

Inhaltsverzeichnis

1 Einfuhrung 1

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1

1.2 Gliederung dieser Versuchsbeschreibung . . . . . . . . . . . .. . . . . . . . . . . . . . 1

1.3 Vor- und Nachbereitung des Versuches . . . . . . . . . . . . . . . .. . . . . . . . . . . 2

2 Theoretische Grundlagen 4

2.1 FIR-Filterung und Faltungscodierung als endliche Automaten . . . . . . . . . . . . . . . 4

2.1.1 Transversalstrukturen . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5

2.1.2 Zustandsubergangsdiagramm . . . . . . . . . . . . . . . . . . . .. . . . . . . 5

2.1.3 Trellisdiagramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 6

2.2 Trellisdecodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 6

2.2.1 Storungsmodell fur die Decodierung . . . . . . . . . . . . .. . . . . . . . . . . 7

2.2.2 Viterbi-Metrik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 7

2.2.3 Viterbi-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 8

2.3 Der Viterbi-Algorithmus zur Kanalentzerrung . . . . . . . .. . . . . . . . . . . . . . . 8

2.3.1 Ubertragungskanal in Transversalstruktur (FIR-Filter) .. . . . . . . . . . . . . 8

2.3.2 Beschreibung des Viterbi-Algorithmus (EuklidischeMetrik) . . . . . . . . . . . 9

2.4 Der Viterbi-Algorithmus zur Faltungsdecodierung . . . .. . . . . . . . . . . . . . . . . 12

2.4.1 Faltungscodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 13

2.4.2 Die Metrik bei Faltungsdecodierung . . . . . . . . . . . . . . .. . . . . . . . . 13

3 Ubungsaufgaben 15

4 Versuchsdurchfuhrung 17

4.1 Kanalentzerrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 18

4.1.1 Vorbereitungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 18

4.1.2 Demonstrationsprogramm VA (zweistufigeUbertragung) . . . . . . . . . . . . . 19

4.1.3 Fehleranalyse fur den VA bei QPSK-Modulation . . . . . .. . . . . . . . . . . 20

4.1.4 Kanalentzerrung bei QPSK-Modulation . . . . . . . . . . . . .. . . . . . . . . 20

4.2 Decodierung von Faltungscodes . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 22

4.2.1 Faltungscode der Rate 1/2 . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 22

4.2.2 FC der Rate 1/3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 22

4.2.3 Faltungsdecodierung . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 22

4.2.4 Soft-Input vs. Hard-Input . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 23

INHALTSVERZEICHNIS II

4.2.5 Fehlerstruktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 23

1 EINFUHRUNG 1

1 Einfuhrung

1.1 Motivation

In diesem Versuch wird mit dem Viterbi Algorithmus (VA) ein fundamentaler Baustein der modernenNachrichtentechnik behandelt. Seine Anwendung ist dabei ungeheuer vielfaltig:

• Entzerrung von gedachtnisbehafteten Kanalen bei digital modulierten Signalen; Einsatz z.B. in“Handys” nach dem GSM-Standard (D- und E-Netz)

• Decodierung von Faltungscodes; Einsatz ebenfalls in GSM-Handys (im Zusammenhang mit demobigen Beispiel also sogar eine Verkettung von zwei VA) oderin Telefonkanal-Modems

• Demodulation von CPM- oder TCM-Signalen (CPM:Continuous Phase Modulation, TCM: TrellisCoded Modulation)

• Spracherkennung

Der VA stellt die effiziente Realisierungsform der optimalen Losung zur Schatzung einer Datensequenzx aus der gestorten Empfangssequenz

y = f(x,S) + n

dar, wobein einen weißen gaußverteilten Rauschvektor beschreibt,f(·) die Ausgangsfunktion des Sy-stems charakterisiert undS den Vektor des System-Gedachtnisses reprasentiert. EinEmpfanger nachdem Maximum-Likelihood–Prinzip, d.h. dem Prinzip der Detektion mit geringstmoglicher Fehlerwahr-scheinlichkeit, berechnet hierzu das Maximum aller Wahrscheinlichkeiten, bei dem ein moglicherweisegesendeter Datenvektorxµ zu dem Empfangsvektory fuhrt:

maxµ

{P (y|xµ)} → x

Diese Berechnung kann effizient mit Hilfe des VA erfolgen. Als Schatzung der gesendeten Datenfolgex

wird diejenige Datenfolge ausgegeben, die zu diesem Maximum der Wahrscheinlichkeit gefuhrt hat.

Im Rahmen dieses Versuches werden wir uns auf zwei Einsatzgebiete des VA beschranken – die Ka-nalentzerrung sowie die Decodierung von Faltungscodes. Anhand dieser beiden Anwendungen soll auf-gezeigt werden, dass der VA fur unterschiedliche Aufgabenstellungen eingesetzt werden kann. DieseAufgaben konnen folgendermaßen formuliert werden:

• Kanalentzerrung: Der VA wird eingesetzt, um storende Intersymbol-Interferenz (ISI) zu ent-fernen, damit im Idealfall dieUbertragungsqualitat des AWGN-Kanals (AWGN:Additive WhiteGaussian Noise) erzielt werden kann.

• Decodierung: Durch den VA wird gezielt die eingebrachte Redundanz zur Verringerung der Feh-lerrate gegenuber einer uncodiertenUbertragung genutzt.

1.2 Gliederung dieser Versuchsbeschreibung

Eine kurze Zusammenfassung der wichtigsten Formeln und Zusammenhange wird in Abschnitt 2 dieserVersuchsbeschreibung angegeben. Zur Vertiefung sind in Abschnitt 3 einigeUbungsaufgaben zu losen.Die Anleitung zur Versuchsdurchfuhrung erfolgt schließlich in Abschnitt 4.

LITERATUR 2

1.3 Vor- und Nachbereitung des Versuches

Zur erfolgreichen und zugigen Durchfuhrung des Versuches ist es unerlaßlich, die erforderlichen theore-tischen Grundlagen zu beherrschen. Die Kenntnis dieser Grundlagen wird deshalbvor Versuchsbeginnuberpruft. Bei unzureichender Vorbereitung der Gruppe wird der Versuch zu einem spateren Zeitpunktnachgeholt.

Die fur den Versuch erforderlichen theoretischen Grundkenntnisse wurden dabei in den Vorlesungen

• “Nachrichtenubertragung”,

• “Digitale Signalverarbeitung” sowie

• “Kanalcodierung”

vermittelt. Spezielle Teile dieser Grundlagen, insbesondere zur Kanalentzerrung, sind im Kapitel 14.5des Lehrbuches [Kam08] (und im Kapitel 10.1 von [Pro01]) beschrieben. Die Grundlagen zur Kanalco-dierung und Decodierung von Faltungscodes sind in Kapitel 4im Vorlesungsskript [KW10] zu finden.Weitere Literaturhinweise zum Viterbi-Algorithmus sind im Literaturverzeichnis angegeben ([Bos99,Fri96, Fri11, KK01, KK09, Vit67, For72, For73, Pro01]).

Bitte beachtet unbedingt die folgenden Punkte:

• Die Ubungsaufgaben in Abschnitt 3 sind von jedem Teilnehmervor dem Versuchsterminzu be-arbeiten und dieeigene schriftlicheLosungen ist zum Versuch mitzubringen. Dabei aufgetreteneProbleme konnenvor Versuchsbeginn diskutiert werden. Die Aufgaben werden vonEuch an derTafel vorgerechnet. Nur wer seine eigenen Losungen vorlegen und erlautern kann, wird zu derVersuchsdurchfuhrung zugelassen!

• Im Verlauf des Versuchs ist ein (handschriftliches) Protokoll anzufertigen, welches die erarbeitetenErgebnisse zu den einzelnen Arbeitspunkten in Abschnitt 4 enthalt. Zur Steigerung der Lesbarkeitdarf hier auch sauber geschrieben werden und die Verwendungeines Lineals verringert nicht dieChance zum bestehen des Versuchs. Die Beantwortung der Fragen wird im Laufe des Versuchsbesprochen und uberpruft. Wurden alle Punkte bearbeitetund sind alle Fragen beantwortet worden,soentfallt die Ausarbeitung eines ausfuhrlichen Protokolls zu Hause. Durch eine gute Vorbereitungkonnt Ihr Euch also eine Menge Arbeit sparen.

• Die Kennzeichnung der fur das Versuchsprotokoll zu beantwortenden Fragen bzw. zu erlauterndenProblemstellungen erfolgt im Text durch eine fortlaufendeNumerierung der Versuchspunkte (z.B.VP-1: ). Diese Numerierung soll vollstandig und in der richtigenReihenfolge in das Versuchspro-

tokoll ubernommen werden, um eine ubersichtliche Ausarbeitung zu erleichtern.

• Falls in dem mitgeschriebenen Protokoll nicht alle Arbeitspunkte zufriedenstellend bearbeitetwurden, ist ein ausfuhrliches Protokoll anzufertigen. Indas Protokoll sinddann auchdie Losungender Ubungsaufgaben zu ubernehmen! Dieses Protokoll sollte mit einem Text-System (z.B. Latexoder Word) ausgearbeitet werden.

Literatur

[Bos99] M. Bossert.Channel Coding for Telecommunications. John Wiley, 1999.

[For72] G.D. Forney. Maximum likelihood sequence estimation for digital sequences in the presence ofintersymbol interference.IEEE Trans. on Information Theory, IT-18:363–378, 1972.

[For73] G.D. Forney. The viterbi algorithm.Proceedings of the IEEE, 61:268–278, 1973.

LITERATUR 3

[Fri96] B. Friedrichs.Kanalcodierung. Springer, Berlin, 1996.

[Fri11] B. Friedrichs.Error-Control Coding. 2011. Online:http://www.berndfriedrichs.de/ .

[Kam08] K.D. Kammeyer.Nachrichtenubertragung. Vieweg+Teubner, Stuttgart, fourth edition, 2008.

[KK01] K.D. Kammeyer and V. Kuhn.Matlab in der Nachrichtentechnik. J. Schlembach Fachverlag, Weil derStadt, 2001.

[KK09] K.D. Kammeyer and K. Kroschel.Digitale Signalverarbeitung: Filterung und Spektralanalyse (mitMatlab-Ubungen). B.G. Teubner, Stuttgart, seven edition, 2009.

[KW10] V. Kuhn and D. Wubben.Kanalcodierung. Vorlesungsskript Universitat Bremen, 2010. Online:http://www.ant.uni-bremen.de/courses/cc1/ .

[Pro01] J. G. Proakis.Digital Communcations, volume 4. McGraw-Hill, 2001.

[Vit67] A.J. Viterbi. Error bounds for convolutional codesand an asymptotically optimum decoding algorithm.IEEE Trans. on Information Theory, IT-13:260–269, 1967.

2 THEORETISCHEGRUNDLAGEN 4

2 Theoretische Grundlagen

2.1 FIR-Filterung und Faltungscodierung als endliche Automaten

In diesem Abschnitt wird auf die strukturellen Gemeinsamkeiten eingegangen, die einem gedachtnisbe-hafteten Kanal – darstellbar als FIR-Filter (FIR:Finite Impulse Response) – und einem Faltungscoderzugrundeliegen.

Kanale mit Gedachtnis sind ungunstig, weil die durch sieeingebrachte Intersymbolinterferenz (ISI)insbesondere im Falle eines langen Gedachtnisses schwer zu bekampfen ist. ISI entsteht durch diezeitliche Verflechtung mehrerer Eingangssymbole zu Ausgangssymbolen, deren Stufigkeit im allge-meinen die der Eingangssymbole deutlich ubersteigt. Die Anzahl der Eingangssymbole, von denenjedes Ausgangssymbol abhangt, ist fur die Klasse der FIR-Kanale endlich groß. GedachtnisbehafteteKanale konnen eine Signalerkennung ohne Entzerrung unmöglich machen – unser Ziel ist es also, dieunerwunschten Einflusse durch einenKanalentzerrerruckgangig zu machen.

Faltungscodes – als eine Klasse der Kanalcodes – erfullen die Aufgabe der kontrollierten Redundanz-zufugung der zu ubertragenden Daten zum Schutz vor Kanaleinflussen, d.h. vorUbertragungsfehlern.Durch die Zufugung von Redundanz wird die Ausgangssymbolrate gegenuber der Eingangssymbolrateerhoht. Auch bei der Faltungscodierung wird eine Eingangssymbolfolge auf eine Ausgangssymbolfolgeabgebildet; die Anzahl der vorangegangenen Eingangssymbole, die von der Abbildung berucksichtigtwerden, ist fur nichtrekursive Faltungscodes endlich. Die Aufgabe desFaltungsdecodersist eine fehler-resistente Ruckgewinnung der Eingangssymbolfolge aus der verrauschten Empfangssymbolfolge.

Die Vorgange der FIR-Filterung (Einfluß des FIR-Kanals) und der Faltungscodierung konnen als dieWirkung einesMealy-Automatenmit Z unterscheidbaren inneren Gedachtniszustanden (“finite-state-machine”) auf die Eingangssymbolfolge aufgefaßt werden.

Die Zuordnung des aktuellen Ausgangssymbolswi ist abhangig vom GedachtniszustandSi des Automa-ten und dem dem Eingangssymbolxi. Sie wird durch dieAusgangsfunktionf

wi = f(xi, Si) (1)

des Mealy-Automaten beschrieben. Von den gleichen Parametern wird der nachfolgende ZustandSi+1

uber dieZustandsubergangsfunktiong gemaß

Si+1 = g(xi, Si) (2)

bestimmt. Diese Beziehung verdeutlicht die rekursive Verkettung der Gedachtniszustande und damit dieKorrelation benachbarter Ausgangssymbole. Die Beziehungen (1) und (2) kennzeichnen einen Mealy-Automaten gemaßAbb. 1.

x 1 wZustandsspeicher (x , )(x , )

Abb. 1: FIR-Filter und Faltungscoder als Mealy-Automat

Dabei gilt furxi undwi:

xi ∈ Ax = {X1, X2, X3, . . . , XM},wi ∈ Aw = {W1, W2, W3, . . . , WMw},


wobeiAx undAw das Eingangs- bzw. Ausgangsalphabet darstellen. Die Anzahl moglicher Eingangs-symbole wird mitM und die Anzahl moglicher Ausgangssymbole mitMw bezeichnet. Die unterscheid-baren Gedachtniszustande werden mit Zustandsnummern beschrieben:

Si ∈{1, 2, . . . , Z},

wobei fur deren Anzahl giltZ = M ℓ = MK−1, wennℓ = K − 1 die Gedachtnislange (d.h. die Anzahlder Speicherplatze) bezeichnet. Der ParameterK = ℓ+ 1 gibt die Anzahl der Ausgangssymbole an, dievon einem Eingangssymbol beeinflusst werden (constraint length).

2.1.1 Transversalstrukturen

Sowohl bei einem FIR-Kanal als auch bei einem Faltungscoderkann das endliche Gedachtnis in einernichtrekursiven Transversalstruktur dargestellt werden(vgl. Abb. 2).

. . .x

w

. . .D D D D D

(x , x 1 , x , x -2 , . . .x +1 , x )

Abb. 2: Transversalform-Darstellung der Gedachtnisstruktur von FIR-Kanalen und Faltungscodern

Das Symbol D reprasentiert ein Speicherelement, dessen Eingangssignal beimUbergang vom Schrittizum Schritti+1 in den Speicher ubernommen wird (D: delay). Die Anzahl der Speicherelemente betragtℓ = K − 1. Falls die EinflußlangeK = 1 betragt, handelt es sich beispielsweise bei einem Kanal umden sogenannten “idealen Kanal”, und bei der Kanalcodierung um eine (triviale) Blockcodierung.

2.1.2 Zustandsubergangsdiagramm

Die Abfolge der Gedachtniszustande(. . . , Si−1, Si, Si+1, . . .) des Mealy-Automaten aus Abb. 1 stellteinen zeitdiskreten stochastischen Prozeß dar. Bei festgelegtem Eingangssymbol ist der nachfolgendeZustand des Automaten nur vom Vorzustand abhangig. Ausgehend von jedem Zustand existierenMUbergange (Anzahl der moglichen Eingangssymbole) zu Folgezustanden. Die unterschiedlichen Zu-standsubergangesind mit der Erzeugung eines Ausgangssymbols (vonMw moglichen) gemaß der Aus-gangsgleichung (1) verknupft. Durch ein Zustandsubergangsdiagramm, wie es inAbb. 3 fur ein Beispielmit den ParameternZ = 3, M = 2 und Mw = 4 dargestellt ist, wird die gesamte Menge derAutomatengleichungen (2) fur alle Kombinationen der ArgumenteSi undxi beimUbergang vom Schritti zum Schritti+ 1 graphisch veranschaulicht.

X2�/W�2 X1�/W�4

X2�/W�1

X1�/W�1

X1�/W�4�

X2�/W�3

31

2

Abb. 3: Zustandsubergangsdiagramm mitZ = 3, M = 2 undMw = 4


2.1.3 Trellisdiagramm

Durch eine Abwicklung des Zustandsubergangsdiagramms uber den Zahlindexi gelangt man zum Netz-oder Trellisdiagramm1 eines Mealy-Automaten (sieheAbb. 4). Dieses Diagramm wird insbesondere zurAnalyse und Darstellung von Kanalentzerrungs- und Faltungsdecodieralgorithmen verwendet.

X2�/W�2

X1�/W�4

X2�/W�1

X2�

W1�

X1�

W4�

. . .

. . .

. . .

. . .

X2�

W3�

X1

W1

X1�/W�1

X1�/W�4�

X2�/W�3

1 2 31

3

1

2

Abb. 4: Trellisdiagramm zum Zustandubergangsdiagramm aus Abb. 3mit einem Beispielpfad

Im Falle des zeitinvarianten Mealy-Automaten ist das Trellisdiagramm von Schritt zu Schritt gleich. DerUbergang im Trellisdiagramm von einem AusgangszustandSi zum FolgezustandSi+1 wird als Zweig(branch)(SiSi+1) bezeichnet. Jedem Zweig ist das AutomateneingangssymbolXi zugeordnet, das denentsprechenden ZustandsubergangSi → Si+1 hervorruft. Außerdem kennzeichnen wir jeden Zweigauch durch das AusgangssymbolWk, das uber die Ausgangsgleichung aus dem Eingangssymbol undden Registerinhalten des Automaten erzeugt wird.

Eine Eingangssymbolfolge(. . . , xi−1, xi, xi+1, . . .) wird auf eine Sequenz von Zweigen im Trellis-diagramm abgebildet, die alsPfad (path)bezeichnet wird. In Abb. 4 ist ein Pfad durch das Trellis-diagramm hervorgehoben. Die Eingangssymbole, die diesen Pfad erzeugt haben, befinden sich unter-halb des Diagramms und sind grau unterlegt. Darunter sind die Symbole der Ausgangssymbolfolge(. . . , wi−1, wi, wi+1, . . .) des Mealy-Automaten eingetragen, die – von einer Storung auf demUber-tragungsweg degradiert – an der Empfangerseite beobachtet werden konnen.

2.2 Trellisdecodierung

Jede Eingangssymbolsequenz(. . . xi−1, xi, xi+1, . . .) wird eindeutig durch einen Pfad im Trellisdia-gramm reprasentiert. Die Detektion der geschatzten Nachricht2 (. . . , xi−1, xi, xi+1, . . .) aus der Se-quenz der Empfangswerte(. . . , yi−1, yi, yi+1, . . .) beruht also auf der Betrachtung dergesamtenNach-richt. Bei diesem sogenannten “Sequenzschatzverfahren”wird festgestellt, welcher Pfad durch das Trel-lisdiagrammnach Erhalt des gesamtenEmpfangssignals, alsoa-posteriori, die großte Wahrscheinlich-keit besitzt. Da hier eine Schatzung uber die gesamte Symbolsequenz erfolgt, wird die BezeichnungMaximum-a-posteriori-Sequenzschatzung benutzt. Unterder Annahme gleichwahrscheinlicher Eingangs-symbole vereinfacht sich diese Methode zu einerMaximum–Likelihood Sequenzschatzung (MLSE: Ma-ximum Likelihood Sequence Estimation).

1trellis (engl.) Gitter, Spalier2bzw. der Eingangssymbolsequenz


2.2.1 Storungsmodell fur die Decodierung

Die Aufgabe der Trellisdecodierung ist es, anhand der Ausgangssymbolfolge, die von Storungen degra-diert wurde(. . . , yi−1, yi, yi+1, . . .), auf die Eingangssymbolfolge(. . . , xi−1, xi, xi+1, . . .) zu schlie-ßen (sieheAbb. 5). Zu diesem Vorgang mussen neben der verrauschten Ausgangsfolge die Ausgangs-funktion f(xi, Si) sowie Kentnisse uber die Gedachtnisstruktur (Zustandsübergangsfunktiong(xi, Si))des Automaten vorliegen. Die Storung der Ausgangssymbolewi wird als additives weißes gaußverteiltesRauschen (AWGN) angenommen.

Mealy-Automat(FIR-Kanal/Faltungscoder) AWGN

x yw

Abb. 5: Storungsmodell

2.2.2 Viterbi-Metrik

Ziel der ML-Decodierung (ML:Maximum Likelihood) ist es, zur Empfangsfolgey diejenige Codefolgex zu wahlen, bei der die bedingte Wahrscheinlichkeitsdichte p(y|x) maximal wird. Wennx die ML-Schatzung ist, so muß fur alle Decoder-Eingangssymbolfolgen (Codefolgen)xµ gelten:

p(y|x) = maxµ

{p(y|xµ)}. (3)

Die bedingte Wahrscheinlichkeitsdichte fur Folgen zerfällt im Fall eines gedachtnislosen, diskreten Ka-nals mit mit weißem Rauschen in ein Produkt der einzelnen bedingten Wahrscheinlichkeitsdichten:

p(y|xµ) =∏

i

p(yi|xµi), (4)

Da der Logarithmus eine monoton steigende Funktion ist, andert sich die Maximierung nicht, wenn mananstelle derUbergangswahrscheinlichkeit deren (skalierten) Logarithmus verwendet. Die entstehendeSumme wird als “Viterbi-Metrik” bezeichnet.

L(y|x) = maxµ

{Lµ(y|xµ)}

= maxµ

{ln p(y|xµ)}

= maxµ

{

∑

i

ln p(yi|xµi)}

= maxµ

{

∑

i

Lµ(yi|xµi)}

(5)

Dabei wirdLµ(yi|xµi) als Metrik-Inkrementbezeichnet. Es stellt ein Maß fur die “Ahnlichkeit” desTrelliszweiges mit dem empfangenen Signal dar. Mit der Maximierung in Gl. (5) wird also derjenigePfad ausgewahlt, dessenAhnlichkeit zu der empfangenen Folge am großten ist.

Haufig wird allerdings aus praktischen Grunden diemoglichst großeAhnlichkeitals moglichst kleineAbweichungberechnet. Das Metrik-InkrementLµ(yi|xµi) bezeichnet dann die “Kosten”, die ein Zweigim Trellis hervorruft, bzw. die “Entfernung” (EuklidischeDistanz) des empfangenen Signals vom Soll-Signal. Wahrend der Viterbi-Decodierung werden diese Kosten minimiert, was aquivalent zur ML-Decodierung ist. In diesem Fall muß die Berechnung abweichend zu Gl. (5) als Minimierung erfolgen:

L(y|x) = minµ

{

∑

i

Lµ(yi|xµi)}

(6)


2.2.3 Viterbi-Algorithmus

Der Viterbi-Algorithmus (VA) [Vit67] ist dieoptimale und zugleich recheneffiziente Methode zur Schat-zung der Eingangssymbolfolge eines endlichen Automaten aus deren Ausgangssymbolfolge, die man imweißen gaußschen Rauschen beobachtet hat.

Gegenuber der MLSE, die oben beschrieben wurde, fuhren folgendeUberlegungen zur effizienten Rea-lisierung in Form des VA:

• Die rekursive Berechnung des Maximum-Likelihood-Funktionals (aufgrund einer bestimmten Me-trik berechnete “Pfadkosten”, vgl. Abschnitt 2.3.2) haltdie Anforderungen an die Rechenleistungin Grenzen.

• In jedem Schritt muß fur jeden derZ Zustande nur ein einziger Pfad weiter berucksichtigt werden,was eine Realisierung mit geringen Speicheranforderungenerlaubt.

• Pfadvereinigung: ab einem bestimmten, zuruckliegenden Zeitpunkt vereinigen sich alleZ betrach-teten Pfade. Basierend auf dieser Beobachtung ist es moglich, den Speicherbedarf zu verringern.Noch wichtiger ist die Tatsache, dass bereitsvor dem Ende der Decodierung des ganzen BlocksDaten ausgegeben werden konnen.

DerViterbi-Algorithmus wird auf folgende Weise ausgefuhrt:

• Fur alle Schrittei im Trellisdiagramm:

Berechnefur ζ = 1 bisZ ·M alle MetrikenLζ(yi|xiζ) zum Schritti.

Fur alle ZustandeSi = 1 bisZ:

Addiere zu den MetrikenLS(1)i−1

, . . . , LS(M)i−1

allerM VorzustandeS(1)i−1, . . . , S

(M)i−1 die aktu-

ellen ZweigmetrikenLS(∗)i−1→Si

(yi|xi∗) der ZweigeS(∗)i−1 → Si, die in den ZustandSi fuhren

(add).

Vergleichedie akkumulierten Metriken fur alle Pfade, die zum ZustandSi fuhren (compare).

Wahleden ZweigS(∗)i−1 → Si zum ZustandSi aus, fur den die Summe aus Vorzustandsmetrik

und Zweigmetrik maximal ist (select). Bei Metrikgleichheit wird eine Zufallsentscheidunggetroffen.

Speicheredie ausgewahlte Metriksumme als neue ZustandsmetrikLSi

= LS(∗)i−1

+ LS(∗)i−1→Si

(yi|xi∗)

und den ZweigS(∗)i−1 → Si.

• Nachdem die obigen Berechnungen durch das gesamte Trellis fur alle Schrittei ausgefuhrt sind,gebe die Datensequenz aus, die dem ubriggebliebenen Pfad entspricht.

Die oben aufgezahlten Schritte sollen in Abschnitt 2.3.2 anhand des speziellen Beispiels der Kanalent-zerrung verdeutlicht werden.

2.3 Der Viterbi-Algorithmus zur Kanalentzerrung

2.3.1 Ubertragungskanal in Transversalstruktur (FIR-Filter)

Wie in Abschnitt 2.1 bereits eingefuhrt, betrachten wir einen FIR-Kanal als eine Spezialform der all-gemeinen Transversalstruktur aus Abb. 2. Die Zustandsubergangsfunktion des Mealy-Automaten ist


durch die Schieberegisterkette bestimmt. Dasi-te Ausgangssymbol ergibt sich als inneres Produkt derKoeffizienten der Kanalimpulsantwortf = (f0, f1, . . . , fℓ) und des Registerinhaltes sowiexi. Mit

dµ = (. . . , xi−1, xi, xi+1, . . .)

als demµ-ten Datenvektor aus allen moglichen, ergibt sich durch diese Operation eine Faltung mit derKanalimpulsantwort.

. . .x

f f f f f f fw

. . .D D D D D

+ + + + + + +

Abb. 6: Ubertragungskanal in Transversalstruktur (Symboltaktmodell)

An dieser Stelle sei darauf hingewiesen, dasspro Eingangssymbolxi – das haufig dem AlphabetAx ={+1, −1} oder {0, 1} entstammt –ein Ausgangssymbolentsteht, das aus einem großeren Alphabetstammen kann, da durch den Kanal verschiedene Signalniveaus erzeugt werden konnen. Die Anzahl derVerzogerungsglieder wird als Gedachtnislangeℓ bezeichnet, aus der sich die sog. EinflußlangeK = ℓ+1,berechnet.

2.3.2 Beschreibung des Viterbi-Algorithmus (EuklidischeMetrik)

Die folgenden Ausfuhrungen fassen im wesentlichen die Aussagen des Kapitels 13.2 aus [Kam08]zusammen. Die Numerierung der Gleichungen, auf die in diesem Abschnitt verwiesen wird, beziehtsich also auf die entsprechenden Gleichungen dieses Buches.

Das ML-Kriterium Gl. (13.1.18) und Gl. (6)

Lµ = |y − Fdµ|2 != min (7)

sagt aus, dass unterallen moglichen ungestorten Empfangsfolgen– zu berechnen aus der FaltungsmatrixF und allen moglichen Sendefolgendµ – diejenige auszuwahlen ist, die die minimale EuklidischeDistanz zur aktuell beobachteten gestorten Empfangsfolge y besitzt. Formuliert man das Funktionalstatt in Matrix- in Summenschreibweise

Lµ(i) =i∑

ζ=0

|y(ζ)− f(ζ) ∗ dµ(ζ)|2 , (8)

so erkennt man leicht die Moglichkeit der rekursiven Berechnung des Funktionals:

Lµ(i) = Lµ(i− 1) + |y(i)− f(ζ) ∗ dµ(ζ)|ζ=i|2 mit µ∈{0, . . . , MFL − 1}, (9)

wobeiFL die Lange der Eingangsdatenfolge undM , wie gewohnt, die Stufigkeit der Eingangsdatenangibt. In jedem Schritt mussen jedoch nicht alle moglichen Pfade im Trellisdiagramm betrachtet wer-den. Von den in jedem Zustand zusammenlaufenden Pfaden muß nur derjenige weiterverfolgt werden,der zum minimalen Funktional gehort, wahrend die anderensich bereits hier als geringer wahrscheinlicherweisen. Dadurch reduzieren sich die zu betrachtenden Funktionale erheblich; wir definieren hierzufolgendePfadkosten:

Lµ ⇒ Pν mit ν ∈{0, . . . , M l − 1} (10)

und dem Kanalgradl. Zweckmaßigerweise werden fur die BerechnungUbergangspfadkostenzu denverschiedenen Signalniveauszνk eingefuhrt

pνk(i) = |y(i)− zνk|2 mit k∈{0, . . . , M − 1}, (11)


so dass sich schließlich folgende rekursive Berechnungsvorschrift der Summenpfadkosten ergibt:

Pν+(i) = mink

{Pν−(i− 1) + pν−k(i)} . (12)

Die Abhangigkeit der aktualisierten PfadkostenPν+(i) von den vorhergehenden PfadkostenPν−(i− 1)ergibt sich dabei aus dem zugehorigen Trellis-Diagramm. In Abb. 7 ist dieser Zusammenhang fur denFall einer zweistufigenUbertragung uber einen Kanal 2. Ordnung veranschaulicht.

0( -1)

1( -1)

2( -1)

3( -1)

0( )10( )

00( )

31( )

1( )

2( )

3( )

Abb. 7: Aktualisierung der Summenpfadkosten:Pν+(i) = mink {Pν−(i− 1) + pν−k(i)}

Faustregel zur Pfadvereinigungslange:Bisher wurde stets von derUbertragung und Detektion endlicher Eingangsdatenfolgender LangeFLausgegangen. Bei sehr langen Datenfolgen oder einer kontinuierlichen Ubertragung wurde hiermit –trotz der Anwendung des VA – eine hohe Verzogerung verbunden sein, da zur Detektion einer Folge dasEnde derUbertragung abgewartet werden musste. Praktische Beobachtungen zeigen jedoch, dass sichalle Pfade ab einem bestimmten, hochstensimax Schritte zuruckliegenden Zeitpunkt vereinigen. Damitkann also bereits zum Zeitpunkti eine Entscheidung uber das Eingangsdatumd(i − imax) (sowie allefruheren Daten) getroffen werden. Als Faustregel fur eine maximale Pfadvereinigungslange gilt in derPraxis der funffache Wert des Kanalgedachtnisses.

Fehlerwahrscheinlichkeit und Betrachtung zu Fehlervektoren:Der Viterbi-Detektor ist der optimale Empfanger fur einen gedachtnisbehafteten Kanal mit additiverweißer Gaußstorung – dies heißt nicht, dass bei der Detektion keine Fehler entstehen, sondern nur,dass die geringstmogliche Anzahl von Fehlern auftritt. Die Berechnung der Fehlerwahrscheinlichkeitbei der Viterbi-Detektion ist ein kompliziertes Unterfangen und soll hier nicht hergeleitet werden (dieausfuhrliche Herleitung findet man in [Kam08], Kap. 13.3).Es soll an dieser Stelle jedoch wiederholtwerden, dass die Leistungsfahigkeit stark von der aktuellen Kanalimpulsantwort abhangt.

Dies wird anhand der Betrachtung von Gl. (13.3.24a) aus [Kam08] deutlich, mit der die Fehlerwahr-scheinlichkeit beiM -stufiger PSK-Ubertragung (PSK,Phase Shift Keying) und gegebener Kanalimpuls-antwort abgeschatzt werden kann:

PS ≈ 1

2Kγmin

· erfc(

√

ldM · Eb

N0· γ2min · sin

π

M

)

. (13)

Der Einfluß desUbertragungskanals ist hierbei im sogenanntenS/N -Verlustfaktorγ2min enthalten:

γ2min = mine

{e∗F∗Fe}, (14)

der die FaltungsmatrixF – und somit die Kanalimpulsantwort3 f – enthalt und nur diejenigenFehler-vektorene berucksicksichtigt, die das Minimum erfullen. Ein Fehlervektor eines individuellen Fehler-ereignisses der LangeLf ist dabei definiert als ein Vektor der LangeLf − l, der die Abweichung vomdetektierten zum wahren Pfad im Trellisdiagramm beschreibt:

e = [e0, e1, . . . , eLf−l−1]T (15)

3Energienormierung auf Eins wird vorausgesetzt


mit

eν =1

dmin

(

d(i0 + ν)− d(i0 + ν))

. (16)

Auf den VorfaktorKγminin (13) soll hier nicht weiter eingegangen werden, da die Fehlerwahrscheinlich-

keit insbesondere bei großemS/N -Verhaltnis starker vom Argument dererfc-Funktion beeinflußt wird.Seine Definition wird der Vollstandigkeit halber angegeben:

Kγmin=

∑

e|γmin

w(e)

Lf−l−1∏

ν=0

m(eν)

M. (17)

Die Definitionen fur dasHamming-Gewichtw(e) und den Faktorm(eν) sind bei Bedarf [Kam08] zuentnehmen.

Entscheidend bei der Bestimmung der Fehlerwahrscheinlichkeit gemaß Gl. (13) ist die Berechnung desS/N -Verlustfaktorsγ2min aus (14), der fur weitere Untersuchungen in Hinblick auf worst-case Kanaleumgeformt werden soll:

γ2min = mine

{f∗ REee f}. (18)

Hierbei beschreibtf den Vektor der Kanalimpulsantwort, bei dem die Elemente in umgekehrter Reihen-folge angeordnet sind:

f = [f(l), f(l − 1), . . . , f(0)]T . (19)

Die Nutzung der Karhunen-Loeve Transformation erlaubt die Beschreibung der Energie-Autokorrela-tionsmatrixRE

ee mittels orthonormaler Basisvektorenqν in der Form

REee = UΛU∗, (20)

wobeiU eine Matrix darstellt, deren Spalten aus den Eigenvektorenuν von REee bestehen undΛ die

Diagonalmatrix mit den zugehorigen Eigenwertenλ0, . . . , λl gemaß Gl. (13.3.27) bezeichnet. Mit Hilfedieser Umformung kann Gl. (18) alternativ geschrieben werden als

γ2min = mine

{f∗ UΛU∗ f} = mine

{

l∑

ν=0

λν |f∗uν |2}

. (21)

Aus diesem Ausdruck kann bei eingehender Betrachtung geschlossen werden, dass der gesuchte Mini-malwertγ2min dann erreicht wird, wenn furf der Eigenvektor mit dem minimalen zugehorigen Eigenwerteingesetzt wird, und dasγ2min identisch ist mit diesem kleinsten Eigenwert.

Mit den oben angegebenen Herleitungen konnen zwei unterschiedliche Aufgaben formuliert werden:

1. Die Suche nach solchen AutokorrelationsmatrizenREee gemaß Gl. (20), die global minimale Eigen-

werte aufweisen, fuhrt auf bestimmte Fehlervektorene. Anhand von Gl. (21) konnen mit diesenFehlervektoren leicht die entsprechende “ungunstigste”Kanalimpulsantwortf , d.h. die schlechte-stenUbertragungsbedingungen, und der zugehorigeS/N -Verlustfaktor bestimmt werden. Die Su-che nach den Fehlervektoren ist (insbesondere bei Kanalenhoherer Ordnung) mathematisch sehraufwendig; in [Kam08] sind die Kanalimpulsantworten fur ungunstigste Kanale 1. und 2. Ordnungangegeben.

2. Bei bekannter Kanalimpulsantwortf konnen diejenigen Fehlervektoren gefunden werden, dieGl. (14) erfullen. Mit diesen wird dann der Wert vonγ2min bestimmt, um die Symbolfehlerwahr-scheinlichkeit gemaß Gl. (13) abschatzen zu konnen. Diese Fehlervektoren (“Fehlermuster”) sindgleichzeitig diejenigen Fehler, die bei einer Detektion amhaufigsten beobachtet werden konnen.


Beispiel: Ungunstigster Kanal 2. Ordnung, QPSK-UbertragungNach [Kam08], Kap. 13.3.3, sind insgesamt vier ungunstigste Kanale 2. Ordnung bekannt, die jeweils zueinemS/N -Verlust vonγ2min = 3.3 dB fuhren:

f1 = [α, β(1 + j), jα]T f2 = [α, −β(1 + j), jα]T

f3 = [α, β(1− j), −jα]T f4 = [α, −β(1− j), −jα]T ,(22)

mit α = 0.4680 sowieβ = 0.5301. Die zugehorigen Fehlervektoren weisen die Lange 3 auf:

e1 = a · [1, −(1 + j), j]T e2 = a · [1, (1 + j), j]T

e3 = a · [1, −(1− j), −j]T e4 = a · [1, (1− j), −j]T .(23)

wobei zu jedem Kanal jeweils vier verschiedene Fehlervektoren gehoren:a∈{+1, −1, +j, −j}. DerKanalf1 fuhrt also beispielsweise haufig zu dem Fehlermustere1, also zu den vier Fehlervrektoren

e1,1 = [1, −1− j, j]T e1,2 = [−1, 1 + j, −j]T

e1,3 = [j, 1− j, −1]T e1,4 = [−j, −1 + j, +1]T .(24)

Die Symbolfehlerwahrscheinlichkeit kann bei der zugrundegelegten QPSK-Ubertragung durch

PS ≈ 3

8· erfc

(

√

0.4689 · Eb

N0

)

(25)

abgeschatzt werden. InAbb. 8 ist dargestellt, wie stark die Symbolfehlerwahrscheinlichkeit trotz derViterbi-Entzerrung gegenuber dem idealen Kanal ansteigt. Zum Vergleich ist zusatzlich die (sehr vielhohere) Fehlerwahrscheinlichkeit eingetragen, die sichbei einer linearen Entzerrung mit einem Symbol-taktentzerrer des Gradesn = 31 ergibt.

0 5 10 1510

-4

10-3

10-2

10-1

100 QPSK, ungunstigster Kanal 2.Ordnung

Eb/N0 [dB] →

PS →

idealer Kanal

Viterbi (analytisch)

Viterbi (Simulation)

lin. Entzerrer (n=31)

Abb. 8: Symbolfehlerwahrscheinlichkeit unter ungunstigen Kanalbedingungen

2.4 Der Viterbi-Algorithmus zur Faltungsdecodierung

Im Gegensatz zu FIR-Kanalen, deren Einflusse auf das gesendete Signal unerwunscht sind und einefehlerfreie Ubertragung storen, wird die Faltungscodierung vor derUbertragung gezielt zur Fehler-bekampfung verwendet. In beiden Fallen wird mit dem Viterbi-Algorithmus die Wirkung einer Faltungruckgangig gemacht – es wird gewissermaßen “entfaltet”.


2.4.1 Faltungscodierung

Faltungs-Encoder uberfuhren eine Sequenz von Eingangssymbolen (“Infobits”) in eine Sequenz vonAusgangssymbolen (“Codebits”), indem die Infobits mit einem Satz von Generatorkoeffizienten gefaltetwerden. Dabei wird die Summation als Modulo-2-Addition ausgefuhrt. Die Zustandsubergangsfunktiondes Faltungs-Encoders (Mealy-Automat) ist hier ebenfallsdurch die Schieberegisterkette bestimmt. ImGegensatz zu FIR-Kanalen, bei denen nurein Satz von FIR-Koeffizienten vorliegt, wird hier mit minde-stens (und inAbb. 9 genau) zweiGeneratorpolynomen“gefaltet”. An den Stellen, an denen die Koeffi-zienten der Generatorpolynome Null sind, existieren keineAbgriffe. Die Gedachtnislangeℓ (Anzahl derSpeicherplatze) entspricht dem Polynomgrad der Generatorpolynome.

Im Gegensatz zu FIR-Kanalen, bei denenpro Eingangssymbol ein Ausgangssymbolentsteht, das al-lerdings aus einem großeren Alphabet stammen kannAy ⊂ R, entstehen hier je nach CoderateproEingangssymbol mehrere Ausgangssymbole, die allerdings dem selben Alphabet entstammen wie dieEingangssymbole:Ay = Ax = {0, 1}.

. . .x

g

g

g

g

g

g

g

g

g

g

g

g

g

g

w. . .D D D D D

Abb. 9: Faltungscoder fur einen Code der RateR = 1/2 mit den Generatorpolynomeng0 = (1, 1, 0, 0, 0, . . .1, 1)undg1 = (0, 1, 0, 0, 1, . . .1, 1)

2.4.2 Die Metrik bei Faltungsdecodierung

Fur den AWGN-Kanal wird das binare Eingangsalphabet zweckmaßigerweise aufAx = {−1, 1} fest-gelegt, damit die folgende Vereinfachung durchgefuhrt werden kann. Der Kanal liefert das Ausgangsal-phabetAy = R, siehe Abb. 5. Die Verteilungsdichtefunktion der Empfangsdaten fur ein gesendetesxiund ein empfangenesyi lautet in diesem Fall

p(yi|xi) =1√πN0

· e−(yi−xi)

2

N0 . (26)

Fur die Viterbi-Metrik ergibt sich entsprechend Gl. (5) daraus

L(y|x) = maxµ

{

∑

i

Lµ(yi|xµi)}

= maxµ

{

∑

i

ln p(yi|xµi)}

= maxµ

{

∑

i

(

ln1√πN0

− y2iN0

−x2µiN0

+2yixµiN0

)}

.

Da Konstanten in der Summe keinen Einfluß auf die Maximierunghaben, konnen die Termeln 1√πN0

undx2µi

N0wegenx2µi = 1 weggelassen werden:

L(y|x) = maxµ

{

∑

i

(

− y2iN0

+2yixµiN0

)}


Der Term y2iN0

ist nur voni abhangig, liefert also zu jeder Summe denselben Beitrag und beeinflußt dieMaximierung uberµ nicht. Damit zerfallt das Metrik-Inkrement in ein einfaches Skalarprodukt:

L(y|x) = maxµ

{

∑

i

(yixµi)

}

, (27)

was die Verarbeitung von unquantisierten Empfangssymbolen (Soft-Decision-Inputs) erlaubt. Es ist zurEmpfangsfolgey die Codefolgex so zu wahlen, dass die Summe der Skalarprodukte ihrer korrespon-dierenden Elemente maximal wird.

Dies entspricht einer Minimierung des Euklidischen Abstandes zwischen Empfangsfolge und gesuchterCodefolge (nach Satz 1.4 aus [Fri96]).

3 UBUNGSAUFGABEN 15

3 Ubungsaufgaben

Zur Erinnerung : Diese Aufgaben sindvor dem Versuchstermin schriflichzu losen und dieeigenenschriftlichenLosungen zu Beginn des Versuches vorzulegen. Wahrend desVersuches werden die Aufga-ben von Euch an der Tafel vorgerechnet. Nur wer seine eigenenLosungen vorlegen und erlautern kann,wird zu der Versuchsdurchfuhrung zugelassen!

Falls Ihr ein ausfuhrliches Protokoll anzufertigen habt,sind in dieses Protokoll die (korrigierten) LosungenderUbungsaufgaben zu ubernehmen!

Aufgabe 1: Parameter des Viterbi-Algorithmus Kap. 13.2

Geben sei die ModulationsstufigkeitM und die Lange der KanalimpulsanwortK = l+ 1. Geben Sie inallgemeiner Form

• die Anzahl an ZustandeZ,

• die Anzahl an Pfaden, die einen Zustand verlassen bzw. in einem Zustand enden,

• die Gesamtanzahl anUbergangspfaden je Zeitpunkt

an. Welche Werte ergeben sich fur dieUbertragung von 8-PSK Symbolen uber einen Kanal der Ordnung2?

Aufgabe 2: Intersymbolinterferenz (ISI) bei QPSK Kap. 13.2

Uber einen gedachtnisbehafteten Kanal 1. Ordnung mit der reellen Symboltaktimpulsantwort

f = [0.8, 0.6]T

werden statistisch unabhangige, gleichverteilte QPSK-Symbole ubertragen. Die QPSK-Symbole ent-stammen dabei dem Symbolalphabet

d1 =1 + j√

2, d2 =

−1 + j√2

, d3 =−1− j√

2, d4 =

1− j√2

.

a) Skizzieren Sie das Symboltaktmodell desUbertragungskanals.

b) Berechnen Sie beispielhaft die sich ergebenden Signalniveausw11 und w42 am Ausgang desKanals fur die beiden Eingangssymbol-Kombinationen{d(i) = d1, d(i− 1) = d1} bzw.{d(i) =d4, d(i− 1) = d2}.

c) Skizzieren Sie das sich ausallen moglichen Eingangssymbol-Kombinationen ergebende Signal-raumdiagramm am Kanalausgang.

d) Zeichnen sie das Trellis-Diagramm und den zugehorigen Pfad durch das Trellis fur die Symbolse-quenz

{d(i)} = {1+j√2, 1−j√

2, −1−j√

2, −1+j√

2, −1−j√

2} for i = 0, . . . , 4

{d(i)} = {−1−j√2} for i < 0, i ≥ 5

3 UBUNGSAUFGABEN 16

Aufgabe 3: Trellis-Diagramm fur einen Kanal 2. Ordnung Kap. 13.2

Es erfolgt eine BPSK-Ubertragung uber einen Kanal, dessen Basisband-Symboltaktmodell eine Impuls-antwort der Lange 3 aufweist. Zeichnen Sie denjenigen Pfadins zugehorige Trellis-Diagramm ein, derder folgenden Datenfolge entspricht:

{d(i)} = {1,−1, 1, 1,−1, 1} fur i = 0, . . . , 5

{d(i)} = {−1} fur i < 0, i ≥ 6

Aufgabe 4: Viterbi-Detektion bei einem Kanal 1. Ordnung Kap. 13.2

Es wird unter Verwendung unipolarer Datend(i)∈ {0, 1} uber einen Kanal mit der Symboltaktimpuls-antwort f = [1, 1]T

ubertragen. Dabei wird weißes, gaußverteiltes Rauschen überlagert.

a) Skizzieren Sie das vollstandige Trellisdiagramm fur die Ubertragung einer Sendefolge der Lange3. Nehmen Sie dabei an, daß der Kanal zu Beginn derUbertragung den Datenwertd = 0 gespei-chert hat und zur Erzeugung eines energiefreien Kanals zum Abschluß derUbertragung als vierterWert in jedem Fall eine “0” gesendet wird.

b) Bestimmen Sie die moglichen Signalniveaus bei ungestorter Ubertragung.

c) Am Empfanger wird die Signalfolge

{y(i)} = {0.9, 1.1, 1.0, 0.8}gemessen. Fuhren Sie den Viterbi-Algorithmus zur optimalen Detektion der gesendeten Daten ausund geben Sie die am wahrscheinlichsten gesendete Datenfolge an.

Aufgabe 5: Trellis-Diagramm eines Faltungs-Encoders Kap. 4 in [KW10]

Erstellen Sie die Schieberegisterstruktur und das Zustandsubergangsdiagramm eines Faltungscoders mitden Generatorpolynomeng0 = (1, 1, 1) undg1 = (1, 0, 1). Bestimmen Sie fur die Eingangsdatenx ={1, 0, 1, 1, (0, 0)} die Funktionstabelle, tragen Sie die Eingangsdaten in Formeines hervorgehobenenPfades in das Trellisdiagramm ein und geben Sie die Ausgangssymboley an. Orientieren Sie sich dabeian den Abbildungen 4 und 9. Aus wieviel Bits besteht die Ausgangssequenz?

Hinweis: Die letzten beiden Nullen des Vektorsx (in den Klammern) stellen die sog. Tailbits dar,mit denen die Transversalstruktur (in diesem Fall der Faltungscoder) in einen definierten Endzustandgebracht wird; die Tailbits gehoren im engeren Sinne nichtzu den Eingangsdaten.

Aufgabe 6: Faltungsdecodierung Kap. 4 in [KW10] u. Kap. 9 in [Fri96]

Kippen Sie ein beliebiges Datenbit in der Mitte der Ausgangssequenz der vorhergehenden Aufgabe um,und fuhren Sie eine Decodierung mit dem Viterbi-Algorithmus aus. Benutzen Sie bei der Berechnung derMetrik die Hamming-Distanz (Hamming-Distanz zweier Bitfolgen: Anzahl der unterschiedlichen Bits).Kann der Fehler behoben werden?

Hinweis: Die Losung dieser Aufgabe erfolgt auf freiwilliger Basis.

4 VERSUCHSDURCHFUHRUNG 17

4 Versuchsdurchfuhrung

Auch bei diesem Praktikumsversuch soll das Verstandnis für das Themengebiet mit Hilfe von Soft-waremodellen in der Programmumgebung MATLAB vertieft werden. Der VA wird dabei, wie bereitsin Abschnitt 1 erwahnt, zum einen fur dieKanalentzerrungund zum anderen in derKanalcodierungangewendet.

Verwendetem-Files

Einige haufig benotigte MATLAB -Befehle sind in Tabelle 1 zur Erinnerung zusammengestellt.

who list variables in memorywhat list m-files of current directorysize row and column dimensionsfind find indices of non-zero elements

load load variables from disksave save variables to file

plot linearx/y plotsemilogy semi-logx/y plot

subplot split graph windowtitle plot titlegrid draw grid linesaxis manual axis scalingzoom zoom in/out on 2-D plot

zplane z-plane zero-pole plotimage displays a matrix as an image

Tabelle 1: Ubersicht wichtiger MATLAB -Funktionen.

Daneben werden zur Durchfuhrung der einzelnen Versuchspunkte spezielle MATLAB -Routinen benotigt,welche in Tabelle 2 aufgelistet sind. Die notwendigen Informationen bezuglich der entsprechendenEingabesyntax sowie der erforderlichen Parameter konnenSie bei Bedarf (wie immer in MATLAB ) mitderhelp -Funktion abrufen.

Hinweis 1: Zur Vereinfachung der Versuchsdurchfuhrung ist eine MATLAB-Routine vitlab.m vor-gegeben, in der einige Variablen definiert sind. In dieses File sind alle folgenden Versuchspunkte bzw.

Kap. 4.1vitdemo Demonstration VA bei zweistufigerUbertragungvitloss VA-Analyseprogrammdig_mod Symbolerzeugung fur digitale Modulationconvfir Faltung fuerviterbi.mrausch Erzeugung eines Rauschvektorsviterbi Viterbi-Detektorqpskcomp Vergleich von QPSK-Symbolvektoren

Kap. 4.2convcod Faltungscoder fuerviterbi.mviterbi Viterbi-Decoder

Tabelle 2:Zu verwendende MATLAB m-Files.


die erforderlichen Kommandosequenzen zu schreiben (Teilweise auch schon im Programm enthalten).Im Laufe der Versuchsdurchfuhrung entsteht damit ein Programm, welches schließlich den gesamtenVersuch wiedergibt. Um nicht immer das gesamtem-File ausfuhren zu mussen, ist es sinnvoll, entwedernur Teile des Programms unter Verwendung des Editors (Markieren & Rechte Maustaste & EvaluateSelection) auszufuhren oder aber einzelne Programmteilegezielt auszukommentieren (“Einklammern”der Passagen inif 0 ... end ).

Hinweis 2: Innerhalb dieses Kapitels weisen die Symbole⇒ Plot und ⇒ Text-File darauf hin, dassdie entsprechende Grafik gespeichert werden sollte bzw. dieaktuelle Ausgabe in einen Text-Datei (zumBespiel fur das evtl. anzufertigende Protokoll) gesichert werden sollte. Die Grafiken konnen mit demMATLAB eigenen Format* .fig fur die weitere Bearbeitung zu Hause mit MATLAB und/oder in dasfur das verwendete Text-System beste Format gespeichert werden (* .eps fur Latex und* .emf furWord). Ihr solltet diese Hinweise unbedingt beachten, da ihr damit viel Zeit einsparen konnt!

4.1 Kanalentzerrung

4.1.1 Vorbereitungen

Um die Beschreibung der Versuchsdurchfuhrung zu erleichtern ist eine MATLAB-Routinevitlab.mvorgegeben, in der folgende Variablen erzeugt werden:

NumSym = 1000; % Anzahl zu uebertragender SymboleEsNoh = 11; % Es/No "high" in dBEsNol = -4; % Es/No "low" in dB

alphabet = 1/sqrt(2) * [1+j; -1+j; -1-j; 1-j]; % QPSK-SymbolalphabetSnutz = ( sum(abs(alphabet).ˆ2) ) / length(alphabet);

% Symboltakt-Kanalimpulsantworten: ------------------ ----------------% a) unguenstigster Kanal 1.OrdnungTheta = 0; % Theta: {0, pi/2 pi, 3 * pi/2}f1 = 1/sqrt(2) * [1; -exp(j * Theta)];f1 = f1/sqrt(sum(abs(f1).ˆ2)); % Leistungsnormierung auf "1"fl1 = length(f1); % Laenge der Kanalimpulsantwort

% b) "normaler" (beliebiger) Kanal 2.Ordnungf21 = [1.0; 0.8 * exp(j * 0.6 * pi); 0.2 * exp(j * 1.1 * pi)];f21 = f21/sqrt(sum(abs(f21).ˆ2)); % Leistungsnormierung auf "1"fl21 = length(f21); % Laenge der Kanalimpulsantwort

% c) unguenstigster Kanal 2.Ordnungalpha = 0.4680;beta = 0.5301;f22 = [alpha; beta * (1+j); j * alpha];f22 = f22/sqrt(sum(abs(f22).ˆ2)); % Leistungsnormierung auf "1"fl22 = length(f22); % Laenge der Kanalimpulsantwort

Bei der Ausfuhrung des Programms werden die Variablen definiert und entsprechendAbb. 10 die Im-pulsantworten und Nullstellnplane dargestellt.

VP-1: Berechnen Sie zu den beidenES/N0-WertenEsNoh=11 dB undEsNol= -4 dB die ent-sprechendenEb/N0-Werte in dB fur eine QPSK-Ubertragung.


0 0.5 1 1.5 20

0.5

1

|f1|

−>

plot(abs(.))

−1 0 1−1

0

1

Real part

Imag

inar

y pa

rt

zplane(.)

0 0.5 1 1.5 20

0.5

1

|f21|

−>

−1 0 1−1

0

1

Real part

Imag

inar

y pa

rt

0 0.5 1 1.5 20

0.5

1

t/T −>

|f22|

−>

−1 0 1−1

0

1

Real partIm

agin

ary

part

Abb. 10: Impulsantworten und Nullstellenplane der verwendetenUbertragungskanale

4.1.2 Demonstrationsprogramm VA (zweistufigeUbertragung)

Das hier zu verwendende Demonstrationsprogrammvitdemo dient der Veranschaulichung grundlegen-der Mechanismen bei der Viterbi-Detektion. Der Aufruf ist denkbar einfach und erfordert lediglich dieAngabe der Kanalimpulsantwort und desES/N0-Verhaltnisses in dB, z.B.vitdemo(f21,EsNoh) .Dargestellt wird daraufhin ein Ausschnitt aus einem Trellisdiagramm, wobei die Pfadentwicklung unddamit eine Detektion von Daten aus einem eingeschwungenen Zustand heraus verfolgt werden kann,indem auf einen beliebigen Tastendruck die Pfadentwicklung fortgesetzt wird. Die Daten werden zuBeginn jedes Aufrufes zufallig ausgewahlt.

An der linken Bildseite sind die “alten” Summenpfadkosten jedes Zustandes angegeben; diese werdennach jeweils zwei Tastendrucken mit den aktuellen Summenpfadkosten uberschrieben. Nach rechts ent-wickeln sich die Pfade immer weiter, wobei zunachstbeidein einen Zustand mundenden Pfade zusam-men mit ihren Summenpfadkosten gestrichelt eingezeichnetwerden. Die niedrigeren Pfadkosten sind helldargestellt und werden auf Tastendruck ubernommen, wahrend die grauen Pfadkosten dem absterbendenZweig zuzuordnen sind. Die entschiedenen Daten sind nach links ab der erfolgten Pfadvereinigungeingetragen – diese konnen mit den ursprunglichen Sendedaten, die am unteren Bildrand angegebensind, verglichen werden.

Fuhren Sie wiederholt Experimente bei zwei unterschiedlichen Konstellationen durch:

1. Konstellation: Kanalf21 bei niedrigem Rauschen:vitdemo(f21,EsNoh)2. Konstellation: Kanalf22 bei starkem Rauschen:vitdemo(f22,EsNol)

Fuhren Sie jeweils mehrere Versuche durch (etwa acht) und beantworten Sie folgende Fragen:

VP-2: WelchemaximalePfadvereinigungslange konnen Sie bei Ihren Versuchen jeweils fur die ersteund die zweite Konstellation beobachten? Wie groß ware diese nach einer Faustformel?

VP-3: Bei welcher Konstellation (1. oder 2.) tritt dieim Mittel großere Pfadvereinigungslange auf?Begrunden Sie diese Beobachtung!


VP-4: Welcher Nachteil ergibt sich dadurch, dass man eine Datenentscheidung erst nach erfolgterPfadvereinigung durchfuhren kann?

VP-5: Beobachten Sie die Entwicklung der Pfadkosten ineinemZustand bei der ersten Konstellation.Kann es vorkommen, dass die Summenpfadkosten in diesem Zustand bei Euklidischer Metrik – alsoeinem positiven Inkrement – von einem Schritt zum nachstenabnehmen? Veranschaulichen Sie IhreErlauterungen an einem konkreten Beispiel.⇒ Plot

Stellen Sie anhand der wahren und der detektierten Daten fest, wann eine Fehlentscheidung bei derzweiten Konstellation vorliegt.

VP-6: Skizzieren Sie ein entsprechendes Stuck aus dem Trellisdiagramm mit zwei vorhergehendenund drei nachfolgenden Schritten, wobei Sie den wahren und den geschatzten Pfad einzeichnen und dieentsprechenden Daten zuordnen.Uber wieviele Symbole erstreckt sich die Pfadabweichung?⇒ Plot

4.1.3 Fehleranalyse fur den VA bei QPSK-Modulation

Unter Verwendung des Programmesvitloss sollen fur alle drei KanaleS/N -VerlustfaktorengamundFehlervektorene_vek festgestellt werden:

[gam1, e_vek1 ] = vitloss(f1);[gam21,e_vek21] = vitloss(f21);[gam22,e_vek22] = vitloss(f22);

Das Programm liefert als Ausgabeparameter durch systematische Suche alleS/N -Verlustfaktoren in dB(z.B. gam1) und die zugehorigen Fehlervektoren (z.B.e_vek1 ) bis zur Lange drei, absteigend sortiertnach dem großtenS/N -Verlust. Da die Ausgabeparameter eine hohe Dimension besitzen, ist es sinvoll,sich jeweils gezielt nur den hier interessanten Anfang anzusehen, beispielsweise mittelsgam22(1:10)odere_vek22(1:10,:) .

VP-7: Stellen Sie fur alle drei Kanale denS/N -Verlustfaktorγ2min fest. Was bedeutet ein Verlust von0 dB und in welchem Fall tritt dieser auf?

VP-8: Geben Sie in einer Tabellefur den Kanalf22 die ersten zehn Verlustfaktoren mit den dazuge-horenden Fehlervektoren an.

VP-9: Stellen Sie durch einen Vergleich fest, welcher Index (1 bis4) aus Gl. (22) den Kanalf22bezeichnet und welcher Index aus Gl. (23) zu den notierten vier Fehlervektoren zuγ2min gehort. OrdnenSie dazu jedem der vier Fehlervektoren den Parametera zu.

4.1.4 Kanalentzerrung bei QPSK-Modulation

Die Untersuchungen fur die Kanalentzerrung werden hier ausschließlich mit dem ungunstigsten Kanal2. Ordnungf22 durchgefuhrt. Die fur die Durchfuhrung benotigten MATLAB -Eingaben sind der Ein-fachheit halber im Folgenden angegeben und bereits invilab.m enthalten:

% Symbolerzeugung -> "Sendesymbole"sym_o = dig_mod(alphabet,NumSym);

% Sender im eingeschwungenen Zustand mit Tailbits:sym_c = convfir(f22,sym_o,alphabet);

% Rauschen addieren -> "Empfangssymbole"sym_r = sym_c + rausch(EsNoh,Snutz,length(sym_c));


% Viterbi-Entzerrung -> "detektierte Symbole"sym_v = viterbi(sym_r,f22,alphabet);

% Vergleich Ein-/Ausgangsfolge -> Fehlervektor, Symbolfe hlerrate:[e_vec,SER] = qpskcomp(sym_o,sym_v);

% Bestimmen der Fehlerstellen und Fehlervektorene_idx = find(e_vec);fehlertab = [e_ind real(e_vec(e_idx)) imag(e_vec(e_idx) )];sprintf(’ | %3d || %4.1f | %4.1f |\n’, fehlertab.’);

VP-10: Das Programmvilab.m enthalt die entsprechenden Programmzeilen zur Darstellung dervier erzeugten Signale in einem Signalraumdiagramm. Wie erklaren Sie, dass die detektierten Symbo-le sym_v im Signalraum exakt auf den Sendesymbolensym_o liegen, obwohl bei derUbertragungoffensichtlich Fehler auftreten?

Fuhren Sie in der oben angegebenen Weisemindestens sechsSimulationen mit unverandertemES/N0-Verhaltnis durch und beantworten Sie dabei die folgenden Fragen (lesen Sie sich zunachstalle Fragenbis zum Ende des Abschnitts durch, damit Sie sie evtl. gleichzeitig beantworten konnen).

VP-11: Notieren Sie die auftretenden Symbolfehlerraten in einer Tabelle, so dass Sie am Ende ausallen Simulationen eine mittlere Symbolfehlerrate berechnen konnen. Geben Sie diese mittlere Symbol-fehlerrate an.

VP-12: Vergleichen Sie die mittlere Symbolfehlerrate mit dem abgelesenen Wert aus Abb. 8. WelcherS/N -Verlust gegenuber dem idealen Kanal ist hier festzustellen? Stellen Sie diesen Verlust grafisch unterVerwendung von Abb. 8 dar.

Der Vektore_vec=sym_o-sym_v enthalt die Differenz zwischen gesendeten und detektierten Sym-bolen entsprechend (14) und gibt somit die Abweichung zwischen detektiertem und wahrem Pfad imTrellisdiagramm an.

Betrachten Sie die auftretenden Pfadabweichungen. Stellen Sie hierfur den Betrag der auf die minimaleSignalraumdistanz normierten Fehlerfolge mitstem(abs(e_vec)) dar4. Die zu den Fehlerereignis-sen gehorenden Indizes lassen sich gezielt durche_idx=find(e_vec) finden und die zugehorigenFehlervektoren lassen sich mite_vec(e_idx) ausgeben. (Das Programmvilab.m enthalt bereitsdie entsprechenden Programmzeilen und gibt die Fehlerstellen und die entsprechenden Eintrage desFehlervektors in einer Tabelle aus.)

VP-13: Notieren Sie samtliche auftretenden Fehlervektoren und ihre Auftrittshaufigkeit, indem Siesich gezielt die (komplexen) Werte in den betreffenden Abschnitten in der Kommandozeile ausgebenlassen, z.B.e_vec(e_idx) . Welche “Fehlermuster” tauchen besonders haufig auf? Deckt sich dieseBeobachtung mit den theoretischen Untersuchungen aus Abschnitt 4.1.3 bzw. VP-8: ?

Hinweis: Es sind also zwei Tabellen zu erstellen. In Tabelle A wird fur jedes Experiment (1, 2, 3, ...) diebeobachtete SER notiert. Tabelle B besteht aus zwei Spalten, wobei die erste Spalte die aufgetretenenFehlervektoren (als Zeilenvektoren geschrieben) und die zweite Spalte eine Strichliste fur die Anzahlder Beobachtung enthalt. Sobald ein Fehlervektor zum ersten mal auftritt, notieren Sie diesen in derlinken Spalte und notieren in der Strichliste die erfolgte Beobachtung. Tritt der Fehlervektor im gleichenoder einem der nachfolgenden Experimente erneut auf, so notieren Sie das in der Strichliste. Am Endeerhalten Sie eine Liste mit allenverschiedenenFehlervektoren und die zugehorigeAuftrittsanzahl inallen Experimenten.

4Vergroßern Sie ggf. genauer zu untersuchende Signalabschnitte mittelszoom – fragen Sie bei Bedarf den Betreuer.


4.2 Decodierung von Faltungscodes

In diesem Abschnitt sollen kurz Einzelheiten des VA bzgl. der Faltungsdecodierung behandelt werden.Fuhren Sie das im vorherigen Abschnitt angelegtem-File fort.

4.2.1 Faltungscode der Rate 1/2

Betrachten Sie einen Faltungscode (FC) mit den Generatorpolynomeng0 = 1+x+ x2 undg1 = 1+x2

und codieren Sie die Datenfolge (1 0 1 1 (0 0)). (Die letzten beiden Nullen in den Klammern sind diesog. Tailbits, die vom Faltungscoderconvcod automatisch eingesetzt werden.) Geben Sie hierzu ein:

G2=[[1 1 1];[1 0 1]];dk=[1 0 1 1];c2=convcod(G2,dk)

VP-14: Uberprufen Sie das Faltungsergebnisc2 , indem Sie es “von Hand” nachrechnen! Wie kommtdie Lange des Vektorsc2 zustande?

4.2.2 FC der Rate 1/3

Wiederholen Sie die Schritte aus dem vorhergehenden Abschnitt fur einen Faltungscode mit den Gene-ratorpolynomeng0 = 1+ x+ x2, g1 = 1+ x2 undg2 = g0 = 1+ x und codieren Sie die Datenfolge (10 1 1 (0 0)). Die MATLAB -Befehle hierzu sind:

G3=[[1 1 1];[1 0 1];[1 1 0]];dk=[1 0 1 1];c3=convcod(G3,dk)

VP-15: Geben Sie eine Formel fur die Langelc3 des Vektorsc3 an, die die GroßenR (Coderate),ld(Lange des Datenvektors ohne Tailbits) undℓ (Grad der Generatorpolynome) enthalt.

4.2.3 Faltungsdecodierung

Nach derUbertragung codierter Bits sind diese ggf. gestort. Die Aufgabe der Decodierung ist es, trotzAbweichungen der empfangenen (gestorten) Codebits von der wahren Codebitfolge, auf die Datenbitszu schließen.

dl=[1 0 1 1 0 1 0 1 1 1];c2=convcod(G2,dl);%***[c2r,fehler]=bschan(c2,0.2); %BSC-Kanal 20% Bitfehlerw ahrsch.fehler’anzahl_fehler_in_codefolge=sum(fehler)dl_hat=viterbi(reshape(c2r,2,length(c2)/2),G2);anzahl_fehler_in_dl_hat=sum(dl_hat ˜= dl)

VP-16: Fuhren sie den MATLAB -Codeausschnitt ab%*** mehrmals aus und beobachten Sie wievieleFehler in der Codebitfolge zu wievielen Fehlern in der decodierten Datenbitfolge fuhren. Hangt derErfolg der Decodierung nur von der Anzahl der Fehler in der Codebitfolge oder auch von deren zeitlicherVerteilung ab?


4.2.4 Soft-Input vs. Hard-Input

Dieser Abschnitt soll dieUberlegenheit einer Soft-Input Decodierung gegenuber Hard-Input Decodie-rung illustrieren. Eine Hard-Input Decodierung ist erforderlich, wenn die empfangenen Codesymbole inhart entschiedener Form (Ac ∈{−1,+1}) vorliegen. Von Soft-Input Decodierung spricht man, wenn dieempfangenen Codesymbole fein quantisiert (Ac ⊂ R) an den Viterbi-Decoder gelangen.

Die MATLAB -Befehle hierzu sind:

dl=fix(rand(1,10000)+0.5);c2=convcod(G2,dl);% Es/No=2dBrauschen = rausch(2,1,length(c2));c2r=(2 * c2-1)+rauschen;% VA-SoftInputdl_hat_soft=viterbi(reshape(c2r,2,length(c2)/2),G2) ;soft_errors=sum(dl_hat_soft˜=dl)% VA-HardInputdl_hat_hard=viterbi(round(reshape(c2r,2,length(c2)/ 2)),G2);hard_errors_v=(dl_hat_hard˜=dl);hard_errors=sum(hard_errors_v)

VP-17: Mit welcher Art der Decodierung erhielt man die niedrigere Fehlerrate? Wie erklaren Sie dies?

4.2.5 Fehlerstruktur

Die im vorangegangenen Abschnitt decodierte Datenbitfolge hard_errors_v enthalt Fehler. Ver-anschaulichen Sie diesen Fehlervektor mitfehlbild(hard_errors_v) . Die dargestellte Matrixenthalt zeilenweise den Vektorhard_errors_v . Fehler sind mit schwarzen Punkten dargestellt.

VP-18: Sind die Fehler nach einer Viterbi-Decodierung uberwiegend Einzel- oder Bundelfehler?Erhohen Sie zudem das Rauschen (Es/N0 = 0 dB) und beobachten Sie die Fehlerstruktur erneut (derfolgende Matlab-Code ist ein Ausschnitt aus dem vorherigenVersuchspunkt):

% Es/No=0dBrauschen = rausch(0,1,length(c2));c2r=(2 * c2-1)+rauschen;% VA-HardInputdl_hat_hard=viterbi(round(reshape(c2r,2,length(c2)/ 2)),G2);hard_errors_v=(dl_hat_hard˜=dl);fehlbild(hard_errors_v)

Documents

Schwerpunktlabor Nachrichtentechnik Viterbi-Algorithmus ... · 1 EINFUHRUNG¨ 1 1 Einfu¨hrung 1.1 Motivation In diesem Versuch wird mit dem Viterbi Algorithmus (VA) ein fundamentaler