Cryptography Reference
In-Depth Information
jedem Zeitpunkt
t
=
k
+1
,k
+2
, ..., l
werden
2
k
Pfade verworfen. Bei gleicher
Metrik entscheidet der Zufall für den überlebenden Pfad (Survivor).
Bei Anwendung von
Terminierung
, in weiteren Betrachtungen zugrunde gelegt,
sind Anfangs- und Endzustand zum Zeitpunkt
t
=0
und
t
=
l
+
k
immer gleich
Null (bei
Tail-Biting
sind diese ein gleiches
σ
zum Zeitpunkt
t
=0
und
t
=
l
,
abhängig von der Quellenkodefolge).
Es überlebt nur eine Kanalkodefolge.
Der
Algorithmus
sieht am Beispiel der MD Dekodierung wie folgt aus:
b
D
t
=
D
0
:= 0
t
=0(1)
l −
1
σ
= 0(1)2
k
−
1
D
t
+1
:= min
∀σ
σ
{D
σ
t
+
d
σ
σ
(
H
)
t
}
Anmerkung 1:
∀σ
σ
bezeichnet alle im Trellis definier-
ten Übergänge zum Zustand
σ
.
i
=1
(
v
σ
σ,i
⊕ y
h,i
(
t
))
m
d
σ
σ
(
H
)
t
=
t
=
l
(1)
l
+
k −
1
σ
= 0(1)2
k
−
1
D
t
+1
:= min
Anmerkung 2:
σ
σ
u
=0
sind Zustandsübergänge mit
Eingabe(Terminierungs-)bit 0.
∀σ
σ
{D
σ
t
+
d
σ
σ
(
H
)
t
}
σ
σ
u
=0
D
l
+
k
;
b
∗
Der Abstand der Empfangsfolge zur geschätzten Kanalkodefolge ist
D
l
+
k
.Mit
dem Survivor sind die Fehler in der Empfangsfolge korrigiert. Die Zurückver-
folgung des Survivors liefert die geschätzte Quellenkodefolge
b
∗
.
Bei der
ML Dekodierung
ändert sich nur die Metrikberechnung. Für Maxi-
mierung soll hier der Metrikwert
Λ
t
stehen:
+1
m
σ
t
+
λ
σ
σ
t
mit
λ
σ
σ
t
σ
Λ
t
+1
=max
∀
σ
σ
{
Λ
}
=
v
σ
σ,i
⊕
y
h,i
(
t
)
.
(8.52)
i
=1
Treffen jetzt zwei Übergänge zusammen, dann wird der Pfad mit der größten
Metrik (größten Übereinstimmung) weiterbetrachtet.
MD/ML Dekodierung werden mit VITERBI ezient umgesetzt. Taktweise
werden
2
k
Kanalkodefolgen aussortiert. Die Dekodierungskomplexität ist im
Vergleich zum FANO-Algorithmus unabhängig vom Fehlerverhalten. Nachtei-
lig ist das Speichern von
2
k
Pfaden. Der Aufwand verdoppelt sich mit
k
+1
(jedoch mit einem Kodierungsgewinn von ca.
0
,
4
dB
). In Anwendungen findet
man deshalb Faltungskodierer nur bis zu einer Einflusslänge von
K
=
k
+1 = 9
(mit dem
(
K
=15
,R
=
4
)
Big-Viterbi-Decoder Anfang der 90er Jahre hatte
man nur versucht, an die SHANNON-Grenze heranzukommen, s. a. [COH 98]).
