Viterbi anstatt Entzerrung

[Martin Laabs]

Hallo,

ich lese gerade etwas mehr über digitale Modulation. Dabei sind
mir zwei Dokumente in die Hände gefallen die so geschrieben sind,
dass man meint, die Enztzerrung durch Kanalschätzung sein
lassen könnte w,enn man anstatt eines Schwellwertentscheiders
einen "Maximum-Likelihood Sequence Estimator" bzw. Viterbi-Algorithmus
verwenden würde.
Darauf hin habe ich mich über den Viterbi-Algorithmus informiert aber
diesen eher als sinnvolle Erzgänzng interpretiert.

Konkret geht es um folgendes Dokument:
http://www.comm.uni-bremen.de/teaching/slab/ofdm_ss2005_de.pdf

Dort steht:
Angenommen, es sollen QPSK-Daten mit einer Datenrate von
RS = 0.5 MSymbole/s [...] über einen Typical Urban Kanal
übertragen werden.
Da der TU-Kanal eine Echolaufzeit von Tmax = 7us aufweist,
hätte man also einen Übertragungskanal mit einer Impulsantwort
der Länge 3.5 bzw. 4. [...]
Wollte man die so empfangenen Daten mit einem Viterbi-Entzerrer
entzerren, entspräche dies einem Aufwand von 4^3 Zuständen.

Nun gehe ich aber davon aus, dass der Viterbi-Entzerrer eher
als Fehlerkorrektur für falsch entschiedene Daten gedacht ist.
Und dies gilt es ja schon im vorhinein durch eine gute Kanalschätzung
zu vermeiden.

Und dann macht die obrige Aussage für mich keinen allzugroßen Sinn
mehr. Oder liege ich da falsch und es gibt verschiedene Entzerrer
von Viterbi?

Vielen Dank
Martin L.

 

[Oliver Bartels]

Hi Martin.
On 29 Oct 2005 20:21:57 GMT, Martin Laabs <98malaab@gmx.de> wrote:

ich lese gerade etwas mehr über digitale Modulation. Dabei sind
mir zwei Dokumente in die Hände gefallen die so geschrieben sind,
dass man meint, die Enztzerrung durch Kanalschätzung sein
lassen könnte w,enn man anstatt eines Schwellwertentscheiders
einen "Maximum-Likelihood Sequence Estimator" bzw. Viterbi-Algorithmus
verwenden würde.

Jein.

Schau mal unter dem Stichwort Forney-Empfänger nach.
Es gibt ein Matched Filter, welches aber beadrfsweise an
den Kanal angepasst werden darf (Entzerrer), dann ein
Dekorellationsfilter auf Symboltaktebene (wird gerne
weggelassen), welches den Einfluß des Matched Filter
auf das Rauschen wieder rückgängig macht, und dann
besagter (Viterbi, es gibt aber auch andere Maximum
Likelyhood-) Entscheider.

Im Prinzip kann ein solcher Entscheider den Entzerrer
bei traditionellen Einzelträger-Modulationen ersetzen,
allerdings nicht immer in der Praxis, da der Rechenaufwand
zu hoch wird.

Darauf hin habe ich mich über den Viterbi-Algorithmus informiert aber
diesen eher als sinnvolle Erzgänzng interpretiert.

Konkret geht es um folgendes Dokument:
http://www.comm.uni-bremen.de/teaching/slab/ofdm_ss2005_de.pdf

Vorsicht, in dem PDF ist von OFDM die Rede, Entzerrung ist da ein
ganz anderes Ding.

Btw.: Besorg Dir doch gleich das ganze Papier:
"Karl-Dirk Kammeyer, Nachrichtenübertragung, 3. Auflage,
Teubner" ist wirklich gut und beschreibt die Zusammenhänge
und kommt aus der Bremer Ecke.

Nun gehe ich aber davon aus, dass der Viterbi-Entzerrer eher
als Fehlerkorrektur für falsch entschiedene Daten gedacht ist.

Nein.
Der Viterbi-Entzerrer _ist_ der Entscheider.

Der bekommt _analoge_ Werte bzw. Wahrscheinlichkeiten herein,
ein klassischer fehlerkorrigierender Code a'la BCH und Reed-Solomon
arbeites mit bereits entschiedenen Bits.

Und dann macht die obrige Aussage für mich keinen allzugroßen Sinn
mehr. Oder liege ich da falsch und es gibt verschiedene Entzerrer
von Viterbi?

Viterbi ist ein schneller Algorithmus zur Bestimmung der Folge
mit der höchsten Wahrscheinlichkeit. Der kann auf vielerlei
Art und Weise eingesetzt werden, genauso wie ein
verschränkter Code per Rauchpfeife ebenso wie hochmodern
auf ein Konstellationsdiagramm übertragen (Trellis) genutzt werden
kann.

Gruß Oliver

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

 

[Martin Laabs]

Hallo Oliver,

Oliver Bartels <spamtrap@bartels.de> wrote:

Im Prinzip kann ein solcher Entscheider den Entzerrer
bei traditionellen Einzelträger-Modulationen ersetzen,
allerdings nicht immer in der Praxis, da der Rechenaufwand
zu hoch wird.

Aber würde die BER nicht besser werden wenn man zusätzlich
zum Entscheider noch einen Entzerrer verwenden würde?
Ich gehe bisher davon aus, dass der Entscheider nur die
zusätzliche Redundanz in den Daten ausnutzt um die Störungen
zu kompensieren.

Vorsicht, in dem PDF ist von OFDM die Rede, Entzerrung ist da ein
ganz anderes Ding.

Ja. Ich wollte eigentlich was über OFDM lernen, bin dabei aber
auf diese Problematik gestoßen.

Btw.: Besorg Dir doch gleich das ganze Papier:
"Karl-Dirk Kammeyer, Nachrichtenübertragung, 3. Auflage,
Teubner" ist wirklich gut und beschreibt die Zusammenhänge
und kommt aus der Bremer Ecke.

Werde ich machen sobald ich das nächste mal in die Bibliothek
komme.

Nein.
Der Viterbi-Entzerrer _ist_ der Entscheider.
Der bekommt _analoge_ Werte bzw. Wahrscheinlichkeiten herein,
ein klassischer fehlerkorrigierender Code a'la BCH und Reed-Solomon
arbeites mit bereits entschiedenen Bits.

Ich habe gestern eine implementation gesehen die nur mit zwei
diskreten Zuständen gearbeitet hat.
Aber ich werde mir mal das Buch ausleihen um einen besseren Überblick
zu bekommen.

Viele Dank
Martin L.

 

[Stefan Engler]

Again: In der Praxis geht beides und die auf "billisch"
gebauten Funksysteme haben keines von beiden ;-/

Bei der QPSK braucht man doch keine Korrektur oder
Frequenzschätzungsverfahren?
Die Signale kommen in einer Ausgangsfrequnz rein - 1. Dibit ist zu
verwerfen da nicht auswertbar. Darauf folgt eine zweite Frequenz.
Anhand des Frequenzunterschiedes zwischen erster und zweiter Frequenz
wird die Bitfolge bestimmt. Die Signale haben immer eine gleich hohe
Amplitude.
Erst bei QAM wird es ja komplexer. Da die Amplitude sich ändert, ist
das Signal nicht mehr so gut vom Hintergrundrauschen zu unterscheiden.

Ich sehe jetzt mal von Empfangssystemen ab, die aus dem Rauschen noch
Singnale dekodieren (häufig bei FSK31 gelesen). Sicher ist hier der
Aufwand wsentlich größer und ohne DSP ist man verloren.
Aber es gibt doch gute Computerprogramme, die dies erledigen (bis 9k6).
Die fressen dann aber auch richtig Rechenleistung. (1GHz reichen für
48kBit/s nicht, kann aber auch am Programm gelegen haben)

 

[Oliver Bartels]

On 30 Oct 2005 08:13:41 GMT, Martin Laabs <98malaab@gmx.de> wrote:

Aber würde die BER nicht besser werden wenn man zusätzlich
zum Entscheider noch einen Entzerrer verwenden würde?
Ich gehe bisher davon aus, dass der Entscheider nur die
zusätzliche Redundanz in den Daten ausnutzt um die Störungen
zu kompensieren.

Der Entzerrer ist bei dem Forney Modell im an die
Kanaleigenschaften angepaßten Matched Filter versteckt.

Ansonsten hat ein Empfänger für einen geeigneten
verschränkten Code schon Eigenschaften, welche
die durch Kanalechos etc. verursachte Intersymbol-
Interferenz berücksichtigen. Besser geht es natürlich
mit Entzerrer, so man die Kanaleigenschaften kennt.
Kennt man sie nicht wirklich (Schwankungen, schnell
bewegte Geräte), dann kann der Schuss mit dem
Entzerrer auch nach hinten losgehen.

( Deshalb versucht man bei OFDM ja, die Kanaleigenschaften
anhand der im _selben_ Symbol vorhandenen Pilotträger
zu schätzen. )

Again: In der Praxis geht beides und die auf "billisch"
gebauten Funksysteme haben keines von beiden ;-/

Ich habe gestern eine implementation gesehen die nur mit zwei
diskreten Zuständen gearbeitet hat.

Üblicherweise bekommt der Viterbi pro Schritt die jeweiligen
Wahrscheinlichkeiten dafür rein, dass es sich bei dem
empfangenen Symbol um den Wert X handelt.

Offensichtlich wird das bei Trellis in I/Q Konstellationsdiagrammen:
Es gibt für den jeweiligen Soll-Wert eines Symbols jeweils einen
Punkt im Diagramm, der empfangene I/Q Wert liegt jedoch zumeist
zwischen mehreren Punkten. Dann nimmt der Empfänger z.B.
den Abstand des Ist-Punktes zu den benachbarten Soll-Punkten
als Mass für die Wahrscheinlichkeit, dass es der jeweilige
Soll-Punkt sei. Der Viterbi-Algorithmus findet dann diejenige
erlaubte Sequenz von Soll-Punkten mit dem (ggf. quadratisch)
geringsten Abstand zu den empfangenen Ist-Punkten, was
dann der wahrscheinlichsten Symbolfolge entspricht.

Gruß Oliver

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

 

[Oliver Bartels]

On 30 Oct 2005 01:41:43 -0800, "Stefan Engler" <Lehrerfreund@web.de>
wrote:

Bei der QPSK braucht man doch keine Korrektur oder
Frequenzschätzungsverfahren?

Oh doch.

Die Signale kommen in einer Ausgangsfrequnz rein - 1. Dibit ist zu
verwerfen da nicht auswertbar. Darauf folgt eine zweite Frequenz.
Anhand des Frequenzunterschiedes zwischen erster und zweiter Frequenz
wird die Bitfolge bestimmt. Die Signale haben immer eine gleich hohe
Amplitude.

man Intersymbolinterferenz

Durch Mehrwegeausbreitung mischt sich ein aktuelles Symbol
beispielsweise mit einem vorangegangenen.

Hat das aktuelle Symbol 0 Grad Winkel und das alte 180 Grad,
dann landet der Punkt irgendwo dazwischen, bei 50% Aufteilung
auf beide Pfade (unwahrscheinlich, aber möglich) ohne
Berücksichtigung eines weiteren Phasenversatzes im Nullpunkt ...

Ohne geeignete Massnahmen (z.B. Equalizer oder verschränkte
Codierung) ist das Symbol dann futsch.

Das macht dann den Unterschied zwischen "zuverlässig Verbindung"
bei Qualitäts-Funksystemen und "häufig Verbindung" bei, ähm,
eher einfach und billisch strukturierter Hardware aus ...

Erst bei QAM wird es ja komplexer. Da die Amplitude sich ändert, ist
das Signal nicht mehr so gut vom Hintergrundrauschen zu unterscheiden.

Das sowieso. QPSK ist bzgl. EB/N0 optimal (deshalb macht BPSK
meist wenig Sinn), die höhere Datenrate der QAM erkauft man
sich natürlich mit einem höheren erforderlichen S/N Verhältnis
für eine sichere Übertragung.

Ich sehe jetzt mal von Empfangssystemen ab, die aus dem Rauschen noch
Singnale dekodieren (häufig bei FSK31 gelesen). Sicher ist hier der
Aufwand wsentlich größer und ohne DSP ist man verloren.
Aber es gibt doch gute Computerprogramme, die dies erledigen (bis 9k6).
Die fressen dann aber auch richtig Rechenleistung. (1GHz reichen für
48kBit/s nicht, kann aber auch am Programm gelegen haben)

Die PC-Architektur ist für Aufgaben wie Equalization und Viterbi
suboptimal. Ein großer Teil des Chipfläche der CPU wird für ganz
andere Dinge genutzt, wie sie von einem Universalrechner
gefordert werden, z.B. Cache, MMU oder, auch nicht zu
vernachlässigen, Branch Prediction. Letztere ist bei einem
FIR-Filter-Algorithmus aber Overkill, es reicht eine einfacher,
vom Compiler oder Programmierer codierter Repeat-Befehl in
Hardware. Umgekehrt tut sich die Intel-Architektur trotz SSE
mit Multiply-Accumulate-Konstellationen schwer, die ein DSP mit
viel weniger Hardware (und Leistungsaufnahme!) dank seiner
dafür ausgelegten Adressgeneratoren und Datenpfade locker
erledigt.

Dafür läuft z.B. ein Programm wie unser Autorouter auch auf
600 MHz DSP's eher schlecht als recht, hier benötigt es die
ausgefeilte Branch Prediction wie auch automatische Resourcen-
verwaltung (Reservation Stations etc.) des Universalrechners
(und ja, das ist bei Intel, AMD & Co. richtig aufwendig,
z.B. weiss man vom Pentium Mobile, dass er eine Hardware
zur Schleifenerkennung implementiert hat, und zwar auch
für Schleifen ohne vorcodierte Anzahl der Iterationen).

Gruß Oliver

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

 

[Henning Paul]

Martin Laabs schrieb:

Btw.: Besorg Dir doch gleich das ganze Papier:
"Karl-Dirk Kammeyer, Nachrichtenübertragung, 3. Auflage,
Teubner" ist wirklich gut und beschreibt die Zusammenhänge
und kommt aus der Bremer Ecke.

Werde ich machen sobald ich das nächste mal in die Bibliothek
komme.

Kannst Dir auch die Vorlesungsfolien zur "Nachrichtenübertragungstechnik"
angucken, sind auch sehr gut und folgen genau dem Buch. Ich habe übrigens
sowohl diese Vorlesung besucht als auch den von Dir erwähnten Versuch im
Labor gemacht.

Der Viterbi-Entzerrer _ist_ der Entscheider.
Der bekommt _analoge_ Werte bzw. Wahrscheinlichkeiten herein,
ein klassischer fehlerkorrigierender Code a'la BCH und Reed-Solomon
arbeites mit bereits entschiedenen Bits.

Ich habe gestern eine implementation gesehen die nur mit zwei
diskreten Zuständen gearbeitet hat.

Du kannst den Viterbi auch zur Dekodierung von Faltungscodes verwenden. Dazu
empfehle ich Dir das Material der Veranstaltung "Kanalcodierung" und das
Laborskript "Viterbi-Algorithmus" aus dem selben Institut.

Gruß
Henning (auch Bremer Nachrichtentechniker, aber z.Zt. im Fachpraktikum)
--
henning paul home: http://www.geocities.com/hennichodernich
PM: henningpaul@gmx.de , ICQ: 111044613