Synchronisation eines Bitstreams

Status
Nicht offen für weitere Antworten.

hannes

Mitglied
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

Gesperrter Benutzer
hast du etwa selber einen fehlerkorrigierenden Code implementiert? Warum?

und was bedeutet "synchronisieren"???
 

hannes

Mitglied
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

Gesperrter Benutzer
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

Mitglied
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:


Code:
	/**
   *  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.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
X Programmieren eines Spieles Softwareentwicklung 25
J Programmierung eines MazeGames Softwareentwicklung 1
G Anzahl der Rekursionsaufrufe eines DFS Algorithmus Softwareentwicklung 16
F Planung und Durchführung eines Projektes Softwareentwicklung 2
A Händische Programmierung eines 1:n-ORM Softwareentwicklung 3
? Fragen zur richtigen Umsetzung eines Projektes Softwareentwicklung 3
M Ada95 - Breite eines Baumes bestimmen Softwareentwicklung 3
B Konstruktion eines Epsilon Automaten & NFA Softwareentwicklung 2
B Signatur eines Abstrakten Datentyps Softwareentwicklung 10
S Länge eines char[][] Softwareentwicklung 12
F Aufwändes eines Software Projektes Softwareentwicklung 21
M Technische Abwicklung eines Onlinekaufs Softwareentwicklung 7
-horn- "Laufzeitberechnung" eines Programmes? Softwareentwicklung 5
U Komplexität eines Algorithmus Softwareentwicklung 1
Z Herangehensweise zum "entschlüsseln" eines Dateifo Softwareentwicklung 2
G Modellierung eines graphentheoretischen Problems Softwareentwicklung 5
V alle abgeleiten Klassen eines Interfaces finden? Softwareentwicklung 2
I Object mit Hilfe eines Class-Objectes instanzieren Softwareentwicklung 3
M Elemente eines Vektors zufällig anordnen Softwareentwicklung 2
M Software zur Erstellung eines Pflichtenhefts? Softwareentwicklung 15
F Zellen eines Excel-Sheets per VBA disablen (ausgrauen)? Softwareentwicklung 10
B Programmierung eines 8051-Assemblers unter Java Softwareentwicklung 3
F Ist der Name eines Ojekts eine Eigenschaft Softwareentwicklung 7

Ähnliche Java Themen


Oben