Code Fehlererkennung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi!
In unserem Skript steht folgender einleuchtender Satz:
"Hat ein Code den Hamming-Abstand d, so können alle Störungen,
die höchstens d-1 Bits betreffen, sicher erkannt werden."
Jetzt steht aber in diesem Skript und auch bei Wikipedia auch das über einen Hamming-Code mit der Hamming-Distanz 3:
"Durch diesen Unterschied von jeweils drei Bitstellen kann der Decoder einen Bitfehler in einem Datenblock immer erkennen und korrigieren, bei zwei oder mehr Bitfehlern wird der Datenblock allerdings falsch decodiert."
Warum können denn nun nicht 2-Bitfehler erkannt werden?
Auch ganz konkret betrachtet müsste das doch gehen: Die Nummer jedes Datenbits hat mind. 2 Einser, wird also von mind. 2 Prüfbits kontrolliert. Wenn jetzt in einem solchen Datenwort ein Bitfehler auftaucht (1 Änderung) müssen noch die beiden Prüfbits geändert werden, damit der Fehler nicht erkannt wird. D.h. 2 Bitfehler werden problemlos erkannt ?!
Wo ist mein Denkfehler?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:31 So 10.01.2010 | | Autor: | Infinit |
Hallo Bit2_Gosu,
ich glaube nicht, dass Du einen Denkfehler machst, aber ich muss zugeben, dass der Wikipedia-Artikel nicht sehr sauber zwischen der Fehlererkennung und der Korrektur unterscheidet. Bei einer Hamming-Distanz von 3 lassen sich 2 Fehler erkennen bzw. lässt sich ein Fehler korrigieren. Wenn man weiss, dass zwei Bitfehler auftreten, so kann der Hamming-Code keine Korrektur mehr auf Bitebene durchführen. Ob man diesen Datenblock dann überhaupt zur Decodierung weiterreicht oder ob man gleich eine Warnung ausgibt, das hängt von der jeweiligen Applikation ab, deren Daten geschützt werden sollen. Es gibt auch Fehlerschutzverfahren, die auf der Applikationsebene arbeiten und falls diese mächtig genug sind, aufgetretene Fehler zu beheben, so macht es sicher Sinn, die Daten, auch wenn man weiss, dass in einem Datenblock eine Korrektur auf Bitebene nicht mehr möglich war, weiterzureichen in der Hoffnung, dass auf der Applikationsebene noch was zu retten ist. Solche Verfahren nennt man im Englischen AL-FEC (Application Layer - Forward Error Correction).
Viele Grüße,
Infinit
|
|
|
| |
|
Phew, bin ich ja froh, dass ich nicht völlig den Verstand verloren habe ;)
D.h. also "Erweiterung von Hamming-Codes auf Hamming-Distanz d=4
durch weiteres Paritätsbit P über alle Stellen.
⇒ Korrektur aller 1-Bit-Fehler und Erkennung aller 2-Bit-Fehler." ist zwar richtig, aber man könnte sogar sagen "Erkennung aller 3-Bit-Fehler"?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:56 So 10.01.2010 | | Autor: | felixf |
Hallo!
> Phew, bin ich ja froh, dass ich nicht völlig den Verstand
> verloren habe ;)
>
> D.h. also "Erweiterung von Hamming-Codes auf
> Hamming-Distanz d=4
> durch weiteres Paritätsbit P über alle Stellen.
> ⇒ Korrektur aller 1-Bit-Fehler und Erkennung aller
> 2-Bit-Fehler." ist zwar richtig, aber man könnte sogar
> sagen "Erkennung aller 3-Bit-Fehler"?
Genau, der Code erkennt auch 3-Bit-Fehler.
Wenn man korrigiert, wird ein 3-Bit-Feher jedoch als 1-Bit-Fehler aufgefasst und zu einem falschen Codewort dekodiert.
LG Felix
|
|
|
|
