Trellis

In der Kommunikationstheorie und Signalverarbeitung ist ein Trellis eine Graphstruktur, die die Entwicklung eines endlichen Zustandssystems über diskrete Zeitschritte abbildet. Jeder vertikale Schnitt stellt einen Zeitpunkt dar, wobei Knoten mögliche Zustände des Systems repräsentieren. Kanten verbinden Zustände bei aufeinanderfolgenden Zeitschritten und zeigen, welche Übergänge die Kodierung oder Modulation erlaubt. Diese Struktur wird unverzichtbar, wenn man die wahrscheinlichste Folge von Zuständen finden muss, die ein durch Rauschen verfälschtes empfangenes Signal erzeugt hat.

Die Kraft des Trellis verdankt sich dem Viterbi-Algorithmus, der die Struktur des Graphen ausnutzt, um empfangene Daten effizient zu dekodieren. Anstatt jeden möglichen Pfad durch alle Zeitschritte zu prüfen, behält der Viterbi-Algorithmus nur den wahrscheinlichsten Pfad zu jedem Zustand bei jedem Zeitschritt und schneidet unmögliche Zweige weg. Bei einem Faltungscode mit Constraint-Länge 7 und binären Symbolen hat der Trellis typischerweise 26 = 64 Zustände pro Zeitschnitt, was die Suche auch bei langen Nachrichten handhabbar macht.

Trellis-Diagramme erscheinen überall dort, wo beschränkungsbasierte Kodierung verwendet wird: Faltungscodes in Satelliten- und Mobilkommunikation, Turbocodes, LDPC-Codes und sogar bei der Entzerrung von dispersiven Kanälen. Die Struktur des Trellis kodiert direkt die Generatorpolynome oder Paritätsprüf-Beziehungen des Codes. Ein Faltungskodierer mit Rate 1/2 und zwei Rückkopplungsabgriffen erzeugt eine andere Trellis-Topologie als ein Code mit Rate 1/3, und dieser Unterschied zeigt sich in der Anzahl der Kanten pro Knoten und dem Verbindungsmuster.

Der Name "Trellis" kommt von seiner Ähnlichkeit mit einem Gartengitter oder einer Rankgerüststruktur: vertikale Spalten (Zeitschritte) mit diagonalen Verbindungen (Zustandsübergänge). Diese visuelle Metapher hat sich durchgesetzt, weil das Diagramm Ingenieuren tatsächlich hilft zu sehen, wie Zustände sich über die Zeit ausbreiten und wieder konvergieren. Bei Tail-Biting- und zirkulären Trellis-Varianten verbindet sich der letzte Zeitschritt wieder mit den Anfangszuständen und ermöglicht Codes ohne verschwendete Füllbits.

Ein Trellis ist nicht eindeutig an ein bestimmtes Modulations- oder Kodierschema gebunden; es ist ein Darstellungswerkzeug, das sich den Zwangsbedingungen des Systems anpasst. Die gleiche Trellis-Struktur kann von verschiedenen Algorithmen durchlaufen werden: Viterbi für Maximum-Likelihood-Dekodierung, der Forward-Backward-Algorithmus für Soft-Output-Dekodierung oder Belief-Propagation-Methoden für Faktorgraphen. Das Verständnis der Trellis-Struktur ist für Hardware-Entwickler, die Dekoder implementieren, unverzichtbar, da der kritische Pfad und die Speicheranforderungen direkt von der Zweig- und Zustandstopologie abhängen.