Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ss15:hamming-code [2015/09/14 16:41]
kevin.stegemann
+++ ss15:hamming-code [2016/05/10 14:46] (aktuell)
@@ Zeile 1: / Zeile 1: @@
 ====== Hamming-Code ======
+===== 1. Funktion =====
+Der Hamming-Code soll uns dabei helfen mögliche Übertragungsfehler zu korrigieren, die durchaus bei einer Schallübertragung vorkommen. Im Prinzip wird unsere zu übertragende Bits verlängert, wodurch darin mehr Informationen enthalten sind, die zur Fehlerkorrektur beitragen. Bei Hamming werden aus unserer Bit-Übertragung immer nacheinander 4 aufeinanderfolgende Bits mithilfe der Umwandlungsmatrix ''G'' in 7 Bits umgewandelt. Damit ist es nun möglich, dass jeder 7. Fehler korrigiert wird, jedoch müssen die Fehler auch einen Abstand von 7 Bits einhalten. Die Bit-Blöcke sollen im nachfolgenden Text als Vektoren verstanden werden.
+===== 2. four_to_seven_bit_code =====
-Der Hamming-Code soll uns dabei helfen mögliche Übertragungsfehler zu korrigieren, die durchaus bei einer Schallübertragung vorkommen. Im Prinzip wird unsere zu übertragende Bits verlängert, wodurch darin mehr Informationen enthalten sind, die zur Fehlerkorrektur beitragen. Bei Hamming werden aus unserer Bit-Übertragung immer nacheinander 4 aufeinanderfolgende Bits mithilfe der Umwandlungsmatrix **G** in 7 Bits umgewandelt. Damit ist es nun möglich, dass jeder 7. Fehler korrigiert wird, jedoch müssen die Fehler auch einen Abstand von 7 Bits einhalten. Die Bit-Blöcke sollen im nachfolgenden Text als Vektoren verstanden werden.
+{{ :ss15:hamming_1.jpg?direct&200|Überblick entstehender 7er Bits}} Bevor die Bits durch Schall übertragen werden, muss der Hamming-Code auf sie angewendet worden sein. Aus unserer Bit-Liste werden dabei nacheinander 4er Bit-Blöcke mit der Umwandlungsmatrix ''G'' in modulo 2 multipliziert und erhalten eben unseren fertigen 7er Bit-Code. Übersicht in nebenstehender Skizze. Modulo 2 bedeutet, dass der Rest der Division aus unserer Zahl durch 2 hingeschrieben wird. Die Funktionsweise der Erkennungsmelodie in unserem Beispiel-Code, die um unseren Haupt-Bit-Strang erweitert wird, wird im nachfolgenden Thema erläutert.
-===== four_to_seven_bit_code =====
-{{ :ss15:hamming_1.jpg?direct&200|Überblick entstehender 7er Bits}} Bevor die Bits durch Schall übertragen werden, muss der Hamming-Code auf sie angewendet worden sein. Aus unserer Bit-Liste werden dabei nacheinander 4er Bit-Blöcke mit der Umwandlungsmatrix **G** in modulo 2 multipliziert und erhalten eben unseren fertigen 7er Bit-Code. Übersicht in nebenstehender Skizze. Modulo 2 bedeutet, dass der Rest der Division aus unserer Zahl durch 2 hingeschrieben wird. Die Funktionsweise der Erkennungsmelodie in unserem Beispiel-Code, die um unseren Haupt-Bit-Strang erweitert wird, wird im nachfolgenden Thema erläutert.
 <code python>
@@ Zeile 26: / Zeile 25: @@
 </code>
-===== seven_to_four_bit_code =====
+===== 3. seven_to_four_bit_code =====
+{{ :ss15:hamming_3.jpg?direct&200|Prinzip der Kontrollmatrix}} Hier nun geschieht das eigentlich Komplizierte. Unsere Aufnahme liefert uns eine Reihe an Bits. Daraus werden wieder nacheinander 7er Bit-Blöcke mit der Kontrollmatrix ''H'' in modulo 2 multipliziert. Wir erhalten einen 3er Vektor, der Aussage darüber gibt, ob ein Fehler vorhanden ist oder nicht. Wenn es ein Nullvektor ist, dann existiert auch der kontrollierte 7er Vektor in unserer Übersicht beim **four_to_seven_bit_code**. Wenn sich der 3er Vektor vom Nullvektor unterscheidet, wissen wir, dass ein Fehler vorhanden ist. Über die Fehlerstelle gibt uns die Kontrollmatrix ''H'' Auskunft. Wir vergleichen unseren 3er Vektor mit den Spalten der Kontrollmatrix und dabei ist die n-te übereinstimmende Spalte unsere Fehlerstelle n. In unserem 7er Vektor ist also die n-te Komponente falsch und wird mit 0 oder 1 ausgetauscht. Somit ist die Fehlerkorrektur durchgeführt. In unserem unten stehenden Code finden sich jedoch nicht alle Spalten von der Kontrollmatrix ''H'', da wir nur die ersten 4 Stellen gebrauchen können. Uns ist nämlich aufgefallen, dass die ersten 4 Komponenten des korrigierten 7er Bit-Codes unseren 4er Bit-Code entsprechen. So erübrigt sich die Fehlerkorrektur der Komponenten 5-7.
-{{ :ss15:hamming_3.jpg?direct&200|Prinzip der Kontrollmatrix}} Hier nun geschieht das eigentlich Komplizierte. Unsere Aufnahme liefert uns eine Reihe an Bits. Daraus werden wieder nacheinander 7er Bit-Blöcke mit der Kontrollmatrix **H** in modulo 2 multipliziert. Wir erhalten einen 3er Vektor, der Aussage darüber gibt, ob ein Fehler vorhanden ist oder nicht. Wenn es ein Nullvektor ist, dann existiert auch der kontrollierte 7er Vektor in unserer Übersicht beim **four_to_seven_bit_code**. Wenn sich der 3er Vektor vom Nullvektor unterscheidet, wissen wir, dass ein Fehler vorhanden ist. Über die Fehlerstelle gibt uns die Kontrollmatrix **H** Auskunft. Wir vergleichen unseren 3er Vektor mit den Spalten der Kontrollmatrix und dabei ist die n-te übereinstimmende Spalte unsere Fehlerstelle n. In unserem 7er Vektor ist also die n-te Komponente falsch und wird mit 0 oder 1 ausgetauscht. Somit ist die Fehlerkorrektur durchgeführt. In unserem untenstehenden Code finden sich jedoch nicht alle Spalten von der Kontrollmatrix **H**, da wir nur die ersten 4 Stellen gebrauchen können. Uns ist nämlich aufgefallen, dass die ersten 4 Komponenten des korregierten 7er Bit-Codes unseren 4er Bit-Code entsprechen. So erübrigt sich die Fehlerkorrektur der Komponenten 5-7.
+Wenn nun ein 3er-Vektor entsteht, der nicht den Spalten der Kontrollmatrix ''H'' entspricht, so ist es ein Hinweis auf eine Folge von Fehlern, die mit Hamming nicht zu korrigieren sind. Hamming ist noch das am einfachsten zu verstehende und umzusetzende Prinzip der Fehlerkorrektur, die unseren Ansprüchen hoffentlich genügen sollte.
 <code python>

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge