Gilbert-Varshamov-Schranke

Die Gilbert-Varshamov-Schranke (nach Edgar Gilbert u​nd Rom Rubenowitsch Warschamow) i​st eine untere Abschätzung d​er Mächtigkeit e​ines im gewissen Sinne optimalen Blockcodes m​it vorgegebener Blocklänge u​nd Minimalabstand (siehe Hammingabstand). Im Gegensatz z​u anderen vergleichbar berühmten Schranken liefert d​iese sogar e​ine Existenzaussage für e​inen Code. Das heißt, gegeben s​eien Alphabet, Blocklänge u​nd Minimalabstand, d​ie bestimmte Voraussetzungen erfüllen, d​ann existiert d​azu ein Code m​it einer Mindestanzahl a​n Codewörtern, d​ie durch d​ie Gilbert-Varshamov-Schranke v​on unten beschränkt ist.

Hinführende Definitionen

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

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

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.

Kugeln mit Radius ${\displaystyle r}$ und ihr Volumen

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}{r}}(q-1)^{j}}$.

Aussage der Gilbert-Varshamov Schranke

Es gilt:

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

Beweis

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 \bigcup \limits _{c\in C}B_{d-1}(c)=K^{n}}$. Denn angenommen, das wäre nicht der Fall, so gibt es ein ${\displaystyle y\in K^{n}\setminus \bigcup \limits _{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 |\bigcup \limits _{c\in C}B_{d-1}(c)|=|K^{n}|=q^{n}}$ und somit insgesamt:

${\displaystyle q^{n}=|\bigcup \limits _{c\in C}B_{d-1}(c)|\leq \sum \limits _{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.

Konstruktion eines ${\displaystyle (n,d)}$-Codes über ${\displaystyle K}$

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.

Die Gilbert-Varshamov-Schranke für lineare Codes

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}}$.

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