Anwendung von CRC-Hard-Blöcken verringert Entwicklungsaufwand
Fehlererkennung in FPGAs
Fortsetzung des Artikels von Teil 3
Fehlererkennung in FPGAs
Dabei werden die Daten als Koeffizienten eines Polynoms interpretiert, das dann durch ein gegebenes Generator-Polynom dividiert wird. Der Rest dieser Division macht dann die CRC-Prüfsumme aus. Bei einer m bit langen Nachrichtenfolge und einem Generator-Polynom vom Grad r erzeugt der Sender eine n bit lange Sequenz mit n = m + r, die als Frame-Check-Sequence (FCS) bezeichnet wird, so dass der resultierende m+r bit lange Frame durch eine vorbestimmte Sequenz geteilt werden kann.
Dazu hängt der Sender insgesamt r 0-Bits an die m bit lange Nachricht an und teilt das resultierende Polynom vom Grad m + r – 1 durch das Generator-Polynom. Dies erzeugt ein Restpolynom vom Grad r – 1 oder niedriger. Das Restpolynom hat r Koeffizienten, welche die Prüfsumme bilden. Der Quotient wird verworfen. Bei den gesendeten Daten handelt es sich dann um die ursprüngliche m bit lange Nachricht, gefolgt von der r bit langen Prüfsumme.
Auf der Empfängerseite kann man nach einer der beiden Standardansätze vorgehen, um die Gültigkeit der empfangenen Daten festzustellen:
- Erneute Berechnung der Prüfsumme für die ersten empfangenen m bit und Vergleich mit der empfangenen Prüfsumme (konkret mit den letzten r empfangenen Bits).
- Berechnung der Prüfsumme für alle empfangenen m+r Bits und nochmaliger Vergleich mit einem Rest von Null.
Jobangebote+ passend zum Thema
Zur Feststellung, dass die zweite Methode zu einem Rest von 0 führt, soll zunächst folgende Konvention gelten:
M = Polynomdarstellung der Nachricht,
R = Polynomdarstellung des Rests, wie er vom Sender berechnet wurde,
G = Generator-Polynom,
Q = Quotient, der sich aus der Division von M durch G ergibt.
Die gesendeten Daten entsprechen dem Polynom M xr – R. Dabei kennzeichnet die Variable xr eine Verschiebung der Nachricht um r bit zur Anpassung an die Prüfsumme. Daraus ergibt sich:
M xr = Q G + R
Das Anhängen der Prüfsumme R an die Nachricht auf der Senderseite entspricht einer Subtraktion des Restes von der Nachricht. Die gesendeten Daten werden dann zu M xr – R = Q G, was eindeutig ein Vielfaches von G ist. Daher kommt im zweiten Fall Null heraus.
Allerdings ist dieses Verfahren unempfindlich gegenüber der Anzahl führender und angehängter Null-Bits in den gesendeten Daten. Mit anderen Worten: Wenn einer Nachricht folgende Null-Bits hinzugefügt oder entfernt werden, dann bleibt der Rest weiterhin 0 und der Fehler wird nicht entdeckt, was letztlich bedeutet, dass sich die ursprüngliche Bit-Sequenz nicht wiederherstellen lässt. Allerdings gibt es eine wirksame Methode, diesen Nachteil auszugleichen.
- Fehlererkennung in FPGAs
- Literatur
- Der Residuen-Ansatz
- Fehlererkennung in FPGAs
