Ich habe mir am Wochenende ein paar Gedanken zur Bitfehlerwahrscheinlichkeit in meinem Fernsteuerungsprojekt gemacht. Ich übertrage über eine Funkstrecke einen 32 Byte großen RS232 Strom. Im Telegramm habe ich eine Checksumme nach dem BCC Verfahren (Byteweise XOR verknüpft) eingebaut. Zur Berechnung der Bitfehlerwahrscheinlichkeit benötige ich aber die minimale und maximale Hamming Distanz. Leider habe ich im Netz bisher keine Hinweise auf ein Vorgehen zur Berechnung der Hamming Distanz gefunden. Kann mir da jemand weiterhelfen? Gegebenfalls ein paar Infos / Tips geben, wie man die Hamming Distanz in diesem Fall berechnen könnte?
Hallo, Thomas! Die Hamming-Distanz ist wie folgt definiert: x und y sind Vectoren, i ist der Index h(x,y) = Aufsummierung mit Index i bis n von |xi - yi| Im Binärensystem zählt man einfach die Anzahl der unterschiedlichen Bits des Vectors x und y. Wie man dies auf Dein spezielles Problem anwenden kann, kann ich Dir nicht genau sagen. Hoffe ich konnte Dir trotzdem weiterhelfen. Stephan
Wo hast Du gesucht? http://de.wikipedia.org/wiki/Hamming-Abstand bzw. http://de.wikipedia.org/wiki/Hamming-Code Die Berechnung ist relativ einfach, die Generierung eines geeigneten Codes nicht mehr ;-) cu chege --- http://www.cybertux.org
Brauchte nicht suchen. Hab mich vor Kurzem noch mit Topologie beschäftigt. Zum dem brauchte ich dies noch als Abstandsbegriff bei Neuronalen Netzen. Meiner Meinung nach, müsste er beim richtigen Einsatz der XOR-Funktion den maximalen/minimalen Hammingabstand berechnen können. Wie siehst Du das chege? Stephan
bei wikipedia war ich bereits, nur kann ich damit nichts anfangen. mir ist schon klar, dass man durch den Vegleich zweier Bytes die Hamming Distanz ermitteln kann. Mich interessiert aber im speziellen wie sich die Verwendung der Checksumme auf die Hamming Distanz auswirkt. Der einzige Sinn einer Checksumme besteht ja darin, die Restfehlerwarscheinlichkeit zu reduzieren. Und das muss man ja im Formelwerk irgendwie berücksichtigen. Die nächste Frage wäre dann natürlich sofort was bei der Verwendung einer CRC besser / schlechter wird als bei der Verwendung der BCC.
Es werden nicht die Bytes verglichen, sondern die gesamten Codes. In diesem Fall also die 264/297 Bits des RS232 Stroms (32 Bytes plus BCC, je 8-9 Bits). Bei simplem Byte-XOR ohne Byte-Parity ist darin h=2, d.h. 2 Bitfehler sind u.U. bereits nicht erkennbar. Deutlich besser schaut's aus, wenn in der seriellen Übertragung noch eine Byte-Parity drin ist.
Ja, das ist schon mal nicht schlecht, aber ... deutlich besser ... kann ich nicht in die Formel einsetzen :)
Apropos: Grad bei solchem Problem ist nicht nur die Erkennung von unabhängigen Bitfehlern interessant. Insbesondere ist die Erkennung von Errors-Bursts interessant - immerhin treten Fehler durch Störsignale gehäuft in benachbarten Bits auf. Das ist übrigens bei magnetischen Datenträgern (Platte, Band) auch nicht anders. Da freilich kommst Du mit dieser simplen Hamming-Metrik nicht aus. Und da ist dieser vergleichsweise miese Byte-XOR-BCC plötzlich auch ohne Byte-Parity ganz passabel, erkennt er doch immerhin zuverlässig einzelne Bursts bis n=8 (Framing-Probleme der asynchronen Übertragung hier mal vernachlässigt).
Hallo, Thomas! Dein Ziel ist also über einen unsicheren oder störanfälligen Kanal ein Nachricht zu versenden, die sicher und unverändert ankommt? Eine Paritätsprufung hat ja immer den Nachteil, daß uU 2 (oder mehrere) Bits so ungünstig gekippt sind, das eine Paritätsprüfung diese Fehler nicht erkennt. Hast Du Dich schonmal mit Kryptoverfahren beschäftigt? Das Buch "Geheimsprachen" von Beutelsbacher würde ich empfehlen, da es klein, kostengünstig, übersichtlich und recht einfach verständlich gehalten ist. So weit ich es in Erinnerung habe, beschreibt es ein Kryptoverfahren, daß zur Datenintegrität dient und Dir sicherlich weiterhelfen kann(ich meine es wurde angelehnt an den RSA-Algorithmus). Treten bei der Datenübermittlung dann Fehler auf, müsste die komplette Nachricht erneut gesendet werden, was natürlich sehr aufwändig ist. Viel Erfolg weiterhin! Stephan
Angehängte Dateien:
-
Bild1.png
77 KB
Hallo Stephan, mir geht es eigentlich jetzt weniger um Übertragungscodes. Der Strom via RS232 funktioniert tadellos. Ich will einfach (in Zahlen) wissen, wie gut oder schlecht meine Funkverbindung ist und wie sich die Verwendung einer Checksumme auf das Gesamtergebnis auswirkt. Ein Maß für die Güte einer (Funk)Verbindung ist die Restfehlerwahrscheinlichkeit. (siehe Anhang) R hängt also von der Bitfehlerwahrscheinlichkeit p und der Anzahl der Bits ab. A(n,i) ist ein Binomialkoeffizient, also A von n über i, ist also eine Angabe wenn i Bits von n verfälscht sind. Warum dann p hoch i * (1-p) hoch n - i drinsteht verstehe ich noch nicht ganz. Vorne in der Summe steht nun die Hammingdistanz. Und genau diese Variable ist mein großes Fragezeichen. Die Bitfehlerwahrscheinlichkeit kann für Funkstrecken mit p > 10^-3 angenommen werden.
Du musst erst mal wissen, welche Codes in Deinem Datenstrom vorkommen können. Wenn in Deinem Datenstrom wirklich 256**32 Codes vorkommen, dann kann man die minimalen und maximalen Hamming-Distanzen offensichtlich nicht mit Brute-Force berechen... Naja, da muss man eben etwas analysieren. In etwa so: Beim Byteweise XOR hast Du insgesammt 8 mal 32 Datenbits plus Prüfbit. Also reicht es ersteinmal, nur ein Prüfbit und die dazugehörigen Datenbits zu betrachten. Naja, und das ist ja nun trivial. Denn das per XOR erzeugt Prüfbit ändert sich immer dann, wenn Du ein Datenbit änderts. Also hast Du bei diesem Code (32 Datenbits plus Prüfbit) immer eine minimale Hammingdistanz von 2. So, und die maximale Hammingdistanz ist auch trivial, nämlich 32. Denn wenn sich alle 32 Datenbits ändern, ändert sich das Prüfbit nicht. Wenn sich nur 31 Datenbits ändert, ändert sich das Prüfbit auch, und die Distanz ist wieder 32. Bei weniger Änderungen in den Datenbits ist die Hammingdistanz immer kleiner als 32. Zwischenstand: Bei 32 Datenbits plus einem Prüfbit per XOR erzeugt, ist die minimale Hammingdistanz 2 und die maximale Hammingdistanz 32. Nun hast Du aber diese Datenbits insgesammt 8 mal (32 Bytes, und nicht nur 32 Bits). Demzufolge ist die minimale Hammingdistanz Deines Codes immer noch 2 dafür die maximale aber 8 mal größer, nämlich 256. Ergo: Minimale Hammingdistanz für Deinen Code 2, maximale Distanz 256. War doch nicht schwer, oder?
Wozu kann man maximale Hamming-Distanz brauchen? Ausserdem habe ich seinen Kommentar oben so verstanden, dass er neben der Block-Parität auch noch jeweils eine Byte-Parität mitschleppt. Er insgesamt also mit Kreuzparität / 2-dimensionaler Parität arbeitet. Dazu siehe http://www.microsoft.com/germany/technet/datenbank/articles/600668.mspx. Blöd dabei: Um für dieses Verfahren die effektive Wahrscheinlichkeit eines unerkannten Übertragungsfehler zu berechnen, muss man etliche Fälle unterscheiden. Weil es nämlich massiv darauf ankommt, wo genau die Fehler auftreten. Mit der minimalen Hamming-Distanz allein kriegt man nur eine untere Schranke dafür, aber keine realistisches Ergebnis.
Ich bin mir jetzt nicht ganz sicher ob ihr mich richtig verstanden habt.
Deshalb hier nochmal ein kleines Beispiel:
2 Datenbytes sollen übertragen werden. Dann sieht mein Telegramm
folgendermaßen aus:
| : | DB1 | DB1 | DB2 | DB2 | BCC | BCC | ; |
| Start | high | low | high | low | high | low | ´End |
Nehmen wir nun mal als Beispiel:
DatenByte1 = 41h = 01000001b
Datenbyte2 = ADh = 10101101b
Dann berechne ich meine Checksumme (BCC) so:
01000001
XOR 10101101
-------------
11101100b = ECh
Zur Übertragung sende ich nun jeden einzelnen Hex Character als ASCII
Zeichen über die Serielle Schnittstelle, deshalb oben im Telegramm
immer high und low.
Mein Telegramm würde also so aussehen:
:41ADEC;
Genauso funktioniert das dann mit meinen 32 Byte, also Startbyte,
Stoppbyte, 2 Byte Checksumme und 14 Datenbytes.
Die Parität auf der RS232 Schnittstelle hab ich nicht aktiviert.
Deshalb ist die minnimale Hammingdistanz zunächst einmal nur 1 meiner
Meinung nach.
Ich mag widerholen was schon diskutiert worden ist. Aber die Hammingdistanz ist der Abstand zweier Codewörter. Die minimale hammingdistanz ist der kleinste Abstand. Wenn ich es richtig verstanden habe, sieht bei Dir ein Codewort so aus: 41ADEC ein anderes könnte unter Umständen so etwas sein 44ABAC (reine willkür ;-)). Jetzt musst Du Dir überlegen Welche Codewörter in Deinem Code Auftreten können und wie der Minimale Abstand zu bestimmen ist. Ich habe im Moment keine Idee wie das zu lösen ist ;-) Was aber nichts heißen mag. Besser wäre natürlich ein Hamming-Code aber da kannst Du nicht mit einem einfachen XOR arbeiten. Gruß Christian.
Jetzt ist's etwas klarer. 1-Bit Fehler werden alle erkannt, bei mehr Fehlern wird's jedoch komplizierter. Auch hier kommst Du für die Berechnung der Wahrscheinlichkeit von unerkannten Fehlern mit der Hamming-Distanz nicht wirklich weiter. Vereinfachend ohne die bin/hex-Umcodierung betrachtet: 2 Bitfehler an der richtigen Position sind zuviel (gleiches Bit in 2 Bytes), 8 Bitfehler günstig verteilt werden erkannt. Eine einfache Betrachtung auf Basis der minimalen Hamming-Distanz von 2 liefert also eine viel zu hohe Wahrscheinlichkeit. Die Umcodierung verkompliziert die Betrachtungen etwas (ebenso das asychrone Framing, aber das kann man dabei wohl vernachlässigen). Für die gewünschte Berechnung musst Du also die jeweiligen Fälle (Muster der Bitfehler) getrennt betrachten. Auch interessant, wie schon geschrieben: Kann man wirklich von einer rein zufälligen Verteilung der Bitfehler ausgehen, oder ist nicht vielmehr die Wahrscheinlichkeit direkt benachbarter Bitfehler weit grösser?
>Auch interessant, wie schon geschrieben: Kann man wirklich von einer >rein zufälligen Verteilung der Bitfehler ausgehen, oder ist nicht >vielmehr die Wahrscheinlichkeit direkt benachbarter Bitfehler weit >grösser Glaube ich eher nicht das trifft wahrscheinlich für Speicher zu. Wenn man vonn einem Fehler ausgeht der durch Strahlung verursacht wird, die benachbarten Bits auch kippen. Hier haben wir es aber mit einer Übertragungsstrecke zu tun. Ich würde von einer Gleichverteilung ausgehen. Gruß
Bei externe Störungen kann man m.E. getrost davon ausgehen, das auch eine sehr kurze Störung oft 2 benachbarte Bits stört. Bei RAM-Speicher ist es durchaus komplizierter. 2 Bits, die RAM-Chips direkt benachbart sind, können aus Sicht des Memory-Controllers weit auseinander liegen, je nachdem, wie der RAM-Chip die Datenbits auf die Banks und Rows verteilt. Der hat da ziemliche Freiheit und so sieht das dann von Hersteller zu Hersteller evtl. auch anders aus. Auch im externen Anschluss muss z.B. ein als A0 bezeichneter Pin nicht zwingend dem entsprechend, was intern das unterste Adressbit des Column-Decoders ist. Ergo: Bei Speicher wird schon deshalb von Gleichverteilung ausgegangen, weil man für genauere Betrachtung unweigerlich die exakte Topologie und damit den Hersteller der Speicherschips mit im Boot hat. Anders bei magnetischem Speicher. Da wird regelmässig davon ausgegangen, dass Fehler recht oft in Bursts auftreten. Ohnehin: Burst-fähiger ECC ist bei massiv auftretenden Daten weit einfacher zu haben. Also bei serieller Übertragung (DSL => Fastpath) oder Platte/Bandlaufwerk. Bei RAM werden die Worte meist unabhängig gespeichert, Burst-fähige ECCs scheiden dann faktisch aus - Ausnahme: Chipkill-Memory.
@Thomas: Naja, Deine Codierung macht die Untersuchung nur wenig komplizierter: Du brauchst auch hier erst mal nur zwei Nibbles (0x0 bis 0xF) plus das dazugehörendes Check-Nibble betrachten. Also sind das insgesammt 256 Codes der Form Nibble_1, Nibble_2 und Check_Nibble, wie Z.B.: 0x011 0x48C ... Also insgesammt 256 Codewörter. Bei der Übertragung werden diese Codewörter ja nicht als 12 Bits, sondern als 3 Bytes also 24 Bits übertragen. Um die Minimale Hamming-Distanz Deiner 256 verschieden 3-Byte-Codewörter zu finden machst Du in diesem Fall am einfachsten eine quadratische Matrix mit 256 * 256 Codewörter (eigentlich brauchst Du nur eine Dreiecks Matrix...). Naja, dann für jede Eintrag in der Matrix die Hammingdistanz eintragen und dann die minimale und die maximale Distanz in der Matrix suchen. Natürlich daran denken, die Einträge auf der Diagonalen mit den gleichen Codewörter zu ignorieren. Naja, und bei Deiner eigentlichen Anwendung werden von diesen Codewörter ja effektiv zwei Stück übertragen, also ist die maximale Hammingdistanz zweimal so groß, die kleinste bleibt gleich, wie gehabt. Start- und Stop-Zeichen kann man bei dieser Betrachtung ignorieren, da immer gleich.
Ok, ich hab mich inzwischen weiter im Netz informiert. Ich vermute mittlerweile, dass meine Überlegung vom Grundsatz her falsch ist. Wenn ich eine bestimmte Restfehlerwahrscheinlichkeit garantieren muss, dann muss ich zuerst die Hamming Distanz bestimmen und darauf aufbauend dann den Code entwickeln. Nach den Formeln zur Bestimmung des Hamming Codes kann ich dann alle möglichen Codewörter berechnen und muss diese zur Datenübertragung einsetzen. Um SIL3 gerecht zu übertragen (Restfehlerwahrscheinlichkeit < 10^-8) darf die minimale Hamming Distanz nicht kleiner als 5 sein. Vermutlich wäre es dann aber günstiger nicht die ganzen 32Byte zu sichern, sondern die Bytes einzeln zu übertragen und die Bits zur Fehlerkorrektur an jedes Byte anzuhängen. Bei einer ASCII Übertragung (7 Bit) würden wohl noch 5Bit pro Zeichen für die Fehlerkorrektur dazukommen, so dass ich insgesamt 12Bit pro Zeichen übertragen muss.
Wenn es nur um eine Fehlererkennung geht, nicht um Fehlerkorrektur: Hinreichend lange CRC hinten dran, statt BCC, und fertig. Die Bytes einzeln abzusichern ist übrigens mitnichten günstiger. Im Gegenteil.
Hallo Firefox, wenn ich Dich richtig verstanden habe geht es Dir um folgendes: Die Hamming-Distanz Deiner 32 Byte ist 1, weil sich alle möglichen 32-bit-Werte um mindestens 1 Bit unterscheiden. Und weiterhin ist die maximale Hamming-Distanz 32 * 8 = 256, weil sich die Werte maximal in allen Bits unterscheiden. Bei jeder Bit-Änderung der 32 Datenbates ändert sich auch der BCC. Damit erhöht sich die Hamming-Distanz um 1 auf 2, das müsste für jedes Parity gelten. Mit Hamming-Distanz 2 lassen sich alle 1-bit-Fehler erkennen und 0 Fehler korrigieren. Es gibt aber leider reichlich Mehrfachfehler, die nicht erkannt werden. Hier ist ein CRC besser. Gruß, Michael
Thread beobachten
Seitenaufteilung abschaltenBitte 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.