Der Text des Ubungsblattes ist nahezu unveraendert aus dem Skript uebernommen worden, falls also jemand seinen Aufgabenzettel verschlampt hat:
http://www.informatik.uni-hamburg.de/TKRN/world/abro/T3/t3k4w01.pdf auf Seite 31 (15 of 22) A1: CRC-Polynome
Die Aufgabe lautet "Weisen Sie nach, dass obige CRC-Polynome [CRC-12, CRC-16, CRC-CCITT] Zweibitfehler nicht immer erkennen"
Wäh immernoch Polynome…also keine Assembelraufgabe diesmal? Dann wirds vermutlich das einfachste sein, ein Gegenbeispiel zu finden, oder?
Wäh immernoch Polynome…also keine Assembelraufgabe diesmal? Dann wirds vermutlich das einfachste sein, ein Gegenbeispiel zu finden, oder?
Wenn Du ne einfache Moeglichkeit weisst, ein Gegenbeispiel zu finden… ich habe einfach alle Moeglichkeiten durchprobiert, und zumindest 32bit breite Worte sind gegen 2Bit-Fehler sicher. Das heisst, entweder nen komplexeren Polydiv Algo schreiben, der lange Strings verarbeiten kann, oder mit ein bischen Hirnschmalz an die Sache gehen.
Fuer die Brute Force Methode wird man allerdings sehr viel Zeit brauchen, denn alleine das Brute Force Testen auf 32 Bit hat hier schon mehrere Minuten gedauert. Also - hat jemand ne Idee, wie man da mit Papier und Bleistift auf ne Loesung bzw. ein Gegenbeispiel kommt?
Die Aufgabe lautet "Weisen Sie nach, dass obige CRC-Polynome [CRC-12, CRC-16, CRC-CCITT] Zweibitfehler nicht immer erkennen"
Ich habe gerade mal ein bischen gegoogled
http://www.hta-bi.bfh.ch/E/Laboratories/Telematic/Telematik/Kurs/codage_d.pdfDa steht auf Seite 19, dass der CRC-CCITT 100% aller 2Bit-Fehler erkennt. Was soll man denn jetzt davon halten?
Muß man diesesmal wieder eine Lösung abgeben?!?
Muß man diesesmal wieder eine Lösung abgeben?!?
Es wird nicht erwartet, dass eine Loesung abgegeben wird.
Muß man diesesmal wieder eine Lösung abgeben?!?
Es wird nicht erwartet, dass eine Loesung abgegeben wird.
–> d.h.: Zur Lösung von Blatt 10 wird jene zu Blatt 9 dringend benötigt!!!
Muß man diesesmal wieder eine Lösung abgeben?!?
Es wird nicht erwartet, dass eine Loesung abgegeben wird.
–> d.h.: Zur Lösung von Blatt 10 wird jene zu Blatt 9 dringend benötigt!!!
1. LOL ;-)
2. Die Erkenntnis, dass 2 Bit Fehler nicht immer erkannt werden, hat man ja auch jetzt schon, ich glaube kaum, dass der "Beweis" fuer den naechsten Aufgabenzettel irgendwie von Relevanz sein duerfte, falls wir da wieder was programmieren sollen.
Ich habe in einen Skriptteil der FU Berlin eine allgemeine Definition gefunden:
Leistungsfähigkeit von CRC mit G(x) vom Grad r
1) Einzelfehlererkennung
2) Erkennung aller Doppelfehler mit einem Abstand von k Bit, falls G(x) nicht den Faktor (xk+1) enthält (k=2…Framelänge)
3) Erkennung aller Fehler mit ungerader Anzahl Fehlerbits, da G(x) den Faktor (x+1) enthält
4) Erkennung von Burst-Fehlern <= r Bit
und von der Uni Leipzig:
Die Fehler, die zufällig Polynomen mit G(x) als Faktor entsprechen, werden nicht entdeckt
(alle anderen aber schon)
Vielleicht kann jemand damit was anfangen
im skript (gleiche seite, in der ausfuehrlicheren druckversion zumindest) steht schon 1/3 der lösung verraten, nämlich das
(x^32768 + 1) / crc-16 = xxx rest 0 ergibt,
hat man also eine 33000-bit information und dreht man das 32768. und das erste bit um, so wird dieser 2er-fehler von crc-16 nicht erkannt..
