Singleton-Schranke

Die Singleton-Schranke bezeichnet eine obere Schranke für die Mindestdistanz $d$ eines Blockcodes der Länge $n$ bei Informationswörtern der Länge $k$ über einem einheitlichen Alphabet $Σ$ .

Sie lautet:

d \leq n - k + 1

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

Annahme: Alphabet $Σ = {0, \dots, q - 1}$
Anzahl der möglichen Informationswörter : $| ℐ | = q^{k}$
Anzahl der Codewörter: $| 𝒞 | = | ℐ | = q^{k}$
Mindestdistanz: $d$

Streicht man nun in den Codewörtern jeweils die letzten ( $d - 1$ ) der $n$ Stellen, so haben die übrigen Codewörter zueinander immer noch mindestens den Hamming-Abstand 1. Bei $d$ Streichungen wäre dies nicht mehr gewährleistet. Damit sind immer noch alle Codewörter unterschiedlich, also

| 𝒞^{'} | = | 𝒞 | = q^{k}

Deswegen muss auch die Anzahl der durch die Länge $n - (d - 1)$ erzeugbaren Wörter $q^{n - d + 1} \geq q^{k}$ sein. Stellt man diese Gleichung um, ergibt sich daraus die Singleton-Schranke

n - d + 1 \geq k \Leftrightarrow d \leq n - k + 1

Für nicht-lineare Codes gilt entsprechend

M \leq q^{n - d + 1}

,

wobei $M = | 𝒞 |$ .

Codes, die die Singleton-Schranke mit Gleichheit erfüllen, nennt man auch MDS-Codes.

Beziehung zur Hamming-Schranke

Im Falle der Hamming-Schranke ist $t = ⌊ (d - 1) / 2 ⌋$ die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming-Distanz $d$ .

Die Hamming-Schranke sagt aus, dass

q^{n} \geq q^{k} \sum_{i = 0}^{t} (q - 1)^{i} (\binom{n}{i})

,

beziehungsweise

n \geq k + \log_{q} \sum_{i = 0}^{t} (q - 1)^{i} (\binom{n}{i})

erfüllt sein muss für einen Code, der mittels $n$ Symbolen eines Alphabets $Σ$ der Größe $q$ eine Nachricht mit der Länge $k$ transportiert.

Für zum Beispiel $n = 512$ und $t = 11$ (erfordert eine Hamming-Distanz von $d = 23$ ) erhält man in Abhängigkeit von der Größe $q$ des Alphabets $Σ$ :

$q = 2 : k \leq 438,3746$
$q = 4 : k \leq 466,4807$
$q = 16 : k \leq 482,8572$
$q = 2^{8} : k \leq 491,8086$
$q = 2^{16} : k \leq 496,4004$
$q = 2^{32} : k \leq 498,7002$
$q = 2^{64} : k \leq 499,8501$
$q = 2^{128} : k \leq 500,4250$
$q = 2^{256} : k \leq 500,7125$
$q \to \infty : k \leq 501,0000$

Die Hamming-Schranke macht vergleichsweise genaue Aussagen in Abhängigkeit von $n$ , $t$ und $q$ . Für sehr große $q$ strebt sie einem Grenzwert zu.

Im Falle der Singleton-Schranke ist $t = ⌊ (d - 1) / 2 ⌋ = ⌊ (n - k) / 2 ⌋$ die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Mindestdistanz $d$ .

Für zum Beispiel $n = 512$ und $t = 11$ (erfordert eine Mindestdistanz von $d = 12$ ) erhält man:

$k \leq 501$

unabhängig von $q$ . Die Singleton-Schranke ist eine ungenauere Abschätzung als die Hamming-Schranke, die die Größe des Alphabets nicht berücksichtigt. Weiterhin gibt es Unterschiede in der Beziehung zwischen $t$ und $d$ .

Literatur

J.H. van Lint: Introduction to Coding Theory (Graduate Texts in Mathematics). 2. Auflage. Springer, Berlin, ISBN 978-3-540-54894-2.
Martin Bossert: Kanalcodierung. 3., überarbeitete Auflage, Oldenbourg Verlag, München 2013, ISBN 3-486-72128-3.
Otto Mildenberger (Hrsg.): Informationstechnik kompakt. Theoretische Grundlagen. Friedrich Vieweg & Sohn Verlag, Wiesbaden 1999, ISBN 3-528-03871-3.
Werner Heise, Pasquale Quattrocchi: Informations- und Codierungstheorie. 2. Auflage, Springer Verlag, Berlin / Heidelberg 1989, ISBN 978-3-540-50537-2.

Weblinks

Codierungstheorie (abgerufen am 22. September 2017)
Algebraische Codierungstheorie (abgerufen am 22. September 2017)
Einführung in die Codierungstheorie (abgerufen am 22. September 2017)
Signale und Codes (abgerufen am 22. September 2017)
FEHLERKORRIGIERENDE CODES (abgerufen am 22. September 2017)