Forum: Digitale Signalverarbeitung / DSP / Machine Learning Hammingdistanz


von Zizi A. (dimer)


Lesenswert?

Hallo Leute,

Hammingdistanz (D) ist Anzahl die Stellen, die bei min. 2 Digitalwerten 
unterschiedlich sind.
Zum Beispiel:
0010  &  1011.
D = 2

Aber bei folgender Frage bin ich machtlos ?
wie Kann ich die Größe eines Hammingdistanz eines CRC-Kodes bestimmen.

hat jemand irgendwelche Tipps für mich.

Herzlichen Dank im Voraus.

von Raven (Gast)


Lesenswert?

Hallo,

die Hammingdistanz heißt bei Codes auch "Mindestdistanz". Sie ergibt 
sich über das primitive Polynom, mit der deine Prüfsumme (das CRC, 
Cyclic Redundant Code) bzw. die Codewörter erstellt wurde. Die Prüfsumme 
ist nichts anderes als der Rest der Polynomdivision. Du musst also dein 
Prüfpolynom kennen, mit dem die wichtigsten Parameter deines Codes 
bestimmt werden: n, k und d. k ist die Dimension deines Codes, also 
wieviele Informationswörter (eine Gruppierung von mehreren Bits) durch 
dein Polynom gejagt werden. n ist dabei die Länge deines Codes. Sie gibt 
an, wieviele Codewörter nach dem Durchlaufen deiner k Informationswörter 
durch das Polynom ausgegeben werden. Und d ist die Mindestdistanz. d 
ergibt sich zu d=n-k+1.
Das Problem ist, es gibt nicht nur einen Code der sowas macht, sondern 
viele verschiedene. Das heißt, deine Mindestdistanz vom CRC ist von 
deinem Polynom abhängig, das benutzt wird. Also einfach mal schauen, 
welcher benutzt wird.

Generell ergibt sich die Distanz d zu 2e+1. e ist hierbei die maximale 
Anzahl der Fehler die KORRIGIERT werden können. Ich schreibe korrigiert 
groß, weil man zwischen Fehlerkorrektur und Fehlererkennung 
unterscheiden muss! Bei binären Codes reicht aber die Fehlererkennung 
aus, da wenn man die Stelle des Fehlers kennt, auch direkt weiß, dass es 
nicht etwa eine 0 sondern eine 1 sein muss. Es gibt schließlich nur zwei 
Möglichkeiten.

Naja, schau mal auf Wikipedia, da findest du einiges dazu. der Artikel 
zu CRC ist ganz gut.

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
Noch kein Account? Hier anmelden.