Synchronisation eines Bitstreams

[hannes]

Hi,
beim Schreiben meiner Diplomarbeit ("Einsatz von fehlerkorrigierenden Codes in der Steganographie") bin ich auf eine harte Nuss gestoßen.

Aus einem Bitstream lese ich immer 12 bit lange Zeichen aus (8 Bit Information und 4 Paritätsbit). Diese 12 Bit werden dann in einer Fehlerkorrektur weiterverarbeitet.

Treten nun bei diesem eingelesenen Bitstrom vereinzelt Fehler auf, so werden diese ohne Probleme korrigiert.
Beispiel für eine funktionierende Fehlerkorrektur:
es soll folgende Zeichenkette übertragen werden:

" 0x96 0x87 0x07 0x59 " hexadezimale Werte
"1001 0110 1000 0111 0000 0111 0101 1001 " Zeichenkette ohne Fehlerkorrektur
"1011 0110 xxxx 1010 0111 xxxx 1000 0111 xxxx 0101 1000 xxxx " Zeichenkette mit Fehlerkorrektur,
dabei steht xxxx für einen 4bit Wert, den ich jetzt nicht berechnet habe.

Tritt jetzt aber auch bei diesem Bitstrom noch eine Bitverschiebung auf, so funktioniert meine Fehlerkorrektur nicht mehr.

Unter Bitverschiebungen meine ich folgendes:
"1001 0110 1000 0111 0000 0111 0101 1001 " wird zu
"1010 1101 0100 1111 0000 0111 0100 1100 ".

Dabei habe ich nun diese Bitverschiebungen stark überzeichnet. Diese treten frühestens nach ca. geschätzten 100 Bits auf. Es bleibt also mehr Zeit zum Synchronisieren. Fehler können jedoch auch bei einer Bitstromverschiebung auftreten.

Falls dazu jemand Tipps bzw. Hilfe geben kann, wär mir sehr geholfen.

Ein Dankeschön im Vorhinein.

MfG,
Hannes.

 

[Bleiglanz]

hast du etwa selber einen fehlerkorrigierenden Code implementiert? Warum?

und was bedeutet "synchronisieren"???

 

[hannes]

habe Fehlerkorrektur implementiert. (wird für DA verlangt).

Synchronisieren heißt, dass ich den Bitstrom in eine zeitlich richtige Folge bringen muss.
ist z. B. das 1. Bit eine "1",
das 2. Bit eine "0"
und das 3. Bit wieder eine "1",
so kann es vorkommen, dass zum Beispiel das 2. bit nicht übertragen wird; sprich gelöscht worden ist.
So kommt also im Bitstrom das 1. Bit, dann das 3. Bit vor und danach alle folgenden.
Meine Implementation bekommt aber nichts vom Löschen des 2. Bits mit.
folglich behandle ich das 3. Bit so, als wäre es das 2. Bit,
das 4. Bit wird dann als 3. Bit angesehen usw.
Könnte ich aber anhand der folgenden Bits feststellen, das Bit 2 wahrscheinlich gelöscht wurde,
und mich somit ab Bit 3, bzw. 4 oder irgend einem späteren Zeitpunkt wieder synchronisieren, und somit den Bitstrom wieder richtig interpretieren, wäre mein Problem gelöst.
Mfg
Hannes.

 

[Bleiglanz]

Puuuh

scheint mir extrem schwierig zu sein....


würde ich mal googeln, irgendwie ist das sehr hart (bist du sicher dass du das brauchst?)


angenommen das bit3 fehlt

später merkst du natürlich bei einer paritätsprüfung, dass irgendwas nicht stimmt (natürlich sind dann auch deine kontrollbits kaputt);

Ein code, der dann ermittelt, dass bit3 fehlt UND dann auch noch den richtigen wert einsetzen kann müsste schon ziemlich gut sein...

 

[hannes]

googeln hat mir dabei bis jetzt noch nicht viel gebracht, außer das java-forum.
Ist ja zumindestens schon etwas, wenn man weiß, dass jemand anderer die eigenen Sorgen teilt. ;-)

Derzeit versuche ich das Problem so zu lösen:

	/**
   *  führt Fehlerkorrektur durch
   *  Eingabeparameter int, 8-stelliges Codewort mit 4 Paritätsbit 
   * 	Rückgabewert int, geprüftes und korrigiertes 8-bit Codewort
   * 		 
   */
	private int errorCorection(int code) {
	  int syndrom = 0;
	  int codeToSync;
	  int extractedByte = 0;
	  int testCode = 0;
	  int testParity = 0;
	 
	  syndrom = ParityCheck(code);	  
	  extractedByte = (code >> 4) & 0xff;
	  testParity |= (code & 16); 	// Paritätsbit zum testen
	  
	  switch (syndrom) {
	    
	  	case 15: extractedByte ^= 128; error++; break;
	  	case 14: extractedByte ^= 64; error++; break;
	  	case 13: extractedByte ^= 32; error++; break;
	  	case 12: extractedByte ^= 4; error++; break;
	  	case 11: extractedByte ^= 16; error++; break;
	  	case 10: extractedByte ^= 2; error++; break;
	  	case  7: extractedByte ^= 8; error++; break;
	  	case  6: extractedByte ^= 1; error++; break;
	  	case  8: testParity ^= 8; break; 	// bei folgenden 4 Fällen tritt
	  	case  4: testParity ^= 4; break; 	// Fehler in Paritätsbit auf
	  	case  2: testParity ^= 2; break;
	  	case  1: testParity ^= 1; break;
	  	case  0: break; 									// Codewort fehlerfrei übertragen
	  	default: return -1; 							//ansonsten nicht lösbarer Fehler
	  }
	  
	  if (syndrom != 0) {
	    // war syndrom != 0, so wurde ein Fehler festgestellt;
	    // ist dieser Fehler richtig korrigiert worden, so muss jetzt
	    // syndrom == 0 sein.
	    testCode = extractedByte << 4;
	    testCode |= testParity;
	    syndrom = ParityCheck(testCode);
	    
	    // falls syndrom noch immer != 0 ist, Datenstrom synchronisieren
	    if (syndrom != 0)
	      Synchro(code);
	  }	  
	  
	  return extractedByte;	 
	}
		
	
	
	/**
   *  führt Paritätsüberprüfung durch
   *  Eingabeparameter int, 8-stelliges Codewort mit 4 Paritätsbit 
   * 	Rückgabewert int, 4-bit Syndrom
   * 		 
   */
	private int ParityCheck(int code) {
	  int syndrom = 0;
	  int bit = 0;
	  int newBit = 0; 	  
	  int[][] parity = {{1, 1, 1, 1},
										 	{1, 1, 1, 0},
										 	{1, 1, 0, 1},
										 	{1, 0, 1, 1},
										  {0, 1, 1, 1}, 
										  {1, 1, 0, 0},
										  {1, 0, 1, 0},
										  {0, 1, 1, 0},
										  {1, 0, 0, 0},
										  {0, 1, 0, 0},
										  {0, 0, 1, 0},
										  {0, 0, 0, 1}};
	  	 
	  for (int i = 0; i < 4; i++) {	    
	    for (int j = 0; j < n; j++) {
	      bit = code >> (n-j-1);
	      bit &= 01;
	      newBit ^= (bit&parity[j][i]);
	    }
	    syndrom <<= 1;
	    syndrom ^= newBit;	    
	    newBit = 0;
	  }	  
	  return syndrom;	  
	}
	
	
	/**
   *  führt, wenn möglich, eine (+1, -1) bit Synchronisation des Datenstroms durch
   *  Eingabeparameter int, 8-stelliges Codewort mit 4 Paritätsbit 
   * 	Rückgabewert int, geprüftes und korrigiertes 8-bit Codewort
   * 		 
   */
	int Synchro (int code) {	  	  
	  int syndrom = 0;
	  int codeToSync;
	  int extractedByte = 0;
	  int testCode = 0;
	  int testParity = 0;
	  
	  
    codeToSync = code;
    codeToSync >>= 1;	    // Bitverschiebung nach rechts und Bit12 = 0
    syndrom = ParityCheck(codeToSync);
    
    if (syndrom == 0) {
      extractedByte = (codeToSync >> 3) & 0xff;	   
      toSync = 1;  		// Datenstrom gehört um 1 Bit "nachgestellt" -
      								// beim nächsten Einlesen eines Codeworts ein Zeichen weniger einlesen und
      pad = code & 1; // erstes Bit = pad setzen
    } else {
      codeToSync += 2048;  // Bit12 wird auf 1 gesetzt
      syndrom = ParityCheck(codeToSync);
      if (syndrom == 0) {
        extractedByte = (codeToSync >> 4) & 0xff;
        toSync = 1;			// Datenstrom gehört um 1 Bit "nachgestellt" -
        								// beim nächsten Einlesen eines Codeworts ein Zeichen weniger einlesen und
        pad = code&1;		// erstes Bit = pad setzen
      } else {
        codeToSync = code;
        codeToSync *= 2;  // Bitverschiebung nach links 
        codeToSync &= 4095; // Löschen der Bitstellen > 12
	      syndrom = ParityCheck(codeToSync);
	      if (syndrom == 0) {
	        extractedByte = (codeToSync >> 4) & 0xff;
	        toSync = -1;		// Datenstrom gehört um 1 Bit "vorgestellt" 
	        								// - also 1 Bit mehr einlesen und verwerfen
	      } else {
	        codeToSync += 1;  // Bit 1 mit 1 auffüllen		        
		      syndrom = ParityCheck(codeToSync);
		      if (syndrom == 0) {
		        extractedByte = (codeToSync >> 4) & 0xff;
		        toSync = -1;		// Datenstrom gehört um 1 Bit "vorgestellt" 
														// - also 1 Bit mehr einlesen und verwerfen
		      }
	      }
      }
    }
	  return extractedByte;
	}

Damit kann ich den Datenstrom zumindestens beim nächsten bzw. übernächsten Zeichen wieder Synchronisieren und ab dort fehlerfrei fortsetzen.

Wenn jemand Verbesserungen sieht, bitte ich um Tipps und Anregungen.
Auch bezüglich Programmierstil wäre ich für Tipps dankbar.
MfG,
Hannes.