Cryptography Reference
In-Depth Information
8.6
Faltungskodes
Definition 8.6.1
Faltungskodes sind binäre, blockfreie Kodes. Die Redun-
danz wird kontinuierlich durch Faltung der Information in die Kanalkodefolge
eingefügt.
Faltungskodes wurden erstmals von ELIAS (1955) vorgestellt. Sie sind mittels
Faltungskodierer (Schieberegisteranordnungen mit linearen Verknüpfungsele-
menten) oder Generatormatrizen (ein Faltungskodierer ist eine Realisierung
der Generatormatrix) einfach beschreib- und erzeugbar. Probleme gibt es aller-
dings beim Finden geeigneter Matrizen. Optimale Generatormatrizen werden
mit Hilfe von Suchverfahren rechentechnisch ermittelt.
25
Für die Dekodierung existieren leistungsstarke Korrekturalgorithmen, die ne-
ben
h
arten Eingangswerten mit
y
h,i
∈{
0
,
1
}
auch weiche Eingangswerte [soft-
input] mit entweder
y
i
∈
R
|Q| >
2
,
verarbeiten und auch weiche Ausgangs(Zuverlässigkeits-)werte [soft-output]
berechnen können. Hatten wir es bisher nur mit hard-decision Dekodierung
zu tun (abgesehen von der Auslöschungskorrektur, Abschn. 8.5.5.3), so fallen
jetzt Begriffe wie soft-decision Dekodierung, soft-input/soft-output Dekodie-
rung und iterative Dekodierung.
Faltungskodes haben Vorteile bei der Korrektur von zufällig verteilten Ein-
zelfehlern, große Bündelfehler zerfallen in (Bündel-)Fehler kleinen Gewichts.
Diese Vorteile nutzt man bei der Verkettung von Kodes, ob mit Blockkodes
oder wieder einem Faltungskode (s. Abschn. 8.7).
Im Abschn. 8.6.1 werden zunächst die Beschreibungsmöglichkeiten von Fal-
tungskodes aufgezeigt. Welche Zusammenhänge bestehen zwischen Faltungsko-
dierer und Generatormatrix, welche Beschreibungsformen lassen sich im Wei-
teren als Grundlage der Dekodierung davon ableiten? Eine wichtige Kenngröße
ist die Koderate. Im Abschn. 8.6.2 soll die Möglichkeit der Koderatenerhöhung
durch mögliche Punktierung aufgezeigt werden. Die Dekodierung von Faltungs-
kodes soll dann ausführlicher im Abschn. 8.6.3 betrachtet werden. Dabei wird
die hard-decision Dekodierung zunächst als ein Spezialfall betrachtet, um dann
Möglichkeiten der soft-decision Dekodierung aufzuzeigen. Basis dafür liefert
der VITERBI-Algorithmus, der ezient das Maximum-Likelihood (ML) De-
kodierungsprinzip umsetzt. Mit dem Maximum-a-posteriori (MAP) Dekodie-
rungsprinzip, umgesetzt im BCJR-Algorithmus, existiert noch eine leistungs-
stärkere Rekonstruktion, aber auch die aufwendigste.
oder
q
uantisiert mit
y
q,i
∈ Q
,wobei
25
Ergebnisse optimaler Generatormatrizen, optimal hinsichtlich Distanz und Distanzspek-
trum, findet man umfassend in der Literatur, wie z. B. in [BOS 98], s. a. Abschn. 9.1.
