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
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!
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:
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
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
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.
