Cryptography Reference
In-Depth Information
die Mindestzahl
k
der redundanten Stellen bei einem Binärkode errechnen. Im
Alphabet
B
=
{
0
,
1
}
n
kann es infolge von Übertragungsstörungen
2
n
Binär-
folgen, davon
n
1
Binärfolgen vom Gewicht
1
,
n
2
Binärfolgen vom Gewicht 2,
usw., geben, wobei
n
i
n
!
i
!(
n − i
)!
=
n
(
n
−
1)
...
(
n
i
+1)
i
(
i −
1)
...
1
−
=
gilt. Dabei sind nur
2
l
Binärfolgen mit einem Gewicht
≥ d
min
Kanalkodewör-
ter. Um entsprechend
d
min
alle Fehlerstellen
≤ f
k
erkennen und korrigieren zu
können, müssen in den
2
l
Korrekturkugeln alle Binärfolgen mit einem Abstand
≤ f
k
zum jeweiligen Kanalkodewort enthalten sein:
l
n
1
n
2
n
f
k
.
n
2
≥
2
1+
+
+
...
+
(8.11)
in Korrekturkugel enthaltene Binärfolgen
Mit
n
=
l
+
k
ist
k
berechenbar.
Beispiel 8.1.5
Für einen Kanalkode mit
n
=7
und
d
min
=3
sind Quellenkodelänge
l
und
Anzahl redundanter Stellen
k
zu berechnen.
Lösung:
Mit
f
k
=1
und Anwendung von Gl. (8.11) ist
2
7
≥
2
l
1+
1
=2
l
+3
l ≤
4
.
Für
l
=4
gilt:
k
=
n
l
−
l
=3
,L
=2
=16
mögliche Quellenkodewörter.
Bei Kenntnis von
l
und
d
min
lässt sich die Berechnung von
k
durch Umstellung
von Gl. (8.11) vereinfachen:
l
n
1
n
2
n
f
k
n
l
k
2
=2
2
≥
2
1+
+
+
...
+
n
i
f
k
k
2
≥
i
=0
n
i
.
f
k
k
≥
ld
(8.12)
i
=0