Cryptography Reference
In-Depth Information
Das
Trellisdiagramm
ist eine Art Kombination von Zustands- und Baumdia-
gramm. Führen Pfade zum Zeitpunkt
t
auf gleiche Folgezustände, dann bringt
man diese auf einen Knoten zusammen. Die Zahl der Knoten ist damit zu je-
dem Zeitpunkt
t ≥ k
genau
2
k
. Das Trellisdiagramm für vorliegendes Beispiel
und Beispielfolge
a
∗
sieht dann folgendermaßen aus:
t
0
1
2
3
4
5
6
z
v=
00
00
11
00
11
00
u(t)=
u(t)=
0
1
11
11
10
01
01
10
10
00
01
10
01
11
a
*
1
1
0
1
0
0
a
11
10
10
00
01
11
verkürztes Trellisdiagramm
Nach
t
=
k
+1
Taktzeitpunkten wiederholt sich das Trellis(diagramm). Zur
Beschreibung und später für die Dekodierung reicht die Kenntnis des verkürz-
ten Trellis aus. Die Kantenbewertungen liefern wieder die Kodesequenzen, die
Kantenlinie (durchgezogen oder gestrichelt) widerspiegelt das Eingabebit. Die
Anzahl Pfade bestimmt die Kardinalität des Faltungskodes, die Kanalkodefol-
gen sind die Pfadbeschreibungen. Das Trellis bildet damit das Kodealphabet
A
vollständig ab. Jede Verlängerung des Trellisdiagramms um
ein
Informati-
onsbit
verdoppelt
die Anzahl der Kanalkodefolgen
a
i
∈
A
.
Im vorliegenden Beispiel wird die Quellenkodefolge durch
k
=2
Null(Termi-
nierungs-)bit abgeschlossen. Damit erreicht man zum einen ein Rücksetzen des
Schieberegisters, zum anderen begrenzt man die Länge der Eingangsfolge auf
l
(= 4)
und somit
l
|
A
|
=2
(= 16)
. Alle Kanalkodefolgen enden im Nullzustand.
Wie im Beispiel gezeigt und auch in praktischen Anwendungen umgesetzt, ist
eine feste Eingangslänge zum einen sinnvoll, um den hohen Speicherplatzbedarf
bei der Dekodierung zu begrenzen, zum anderen das Rekonstruktionsergebnis
zu beeinflussen (s. Abschn. 8.6.3). Es sollen deshalb einige Bemerkungen zu
den Möglichkeiten der
Begrenzung von Eingangsfolgen
gemacht werden:
