CRC-Beispiel - Übung PDF

Preview

Summary

Übung...

Description

CRC-Beispiel.docx, 10.12.2015 10:03, S. 1 / 2

CRC – cyclic redundancy check Quelle: https://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung

Es folgt ein Beispiel, in dem für einen Binärcode von 5 Bit der CRC berechnet und überprüft werden soll. Das Generatorpolynom (CRC-Polynom) lautet 110101 (

) und ist somit 5. Grades.

Der zu übertragenden Bitfolge, welche auch als Rahmen (engl. frame) bezeichnet wird, werden Nullen angehängt (Rahmen mit Anhang), wobei dem Grad des Generatorpolynoms entspricht (bzw. der Anzahl der Bits des Generatorpolynoms minus eins). Generatorpolynom: 110101 (zuvor festgelegt) Rahmen: 11011 (Nutzdaten) Rahmen mit 1101100000 (das Generatorpolynom hat Stellen, also werden Anhang: Nullen ergänzt; hier ist ) Nun wird der Rahmen mit Anhang von links her durch das Generatorpolynom dividiert. Dabei wird ausschließlich das exklusive OR (XOR) verwendet. Wenn man dies im ersten Schritt anwendet, wird aus 110110 XOR 110101 die Zahl 000011 (wobei gilt: 1 XOR 1 = 0; 1 XOR 0 = 1; 0 XOR 1 = 1; 0 XOR 0 = 0). Es folgt das vollständige Beispiel: ↓ immer mit der ersten gemeinsamen 1 anfangen

1101100000 110101 -----0000110000 110101 -----101 (Rest) An den Rahmen ohne Anhang wird nun der Rest angehängt. Dieser muss ebenfalls aus bestehen. Damit hängen wir nun 00101 an den Rahmen an.

Bit

Übertragener Rahmen: 1101100101 Diese Nachricht kann jetzt beispielsweise über ein Netzwerk übertragen werden. Wenn die Nachricht beim Empfänger eintrifft, kann dieser überprüfen, ob sie korrekt angekommen ist.

CRC-Beispiel.docx, 10.12.2015 10:03, S. 2 / 2

Mittels Division durch das Generatorpolynom kann jetzt die fehlerhafte Übertragung erkannt werden: Korrekte Übertragung der Nachricht: 1101100101 Das Generatorpolynom (wie oben): 110101

1101100101 110101 -----110101 110101 -----000000 Der Rest der Division ist gleich null. Es ist also wahrscheinlich kein Fehler aufgetreten Fehlerhaft übertragene Nachricht (Beispiel): Das Generatorpolynom (wie oben):

1001100101 110101

1001100101 110101 -----100110 110101 -----100111 110101 -----100100 110101 -----100011 110101 -----10110 Der Rest der Division (10110) ist ungleich null. Also ist ein Fehler aufgetreten. Bei der Überprüfung auf Richtigkeit können folgende vier Fälle auftreten: 1. Der Rest der Division ist null und die Nachricht ist richtig 2. Der Rest der Division ist null und die Nachricht ist fehlerhaft (dieser Fall ist unwahrscheinlich, kann aber vorkommen, wenn das Fehlerpolynom ein Vielfaches des Generatorpolynoms ist oder wenn der Fehler im Datenteil und im CRC-Wert ist) 3. Der Rest der Division ist ungleich null und die Nachricht ist fehlerhaft 4. Der Rest der Division ist ungleich null und die Nachricht ist richtig (dieser Fall tritt ein, wenn lediglich der angehängte Rest fehlerhaft übertragen wird; dies ist jedoch ebenfalls unwahrscheinlich, da der übertragene Rest im Vergleich zur Gesamtlänge des Pakets kurz ist)...