Cryptography Reference
In-Depth Information
8.6.4
Blockkodes und Trellisstruktur
Die hard-decision Dekodierungsalgorithmen der betrachteten Blockkodes set-
zen
nur
das Prinzip der begrenzten Mindestdistanz um. Die Abbildung einer
Generator- oder Kontrollmatrix in eine Trellisstruktur (bereits 1974 erstmals
vorgestellt, eine Weiterentwicklung erfolgte dann in den 90er Jahren mit dem
Durchbruch der soft-decision Dekodierung) macht auch für Blockkodes eine
MD/ML Dekodierung möglich.
Die folgenden Betrachtungen beschränken sich auf die Umsetzung der Kontroll-
matrix in eine Trellisstruktur.
Interessant erscheint hier das Aufzeigen einer
möglichen soft-decision Dekodierung für die betrachteten Blockkodes.
Die
k
×
n
Kontrollmatrix
H
sei wie folgt gegeben:
⎛
⎞
⎛
⎞
c
10
c
11
... c
1
,n−
1
c
20
c
21
... c
2
,n−
1
. .
.
.
.
.
c
k
0
c
k
1
... c
k,n−
1
c
1
i
c
2
i
.
c
ki
⎝
⎠
=(
H
0
H
1
... H
n−
1
)
⎝
⎠
H
k×n
=
mit
H
i
=
.
Der Blockkode kann, muss nicht, systematisch sein. Mit der Kontrollmatrix
wird der Nachweis geführt, ob eine Empfangsfolge Element eines Kanalkode-
alphabets ist oder nicht. Dafür gilt der bekannte
Syndrom
zusammenhang:
b
T
s
=
H
k×n
·
=
0
?
Das Syndrom ist für eine Kanalkodefolge Null.
Diesen Zusammenhang nutzt man für den Aufbau des
Syndrom
trellis. Kanal-
kodefolgen beginnen und enden im Nullzustand. Jede andere Folge ist nicht
Kanalkodefolge und wird im Trellis auch nicht dargestellt.
Die Anzahl möglicher Zustände hängt von den redundanten Stellen
k
und den
Informationsstellen
l
ab. Je Taktzeitpunkt sind
≤
2
min
{l,k}
Zustände (WOLF-
Schranke, eine obere Schranke für die Anzahl von Zuständen) möglich. Die
Blocklänge
n
bestimmt die Länge des Trellis. Im Vergleich zu Faltungskodes
gibt es kein verkürztes Trellis.
Der Algorithmus nutzt zum Aufbau des Syndromtrellis das mathematische
Vorgehen der Syndromberechnung: spaltenweise Multiplikation von Korrek-
torspalte
H
i
und zugehörigem Element
i
der Empfangsfolge, Addition und
Fortsetzung mit
i
=0
,
1
, ...,
(
n
−
1)
. Das Endergebnis ist Null, wenn die Emp-
fangsfolge eine Kanalkodefolge ist.
Zum Aufbau des Kanalkodealphabets im Trellis muss die Multiplikation über
alle Kodeelemente ausgeführt werden. Im Folgenden ist der Algorithmus als
Struktogramm notiert.
σ
σ
widerspiegelt, wie bekannt, einen Zustandsüber-
gang vom Zustand
σ
zum Taktzeitpunkt
t
in den Folgezustand
σ
zum Takt-
