Hamming Distanz, Prüfschema

Wissenschaft Informatik
#1

Sorry erstmal, ich wußte jetzt nicht genau wo ich dieses Thema eröffnen soll…

Ich hoffe mir kann einer bei meinen Problemen zu Haming helfen, ich denke, es wird wohl am besten erklärt an einer Beispielaufgabe:

Ein Hamming Code soll 8 Nutzbits absichern.

[a]Wieviele Fehler können erkannt / korrigiert werden?
[b]Hammingdistanz
[c]Wieviele Prüfstellen benötigt der Code?
[d]Prüfschema H mit möglichst wenigen 1en
[e]Codewort 1 aus Prüfschema bestimmen
[f]Erstellen von hT aus Prüfschema
[g]Erstellen der Generatormatrix
[h]Bestimmen des Codewort 1 aus Generatormatrix

a) korrigieren = 1, erkennen 2
b) h = 3
c) k = 4
d) Mir ist Bekannt, dass ich dort insgesamt 12 Stellen brauche, 8 Nutzbits + 4 Prüfstellen. Wie bekomme ich raus, wieviele 1en pro Zeile ich brauche? und wie ordne ich diese an?

den Rest hab ich zur Zeit wenig Ahnung, da ich erstmal d) hinbekommen möchte - da es auch darauf aufbaut.

d) sieht so im moment bei mir aus:

m8 m7 m6 m5 m4 m3 m2 m1 k4 k3 k2 k1
x x x x x x x x 1 0 0 0
x x x x x x x x 0 1 0 0
x x x x x x x x 0 0 1 0
x x x x x x x x 0 0 0 1

#2

Hallo!

Ich weiß ja nicht, wie ihr die Matrizen jeweils aufgestellt habt. Eine Möglichkeit wäre, von rechts nach links die Spaltennummern in Binärdarstellung zu nutzen:
1 1 1 1 1 0 0 0 0 0 0 0
1 0 0 0 0 1 1 1 1 0 0 0
0 1 1 0 0 1 1 0 0 1 1 0
0 1 0 1 0 1 0 1 0 1 0 1
(Ganz rechts ist die erste Spalte = 0001).
Damit kannst du dann auch die Prüfgleichungen ermitteln (ich nehme an, die wolltest du für c) haben). Denn in jeder Zeile eine 0 rauskommen.

Nico

#3

Die Prüfstellen sind bei mir „k“ = 4, welche ich in meiner Matrix ganz hinten festgelegt habe.

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Ich verstehe im Moment nur nicht, wie ich die Einsen der Nutzbits (m) setzen muss, mit welchem Schema?

1 Like
#4

Die Spalten kannst du natürlich auch vertauschen. Wenn du also von rechts anfängst und erst deine Kontrollstellen haben willst, kommst du ja auf die Einheitsmatrix. Das entspricht der Binärdarstellung der 2er-Potenzen.
Wenn du dann nach links weitergehst, nimmst du dann einfach die Binärdarstellung der Nicht-2er-Potenzen. Zum Beispiel so:
1 1 1 1 0 0 0 0 1 0 0 0
1 0 0 0 1 1 1 0 0 1 0 0
0 1 1 0 1 1 0 1 0 0 1 0
0 1 0 1 1 0 1 1 0 0 0 1
Die Bits wären dann entsprechend:
n8 n7 n6 n5 n4 n3 n2 n1 k4 k3 k2 k1
Wenn n die Informationsstellen und k die Kontrollstellen sind.

Nico

#5

Gut… das mit dem Prüfschema habe ich verstanden… Was mich jetzt grad interessiert ist, wie ich ein CWx aus dem Prüfschema bestimmen kann.

Könntest du das erklären? Vielleicht für CW1 und CW5?

#6

Mit CWx meinst du ein Code-Wort?
Dazu kannst du die Bestimmungsgleichungen der redundanten Stellen aus der Kontrollmatrix erstellen - im Prinzip sind das einfach nur die umgestellten Prüfgleichungen.
k4=n8+n7+n6+n5
k3=n8+n4+n3+n2
k2=n7+n6+n4+n3+n1
k1=n7+n5+n4+n2+n1
Wenn du also ein Quellwort hast (bspw. 10011011), dann kannst du die redundanten Stellen durch die Bestimmungsgleichungen berechnen und einfach hintendran hängen:
=>100110110100
Wenn du das Wort dann wieder mit der Kontrollmatrix multiplizierst, müsste dann ein 0-Wort rauskommen.

Nico

#7

Ja ich meine mit CW Codewort. Angenommen ich habe folgendes Prüfungsschema:

1 1 1 0 1 1 0 1 0 0 1 | 1 0 0 0
1 0 1 1 1 1 1 0 0 1 1 | 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 | 0 0 1 0
1 1 1 1 0 0 1 1 1 0 0 | 0 0 0 1

Ich möchte jetzt CW1 und CW5 daraus erstellen. Das es nach dem Schema funktioniert, welches du oben aufgeführt hast - steht so ähnlich in meinem Script - jedoch verstehe ich nicht exakt die Anwendung…

Könntest du das ausführlich mit dem obg. Beispiel für CW1 und CW5 erklären? Wäre sehr hilfreich.

Gruß und danke für deine schnellen Antworten.

1 Like
#8

Mir ist nicht ganz klar, was du mit CW1 und CW5 meinst… Insgesamt hat der Code 2^8=256 Codewörter. Diese kann man alle aus den Quellwörtern aus Z_2^8 (sprich 8-stellige Binärwörter) erstellen indem man die Kontrollstellen mit den Bestimmungsgleichungen berechnet und hintendranhängt.
Meine Vermutung wäre jetzt, für CW1 das Quellwort 00000001 und für CW5 das Quellwort 00000101 zu verwenden. Das Schema wäre dann das gleiche, wie ich es schonmal an einem Beispiel vorgerechnet habe. Aber ich glaube, du meinst da etwas anderes…

Nico

#9

nun ich hab hier eine musterklausur vor mir liegen. In der heißt es bestimmen sie CodeWort 1 aus dem Prüfschema.

Das Prüfschema:

1 1 1 0 1 1 0 1 0 0 1 | 1 0 0 0
1 0 1 1 1 1 1 0 0 1 1 | 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 | 0 0 1 0
1 1 1 1 0 0 1 1 1 0 0 | 0 0 0 1

Lösung für CW1:

0 … 0 1 | 1 0 0 0
0 … 0 1 | 0 1 0 0
0 … 0 0 | 0 0 1 0
0 … 0 0 | 0 0 0 1

codewort1 = 0 … 0 1 | 1 1 0 0

Wie kommt man darauf? und kann ich damit alle möglichen Codeworter bestimmen?

#10

Na dann ist es ja doch, was ich gedacht habe. Das Quellwort ist dann 00…01. Damit kannst du die Kontrollstellen via Bestimmungsgleichungen berechnen (k4=1, k3=1, k2=0, k1=0), womit du dann dein Gesamtes Codewort hast:
00…01 1100
Genau so geht es für alle Code-Wörter.

#11

Nun, ich glaube ich habe das mit dem Prüfschema doch noch nicht verstanden, kann hier jemand noch ein Beispiel von mir machen?

Beispiel 1:
Ein Hamming Code soll 8 Nutzbits absichern, Distanz 3, Prüfstellen 4.
Entwickeln Sie ein Prüfschema H mit möglichst wenigen „1“-en.

Lösung:

0 1 1 0 1 0 0 1 1 0 0 0
1 1 0 1 0 0 1 1 0 1 0 0
1 1 0 0 1 1 1 0 0 0 1 0
1 0 1 1 0 1 0 0 0 0 0 1
aufbau nach
m8,7,6,5,4,3,2,1,k4,3,2,1

Beispiel 2:
Ein Hamming Code soll 11 Nutzbits absichern. Distanz 3, Prüfstellen k=4.
Entwickln Sie ein Prüfschema H zu diesem Hamming Code

Lösung:
1 1 1 0 1 1 0 1 0 0 1 1 0 0 0
1 0 1 1 1 1 1 0 0 1 1 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 0 0 1 0
1 1 1 1 0 0 1 1 1 0 0 0 0 0 1
aufbau
m,k

Ich verstehe da ein paar Sachen nicht.

  1. Wie weiß ich, was möglichst wenig "1"en bedeutet, Beispiel 1.
  2. Gibt es da Formeln, wie ich das Schema befülle? Ich habe da nur verstanden, dass k immer eine diagonale 1en hat und der rest von k 0 ist.

Wäre für eine ausführliche Beschreibung/Erklärung sehr dankbar.

#12

Die Anzahl der Spalten ist ja Nutzbits+Prüfstellen. Die Anzahl der Zeilen ist die Anzahl der Prüfstellen. Soviel dazu.
Dass im Prüfteil eine Einheitsmatrix steht, hast du ja schon rausgefunden.
Bei den Nutzbits sieht es so aus (also ich kann jetzt nur schätzen, wie das aufgebaut ist - musst mal sehen, ob dir was bekannt vorkommt), als ob von rechts nach links alle möglichen Kombinationen mit zwei 1en, drei 1en usw. vorkommen…
Also links an die Einheitsmatrix der Prüfstellen kommen alle möglichen Spaltenkombinationen mit genau 2 Einsen. Das sind übrigens (4 über 2). Danach kommen alle Kombinationen mit genau 3 Einsen usw. Bis du die Spalten voll hast. Die Reihenfolge, in der die Kombinationen auftreten, ist wohl unwichtig.
So hast du dann möglichst wenige Einsen. Wenn du das gleiche mit den Nullen machst, hast du möglichst wenige Nullen. Da bin ich mir aber nicht sicher, ob das noch ein Hamming-Code ist, da die Prüfstellen dann ja keine Einheitsmatrix mehr bilden.

Nico

#13

Hallo,

ja so in etwa hatte ich mir das auch gedacht.

Nur da habe ich folgendes Problem:

Nutzbits 11, Prüfstellen 4

Lösung:

1 1 1 0 1 1 0 1 0 0 1 1 0 0 0
1 0 1 1 1 1 1 0 0 1 1 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 0 0 1 0
1 1 1 1 0 0 1 1 1 0 0 0 0 0 1

1 2 3 4 5 6 7 8 9…

In Nutzbitsteil Spalte 4 und 5 sind gleich.

#14

So, ich habe jetzt aus folgendem Prüfschema H, hT gebildet.

Prüfschema
0 1 1 0 1 0 0 1 1 0 0 0
1 1 0 1 0 0 1 1 0 1 0 0
1 1 0 0 1 1 1 0 0 0 1 0
1 0 1 1 0 1 0 0 0 0 0 1

hT=

0 1 1 1
1 1 0 0
1 0 0 1
0 1 0 1
1 0 1 0
0 0 1 1
0 1 1 0
1 1 0 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Soweit so gut, nun soll man aus hT eine Generatormatrix erstellen. Wie funktioniert das?