Hamming-Codes & lineare Abhängigkeit

Neue Frage »

phi Auf diesen Beitrag antworten »
Hamming-Codes & lineare Abhängigkeit
Es geht um eine LA-Aufgabe über Hamming-Codes. Bevor ich mir die Finger wundtippe eine Frage vorneweg: Kennt sich hier jemand aus, also über Codes und Algebra?
AD Auf diesen Beitrag antworten »

Zur Not (also mangelnde Kompetenz hier) kannst du deine Anfrage immer noch per Copy+Paste ins Informatikerboard befördern. Augenzwinkern
phi Auf diesen Beitrag antworten »

Hab ich schon! Da muss ich erst mal abwarten ob sich jemand auch mit linare Algebra auskennt. Aber ich überleg´grade wie ich es als reine LA-Aufgabe umformulieren kann, der Code ist ja einfach nur ein Vektorraum über GF(2)^n....bis später.
Tobias Auf diesen Beitrag antworten »

Zitat:
Kennt sich hier jemand aus, also über Codes und Algebra?


Diese Frage ist höchstwahrscheinlich mindestens genauso schwer zu beantworten wie deine eigentliche Frage/Aufgabe. Hammer

Also schreib am besten die Aufgabe hier rein.
phi Auf diesen Beitrag antworten »

Kurze Definition von Ham(r):

Ham(r):={c=(c_1, c_2, ..., c_n} aus {0,1}^n | cH^t=0}.
(alle 0,1-Ketten der Länge n, für die c mal H^t gleich Null ist.)

Ham(r) ist also ein 1-fehlerkorrigierender perfekter Code mit w(Ham(r))=d(Ham(r))>=3 der Länge n=(2^r)-1. Wobei mit w() das Mindestgewicht definiert ist, also die Mindestanzahl von Einsern die einen Code vom Nullvektor unterscheiden. Und d() der Hamming-Abstand, also der Mindestunterschied von Stellen ist zwischen zwei Elementen aus Ham(r).

Seine Kontrollmatrix H ist eine rx((2^r)-1)-Matrix.


Hier die Aufgabe:
a) Angenommen, es gäbe ein Codewort in Ham(r) vom Gewicht 1 oder 2. Schließe daraus, dass eine bzw. zwei Zeilen von H linear abhängig sein müssten.


b) Verallgemeinerung von a):
Sei C ein beliebiger linearer Code, und sei H eine Kontrollmatrix von C. Dann gilt:

Wenn je d-1 Spalten von H linear unabhängig sind, so gilt d(C) ist größer-gleich d.

Wenn ihr wollt kann ich noch Ham(3) als Beispiel posten...
phi Auf diesen Beitrag antworten »
Zeilenvektor mal Matrix
So, ich hab´s jetzt mal als rein mathematische Aufgabe formuliert:

Seien die Vektoren c Tupel der Länge 7 über dem Körper GF(2), also Elemente aus dem Vektorraum V={0,1}^7. (z.B. ).
Und eine Matrix wie folgt definiert:



Sei C die Teilmenge von V für die gilt. Das sind intressanterweise grade die Vektoren die mindestens drei Einsen haben (einzige Ausnahme: der Nullvektor (0000000)).

(Beim Rechnen mit diesen Matrizen ist 1+1=0 zu beachten, da wir in GF(2) sind.)

Beispiel: . Also ist c_1 ein Element von C.

Soweit sogut. Nun die Aufgabe: Sei . (Nur zwei Nullen!)

Wenn x Zeilen linear abhängig. Was ist x ?
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »