Hamming-Codes & lineare Abhängkeit

Gast

Hallo allerseits!

Ich hab hier eine Aufgabe über Hamming-Codes aus einem Buch der linearen Algebra. Bevor ich (umsonst?) drauflostippe, eine Frage vorneweg: Kennt sich jemand hier sowohl mit H-Codes und linearer Algebra aus?

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Tja. Beides ist ein weites Feld und von beidem habe ich schonmal gehört. Da aber Selbsteinschätzungen grundsätzlich in die Hose gehen, wäre wohl das einfachste, die Aufgabe zu posten.

phigital · Anmeldungsdatum: 27.05.2005 Beiträge: 1 Wohnort: Spiralarm Orion

Hallo, ich hab´ mich regestriert (bin also der Gast der die Frage gepostet hat). 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.

Seine Kontrollmatrix H ist eine rx((2^r)-1)-Matrix. H^t ist die transponierte Matrix zu H, einfacher gesagt H^t ist die Matrix bei der die Zeilen von H zu den Spalten von H^t werden.

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 du willst kann ich noch Definition von linear abhängig/unabhängig und Ham(3) als Beispiel posten...