Suche Protokoll, in dem keine zwei gleichen Bytes aufeinanderfolgen

Hallo Programmierer,

Ich habe eine Hardware, die mir das letzte Byte nochmal liefert, wenn sie nichts zu senden hat. Dieses Verhalten kann ich nicht beeinflussen, wohl aber, was gesendet wird. Meine Frage:

Kennt ihr ein Protokoll das sicherstellt, dass dasselbe Byte nicht zweimal hintereinander im Datenstrom erscheint?

Danke für eure Mühe,

Hacker21

volkard

Rechne die Bytefolge um in ein kleineres Zahlensystem und lass freie Bits wackeln.

void send(char byte){
   static char wackel=0;
   char hi=byte>>4;
   char lo=byte&15;
   hardwaresend(hi|wackel);
   wackel^⁼0xf0;
   hardwaresend(lo|wackel);
   wackel^⁼0xf0;
}

char receive(){
   char hi=hardwarereceive();
   static char old=hi;
   while(old==hi)
      hi=hardwarereceive();
   old=hi;
   char lo;
   while(old==lo)
      lo=hardwarereceive();
   old=lo;
   return ((hi&0x0f)<<4)|(lo&0x0f);
}

Ist das erste, was mir eingefallen ist. Hab noch nie auf so eine Weise eine static-Zeile verzögert. Bestimmt gibt es auch Protokolle mit weniger Overhead, mir fällt aber gerade keins ein.

volkard

Wenn Du nicht alle 256 verschiedenen chars schickst, sondern zum Beispiel niemals die -128, dann kannste vielleicht die nehmen, um sie beim Senden zwischen Doppelbytes zu stecken, und beim Empfangen ingorieren.

volkard schrieb:

Rechne die Bytefolge um in ein kleineres Zahlensystem und lass freie Bits wackeln.
void send(char byte){
   static char wackel=0;
   char hi=byte>>4;
   char lo=byte&15;
   hardwaresend(hi|wackel);
   wackel^⁼0xf0;
   hardwaresend(lo|wackel);
   wackel^⁼0xf0;
}
char receive(){
   char hi=hardwarereceive();
   static char old=hi;
   while(old==hi)
      hi=hardwarereceive();
   old=hi;
   char lo;
   while(old==lo)
      lo=hardwarereceive();
   old=lo;
   return ((hi&0x0f)<<4)|(lo&0x0f);
}
Ist das erste, was mir eingefallen ist. Hab noch nie auf so eine Weise eine static-Zeile verzögert. Bestimmt gibt es auch Protokolle mit weniger Overhead, mir fällt aber gerade keins ein.

Danke für den Vorschlag. Eine ähnliche Idee hatte ich auch schon, nur dass dabei die halbe Bandbreite draufgeht.

Ich dachte eher an eine Möglichkeit, zwei aufeinanderfolgende Bytes irgendwie in Beziehung zu bringen, so dass eindeutig entschieden werden kann, ob das aktuelle Byte gültig oder ungültig ist. Da muß es doch etwas geben.

Der Bus ist nicht gerade schnell (SPI, 18 Mhz Clock). Halbieren von Bytes wäre daher keine so gute Lösung.

volkard schrieb:

Wenn Du nicht alle 256 verschiedenen chars schickst, sondern zum Beispiel niemals die -128, dann kannste vielleicht die nehmen, um sie beim Senden zwischen Doppelbytes zu stecken, und beim Empfangen ingorieren.

Ich kann leider auch nicht beeinflussen, wann Verdopplungen auftreten.

Beispiel: ich sende 1,2,3,4,5 und empfange 1,2,2,2,3,4,5. Die beiden Zweien müssen daher als falsch erkannt und weggeworfen werden.

volkard

Hacker21 schrieb:

volkard schrieb:

Wenn Du nicht alle 256 verschiedenen chars schickst, sondern zum Beispiel niemals die -128, dann kannste vielleicht die nehmen, um sie beim Senden zwischen Doppelbytes zu stecken, und beim Empfangen ingorieren.

Ich kann leider auch nicht beeinflussen, wann Verdopplungen auftreten.

Beispiel: ich sende 1,2,3,4,5 und empfange 1,2,2,2,3,4,5. Die beiden Zweien müssen daher als falsch erkannt und weggeworfen werden.

Das geht ja so auch schon. Einfach die Doppel wegwerfen im receive().

Aber was ist, wenn Du wirlkich 1,2,2,4,5 schicken WILLST? Dann sendest Du 1,2,-128,2,4,5. Es kommt an 1,1,2,2,2,-128,-128,2,4,4,5. Doppel raushauen: 1,2,-128-,2,4,5. Danach jede -128 raushauen. 1,2,2,4,5. Viola!

Ich bin sicher, das kriegt man sogar hin, ohne eine Zauberzahl -128 als Nutzcode verbieten zu müssen, nur hab ich's noch nicht raus.

Daher erstmal die Frage, was DU schicken willt, gibt es da Sachen, auf die man sich stützen kann, oder muß man ein allgemeines Protokoll schreiben, das jeden beliebigen Byte-Strom beim Senden mit send() so verändert, daß trotz der komischen Hardware beim Empfänger, der receive() benutzt, das Richtige ankommt?

volkard schrieb:

Aber was ist, wenn Du wirlkich 1,2,2,4,5 schicken WILLST? Dann sendest Du 1,2,-128,2,4,5. Es kommt an 1,1,2,2,2,-128,-128,2,4,4,5. Doppel raushauen: 1,2,-128-,2,4,5. Danach jede -128 raushauen. 1,2,2,4,5. Viola!

Stimmt, das sieht sehr gut aus.

volkard schrieb:

Daher erstmal die Frage, was DU schicken willt, gibt es da Sachen, auf die man sich stützen kann, oder muß man ein allgemeines Protokoll schreiben, das jeden beliebigen Byte-Strom beim Senden mit send() so verändert, daß trotz der komischen Hardware beim Empfänger, der receive() benutzt, das Richtige ankommt?

Es sind Rohdaten, d.h. jedes Byte ist erlaubt. Ich könnte aber eine Kodierung einbauen, die die -128 ausschließt, ähnlich Base64, so dass ich aus 8 Bytes 9 Bytes mache. Das würde bedeuten, dass ich immer Pakete schicke, deren Länge durch 9 teilbar ist, aber das wäre noch akzeptabel.

volkard

(getippt bevor Dein Bas64 da war, nur eine ZusatzIdee, keine AHnung, ob Base64 für Dich besser ist.)

Wir machen die 0 zum verbotenen Zeichen, die niemals verschickt wird. Außerdem machen wir die 1 zum Escapezeichen, auf eine 1 folgt immer eine 2 oder 3. Folgt auf die 1 eine 2, war tatsächlich eine 0 gemeint. Folgt auf eine 1 eine 3, war tatsächlich eine 1 gemeint.
So, jetzt haben wir ein Protokoll geschaffen, wo niemals eine 0 über den Kanal geht. Zusatzkosten bei zufälligen Daten: 2/256 mal ein Zusatzbyte, nämlich immer, wenn eine 0 oder 1 gemeint war, und deswegen 1,2 bzw. 1,3 geschickt wird.

Das jetzt nullfreie Protokoll wird durch einen weiteren Filter geschickt, der immer, wenn zwei Doppelbytes gemeint sind, eine 0 einfügt, die vom Empfänger verworfen wird. Zusatzkosten bei zufälligen Daten: 1/256, nämlich immer bei Dopplung.

Gesamtzusatzkosten: 258/256 * 257/256 = 1.01174927, also 1,2%.
Geht ja noch, dafür, daß es so einfach ist.

Bei Nicht-Zufälligen Daten könnte man aber schwer Pech haben, was ist, wenn man mal 100 aufeinmandetrfolgende Nullen schicken will? Dagegen würde ich den Stream mit Pseudozufall würzen.

Beim Sender und Empfänger wird immer rnd+=89 gemacht und das gesendete oder empfangene Byte mit byte^=rnd ver- und entschlüsselt.

Dann gibt es zwar immernoch krankhafte Datenn, bei denen das Protokoll lahm ist, aber um die zu treffen, müßte der Datenersteller schon böswillig diese Schwäche suchen und exploiten.

volkard

Hacker21 schrieb:

Ich könnte aber eine Kodierung einbauen, die die -128 ausschließt, ähnlich Base64, so dass ich aus 8 Bytes 9 Bytes mache. Das würde bedeuten, dass ich immer Pakete schicke, deren Länge durch 9 teilbar ist, aber das wäre noch akzeptabel.

Das war die erste Idee. Bei Base128 hast Du pro Byte auf dem Kanal 1 Bit unbenutzt, das kannste einfach wackeln lassen.

hustbaer

Die einfachste Variante die mir einfällt (die < 50% Overhead hat), wäre ein Bit als "Taktbit" zu verwenden. 1 von 8 ist 12.5%. Das ist sicherlich schlechter als andere Verfahren, aber dafür ist es noch halbwegs einfach.

Beim Umwandeln von 8 Bittigen Bytes in einen 7 Bit Datenstrom gibt es auch mehrere Möglichkeiten
* du sendest immer 7 Byte auf einmal, kodiert als 8 Byte Block
* du sendest die länge jedes Blocks vor dem Block, und dann so viele Datenbyte (zu je 7 Bit) bis alle Bits versendet wurden
* du verwendest ein Stop-Zeichen/Signal ähnlich BASE64

Das Stop-Signal könnte z.B. sein wenn das "Taktbit" sich nicht ändert, der Wert des Bytes aber schon. Beispiel (Taktbit = MSB): 0x00, 0x80, 0x81.
Das 0x81 wäre das "Stop-Signal", d.h. der Block ist 2 Byte a 7 Bit lang, also 14 Bit, 14/8 = 1.xxx d.h. wir haben ein 8-Bit Byte empfangen (mit dem Wert 0).
Bei zwei Nullbytes wäre die Folge dann 0x00, 0x80, 0x00, 0x01. Usw.

Die "Stop-Signal" Variante ist vielleicht etwas fummeliger zu implementieren als die anderen, dafür recht flexibel in der Anwendung.

EDIT: das wäre die Base128 Variante, die noch nicht dastand als ich angefangen hatte zu tippen /EDIT

-----

@volkard: den 2. Layer kannst du optimieren, indem du die 0 nicht verwirfst, sondern bereits die 0 als "nochmal-Zeichen" interpretierst. D.h. aus 2-2-3 wird 2-0-3 und aus 2-2-2-3 wird 2-0-2-3. Dadurch wird dieser Layer "gratis".

Mit einem PRNG mixen sollte man trotzdem, denn sonst könnte man wieder ein Problem mit vielen Nullen oder Einsern im Original-Datenstrom bekommen. Wobei ich persönlich einen besseren PRNG verwenden würde. Vielleicht nicht gerade einen MT, aber ein einfacher LCG darf es IMO schon sein

volkard

hustbaer schrieb:

* du sendest immer 7 Byte auf einmal, kodiert als 8 Byte Block

Dann kann man auch auf das nervige umhershiften zwischen den Nutzbytes verzichten, man ändert vor dem Senden die rechtesten Bits der 7 Bytes so, daß sie alternierend sind, und sammelt, wo man gewechselt hat.

void send(char block[7]){
   char header=0;
   for(int i=0;i!=7;++i){
      if((block[i]&1) != (i&1)){
         block[i]^=1;
         header^=1;
         header<<=1;
      }
   }
   hardwaresend(header);
   for(int i=0;i!=7;++i){
      hardwaresend(block[i]);
}

Und schickt dem Siebenerblock den header voran. Der Empfänger tut mit ähnlicher Schleife den Header wieder an die Daten knallen.

Das rechteste Header-Bit ist frei und wird immer so eingestellt, daß es anders ist als das rechteste Header-Bit des vorangegangenen Siebenerblocks.

void send(char block[7]){
   static lastSentByte=0;//neu
   char header=0;
   for(int i=0;i!=7;++i){
      if((block[i]&1) != (i&1)){
         block[i]^=1;
         header^=1;
         header<<=1;
      }
   }
   header|=lastSentByte&1;//neu
   hardwaresend(header);
   for(int i=0;i!=7;++i){
      hardwaresend(block[i]);
   lastSentByte=block[6];
}

Ich habe da schreckliche Erinnerungen an Base128 und Konsorten (und ein wenig Angst), irgendwie war das Programmieren sehr unhandlich. Kann aber auch sein, daß ich damals noch zu unerfahren war.