www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Berechnung der Hamming Distanz


Autor: FireFox (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Jürgen K. (microman)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Christian Ege (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Jürgen K. (microman)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Thomas Walter (firefox)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Thomas Walter (firefox)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, das ist schon mal nicht schlecht, aber

... deutlich besser ... kann ich nicht in die Formel einsetzen :)

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Jürgen K. (microman)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Thomas Walter (firefox)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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....

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.

Autor: Thomas Walter (firefox)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Christian Ege (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Christian Ege (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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ß

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Thomas Walter (firefox)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Michael Appelt (micha54)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.