Cryptography Reference
In-Depth Information
Der Zustandsgraph bietet eine Möglichkeit der Bestimmung der
freie
n
Dis-
tanz
, eine wichtige Eigenschaft von Faltungskodes. Dazu betrachtet man alle
Eingangsfolgen, die zum Zeitpunkt
t
=0
den Nullzustand verlassen und nach
wenigen Übergängen (frühestens nach
(
k
+1)
) zum ersten Mal wieder in den
Nullzustand übergehen. Die freie Distanz ergibt sich dann aus dem minimalen
Gewicht der Ausgangsfolgen, bezogen auf unser Beispiel:
nach 3 Übergängen:
a
1
= (100)
−→
a
1
= (11 01 11)
−→
w
(
a
1
)=5
,
nach 4 Übergängen:
a
2
= (1100)
−→
a
2
= (11 10 10 11)
−→
w
(
a
2
)=6
.
Die freie Distanz ist damit
d
f
=mi
i
w
(
a
i
)=5
.
Bei optimalen Generatormatrizen ist
d
f
meist nach
(
k
+1)
oder
(
k
+2)
Über-
gängen bestimmt. Ein Vergleich mit dem Gewicht dieser Matrizen offenbart,
dass dann auch
d
f
=
w
(
G
)
oder
d
f
=(
w
(
G
)
−
1)
ist.
Über den bekannten Zusammenhang
d
min
(
d
f
)=2
f
k
+1
berechnet sich der
Fehlerkorrekturgrad
f
k
. Je nach Fehlerstruktur kann die
Anzahl korrigierbarer
Fehler
auch bei
d
f
liegen, d. h.
über die begrenzte Mindestdistanz hinaus!
Für diese Umsetzung ist es notwendig, Zusammenhänge in zeitlicher Entwick-
lung darzustellen. Dazu wird der Zustandsgraph zeitlich „abgerollt“. Zunächst
das
Baumdiagramm
(für vorliegendes Beispiel):
00
00
00
Jeder Pfad widerspiegelt eine mög-
liche Eingangsfolge. Jede Eingangs-
folge und damit auch Kanalkodefol-
ge beginnt im Nullzustand, d. h., der
Wurzelknoten des Baumes ist im-
mer auch Startknoten. Bei Eingabe
von
u
(
t
)=0
geht die Bewegung
vom Knoten
z
(
t
)
immer nach oben
und liest die entsprechende Kanten-
bewertung
v
(
t
)
aus, gleiches bei Ein-
gabe von
u
(
t
)=1
und Abwärts-
bewegung. Die Eingangsfolge unter-
liegt (eigentlich) keiner Begrenzung.
Nach
t
=(
k
+1)
Eingaben wieder-
holt sich die Struktur und wächst
allerdings mit
t
exponentiell. Die-
se Beschreibungsform nutzt man für
die sequentielle Dekodierung (s. Ab-
schn. 8.6.3.1).
00
11
10
00
01
01
11
v(t)=
00
10
10
11
0
u(t)=
00
1
00
11
01
11
01
00
10
10
01
10
10
11
01
11
