Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ss15:hamming-code [2015/09/14 15:49]
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.
+{{ :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 entstandener 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 später noch erläutert.
 <code python>
@@ Zeile 24: / Zeile 23: @@
 	#print k #letztes Schnipsel an Code
 	return i #umgewandelter Code
+</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.
+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>
+def seven_to_four_bit_code(i):
+	o=[]
+	n=0
+	H=np.matrix([[1,1,0,1,1,0,0],[1,0,1,1,0,1,0],[0,1,1,1,0,0,1]])
+	while True:
+		w=[] #Zwischenliste, worauf Korrektur angewendet wird
+		v=[] #Vergleichsliste
+		k=np.matrix(i[0+n*7:7+n*7]) #7er Bit-Block
+		if k.shape[1]<7: #letztes Schnipsel an Code, dass kleiner 7 ist, wird nicht gelesen (müsste immer leer sein)
+			break #Sicherheitsbreak
+		h=np.fmod(H.dot(k.reshape(7,1)),2)       # viele Syntaxumwandlungen nötig
+		v.extend(np.array(h).flatten().tolist()) # ""         ""        ""
+		b=tuple(v)                               # ""         ""        ""
+		if b==(1,1,0): #1. Spalte von H
+			w.extend(i[0+n*7:7+n*7-3])
+			if w[0]==1:
+				w[0]=0
+			else:
+				w[0]=1
+			o.extend(w)
+		elif b==(1,0,1): #2. Spalte von H
+			w.extend(i[0+n*7:7+n*7-3])
+			if w[1]==1:
+				w[1]=0
+			else:
+				w[1]=1
+			o.extend(w)
+		elif b==(0,1,1): #3. Spalte von H
+			w.extend(i[0+n*7:7+n*7-3])
+			if w[2]==1:
+				w[2]=0
+			else:
+				w[2]=1
+			o.extend(w)
+		elif b==(1,1,1): #4. Spalte von H
+			w.extend(i[0+n*7:7+n*7-3])
+			if w[3]==1:
+				w[3]=0
+			else:
+				w[3]=1
+			o.extend(w)
+		else: #alles nach der 4. Spalte unserer H matrix führt zu keiner Veränderung in unserer 4er Liste
+			o.extend(i[0+n*7:7+n*7-3]) #übersetzung direkt schreiben, sodass direkt zugeordnet wird
+		n+=1
+		#print w
+	return o
 </code>

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge