www.mikrocontroller.net

Forum: Projekte & Code Zwei ECC-Codes


Autor: Rolf F. (Gast)
Datum:
Angehängte Dateien:

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

Autor: Frankl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was will das, mir das sagen ?

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich vermute mal, damit ist der Hamming Code gemeint, z.B.:

http://www.cs.utsa.edu/~wagner/laws/hamming.html


Peter

Autor: Rolf F. (Gast)
Datum:

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

Autor: Rolf F. (Gast)
Datum:

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

Autor: Frankl (Gast)
Datum:

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

Autor: Matthias (Gast)
Datum:

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

Autor: Rolf F. (Gast)
Datum:

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

Autor: Rolf F. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Matthias:

Welche Verfahren werden denn für Raumsonden genommen?
Werden Korrelationsverfahren verwendet oder ist es etwas ganz anderes?

Autor: Peter Dannegger (peda)
Datum:

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

Autor: Matthias (Gast)
Datum:

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

Autor: Rolf F. (Gast)
Datum:

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

Autor: Rolf F. (Gast)
Datum:

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

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

Längenfehler erkennt man üblicherweise daran das die Länge des Pakets
nicht mit der angegebenen Länge übereinstimmt.

Matthias

Autor: Rolf F. (Gast)
Datum:

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

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.