DE

Codes zur Fehlererkennung und -korrektur

Parität, Hamming-Code, Hamming-Distanz, Prüfsummen und CRC

Zahlensysteme: Binär und hexadezimal Gray-Code BCD-Codes Gleit- und Festkomma Parität, Hamming und CRC

Paritätsbit

Daten

Hamming-Code

Geben Sie die Datenbits ein, die Paritätsbits werden berechnet. Dann klicken Sie auf ein beliebiges Bit des Codeworts, um es wie einen Übertragungsfehler zu kippen, und sehen, was der Empfänger tut: Das Syndrom gibt die Position des falschen Bits an. Probieren Sie einen und zwei Fehler, mit und ohne Gesamtparitätsbit.

Daten

Parität · Daten · Gesamtparität · gekipptes Bit.

Hamming-Distanz zwischen zwei Wörtern

Wörter

CRC- und Prüfsummenrechner

Geben Sie das Telegramm als hexadezimale Bytes (mit oder ohne Leerzeichen) oder als Text ein. Die Spalte „im Telegramm“ zeigt die Bytes in Sendereihenfolge.

Telegramm

CRC Schritt für Schritt: die Polynomdivision

Division

Warum man sie braucht

Kein Kanal ist perfekt: Ein RS-485-Telegramm neben einem Umrichter, ein von einem Teilchen getroffenes Speicherbit oder ein Kratzer auf einer Disc können aus einer 0 eine 1 machen. Um das zu bemerken, fügt der Sender den Daten einige daraus berechnete Redundanzbits hinzu, und der Empfänger wiederholt die Berechnung. Stimmt sie nicht überein, gibt es zwei Strategien:

Hamming-Distanz

Die Hamming-Distanz zwischen zwei gleich langen Wörtern ist die Anzahl der Bits, in denen sie sich unterscheiden: zwischen 1011101 und 1001001 sind es 2. Die minimale Distanz \(d\) eines Codes ist die kleinste zwischen zwei beliebigen gültigen Wörtern und bestimmt, was er leisten kann:

\[ \text{erkennt bis zu } d - 1 \text{ Fehler} \qquad \text{korrigiert bis zu } \left\lfloor \frac{d-1}{2} \right\rfloor \text{ Fehler} \]
CodeMinimale DistanzErkenntKorrigiert
Daten ohne Redundanz1nichtsnichts
Paritätsbit, 2-aus-521 Fehlernichts
Hamming32 Fehler1 Fehler
Hamming mit Gesamtparität (SECDED)43 Fehler1 Fehler, erkennt 2
Jedes Bit 3-mal wiederholen32 Fehler1 Fehler (durch Mehrheit)

Die Idee ist geometrisch: Liegen die gültigen Wörter mindestens 3 auseinander, ist ein Wort mit einem Fehler immer noch näher am Original als an jedem anderen.

Parität

Der einfachste Code: Es wird ein Bit hinzugefügt, damit die Gesamtzahl der Einsen gerade (gerade Parität) oder ungerade (ungerade Parität) ist. Er erkennt jede ungerade Anzahl von Fehlern, aber nicht zwei gleichzeitig gekippte Bits. Das ist die Parität serieller Schnittstellen (8E1 bedeutet 8 Datenbits, gerade Parität und 1 Stoppbit; Modbus RTU verwendet standardmäßig gerade Parität) und einiger alter Speicher. In einer Schaltung wird sie mit einer Kette von XOR-Gattern gebildet.

Bei der zweidimensionalen Parität werden die Daten in einer Tabelle angeordnet und die Parität jeder Zeile und jeder Spalte angehängt. Ein Fehler ändert die Parität einer Zeile und einer Spalte, und ihr Kreuzungspunkt zeigt das zu korrigierende Bit.

Der Hamming-Code

Richard Hamming entwickelte ihn 1950, weil ihm Fehler der Relaisrechner immer wieder die Wochenendrechnungen verdarben. Die Positionen des Codeworts werden ab 1 nummeriert; die Zweierpotenzen (1, 2, 4, 8 …) tragen Paritätsbits, die übrigen die Daten. Jedes Paritätsbit \(p_k\) deckt die Positionen ab, deren Binärzahl das Bit mit der Wertigkeit \(k\) gesetzt hat: \(p_1\) deckt 1, 3, 5, 7 … ab; \(p_2\) 2, 3, 6, 7 …; \(p_4\) 4–7, 12–15 … Mit \(r\) Paritätsbits werden \(m\) Datenbits geschützt, wenn gilt:

\[ 2^{r} \ge m + r + 1 \]
Beispiel: Hamming (7, 4) mit den Daten 1011

Die Daten stehen an den Positionen 3, 5, 6 und 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) und \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). Gesendet wird \(0110011\). Kommt \(0110111\) an (Position 5 ist falsch), berechnet der Empfänger die drei Paritäten über das Empfangene neu: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). Das Syndrom \(s_4 s_2 s_1 = 101_2 = 5\) ist genau die Fehlerposition, und dieses Bit muss nur invertiert werden.

CodeDatenbitsParitätsbitsCoderate
Hamming (7, 4)4357 %
Hamming (15, 11)11473 %
Hamming (31, 26)26584 %
Hamming (63, 57)57690 %
SECDED (72, 64), ECC-Speicher64889 %

SECDED: einen korrigieren, zwei erkennen

Bei zwei Fehlern liefert der einfache Hamming-Code ein Syndrom ungleich null und „korrigiert“ ein richtiges Bit, wodurch das Wort schlechter wird. Um das zu vermeiden, wird ein Gesamtparitätsbit P über das ganze Wort angehängt (single error correction, double error detection):

So arbeitet der ECC-Speicher von Servern und vielen Mikrocontrollern für Automobil- und Sicherheitstechnik: 8 Prüfbits je 64 Datenbits.

Prüfsummen

Sie sind schnell und leicht zu programmieren, erkennen aber deutlich schlechter als ein gleich großer CRC.

CRC (zyklische Redundanzprüfung)

Der CRC behandelt die Nachricht als Polynom mit den Koeffizienten 0 und 1 (\(1011 = x^3 + x + 1\)) und teilt sie durch ein Generatorpolynom vom Grad \(r\). In dieser Arithmetik (modulo 2) sind Addition und Subtraktion dasselbe wie das exklusive ODER, und es gibt keine Überträge. Der Sender hängt \(r\) Nullen an die Nachricht, dividiert und sendet den Rest an ihrer Stelle; der Empfänger dividiert das ganze Telegramm, und ohne Fehler ist der Rest 0.

Beispiel: Nachricht 11010011101100 mit dem Generator 1011 (\(x^3 + x + 1\))

Es werden 3 Nullen angehängt und unter jeder links verbleibenden 1 der Generator subtrahiert (XOR). Der Rest ist 100, gesendet wird also 11010011101100100. Das ist das Beispiel, das im Rechner oben geladen ist.

Mit einem guten Polynom vom Grad \(r\) erkennt der CRC:

Warum derselbe „CRC-16“ unterschiedliche Werte liefert

Neben dem Polynom legt jeder CRC den Startwert des Registers fest, ob die Bits jedes Bytes gespiegelt eingehen (niederwertigstes zuerst, wie sie aus einem UART kommen), ob das Ergebnis gespiegelt wird und mit welchem Wert das abschließende exklusive ODER erfolgt. Deshalb liefern CRC-16/MODBUS, CRC-16/ARC und CRC-16/CCITT bei denselben Daten verschiedene Ergebnisse. Um herauszufinden, welchen ein Gerät verwendet, berechnet man den der Zeichenkette 123456789 und vergleicht ihn mit dem Prüfwert: 4B37 für Modbus, 29B1 für CCITT-FALSE, CBF43926 für CRC-32.

CRC in der Industrie

Weitere korrigierende Codes

Siehe auch: Binär- und Hexadezimal-Umrechner, 2-aus-5-Code und Logikgatter-Simulator (das XOR).