Anwendung von CRC-Hard-Blöcken verringert Entwicklungsaufwand
Fehlererkennung in FPGAs
Fortsetzung des Artikels von Teil 2
Der Residuen-Ansatz
Im praktischen Fall erfolgt eine Komplementierung der Prüfsumme, bevor sie angehängt wird. Damit ergibt sich der berechnete Rest (über m + r bit) auf der Empfängerseite ungleich Null. Der Rest, den der Empfänger in derartigen Fällen enthält, ist dann ein fester Wert, der als das Residuum eines Polynoms bezeichnet wird.
Mit etwas Mathematik lässt sich dieser Ansatz verdeutlichen: Angenommen, das %-Symbol sei eine Modulo-Operation. Im Falle einer Anfügung der Prüfsumme ohne Inversion ergibt sich:
(M xr – R) xr % G = 0
Dabei führt der Empfänger wieder die gleiche Schiebeoperation wie der Sender durch.
Jetzt wird der Fall betrachtet, in dem die Prüfsumme invertiert und dann an den Nachrichtenstrom des Senders angehängt wird:
(M xr – Rc) xr % G
Hier bezeichnet Rc die komplementäre Prüfsumme. Dies lässt sich umschreiben zu: (M xr – R + (xr–1 + ... + x + 1)) xr % G
Jobangebote+ passend zum Thema
Die Komplementierung eines Bits ist das gleiche wie eine XOR-Funktion mit 1. Hier repräsentiert das +-Zeichen eine Addition in Modulo-2-Arithmetik (in Modulo-2-Arithmetik sind bekanntlich Addition und Subtraktion gleich). In dem Fall ist der Rest gleich
(xr-1 + ...x + 1)xr % G
Das ergibt sich für den Fall eines gegebenen Generator-Polynoms als Konstante.
Das meist genutzte Generator-Polynom für CRC-32 ist
G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Das entspricht einem hexadezimalen Wert von 04C11DB7. Der zur CRC-32 korrespondierende konstante Residuen-Wert ist in hexadezimaler Notation C704DD7B. Für ein gegebenes Generator-Polynom G bleibt der Residuen-Wert eine Konstante für jedes Datenmuster, das am Eingang erscheint.
- Fehlererkennung in FPGAs
- Literatur
- Der Residuen-Ansatz
- Fehlererkennung in FPGAs
