Gilbert-Varshamov-Schranke

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

Für die folgenden Definitionen sei ein Alphabet mit

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

[Bearbeiten | Quelltext bearbeiten]

Wir definieren als die größte Mächtigkeit eines Codes über mit Blocklänge und Minimalabstand , genauer also . Merke, dass ausschließlich von der Mächtigkeit von , der Blocklänge und vom Minimalabstand abhängt.

Kugeln mit Radius r und ihr Volumen

[Bearbeiten | Quelltext bearbeiten]

Es sei die Kugel um das Wort . Die Mächtigkeit (oder auch das Volumen) von ist gegeben durch

.

Aussage der Gilbert-Varshamov Schranke

[Bearbeiten | Quelltext bearbeiten]

Es gilt:

.

Es sei ein Code mit Minimalabstand , Blocklänge und Mächtigkeit . ist also ein -Code mit größter Mächtigkeit. Dann gilt, dass . Denn angenommen, das wäre nicht der Fall, so gibt es ein . Dieses erfüllt , womit ein Code mit Minimalabstand über wäre, der eine größere Mächtigkeit als hat. Das kann nach Definition von nicht sein. Daher bekommen wir und somit insgesamt:

,

wobei irgendein Wort ist. Nach Umstellen erhalten wir unsere Behauptung.

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

[Bearbeiten | Quelltext bearbeiten]

Der Beweis der Schranke liefert einen Greedy-Algorithmus zur Konstruktion eines Codes , der die Gilbert-Varshamov-Schranke erfüllt, das heißt . Dabei startet man mit einem beliebigen Wort und setzt . Danach wählt man , , so dass . Man stoppt, sobald man kein mit mehr wählen kann.

Die Gilbert-Varshamov-Schranke für lineare Codes

[Bearbeiten | Quelltext bearbeiten]

Man kann die Gilbert-Varshamov-Schranke für lineare Codes (siehe linearer Code) verbessern: Es sei eine Primpotenz und ein (bzw. auch der) Körper mit Elementen. Weiterhin seien mit und . Wenn gilt, so gibt es einen linearen Code mit . Damit erhalten wir, dass .