Hallo, ich habe mal noch eine allg. Frage zu Prüfsummen. Gibt es eine Rechenregel mit der man für jede Wortbreite (32Bit,64Bit,128Bit,256Bit) die optimale Länge einer Prüfsumme berechnen kann? Bei einem 32Bit Wort ist ja eine 32Bit Prüfsumme sehr ineffizient. Es geht hier speziell um XOR, Fletcher, Adler und 1er Kompl. Prüfsummen. Ich hoffe ihr könnt mich aufklären.
Das ist doch immer abhaengig davon, was man genau machen moechte. Fehlererkennung oder auch Fehlerkorrektur? Sprich, welche Hamming-Distanz ist angedacht? Reden wir hier von Pruefsummen ueber EIN oder ueber MEHRERE Worte? Und um die Frage etwas genauer zu beantworten: Wirf mal einen blick auf "perfekte Codes" und "optimale Codes" Aber dazu solltest Du ersteinmal noch die Aufgabenstellung konkretisieren...
Ich war der Meinung, dass die von mir genannten Verfahren ausschließlich zur Fehlererkennung sinnvoll sind und keine Fehlerkorrektur unterstützen. Wir reden hier von Prüfsummen über EIN Wort. Es sollen nur bestimmte Prüfsummen so implementiert werden, dass diese nicht unnötig Bandbreite verschwenden.
nun, ein XOR ueber ein einziges Wort ist aber erm, schwierig, bzw. ziemlich sinnfrei. Nachdem einen aber niemand zwingt ein 32-Bit wort nicht als 4 8-bit worte zu betrachten etc., ist die Aufgabe sicher nicht trivial zu loesen, es kommt sicher zumindest auch darauf an, wie viele Fehler man erkennen koennen moechte, wobei wir wieder bei der gewuenschten Hammingdistanz waeren? Das hatte ich nicht erwaehnt, weil fuer mcih alles, was ueber mehr als einen Fehler erkennen rausgeht automatisch in 1 Fehler korrigieren uebergeht...
Frank L. schrieb: > Wir reden hier von Prüfsummen über EIN Wort. Da ist die einfachste Prüfsumme das Parity. Damit lässt sich eine ungerade Anzahl von Bitfehlern erkennen. Wenn das ausreicht, ist diese 1-Bit-Prüfsumme genügend... Und die einfachste Prüfsumme über ein Byte ist das Byte selber. Zweimal übertragen und zweimal gleich empfangen --> höchstwahrscheinlich fehlerfrei. Frank L. schrieb: > Gibt es eine Rechenregel mit der man für jede Wortbreite > die optimale Länge einer Prüfsumme berechnen kann? Nein, denn du hast hier die nötige Sicherheit, mit der ein Fehler erkannt werden kann, aussen vor gelassen. Die optimale Länge ist die, die wenig Aufwand bereitet und ausreichend sicher die Erkennung von Fehlern erlaubt.
OK, ich steh jetzt richtig auf dem Schlauch. Grundsätzlich war ich der Meinung, dass zur Fehlerbehebung CRC oder Hamming Code verwendet wird. Ist eine Prüfsumme (XOR, Fletcher, Adler) auch in der Lage Fehler zu korrigieren? Wie würdet ihr eine Prüfsumme für ein Wort mit 128Bit nach XOR und Fletcher berechnen? Also die Berechnung ist mir klar aber ich weiß nicht wie ich die Länge der Prüfsumme wählen sollte. Da steig ich noch nicht hinter. 128Bit in 4Bit o. 8Bit o. 32Bit Wörter zerlegen?
Frank L. schrieb: > Ist eine Prüfsumme (XOR, Fletcher, Adler) auch in der Lage Fehler zu > korrigieren? Bei grösseren Datenmengen: Beispielsweise 16 Blöcke zu je 512 Bytes mit einer normalen nicht korrekturfähigen CRC pro Sektor. Von den 16 sind die letzten 2 Blöcke abwechselnd aufsummierte XOR-Blöcke. Kann jeden Burst-Fehler bis zur Länge eines Blocks korrigieren und ist so einfach, dass es noch der dümmste embedded Controller schafft (QIC-1000 Bandformat).
Deine Frage kann man nicht pauschal beantworten. Du musst den Übertragungsweg und dessen Fehlerwahrscheinlichkeit kennen. Du musst auch wissen, wie viele Fehler tollerierbar sind. Mit diesen Angaben kann dann die Kanalkodierung (bei dir Prüfsumme) bestimmt werden. nicht ohne Grund bleibt bei WLan von den 54MBit brutto netto nicht mehr viel übrig. Der Kanal ist sehr fehleranfällig. Bei RS232 mit 9600 baud muss man sich fast keine Gedanken machen. Bei 1Mbaud sieht die Sache wieder anders aus.
Man kann mit Kanalkodierung Fehler erkennen und auch beheben. Das hängt von der Redundanz im Code ab.
Danke Tilo für deine Hilfe. Der Übertragungsweg ist auf einem FPGA zwischen PowerPC und PCB. Bitte keine Fragen wie sinnvoll das ist, ist eben so. Wie würde Redundanz in einem Code gebildet werden. Ich würde mich über ein Bsp. sehr freuen. VG
Das einfachste Beispiel für Redundanz würde bereits genannt: Ein "dummer" Wiederholungscode: 0xAA 0xAA Hier kann man Fehler erkennen (und im rein digitalen) keinen Fehler beheben. Ich denke das geläufigste Beispiel für Fehlerkorrektur dürften Reed-Solomon-Codes sein (zum Beispiel macht das der CD-Player). Allgemein: was ist Redundanz: Zusätzliche Daten, die an die in den eigentlichen Nutzdaten enthalten sind oder gezielt an diese angefügt werden. Quasi "unnötige" Daten. Die kann man aber eben hervorragend nutzen, um kaputte Signale wieder zu reparieren. Einfaches Beispiel: Wenn ich Datum A, Datum B und Datum A xor B übertrage, dann übertrage ich zwar drei Datenworte, kann aber wenn der Kanal oBdA Datum B verworfen hat (Beispiel Ethernet, UDP, Prüfsumme) trotzdem Datum B wiederherstellen (ja, das ist nicht, was Du suchst, ich weiss)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.