Der Hamming Code für den Arduino

Bei einer digitalen Funkübertragung kann es zu Störungen kommen und einzelne Bits werden falsch empfangen, kippen sozusagen um. Aus einer 1 wird eine 0.

Richard Wesley Hamming hat sich dazu Gedanken gemacht und eine Codierung entwickelt, die es erlaubt zu überprüfen ob alle Bits richtig übertragen wurden. Einzelne Bits können sogar rekonstruiert werden.

Hier sollen 4 Daten-Bits übertragen werden. Dazu werden nach einem bestimmten Schema 3 Paritäts-Bits hinzugefügt, die Daten werden codiert. Es müssen nun 7 Bits übertragen werden. Wird ein Bit falsch empfangen, so lässt es sich später bei der Decodierung rekonstruieren.

Die 4 Daten-Bits werden mit 3 Paritäts-Bit nach diesem Schema ergänzt.
Die Datenbits: d4, d3, d2, d1

p1 ist die Parität (gerade oder ungerade Summe) aus den Datenbits d1, d2 und d4
p2 ist die Parität aus den Datenbits d1, d3 und d4
p3 ist die Parität aus den Datenbits d2, d3 und d4

Das Ergebnis der Hamming Codierung zur Übertragung: p1 / p2 / d1 / p3 / d2 / d3 / d4

In C für den Arduino sieht das ganze dann so aus

byte code4Bit2Hamming74(byte input){
// https://de.wikipedia.org/wiki/Hamming-Code
// input: x, x, x, x, d4, d3, d2, d1
// output: p1 / p2 / d1 / p3 / d2 / d3 / d4 / 0
byte output=0;

output += ((input & B00000001)<<5); // d1
output += ((input & B00000010)<<2); // d2
output += ((input & B00000100));    // d3
output += ((input & B00001000)>>2); // d4
output += ( ( ((output & B00100000)>>5) ^ ((output & B00001000)>>3) ^ ((output & B00000010)>>1) ) << 7); // p1
output += ( ( ((output & B00100000)>>5) ^ ((output & B00000100)>>2) ^ ((output & B00000010)>>1) ) << 6); // p2
output += ( ( ((output & B00001000)>>3) ^ ((output & B00000100)>>2) ^ ((output & B00000010)>>1) ) << 4); // p3
return output;
}

Die Daten können nun übertragen werden.

Auf der Empfänger Seite werden die Paritäten mit den Daten-Bits zurück gerechnet und Fehler ggf. aufsummiert. Ist die Summe 0, liegt kein Fehler vor. Ist die Summe 1 bis 7, so ist dieses Bit umgekippt und muss invertiert werden.

Das ganze wieder in einer C Funktion für den Arduino

byte decode4Bit2Hamming74(byte input){
// input: p1 / p2 / d1 / p3 / d2 / d3 / d4 / 0
// output: 0, 0, 0, 0, d4, d3, d2, d1
byte error=0, output=0;

error += ( ((input & B10000000)>>7 ) ^ ((input & B00100000)>>5) ^ ((input & B00001000)>>3) ^ ((input & B00000010)>>1) );
error += ( ((input & B01000000)>>6 ) ^ ((input & B00100000)>>5) ^ ((input & B00000100)>>2) ^ ((input & B00000010)>>1) ) * 2;
error += ( ((input & B00010000)>>4 ) ^ ((input & B00001000)>>3) ^ ((input & B00000100)>>2) ^ ((input & B00000010)>>1) ) * 4;
if(error > 0) { // >0: Fehler an Stelle error von links 1 - 7 oder 0: kein Fehler
  input ^= (B10000000 >> (error-1)); // ein bit Fehler reparieren
}
output += ((input & B00100000)>>5); // d1
output += ((input & B00001000)>>2); // d2
output += ((input & B00000100));    // d3
output += ((input & B00000010)<<2); // d4
return output;
}

Am Ende erhalten wir wieder die 4 Daten-Bits.

Wenn mehrere Bits umgekippt sind lässt sich das hierdurch nicht korrigieren.

Für den Testlauf habe ich folgendes Programm geschrieben, dass die beiden oberen Routinen verwendet.

// 4 Bit mit Hamming codieren zu 7 Bit
// decodieren mit Fehlerkorrektur
// max. 1 Bit darf auf der Übertragungsstrecke umkippen, das wird im decoder wieder repariert
//
// Matthias Busse 29.10.2015 Version 1.1

byte zu, za, hamming;

void setup() { 
  Serial.begin(38400);
}

void loop() {
  za=random(16); // Zufallszahl 0..15
  hamming=code4Bit2Hamming74(za); // Zahl zu Hamming codieren 
  Serial.print("Zahl: ");
  Serial.print(za);
  Serial.print(" \t");
  Serial.print("Hamming: ");
  Serial.println(hamming, BIN);
  // Fehlerbit einbauen
    zu=random(7); // 0..6 Zufallszahl
    hamming ^= (B10000000 >> zu);  // Bit an 1. - 7. Stelle umdrehen
  za=decode4Bit2Hamming74(hamming); // Hamming decodieren zu Zahl
  Serial.print("Zahl: ");
  Serial.print(za);
  Serial.print(" \t");
  Serial.print("Hamming: ");
  Serial.print(hamming, BIN);
  Serial.print("     \t Fehler war an Stelle: ");
  Serial.println(zu);
  Serial.println("");
  delay(1000); 
}

von Matthias Busse

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.