Gilbert-Varshamov-Schranke

Die Gilbert-Varshamov-Schranke (nach Edgar Gilbert und Rom Rubenowitsch Warschamow) ist eine untere Abschätzung der Mächtigkeit eines im gewissen Sinne optimalen Blockcodes mit vorgegebener Blocklänge und Minimalabstand (siehe Hammingabstand). Im Gegensatz zu anderen vergleichbar berühmten Schranken liefert diese sogar eine Existenzaussage für einen Code. Das heißt, gegeben seien Alphabet, Blocklänge und Minimalabstand, die bestimmte Voraussetzungen erfüllen, dann existiert dazu ein Code mit einer Mindestanzahl an Codewörtern, die durch die Gilbert-Varshamov-Schranke von unten beschränkt ist.

Hinführende Definitionen

Für die folgenden Definitionen sei $K$ ein Alphabet mit $|K|=q\in \mathbb {N} \setminus \{0\}$

Die größte Mächtigkeit eines Codes mit vorgegebener Blocklänge und Minimalabstand

Wir definieren ${\mathcal {A}}_{q}(n,d)$ als die größte Mächtigkeit eines Codes über $K$ mit Blocklänge $n$ und Minimalabstand $d$, genauer also ${\mathcal {A}}_{q}(n,d):=\max\{|C|:~C\subseteq K^{n}{\text{ und }}\operatorname {d} (C)=d\}$. Merke, dass ${\mathcal {A}}_{q}(n,d)$ ausschließlich von der Mächtigkeit von $K$, der Blocklänge und vom Minimalabstand abhängt.

Kugeln mit Radius r und ihr Volumen

Es sei $B_{r}(c):=\{y\in K^{n}:~d(c,y)\leq r\}$ die Kugel um das Wort $c\in K^{n}$. Die Mächtigkeit (oder auch das Volumen) von $B_{r}(c)$ ist gegeben durch

$V_{q}(n,r):=|B_{r}(c)|=\sum \limits _{j=0}^{r}{\binom {n}{j}}(q-1)^{j}$.

Aussage der Gilbert-Varshamov Schranke

Es gilt:

${\mathcal {A}}_{q}(n,d)\geq {\frac {q^{n}}{V_{q}(n,d-1)}}$.

Beweis

Es sei $C\subseteq K^{n}$ ein Code mit Minimalabstand $d$, Blocklänge $n$ und Mächtigkeit $|C|={\mathcal {A}}_{q}(n,d)$. $C$ ist also ein $(n,d)$-Code mit größter Mächtigkeit. Dann gilt, dass $\textstyle \bigcup _{c\in C}B_{d-1}(c)=K^{n}$. Denn angenommen, das wäre nicht der Fall, so gibt es ein $\textstyle y\in K^{n}\setminus \bigcup _{c\in C}B_{d-1}(c)$. Dieses $y$ erfüllt $d(y,C):=\min\{d(y,c):~c\in C\}\geq d$, womit $C\cup \{y\}$ ein Code mit Minimalabstand $d$ über $K^{n}$ wäre, der eine größere Mächtigkeit als $C$ hat. Das kann nach Definition von ${\mathcal {A}}_{q}(n,d)$ nicht sein. Daher bekommen wir $\textstyle |\bigcup _{c\in C}B_{d-1}(c)|=|K^{n}|=q^{n}$ und somit insgesamt:

$q^{n}=|\bigcup _{c\in C}B_{d-1}(c)|\leq \sum _{c\in C}|B_{d-1}(c)|=|C|\cdot |B_{d-1}(c^{\ast })|={\mathcal {A}}_{q}(n,d)\cdot V_{q}(n,d-1)$,

wobei $c^{\ast }\in K^{n}$ irgendein Wort ist. Nach Umstellen erhalten wir unsere Behauptung.

Konstruktion eines (n,d)-Codes über K

Der Beweis der Schranke liefert einen Greedy-Algorithmus zur Konstruktion eines Codes $C\subseteq K^{n}$, der die Gilbert-Varshamov-Schranke erfüllt, das heißt $|C|\geq {\tfrac {q^{n}}{V_{q}(n,d-1)}}$. Dabei startet man mit einem beliebigen Wort $y_{0}\in K^{n}$ und setzt $C_{0}:=\{y_{0}\}$. Danach wählt man $y_{i}\in K^{n}$, $i\in \mathbb {N} \setminus \{0\}$, so dass $d(y_{i},C_{i-1}):=\min\{d(y_{i},c):~c\in C_{i-1}\}\geq d$. Man stoppt, sobald man kein $y\in K^{n}$ mit $d(y,C_{i})\geq d$ mehr wählen kann.

Die Gilbert-Varshamov-Schranke für lineare Codes

Man kann die Gilbert-Varshamov-Schranke für lineare Codes (siehe linearer Code) verbessern: Es sei $q$ eine Primpotenz und $\mathbb {F} _{q}$ ein (bzw. auch der) Körper mit $q$ Elementen. Weiterhin seien $n,k,d\in \mathbb {N} \setminus \{0\}$ mit $2\leq d\leq n$ und $1\leq k\leq n$. Wenn $V_{q}(n-1,d-2)\leq q^{n-k}$ gilt, so gibt es einen linearen Code $C\subseteq \mathbb {F} _{q}^{n}$ mit $|C|\geq q^{k}$. Damit erhalten wir, dass $A_{q}(n,d)\geq q^{k}$.

Literatur

• J.H. Lint: Introduction to Coding Theory (Graduate Texts in Mathematics. Band 86). Third Edition, Springer-Verlag Berlin Heidelberg, 1999, ISBN 978-3-642-63653-0, DOI:10.1007/978-3-642-58575-3
• San Ling, Chaoping Xing: Coding Theory A First Course. Cambridge University Press, 2004, ISBN 978-0-521-82191-9, DOI:10.1017/CBO9780511755279