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 $\mathrm{\Sigma }$.

Sie lautet:

$d\le n-k+1$

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

• Annahme: Alphabet $\mathrm{\Sigma }=\{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

$|{𝒞}^{\prime }|=|𝒞|=q^k$

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

$n-d+1\ge k\iff d\le n-k+1$

Für nicht-lineare Codes gilt entsprechend

$M\le 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=\lfloor (d-1)/2\rfloor$ die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming-Distanz $d$.

Die Hamming-Schranke sagt aus, dass

$q^n\ge q^k\sum _{i=0}^t(q-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})$,

beziehungsweise

$n\ge k+{\log }_q\sum _{i=0}^t(q-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})$

erfüllt sein muss für einen Code, der mittels $n$ Symbolen eines Alphabets $\mathrm{\Sigma }$ 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 $\mathrm{\Sigma }$:

• $q=2:k\le 438,3746$
• $q=4:k\le 466,4807$
• $q=16:k\le 482,8572$
• $q=2^8:k\le 491,8086$
• $q=2^{16}:k\le 496,4004$
• $q=2^{32}:k\le 498,7002$
• $q=2^{64}:k\le 499,8501$
• $q=2^{128}:k\le 500,4250$
• $q=2^{256}:k\le 500,7125$
• $q\to \mathrm{\infty }:k\le 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=\lfloor (d-1)/2\rfloor =\lfloor (n-k)/2\rfloor$ 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\le 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

• Vorlage:Literatur
• 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)