Cryptography Reference
In-Depth Information
Die Darstellung obiger Zusammenhänge ist notwendig für die Beschreibung
nachfolgender Dekodierungsalgorithmen.
Zunächst wird eine sequentielle Dekodierung am Beispiel des FANO-Algorith-
mus vorgestellt. Diese ist eine hard-decision Dekodierung auf der Basis des
Baumdiagramms. Eine e
ziente Umsetzung des Maximum-Likelihood (ML)/
Minimum-Distance (MD) Dekodierungsprinzips zeigt der VITERBI-Algorith-
mus (Abschn. 8.6.3.2). Dieser verwendet das Trellisdiagramm zur Rekonstruk-
tion. Zur Einführung soll zunächst als Spezialfall die Möglichkeit der hard-
decision Dekodierung gezeigt werden, um im Folgenden auf die Möglichkeiten
der soft-decision Dekodierung (soft-input, soft-output) einzugehen. Am e
zi-
entesten, aber auch aufwendigsten ist die Maximum-a-posteriori Dekodierung
basierend auf dem BCJR-Algorithmus im Abschn. 8.6.3.3. Eine vereinfachte
Umsetzung wird gezeigt. Grundlage bildet auch hier die Trellisdarstellung.
8.6.3.1 Sequentielle MD Dekodierung: FANO-Algorithmus
Der FANO-Algorithmus setzt eine hard-decision Dekodierung um. Grundlage
dafür ist das Baumdiagramm (s. S. 213). Die Sequenzen in der Empfangsfolge
b
=(
..., y
h
(
t
)
,y
h
(
t
+1)
, ...
)
m
.Taktweisewird
eine Empfangssequenz
y
h
(
t
)
mit einer Kodesequenz
v
(
t
)
im Diagramm ver-
glichen. Es wird mit
d
(
H
)
(
v
(
t
)
,y
h
(
t
))
die HAMMING-Distanz (Gl. (8.5)) zum
Taktzeitpunkt
t
berechnet und über den betrachteten Pfad summiert. Ausge-
hend vom Wurzelknoten wird immer nur ein Pfad betrachtet. Dabei können
im Baum die Bewegungen „vorwärts, rückwärts, seitwärts“ ausgeführt werden.
Der Algorithmus lässt sich vereinfacht wie folgt notieren:
sind Belegungen
y
h
(
t
)
∈{
0
,
1
}
b
D
:= 0 ;
j
:= 0
d
(
H
)
(
a
i
,b
)=
D
j
:= 1
D
:=
D
+1
j
=1
a
i
;
D
Beim Durchlaufen des Baumes wird eine Distanzschwelle
D
vorgegeben. So-
bald diese beim Vergleich von Empfangssequenzen in
b
und Kodesequenzen in
einer Kodefolge
a
i
(= Pfad im Baumdiagramm) überschritten wird, erfolgen
Rückwärtsbewegung(en) und Seitwärtsbewegung, um nach Zusammenhängen
in einem anderen Pfad zu suchen. Erfüllt kein Pfad den Distanzwert, geht es
