Zur Fehlererkennung sind zwar Verfahren wie CRC oder Paritätsbit immer noch weit verbreitet, aber weil die nichts korrigieren und bestenfalls nur das System mit einer passenden Fehlermeldung anhalten können sind die fast überall durch ECC (error correcting code) abgelöst worden. Auf Festplatten, CDs und in den meisten Server-RAM-Riegeln wird deshalb heutzutage fast nur ECC verwendet. Mit einfachem ECC kann nämlich jeder 1-Bit-Fehler richtig korrigiert werden und jeder 2-Bit-Fehler korrekt gemeldet werden. Gegenüber CRC erspart man sich so Datenverlust und folgenden Systemstillstand (ist besser als mit Datenmüll Unsinn auszurechnen) oder das mehrmalige Schicken von Datenpaketen. Dabei steigt die Anzahl der Korrektur-Bits nur logarithmisch mit der Nutzbit-Anzahl. Ich habe deshalb mal die folgenden 2 Beispiele in C gecodet. Two simple short Codes for ECC: =============================== Code [8, 4, 4, 2]: ------------------ 00000000 = 0 00001111 = 15 00110011 = 51 00111100 = 60 01010101 = 85 01011010 = 90 01100110 = 102 01101001 = 105 10010110 = 150 10011001 = 153 10100101 = 165 10101010 = 170 11000011 = 195 11001100 = 204 11110000 = 240 11111111 = 255 * Complete correction of all 1-bit errors. * Correct detection of all 1- and 2-bit errors. * Detection of all 1-, 2- and 3-bit errors and most other errors. Code [8, 1, 8, 2]: ------------------ 00000000 = 0 11111111 = 255 * Complete correction of all 1- to 3-bit errors. * Correct detection of all 1- to 4-bit errors. * Detection of all 1- to 7-bit errors.
Ich vermute mal, damit ist der Hamming Code gemeint, z.B.: http://www.cs.utsa.edu/~wagner/laws/hamming.html Peter
Ich denke das ist offensichtlich, denn man lernt doch schon in den Grundlagen der technischen Informatik was die Hamming-Distanz ist. Wie man an den beiden Codes oben sieht, erkennt man bei beiden bei einem gekippten (d. h. 0->1 oder 1->0) Bit eines Code-Wortes A) welches Bit gekippt ist und B) wie man das gekippte Bit korrigieren muß bzw. was mit dem Codwort an Nutzbits codiert wurde. Dafür müssen sich zwei (intakte) Codewörter um mindestens 3 Bits unterscheiden, also die Hamming-Distanz mind. gleich 4 sein. Die Kurzschreibweise für den Code ist [Anzahl_bits_je_Codewort, Anzahl_Nutzbits, Mindest-Hamming-Distanz_zwischen_je_zwei_Codewörtern (, Zahlenbasis)].
Korrektur: Die Mindest-Hamming-Distanz muß 3 sein. Mit 4 kann man 1- bis 2-Bit-Fehler korrekt erkennen, aber bei 2 ist der Fehler genau in der Mitte zwischen 2 Codewörtern und nicht korrgierbar, so dass dieser Fehler nur gemeldet werden kann. Für den Fall ist der zweite der obigen Codes; der korrigiert bis zu 3 gekippte Bits eines Bytes korrekt und meldet 4 gekippte Bits korrekt.
Sorry hier Forum habe nicht alle technische Informatik studiert und sind vielleicht gerade mal 12 Jahre alt. Und wie man sieht schützt auch ein Studium nicht vor Korrekturen.
Hi den "besseren" Code gibt es garnicht. z.B. macht es keinen Sinn auf guten Leitungen mit wenigen Bitfehlern einen fehlerkorrigierenden Code zu verwenden da die Redundanz die dazu in den Daten stecken muß zu viel Performance kosten würde. So setzt Ethernet IIRC gar keinen fehlerkorrigierenden Code ein da das Medium so gut ist das das garnicht notwendig ist. Kommte es doch mal zu einem Fehler sorgen höhere Protokollschichten dafür das die Daten einfach neu gesendet werden. Und genau hier kommen wir an den Punkt an dem diese korrigierenden Codes eingesetzt werden. Nämlich genau dort wo ein erneutes Senden der Daten nicht möglich ist bzw. Probleme bereitet oder bei extrem sicheren Datenkanälen. z.B. bei der gennanten CD/DVD. Kommt es hier zu einem Lesefehler müßte für einen erneuten Versuch der Laser erstmal neu positioniert werden was unheimlich viel Zeit kostet. Außerdem ist die optische Strecke bei der CD und vor allem bei der DVD relativ anfällig für Staub und Kratzer so das es u.U . garnicht möglich ist die Daten an einer bestimmten Stelle zu lesen. Durch die Redundanz die in den Daten steckt kann das aber bis zu einem gewissen Grad behoben werden. Weitere Anwendungsfall für korrigierende Codes ist z.B. die Übertragung von Daten von Weltraumsonden. Auch hier ist ein erneutes Senden mit extremen Zeitverzögerungen verbunden (Signallaufzeiten von 20min sind schon ein Wort) Allerdings sind die verwendeten Verfahren hier deutlich komplexer als der doch relativ einfache Hamming-Code. Also jedem Anwendungsfall seinen Code. Matthias
Also es kommt drauf an, denn bei 120 Nutzbits braucht man nur 8 Korrektur-Bits und das sind deutlich weniger als 10 %. Und auf diese weniger als 10 % kommt es sicherlich nur extrem selten an, denn für einen subjektiven Geschwindigkeitsunterschied braucht man mindestens 30 %. Aus dem Grund gibt's ECC ja auch bei CPU-Caches und in neueren PCI-Spezifikationen. Das Kodieren wie Enkodieren geschieht dort in Hardware und kostet keine nennenswerte Performance. Dass die Redundanz in den Daten steckt stimmt so nicht, denn bei der ECC-Kodierung wird ein Nutzdatenwort in ein längeres ECC-Codewort übersetzt und dieses übersetzte Codewort kann man i. Allg. nicht in Nutz- und Korrektur-Bits zerlegen. Insofern sind ECC und CRC oder md5sum nicht direkt vergleichbar. Jedenfalls ist ECC einem Prüfsummenverfahren vorzuziehen, wenn die Datenblöcke nicht allzu groß sind, denn der Aufwand ist nicht größer als für z. B. CRC und im Gegensatz zu CRC kann man mit ECC einzelne gekippte Bits richtig korrigieren. Deshalb bin ich auch privat ECC-Fan; in meinen PCs steck als RAM nur registered ECC RAM :-) Da sehe ich in Log-Files (auch im BIOS) ob 1-Bit-Fehler aufgetreten sind; ein defektes RAM kündigt sich so an und kann rechtzeitig, also vor >=2-Bit-Fehlern, ausgetauscht werden. Ich hatte nämlich früher spontan gestorbene RAMs, die einige Partitionen zerstört haben und mit ECC RAM kann mir das (praktisch)nicht mehr passieren. Und auch in Embedded Systemen kann sowas nicht schaden. Auch da macht es Sinn auftretende Fehler zu korrigieren + protokollieren und bei nicht korrigierbaren Fehlern das System stillzulegen anstatt mit Datenmüll groben Unfug anzustellen. Schließlich kann man mit ECC das betreffende Modul ja schon bei korrigierbaren Fehlern austauschen bevor nicht korrigierbare Fehler (u. ggf. Katastrophen) passieren.
@Matthias: Welche Verfahren werden denn für Raumsonden genommen? Werden Korrelationsverfahren verwendet oder ist es etwas ganz anderes?
ECC-Verfahren haben nur dort einen Vorteil, wo die Informationen parallel vorliegen (Pits auf einer CD, Bits im RAM), d.h. Störungen nur auf einzelne Bits wirken können. Bei serieller Übertragung nutzen sie nichts. Fehler bei einer seriellen Übertagung beruhen in der Regel auf zu hoher Kapazität, Widerstand, Kontaktproblemen, falscher Baudrate. D.h. sie wirken immer auf mehrere aufeinanderfolgende Bits gleichzeitig. Und dabei treten immer gleich so massive Datenverfälschungen auf, daß eine ECC machtlos ist. Deshalb reicht eine CRC vollkommen aus (z.B. CAN-Bus) um eine Fehlermeldung zu generieren. Um dann wieder fehlerfreie Daten zu erhalten hilft nur die Leitung zu überprüfen oder die Baudrate runtersetzen. Peter
Hi @Rolf Nur um das klarzustellen: Ich bin kein Kodierungsexperte. Nicht das die Fragen jetzt noch viel komplexer werden :-) Aber bei Voyager 2 (Sonde zu den äußeren Planeten) kam ein Reed-Solomon-Code zum Einsatz. Dieser kommte (in einer anderen Variante und AFAIK doppelt angewendet) auch auf der CD zum Einsatz. Wie es bei den aktuellen Sonden wie MEX oder MER ist weiß ich nicht. Aber sicher kommen dort auch fehlerkorrifierende Codes zum Einsatz. @Peter ob die Übertragung jetzt seriell oder parallel ist spielt beim Einsatz von korrigierenden Codes überhaupt keine Rolle. Denn die Übertragung stellt nur den Kanal dar über den die Daten übertragen und evtl. verfälscht werden. Die CD/DVD ist auch auch seriell ebenso wie die Funkübertragung bei Raumsonden. Wichtig ist der Vorteil den man dank der Redundanz (ja sie steckt in den Daten die im Kanal übertragen werden, das kann man drehen wie man will) bekommt. Wie ich oben schrieb ist das vom Einsatzzweck abhänig. Bei einem Hochverfügbarkeitsserver von dem das Einkommen eines Unternehmens abhängt macht das sicher Sinn auf etwas Perfomance zu verzichten und mehr Geld auszugeben. Ebenfalls bei der CD/DVD auf etwas Speicherplatz zu verzichten und sich dadurch Datensicherheit zu erkaufen. Es macht aber keinen Sinn auf einer transatlantischen Glasfaserstrecke 10% Performance herzugeben (und damit 10% Einnahmen) nur um einen Bitfehler in 10^12 Übertragungen zu korrigieren. Wenn die Verbindung mal schlecht wird (z.B. durch Eindringen von Seewasser) wird die Verbindung gleich so schlecht das eine Übertragung nicht mehr möglich ist. Das schöne an CRC ist ja das man Fehlerbündel sehr gut erkennen kann (was bei ECC oder ähnlichem garnicht möglich ist) und das macht dieses Verfahren so hervorragend geeignet für serielle Übertragungen. Matthias
@ Matthias: Ja, das sehe ich auch so. Bei serieller Übertragung ist ECC natürlich nur ein Baustein von vielen, denn es kann ja auch ein Byte verloren gehen, weil der UART sich nicht auf die Bits synchronisieren kann. Da hilft dann ECC allein nicht und ohne Synchronisierungs-Marken auch CRC allein nicht (weil nicht zwischen Daten u. Prüfsumme unterschieden werden kann).
@ peter dannegger: Beim [8, 1, 8, 2]-Code können bis zu 3 gekippte Bits je Byte korrigiert werden und das sollte praktisch immer reichen. Wenn bei einer Übertragung mehr als 3 Bits je Byte gekippt werden, dann werden auch andere Verfahren kaum helfen.
Hi Längenfehler erkennt man üblicherweise daran das die Länge des Pakets nicht mit der angegebenen Länge übereinstimmt. Matthias
Ja, dafür muss man separate Pakete verwenden und keinen mehr oder minder kontinuierlichen Datenstrom mit Steuerzeichen, denn die können verloren gehen. Man kann z. B. immer dieselbe Paketlänge verwenden oder die Länge in das erste Byte (u. ggf. zweite) packen und alles verwerfen was eine andere Länge hat. Dafür braucht man count-down-Zähler, zum Überprüfen ob a) in den ms vor dem ersten Byte nichts empfangen wurde, b) das Paket in x ms empfangen wurde (d. h. ob es unfragmentiert ist) und c) in den ms nach dem letzten Byte wirklich nichts empfangen wurde. Sowas habe ich auch mal programmiert und das wird nun mit einigen Produkten verkauft.
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.