Cryptography Reference
In-Depth Information
zurück zum Wurzelknoten. Die Distanzschwelle wird erhöht und die Suche be-
ginnt von neuem. Wird eine Kanalkodefolge
a
i
mit
d
(
H
)
(
a
i
,b
)=0
gefunden,
liegt kein erkennbarer Fehler vor. Bei
d
(
H
)
(
a
i
,b
)=
D>
0
gibt die Distanz-
schwelle den Abstand zwischen beiden Folgen an, damit auch die Zahl korri-
gierter Fehler. Es ist möglich, dass mehrere Kanalkodefolgen zur Empfangsfolge
die gleiche Distanz haben. Die Entscheidung fällt zugunsten der Folge, welche
die Distanzschwelle als erste erfüllt.
Die Folge
a
i
ist die geschätzte, wahrschein-
lichste Kanalkodefolge
a
(=
b
korr
)
.
Der Nachteil des Algorithmus liegt in der sich ändernden Bearbeitungszeit,
abhängig von der Fehleranzahl. Bei geringem Störverhalten, auch bei Betrach-
tung der durchschnittlichen Bearbeitungszeit, hat dieser Algorithmus Vorteile
gegenüber anderen Verfahren. Für Realzeit[real time]-Anwendungen ist dieser
Algorithmus jedoch wenig attraktiv. So sind z. B. bei Sprachübertragungen
feste Verzögerungszeiten notwendig. Beim Filetransfer [non real time packet
application] stellen unterschiedliche Verzögerungszeiten kein Problem dar.
Der Algorithmus ist weiterhin nahezu unabhängig von der Einflusslänge
K
(z. B.
K
=32
in Pioneer-Missionen [COH 98]; zum Vergleich: beim VITERBI-
Algorithmus sollte
K
nicht größer 9 sein, s. Abschn. 8.6.3.2).
Die Anzahl Pfade und damit die Mächtigkeit des Kodealphabets
A
wächst
exponentiell mit der Informationslänge. Sinnvolle Längen liegen bei
l ≤
100
.
Zu dem liegt der Vorteil des Algorithmus in der
Speicherung immer nur einer
Kanalkodefolge
.
Eine Begrenzung durch Terminierung schränkt bei Übertragungsfehlern die
Zahl möglicher Kanalkodefolgen gleichen Abstands zu
b
ein, verlängert natür-
lich das Baumdiagramm um die
k
Terminierungsstellen.
Beispiel 8.6.5
Auf der Grundlage des Faltungskodierers aus Beispiel 8.6.2 ist der FANO-
Algorithmus zur Kodierung von
a
∗
= (1101)
und zur Dekodierung von
b
=
(101011100111)
, unter Berücksichtigung von Terminierung, anzuwenden.
Lösung:
s. S. 222
(Die Knoten in
t
+1
sind mit dem Abstand
i
=0
t
d
(
H
)
(
v
(
i
)
,y
h
(
i
))
bewertet.)
Für eine Distanzschwelle von
D
=3
wurde eine Kodefolge mit
d
(
H
)
(
a, b
)=3
gefunden. Die zugehörige Quellenkodefolge
b
∗
stimmt mit
a
∗
überein. In diesem
Beispiel wurden demzufolge 3 Fehler korrigiert, d. h. mehr als
f
k
=
d
f
−
1
2
=2
mit Sicherheit rekonstruierbare Fehler.
Die Leistungsfähigkeit von Faltungskodes liegt in der Regel über dem Fehler-
korrekturgrad
f
k
. Vorteile findet man vor allem bei zufällig verteilten Einzel-
fehlern.
Die Dekodierungsergebnisse sind immer korrekt oder falsch. Ein De-
kodierungsversagen kann nicht auftreten.
