Cryptography Reference
In-Depth Information
Bevor Verkettungsbeispiele aufgezeigt und praktische Umsetzungen ausgeführt
werden, sei zunächst zum besseren Verständnis ein kurzer
Exkurs zum In-
terleaving
gegeben:
Kodewörter werden so ineinander verschachtelt, dass die Kodewortelemente in
einem bestimmten Abstand zeitlich voneinander versetzt weiter „verarbeitet“
werden.
Bei einem
I ×n
Blockinterleaver
werden
I
Kodewörter
a
i
(
i
=1
,
2
, ..., I
)
der
Länge
n
zeilenweise in eine Matrix geschrieben und anschließend spaltenweise
gelesen:
⎛
⎞
u
11
u
12
u
13
... u
1
n
u
21
u
22
u
23
... u
2
n
u
31
u
32
u
33
... u
3
n
..................
u
I
1
u
I
2
u
I
3
... u
In
⎝
⎠
M
I×n
=
.
Nach
I
-facher Spreizung (auch als Interleavingtiefe [interleaving depth] be-
zeichnet) lautet der Ausgabeblock der Länge
I
·
n
a
Block
=(
u
11
u
21
u
31
... u
I
1
u
12
u
22
u
32
... u
I
2
u
13
u
23
u
33
... u
I
3
... u
In
)
,
d. h., zwischen anfangs aufeinanderfolgenden Elementen liegen jetzt
(
I −
1)
Elemente aus anderen Kanalkodefolgen.
Zum Entspreizen [deinterleaving] wird der Empfangsblock
b
Block
jetzt spalten-
weise in eine
I × n
Matrix geschrieben und zur Fehlerkorrektur eine
n
-stellige
Empfangsfolge zeilenweise ausgelesen.
Wenn
I
Zeilen einer Matrix Empfangsfolgen
b
i
(
i
=1
,
2
, ..., I
)
eines
f
k
fehler-
korrigierenden Kodes der Länge
n
sind, dann können im Block der Länge
I
n
insgesamt
f
k
Bündelfehler der Länge
I
oder ein Bündelfehler der Länge
I ·f
k
vollständig korrigiert werden.
·
Beispiel 8.7.1
Dem Kodierer eines
(15
,
11
,
5)
RS-Kodes über
GF
(2
4
)
ist ein Blockinterleaver
mit einer Interleavingtiefe von
I
=8
nachgeschaltet. Ohne Interleaving wären
nach der Übertragung Bündelfehler bis zu einer Länge von
f
k
·
k
1
=2
·
4
=8
Bit
(mit Sicherheit nur
(
f
k
−
1)
·
k
1
+1=5
Bit
) korrigierbar. Mit einem Blockin-
terleaver sind Bündelfehlerlängen bis zu
I · f
k
·
k
1
=64
Bit
(bzw.
I · f
k
=
16
Elemente
) möglich.
Die folgende Grafik veranschaulicht diesen Sachverhalt. Die Elemente sind fort-
laufend nummeriert.