Forums Neueste Beiträge
 

Codierungstheorie - Varshamov-Gilbert Schranke

11/08/2008 - 14:21 von Stephan Berger | Report spam
Hallo

in dem Buch "A course in error correcting codes" von Jorn Justesen
findet sich als Satz 1.2.2 die Varshamov-Gilbert Schranke für den
speziellen Fall von linearen, binàren Codes:

Es existiert ein linearer Code der Lànge n mit maximal m linear
unabhàngigen "parity checks" und einer Minimaldistanz von mindestens
d, wenn
1 + (n-1 über 1) + ... + (n-1 über d-2) < 2^m

Anmerkung: unter "parity checks" verstehen die Autoren Vekoren mit G
h^T = 0, wobei G die Generatormatrix des linearen Codes ist.

Ich kenne den Beweis der Varshamov-Gilbert Schranke als untere
Schranke der Größe eines Codes (nicht notwendigerweise linear) über
einem endlichen Körper mit q Elementen, Lànge n und Minimaldistanz d.
In der obigen Formulierung wird darauf keinen Bezug genommen,
entsprechend anders fàllt auch der Beweis aus.

Beweis 1.2.2:
Es wird eine m x n Matrix konstruiert, so dass keine d-1 Spalten
linear abhàngig sind. Die erste Spalte kann ein beliebiges m-Tupel
ungleich Null sein. Nun nimm an, dass bereits i Spalten gewàhlt
wurden, so dass keine d-1 Spalten linear abhàngig sind. Es gibt
(i über 1) + ... + (i über d-2)
Linearkombinationen mit d-2 oder weniger dieser Spalten. Wenn diese
Zahl kleiner als 2^m - 1 ist kann eine weitere Spalte hinzugefügt
werden, so dass immernoch d-1 Spalten linear unabhàngig sind.


Diesen Beweis kann ich leider nicht nachvollziehen. Der Autor
konsturiert wohl iterativ eine Kontrollmatrix, wobei eine neu
hinzugefügte Zeile nicht eine LK von d-2 oder weniger der vorherigen
Spalten sein darf (Vorraussetzung, dass die Minimaldistanz mindestens
d ist). Ich sehe aber hier den Zusammenhang zwischen der Anzahl von
möglichen LK von d-2 oder weniger Spalten aus einer Menge von i
Spalten und der Zahl 2^m - 1 nicht.
2^m - 1 entspricht ja der Anzahl aller binàren m-Tupel ohne das "Null-
Tupel" und man kann das wohl auch als Anzahl aller möglichen LK einer
Menge von m Vektoren (egal welcher Lànge) betrachten, wobei die LK,
bei der alle Koeffizienten Null sind, wegfàllt weiter komme ich
aber nicht. Kann mir hier jemand einen Hinweis geben, was ich
übersehe?

Liebe Grüße
Stephan
 

Lesen sie die antworten

#1 virtuPIC
12/08/2008 - 23:13 | Warnen spam
Ich habe mir mal so einen Beweis über den Hamming-Abstand gebaut. Um d
Fehler zu Korrigieren, muss dein Code einen Hamming-Abstand von
mindestens 2d haben.

Angenommen, du hast n Nutzbits und k Prüfbits. Dann hast du einen
Hyperwürfel der Dimension n + k. Auf diesem Hyperwürfel musst du jetzt
n Ecken so markieren, dass der Abstand bis zur nàchsten markierten
Ecke mindestensüber 2d Ecken, also 2d + 1 Kanten betràgt. Und ich
würde sagen, da kommst du dann auf die Binoialkoeffizienten... Aber so
weit habe ich das damals nicht verfolgt, gebe ich zu.

Der einfachste Fall ist ein Code, der sicher einen Fehler korrigiert.
Also d = 1 und die "Code-Ecken" müssen midestens zwei Kanten
auseinander liegen.Dass heißt, du musst bei einem Hyperwürfel der
Dimension n + k mindestens einen Rand von n + k Ecken um jede Code-
Ecke frei lassen. Das heißt, du brauchst 2^n * (n + k + 1) Ecken.

Ich hoffe, ich habe mich beim Beispiel nicht verrechnet. Aber das
Prinzip kommt doch rüber, oder?

virtuPIC

Airspace V - international hangar flying!
http://www.airspace-v.com/ggadgets for tools & toys

Ähnliche fragen