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.

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

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

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

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

Es gilt:

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

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

${\displaystyle 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 ${\displaystyle c^{\ast }\in K^{n}}$ irgendein Wort ist. Nach Umstellen erhalten wir unsere Behauptung.

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

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

• 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