Guten Abend! Ich habe folgendes Problem und hoffe, dass mir dabei vllt jemand helfen kann!? Also ich sende Daten per Funk in einem Datenpaket. Dabei besitzt das Paket eine Magic Number zur Identifizierung mit dem Bitmuster BA:AD:FO:OD also 10111010101011011111000000001101. Meine Frage ist nun, mit welcher Wahrscheinlichkeit dieses Bitmuster im Datenpaket vorkommen kann? Der Header beträgt eine Gesamtlänge von 10 Byte und das Datenelement besitzt eine Größe von 28 Byte. Ich hoffe ihr könnt mir das vllt mit einer Beispielrechnung verständlich erklären ;) Vielen Dank! Torsten
Wenn Du das so sendest, sollte die Wahrscheinlichkeit doch möglichst 1 sein.
Hallo, nun, du sagst, dass du diese Magic Number sendest. Also wird sie doch mit Wahrscheinlichkeit 1 = 100% auch im Datenpaket enthalten sein.
42. Die Daten in deinem Datenpaket sind vermutlich nicht zufällig, deswegen kann hier auch niemand eine seriöse Antwort geben.
Nein, die Frage war eigentlich folgende. Die Magic Number dient im header zur identifizierung des Headeranfangs (Datenpakets). Nun kann es ja sein, dass Nutzdaten gesendet werden mit gleichem Bitmuster. Sollte dies vorkommen, könnte es zu Fehlern in der Datenübertragung kommen, da der Empfänger statt Daten ein neues Datenpaket erwartet. Gesucht ist also die Wahrscheinlichkeit, dass soetwas vorkommt und dies sollte eigentlich sehr gering sein und nicht 100%! Ich hoffe, ich konnte es jetzt nochmal verstädnlicher machen... Danke!
Wenn die Daten zufällig sind, dann ist meiner Meinung nach die Wahrscheinlichkeit für das Auftreten des Headers (10 Bit) im Datenpaket (28 Bit)
Weil ja das vorgegebene 10-Bit-Muster an 18 verschiedenen Stellen des Datenpakets anfangen kann. Kann mich aber auch täuschen, Stochastik ist schon etwas her. Verrate doch mal, um was für Daten es sich handelt, diese werden ja eventuell nicht zufällig sein. Du könntest auch beim Sender erst prüfen, ob dein Header in den Daten enthalten ist und das dann quasi maskieren, z.B. über zwei zusammenhängende Pakete.
ich denke das war den Leuten hier schon klar. Wir wissen aber nichts über die daten die gesendet werden sollen, wie soll man das eine Wahrscheinlichkeit ableiten.
Hallo Torsten, das hatte ich mir schon gedacht. Nur ohne etwas über die Nutzdaten zu wissen, kann man darüber halt keine Aussage machen. Es handelt sich ja wahrscheinlich um irgendwelche sinnvollen Daten, da sind die Werte 0x00-0xff in der Regel nicht gleich verteilt und es gibt Korrelationen. Wenn das erste Byte X war, könnte als nächster Wert Y häufiger vorkommen als Z. Und auch für das dritte Byte sind dann in der Regel auch nicht alle Werte gleich wahrscheinlich usw. Nur wenn man diese Informationen hat, könnte man überhaupt etwas ausrechnen. Alles andere ist Kristallkugel. Gruß, DetlevT
Laut Murphy spielt das alles aber nicht wirklich eine Rolle. Nach Murphy ist die Wahrscheinlichkeit 100%, dass etwas schiefgeht, wenn es schiefgehen kann.
Die Daten die gesendet werden sind letzenendes folgende. Gewicht in g (uint32), Tara in g (uint32) und ticks (long). mehr wird nicht gesendet. Das Gewicht ist dabei zufällig oder besser gesagt variabel! @ hdd das sieht vielversprechend aus. Sowas habe ich mir vorgestellt! =) Wenn das jetzt noch richtig zu sein scheint, und ich glaube das ist es, dann vielen Dank!
achja, so ein paket sieht folgendermaßen aus: ___________________ |Header | Datenelement| Das Datenpaket ist somit 28 + 10 = 32 byte groß.
Schick den Header und die Daten und häng noch eine Prüfsumme an. Der Empfänger kann den Header prüfen und die Checksumme. Wenn beides passt kannst du die Daten auf plausibilität überprüfen.
Torsten schrieb: > Die Daten die gesendet werden sind letzenendes folgende. > Gewicht in g (uint32), Tara in g (uint32) und ticks (long). mehr wird > nicht gesendet. Das Gewicht ist dabei zufällig oder besser gesagt > variabel! Du verstehst es nicht. Du redest von insgesamt 38 Bytes, gibst hier aber nur 12 an. Was ist mit dem Rest? Kristallkugel? Außerdem glaube ich nicht, dass alle Gewichte zwischen 1g und ~4300 Tonnen mit der gleichen Wahrscheinlichkeit vorkommen. Was für eine Waage soll das denn sein? Und was sind die "ticks"? Gehen wir einmal davon aus, dass alle anderen Bytes 0x00 sind. Gehen wir weiter davon aus, dass diese Wage maximal mittelgroße Lastwagen bis 16 Tonnen (2^24) wiegt und das Tara auch nicht größer ist, dann kann das Bitmuster nur noch durch die "Ticks" erzeugt werden. Da musst du dir halt nur noch überlegen, ob dieser Wert dort vorkommen kann und wenn ja, wann. Gruß, DetlevT
@hdd: Diese Lösung wollte ich auch erst schreiben, aber Vorsicht die Wahrscheinlichkeit die Du ausrechnest ist nur eine obere Grenze, denn es kann passieren, dass der Header genau zweimal vorkommt, dann wurde er aber schon mitgezählt, diese Fälle müßtest Du abziehen. Ein einfaches Beispiel: In der 4 Bitfolge soll die Wahrscheinlichkeit berechnet werden, dass die Bitfolge 10 auftaucht: 1 0000 2 0001 3 0010 x 4 0011 5 0100 x 6 0101 x 7 0110 x 8 0111 9 1000 x 10 1001 x 11 1010 x (!) 12 1011 x 13 1100 x 14 1101 x 15 1110 x 16 1111 Die Folge 10 kommt 11 (!) mal vor (wegen Bitfolge 11), macht 11/16 = 0.6875 = 68.75%. Die Folge 10 kann an 3 Positionen (1,2,3, 4 geht nicht da kein Platz mehr) anfangen, d.h. jeweils 2 weitere Bits sind frei wählbar, das macht: 3*(2^2) Möglichkeiten, insgesammt gibt es 2^4 (da Bitfolge der Länge 4), das macht dann 12/16 = 75%. Also gibt dieses Vorgehen nur eine obere Schranke an... Aber vielleicht reicht das ja schon. Wenn ich mehr Zeit habe, dann versuche ich mal eine bessere Lösung anzugeben. Viele Grüße Stephan
Erratum: Der Wert ist 0x0DF0ADBA (Little Endian vorausgesetzt) entspricht über 200 Tonnen. Man kann also Lastwagen und kleinere Schiffe damit wiegen ohne dieses Bitmuster zu erzeugen.
Eine Lösung für solche Probleme ist Bit Stuffing. Ein Beispiel dafür findet sich bei HDLC. Bei HDLC fängt ein Frame immer mit der Bitfolge 01111110 an (und hört mit derselben Folge auf). Um zu verhindern, dass diese Sequenz mitten im Paket auftreten kann, wird jeweils nach 5 Eins-Bits eine 0 in den Bitstrom eingefügt, und auf Empfängerseite wird eine 0 nach 5 Eins-Bits verworfen. Angenommen es wäre ein Paket mit genau einem einzelnen der Sync-Sequenz entsprechenden Octet (0b01111110 = 0x7e) zu übertragen, dann sieht der Bitstrom auf der Leitung dann so aus:
1 | 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 |
2 | Frameanfang Daten ^ Frameende |
3 | | |
4 | hier ist das eingefügte Bit |
Beachte, dass das Zusatzbit nach jeder Folge von 5 Eins-Bits eingefügt werden muss, da der Empfänger eine folgende 0 sonst fälschlicherweise verwerfen würde. "0xff 0xff" würde also so gesendet:
1 | 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 |
2 | Frameanfang Daten ^ ^ ^ Frameende |
3 | | | | |
4 | +--- eingefügte Bits ---+ |
Im Extremfall führt das natürlich dazu, dass bis zu 20% mehr Bits übertragen werden müssen. Übertragen auf deine eigene Sync-Sequenz könntest du z.B. eine 0 einfügen, wenn eine Bitfolge gesendet wurde, die bis zur letzten 0 (dem vorletzten Bit) mit deiner Sync-Sequenz übereinstimmt. Andreas
Tobi schrieb: > Schick den Header und die Daten und häng noch eine Prüfsumme an. Der > Empfänger kann den Header prüfen und die Checksumme. Wenn beides passt > kannst du die Daten auf plausibilität überprüfen. Das ist keine Lösung des Problems! Zwar würde man damit erkennen, wenn ein Paket durch sein Bitmuster zu einem Verlust der Synchronisation der Paketgrenzen führt. Der Preis wäre aber, dass man dann etwas geschaffen hätte, was sich "Deterministic Packet Loss" nennt, das heisst Pakete mit bestimmten Daten drin gehen immer während der Übertragung verloren. Ein solches Verhalten ist für Protokolle, die die Auslieferung der Daten sicherstellen sollen (z.B. TCP) mit Abstand der "ekligste" Fall überhaupt. Mir ist kein Protokoll bekannt, das diesen Fall abdecken würde (bei TCP bleibt z.B. in soeinem Fall die Verbindung einfach "hängen", und bricht irgendwann nach einem Timeout ab). Andreas
... 28 + 10 = 32 ... Werd' das nachher noch einmal nachrechnen.
Andreas Ferber schrieb: > Ein solches Verhalten ist für Protokolle, die die Auslieferung der Daten > sicherstellen sollen (z.B. TCP) mit Abstand der "ekligste" Fall > überhaupt. Noch kleine Ergänzung, warum das so eklig ist: Deterministic Packet Loss ist eigentlich der einzige Fall von Paketverlust (ausser einer dauerhaft unterbrochenen Verbindung, aber da hilft eh überhaupt nichts mehr), der sich nicht durch Retransmit der verlorenen Pakete lösen lässt. Beim erneuten Senden enthält das Paket wieder die gleichen Daten, und geht deshalb dann auch verloren. Auch Routing-Protokolle, die bei unterbrochenen Verbindungen nach kurzer Zeit für eine Umleitung auf funktionierende Verbindungen führen (wie es z.B. im Internet gemacht wird) helfen hier nicht weiter, da die Verbindung eben nicht unterbrochen ist. Andreas
Ähnlich zum oben beschriebenen Bitstuffing funktioniert auch die DLE-Verdoppelung. Solche Daten wie z.B. Deine Magic-Number beginnen immer mit einem DLE (0x10; und dann sind es zusammen 2 Bytes). Sollte einmal eine 0x10 in Datenstrom vorkommen, was so alle 256 gesendete Bytes sein sollte (statistisch und gleichverteilt), dann wird das DLE einfach verdoppelt. Beim Empfänger entsprechend rückwärts. Dieses Verfahren ist gefühlte 100 Jahre alt aber Byte-orientiert und damit wohl etwas leichter zu handeln als Bitstuffing. Google mal ein wenig. Schönen Äbend noch!
Mal so eine ganz blöde Frage: Warum wird nicht einfach definiert in welchem Zusammenhang und/oder an welcher Stelle die Magic Number auftauchen darf? So arbeiten andere Protokolle doch auch, es wird genau definiert was in welchen Bits steht und welche Werte dort zulässig sind. Wenn ich nun also definiere dass die Bytes 6 bis 9 des Headers die Magic Number enthalten dann kann ich mein Programm entsprechend anpassen dass es nur reagieren soll, wenn an dieser Stelle das entsprechende Bitmuster auftaucht. Zumindest versteh ich grad nicht wo das Problem an einer solchen Vorgehensweise ist.
Daniel H. schrieb: > Warum wird nicht einfach definiert in welchem Zusammenhang und/oder an > welcher Stelle die Magic Number auftauchen darf? So arbeiten andere Ist natürlich blöd wenn dann aus Zufall an dieser Stelle das Bitmuster steht obwohls nicht das richtige Paket ist. Zur Problem lösung wäre wohl Bitstuffing ein guter weg. Und zur eigentlichen Frage, unter der Annahme das alle Werte gleich Wahrscheinlich sind könnte man das Wohl mit dem Urnenmodell lösen. Die Frage ist nur, was es dir bringt wenn du weisst das es schiefgehn kann. Schönen Abend noch.
Daniel H. schrieb: > Mal so eine ganz blöde Frage: > Warum wird nicht einfach definiert in welchem Zusammenhang und/oder an > welcher Stelle die Magic Number auftauchen darf? Es handelt sich hier um Funk. Wenn keine Daten gesendet werden bekommt man nur Müll, vor allem wenn der Empfänger eine AGC hat. Ich würde eine Checksumme am Ende empfehlen. Wenn das Startmuster gefunden wurde wird die entsprechende Anzahl Bytes empfangen und mit der Summe verglichen.
Der Schelm schrieb: > Ähnlich zum oben beschriebenen Bitstuffing funktioniert auch die > DLE-Verdoppelung. Solche Daten wie z.B. Deine Magic-Number beginnen > immer mit einem DLE (0x10; und dann sind es zusammen 2 Bytes). Sollte > einmal eine 0x10 in Datenstrom vorkommen, was so alle 256 gesendete > Bytes sein sollte (statistisch und gleichverteilt), dann wird das DLE > einfach verdoppelt. Das reicht nicht. Auf der (fast) untersten Ebene (dem nackten Bitstrom) weiss der Empfänger nicht einmal, an welchen Stellen die Grenzen zwischen den Bytes liegen. Deshalb darf das Bitmuster der Frame-Syncsequenz nirgendwo sonst im Datenstrom auftauchen, auch nicht als Kombination von Bits zweier aufeinanderfolgender Bytes, und deshalb reicht ein Escaping auf Byte-Ebene nicht aus. (nicht "Gast") schrieb: > Ich würde eine Checksumme am Ende empfehlen. Wenn das Startmuster > gefunden wurde wird die entsprechende Anzahl Bytes empfangen und mit der > Summe verglichen. Das würde einen Resync dauerhaft verhindern (oder zumindest unnötig verzögern), wenn zufällig mal ein Bit verloren geht und kurz danach die Syncsequenz in den Nutzdaten auftaucht. Solche "Lösungen" sind Käse, da sie in bestimmten Situationen (die sich vorhersehen lassen!) ohne sichtbaren Grund einfach mal versagen. Auch wenn diese Situationen nur selten auftreten mögen, irgendwann wird der Tag kommen. Um auf einem nackten Bitstrom Framing sauber hinzubekommen darf die Syncsequenz einfach nicht in den Nutzdaten auftauchen. Wie man das erreichen kann habe ich oben ja schon erklärt. Wem das zu aufwendig erscheint: wenn man sowieso auf Bitebene "rumfummelt" (um die Syncsequenz zu erkennen), dann ist die Implementierung von Bit Stuffing trivial. Andreas
Das Magic wird am Anfang deiner Pakete gesendet damit diese beim Empfänger erkennt werden können. Dh. wird dieses Magic nicht erkannt so wird das Paket nicht ausgewertet. Ergo: BA:AD:FO:OD = ein 32 Bit Muster aus 2^32 möglichen Bitmustern = 1/2^32 Wahrscheinlichkeit. Was danach kommt und wie lang das Paket ist spielt keine Rolle. Entscheidend ist aber nicht diese Wahrscheinlichkeit sondern die Bitfehler-Wahrscheinlichkeiten die dazu führen könnten das aus einem nicht-Magic ein Magic-Code wird. Und das hängt von der Empfängercharakteristik/Hardware, Übertragungs/Modulationsart und den Störungen in der Kommunikation ab. Gruß Hagen
@Andreas: >> Ich würde eine Checksumme am Ende empfehlen. Wenn das Startmuster >> gefunden wurde wird die entsprechende Anzahl Bytes empfangen und mit der >> Summe verglichen. >Das würde einen Resync dauerhaft verhindern (oder zumindest unnötig >verzögern), wenn zufällig mal ein Bit verloren geht und kurz danach die >Syncsequenz in den Nutzdaten auftaucht. >Solche "Lösungen" sind Käse... Nö, nicht Käse. Die CRC gibt nur die Erkenntnis das die vorher empfangenen Daten mit der Fehlerwahrscheinlichkeit der CRC eben korrekte Daten sind. Die CRC hat mit dem Resync, der Synchronisation oder dem Magiccode garnichts zu tun. Man kann auch Bitweise alle Daten fließend auswerten und darüber nach jedem Bit die CRC berechnen. Das würde dann genauso schnell einen Resync erzwingen wie du in deinem Posting beschrieben hast. Ergo: die CRC hat mit dem Resync und dessen Fehler/Problemen nichts zu tun. Gruß Hagen
Die Wahrscheinlichkeit ein 80bit muster per Zufall zu treffen ist doch 1/(2^80), etwa 1.2e24, wenn wir nun noch 10^3 bit daran vorbeiziehen, erniedrigt sich die Chance auf 1.2e21. Nein ?
Hagen Re schrieb: > Nö, nicht Käse. Doch. Was ist wenn ein Bit im Datenstrom fehlt, also nicht den falschen Wert hat sondern wirklich weg ist? Was ist wenn ein Bit in der Längenangabe von 0 nach 1 wechselt? Das sind beides Fälle, wo dann durch einen Einzelbitfehler zwei oder mehr vollständige Datenpakete verloren gehen, da du dann in den nächsten Frameanfang hineinliest. Deshalb ist das so wie von "(nicht "Gast")" beschrieben in vielen Fällen Käse. BTW, es gibt "CRC based framing", das wird unter anderem von ATM verwendet, ist aber nur bei festen Framelängen (wie z.B. ATM-Zellen) gut geeignet, bei variabler Länge wird der (Speicher-)Aufwand sehr hoch, so dass man das de fakto nur nimmt, wenn der Overhead beim Bit Stuffing für die jeweilige Anwendung zu gross oder zu variabel (da datenabhängig) würde. http://en.wikipedia.org/wiki/CRC-based_framing Andreas
Andreas Ferber schrieb: > Doch. Was ist wenn ein Bit im Datenstrom fehlt, also nicht den > falschen Wert hat sondern wirklich weg ist? Wie kann denn bitte ein Bit verschwinden? Wenn der Sender glaubt er müsse mal eben ein bit auslassen, dann geht doch beim Sender was schief. Wenn x Bit gesendet werden sollen dann dauert das auch immer x Bitzeiten. Da kann kein bit fehlen, außer der Sender und Empfänger bewegen sich auseinander. Außerdem implementiert man eine CRC auch nicht in der Bit Ebene. Mir ist schon klar das eine CRC nicht beim Synchronisieren hilft. Aber wenn mal ein Frame kaputt ist sollte man es lieber wegschmeißen.
Hallo Leute, die Frage von Torsten war, wie groß die Wahrscheinlichkeit ist, dass diese "Magic Number" im Datenstrom auftaucht. Ihr diskutiert hier Verbesserungen auf Senderseite ohne überhaupt zu wissen, ob man daran überhaupt etwas ändern kann. Vielleicht ist das ein fertiges Gerät zu dem ein neuer Empfänger gebaut werden soll, schon einmal daran gedacht? Die naheliegende Frage kam dabei trotzdem nicht zur Sprache: Wurde als "Magic Number" überhaupt ein Wert gewählt, der im normalen Datenstrom vorkommen kann? Und wenn ja: warum? Woher kommt diese spezielle Kombination überhaupt? Möglicherweise wurde diese Kombination ja gerade deshalb gewählt, weil sie in dem restlichen Strom eben nicht vorkommen kann. Nehmen wir an, das ist eine Waage, die bis maximal 100 kg wiegt. (Leider macht Torsten dazu keine Angaben, so dass wir in unsere Kristallkugel gucken müssen) Das wären eine Folge von maximal 17 Bits, die grundsätzlich von 0 verschieden sein können. Es gibt 15 weitere Bits in Folge, die 0 sind. Damit kann man die "Magic Number" nicht verwechseln. Es könnte natürlich auch sein, dass die Daten Byte-weise übertragen werden, little Endian mit MSB first. Leider macht Torsten auch dazu keine Angaben, so dass wir auch hier auf unsere Kristallkugeln angewiesen sind. Dann würde sich ein anderes Muster ergeben: 16 beliebige Bits, 7 mal eine 0, dann eine 1 oder 0, gefolgt von 8-mal einer 0. Auch hier besteht keine Verwechslungsgefahr. Für "Tara" gilt das gleiche, selten ist die Verpackung schwerer als das Gut. Bleiben die "Ticks", von denen Torsten nicht angibt, was das ist (Kristallkugel!), die restlichen Daten, von denen wir gar nichts wissen (Kristallkugel!) und einem Header, zu dem Torsten keinerlei Angaben macht (Kristallkugel!) Ich verstehe nicht, wie ihr hier ernsthaft versuchen könnt, irgendwelche quantitativen Aussagen zu machen. Gruß, DetlevT
Hier mal ein Artikel von Wiki dazu, der das Beschreibt (Abschnitt: "Magische Zahlen in der Programmierung"): http://de.wikipedia.org/wiki/Magische_Zahl_(Informatik)
Sry, ich beschreibe es nochmal genauer: Gewicht = zwischen 0 und 250kg Tara = max 400 kg Ticks = ist sowas wie die Uhrzeit, allerdings als fortlaufende Zahl (long) Der Header ist folgendermaßen aufgebaut: Magic Number = 4 Byte HeaderLength = 2 Byte DataLength = 2 Byte Datenelemente= 1 Byte Revision = 1 Byte (ob aktuelle Protokollversion genutzt wird) Ich hoffe, damit ist nun alles klar!?
(nicht "Gast") schrieb: > Wie kann denn bitte ein Bit verschwinden? Wenn der Sender glaubt er > müsse mal eben ein bit auslassen, dann geht doch beim Sender was schief. > Wenn x Bit gesendet werden sollen dann dauert das auch immer x > Bitzeiten. Da kann kein bit fehlen, außer der Sender und Empfänger > bewegen sich auseinander. Kommt drauf an, wie übertragen wird. Wenn Du mit festen Bitzeiten arbeitest, können eigentlich keine Bits verschwinden, sondern höchsten falsch ausgewertet werden. Das passiert durch Störungen oder Timingproblemen. Wenn es sich aber um ein asyncrones Protokoll handelt, können Bits durch Störungen verschwinden. Über die Übertragung hat sich hier noch niemand ausgelassen. Wir wissen nur, dass es Funk ist - also leicht zu stören. Das Problem sind hier wohl eher die zufälligen Werte aufgrund des erwähnten Grundrauschens. Wie wahrscheinlich ist es, dass in diesem Rauschen genau die erforderlichen Magic-Bytes und ggf eine Prüfsumme stimmen? Ich würde schätzen, recht gering. Ist nur noch zu klären, ob das tollerierbar ist. Hier werden in diesem Fall falsche Gewichte angezeigt/verrechnet. Das kann man wiederum über einen Plausibilitätscheck mit mehreren Messungen ausfiltern.
Torsten schrieb: > Ich hoffe, damit ist nun alles klar!? Nö. Lese dir doch einmal die Informationen durch, die du hier preisgegeben hast und überlege dir, ob du das zugehörige Bitmuster damit konstruieren könntest. Weißt du dann zum Beispiel, ob Daten aus mehreren Bytes in Little oder Big Endian übertragen werden? Weißt du, ob von den Bytes das niederwertigste Bit (LSB) oder das höchstwertige (MSB) zuerst übertragen wird? Kennst du den Wertebereich der "Ticks" - und an welcher Stelle der Daten diese zu finden sind? Ich klinke mich hier aus. Dieses Aus-Der-Nase-Ziehen nervt mich.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.