Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Hamming-Distanz und Fehlererkennung
Heyho,
ein Gray-Code hat ja das besondere Feature, dass er einschritt ist, sprich eine minimale und maximale Hammingdistanz von 1 hat. Ist die Aussage korrekt?
Bei einem Huffman- und einem Shannon-Fano-Code haben die Codewörter eine unterschiedliche Länge. Von daher kann man für diese beiden Codewörter auch keine Fehlererkennung und -korrektur mit ganz normalen Hammingdistanzen durchführen, da man kann ja keine HD-Min berechnen oder? Es gibt ja die Formel, dass man bei einer HDmin von d genau d-1 Fehler erkennen und (d-1)/2 Fehler korrigieren kann. Darum benötigt man hier die Fehlererkennung/ -korrektur mit Paritätsbits oder?
Thank you!
Konstruiere dir als Gegenbeispiel mal einen Graycode mit 3 Bits (mit dem Verfahren aus der VL):
000
001
011
010
110
111
101
100
Einschrittig heißt, dass die Hammingdistanz aufeinanderfolgender Codewörter 1 ist. (Das heißt, dass du bei Graycodes eine Reihenfolge hast, die du z. B. beim Huffmann-Code nicht hast.)
Die minimale Hammingdistanz ist auch 1, mir fällt gerade auch kein Code mit einer Hammingdistanz von 0 ein. Da hättest du zwei identische Codewörter, die du nicht auseinanderhalten könntest. Weil ein Graycode mit n Bits immer alle 2^n Bitmuster benutzt (bei 3 Bits: 000 bis 111), ist die maximale Hammingdistanz immer n (000 → 111 als Extremfall).
Ob es eine alternative Definition für HD zweier unterschiedlich langer Codewörter gibt, weiß ich nicht.
Huffmann- und Shannon-Fano-Codes haben jedoch ein anderes, der Fehlerkorrektur widersprüchliches Ziel: sie wollen die Daten komprimieren, die Redundanz vermindern. Bei fehlerkorrigierenden Codes setzt man jedoch auf Redundanz, um so Fehlerkorrektur zu ermöglichen.
Natürlich kannst du eine weitere Schale um die Kompressionscodes bauen und Fehlerkorrektur ermöglichen (ähnlich wie die Verschlüsselung TLS um HTTP gebaut ist).
Zur Fehlerkorrektur gibt es viele unterschiedliche Verfahren, darunter auch Partitätsbits
Vielen Dank