Cryptography Reference
In-Depth Information
zwei Stufen) oder als Signalwertfolge vor, dann berechnet sich der Abstand
aus der quadratischen EUKLIDischen Distanz, zeitunabhängig ausgeführt:
i
=1
(
x
i
− y
[
q,
]
i
)
2
m
d
(
E
)
(
x, y
[
q
]
)=
mit
x
i
∈{
+1
, −
1
},y
[
q,
]
i
∈ Q
bzw.
R
.
Der Bearbeitungsaufwand für den Vergleich einer Empfangsfolge mit allen
Kanalkodefolgen wächst exponentiell mit der Anzahl an Informationsstellen
(Länge der Quellenkodefolge). Eine e
ziente Lösung liefert der VITERBI-
Algorithmus. Zunächst sollen dafür Zusammenhänge am Beispiel der hard-
decision Dekodierung aufgezeigt werden. Die beiden folgenden Abschnitte be-
schäftigen sich dann mit der soft-decision Dekodierung, aufgespalten nach Mög-
lichkeiten des soft-input und soft-output.
8.6.3.2.1 Spezialfall: hard-decision Dekodierung
Basis für die Anwendung des VITERBI-Algorithmus ist das Trellisdiagramm
(s. S. 214). Die Bearbeitung erfolgt taktweise. Zum Zeitpunkt
t
wird die Emp-
fangssequenz
y
h
(
t
)
∈{
0
,
1
}
m
mit jeder
Kodesequenz
v
σ
σ
im verkürzten Trellis
verglichen und eine Zweigmetrik berechnet. Am Beispiel der
MD Dekodie-
rung
ist es die HAMMING-Distanz
d
σ
σ
(
H
)
t
(
v
σ
σ
,y
h
(
t
))
,kurzmit
d
σ
σ
(
H
)
t
angege-
ben. Mit
σ
σ
werden die Zustandsübergänge vom Zeitpunkt
t
zum Zeitpunkt
t
+1
beschrieben. Für
σ
und
σ
sind mit
σ
,σ ∈{
0
,
1
, ...,
2
k
−
1
}
2
die
2
k
Zustände definiert, dual oder dezimal angegeben. Die Zweigmetrik
d
σ
σ
(
H
)
t
wird
zum Metrikwert
D
σ
t
addiert. Man erhält den neuen Metrikwert
D
t
+1
, welcher
den kleinsten Abstand von Kodesequenzen zu den Empfangssequenzen zum
Zeitpunkt
t
+1
im Zustand
σ
widerspiegelt:
m
D
σ
t
+
d
σ
σ
(
H
)
t
mit
d
σ
σ
D
t
+1
=min
∀
σ
σ
{
}
(
H
)
t
=
(
v
σ
σ,i
⊕
y
h,i
(
t
))
.
(8.51)
i
=1
Die folgende Darstellung soll die Zusammenhänge nochmals verdeutlichen (ver-
kürztes Trellis aus Beispiel 8.6.2):
VV
t
t+
1
'
00
11
00
D
00
t
d
00,10
t
11
D
10
t+
1
D
00
t
d
00,10
t
D
01
t
d
01,10
t
10
01
= min{
+
,
+
}
10
00
d
01,10
t
01
D
01
t
10
01
11
Nach
t>k
Schritten treffen in jedem Zustand jeweils zwei Übergänge zusam-
men. Es wird nur der Pfad mit der kleinsten Metrik weiterbetrachtet, d. h., zu