Hallo Leute, wenn ich ein Datenblock habe, der 8bit breit und 100 Wörter lang ist, welche Prüfsumme muss ich wählen, um diesen Datenblock anhand der Prüfsumme klar identifizieren zu können? Gibt es hierzu Literatur, die Ihr empfehlen könnt, gerade im Hinblick auf HDL-Implementierung? LG, Leo
Eine Prüfsumme, die kürzer als der Datenblock ist, kann diesen nie eindeutig identifizieren. Eine Prüfsumme, wenn sie richtig gewählt wird, kann aber dafür sorgen, dass eine Kollision (d.h. zwei Datenblöcke mit derselben Prüfsumme) nicht sehr wahrscheinlich ist. Gruß Marius
Hmmmm, leider ist die Antwort nicht sehr hilfreich. Mir fehlen Zahlen ...
Da gibt es doch was beim Gruyter-Verlag: "Cyclic Redundancy Check für die industrielle Kommunikation, Merchant 2013"
Marius Wensing schrieb: > Eine Prüfsumme, die kürzer als der Datenblock ist, kann diesen nie > eindeutig identifizieren. > > Gruß > Marius Da muss ich widersprechen. Wenn dem so ist, würden all die Kompressions Verfahren nicht funktionieren. Grüsse, René
Rene H. schrieb: > Da muss ich widersprechen. Wenn dem so ist, würden all die Kompressions > Verfahren nicht funktionieren. beim Kompressions kann es aber auch länger werden. außerdem kann man nie vorher die ziellänge festlegen.
Überleg doch mal, wie willst du z.B. 10 Leute unterscheiden mit nur 8 Namen? ... >Da muss ich widersprechen. Wenn dem so ist, würden all die Kompressions >Verfahren nicht funktionieren. Oder du dessen Funktion nicht verstanden... Gruß Jonas
Peter II schrieb: > Rene H. schrieb: >> Da muss ich widersprechen. Wenn dem so ist, würden all die Kompressions >> Verfahren nicht funktionieren. > > beim Kompressions kann es aber auch länger werden. außerdem kann man nie > vorher die ziellänge festlegen. Das ist natürlich Richtig. Kompression für eine Prüfsumme ist natürlich auch Schwachsinn. Mir ging es nur um das Wort nie. Grüsse, René
Jonas Biensack schrieb: > Überleg doch mal, wie willst du z.B. 10 Leute unterscheiden mit > nur 8 > Namen? ... > >>Da muss ich widersprechen. Wenn dem so ist, würden all die Kompressions >>Verfahren nicht funktionieren. > > Oder du dessen Funktion nicht verstanden... > > Gruß Jonas Aha. Du willst also z.Bsp. die Funktionstauglichkeit des Lempel Ziv Markow Algorithmus in Frage stellen? Grüsse, René
Das beruht aber auf bestimmten Eigenschaften der Eingangsdaten. In der Realität ist das zwar ein interessantes und auch häufiges Subset, aber eben nur ein Subset. Für wirklich zufällige Werte kann kein Kompressionsalgorithmus eine kürzere Ausgabefolge produzieren, dann wäre sie eben nicht zufällig ;)
Georg A. schrieb: > Das beruht aber auf bestimmten Eigenschaften der Eingangsdaten. In > der > Realität ist das zwar ein interessantes und auch häufiges Subset, aber > eben nur ein Subset. Für wirklich zufällige Werte kann kein > Kompressionsalgorithmus eine kürzere Ausgabefolge produzieren, dann wäre > sie eben nicht zufällig ;) Ok. Jetzt bin ich spitzfindig. Es kommt darauf an wie zufällig die Zufälligkeit ist. :-). Da sind wir wieder bei den Affen und Goethe. ;-) Grüsse, René
Das Stichwort dürfte "Kodierungstheorie" lauten... weitere Blockcode, Hamming-Distanz, Kanalkodierung usw... Gibt auch viele Scripte (FH/UNI) zu dem Thema... ist meistens eine Vorlesung.
Für Speziallfälle lässt sich eine Ausnahme finden, allgemein geht aber nix. Für so typische Pseudozufallsfolgen ala rand() kann man natürlich nur den Seed und die Länge übermitteln, selbst wenn kein normaler Kompressionsalgo das rausbekommt. Auch Mozart und alle Bücher könnte man als KV oder ISBN-Nummer komprimiert übertragen. Aber einerseits wird dann das Patternmatching auf Kompressorseite wohl NP und andererseits ist das immer nur ein vernachlässigbares Subset aller möglichen Eingangsfolgen.
Rene H. schrieb: > Ok. Jetzt bin ich spitzfindig. Es kommt darauf an wie zufällig die > Zufälligkeit ist. Naja, nicht ganz. Das Problem ist halt, das es keine injektive Abbildung von M^n nach M^m mit m<n gibt. (M ist das verwendete, endliche, Alphabet.) Aber es stellt sich die Frage, was der TE mit 'eindeutig' identifizieren meint. Absolut eindeutig, wäre das in der Nähe der Entropie der Quelle. Aber für alle praktische Erwägungen reicht natürlich weniger. (Was wird denn angenommen? Zufällige Bitfehler, d.h. rauschen im Kanal? Oder ein normaler Angreifer; oder ein allmächtiger Angreifer?)
Also mit der Kompression sind wir ein wenig vom Thema ab gekommen. Grundsätzlich kann man von einer Prüfsumme nie zurück auf die Daten kommen die dieser Prüfsumme zugrunde liegen, es sei denn man hat die gleiche Datentiefe ... was aber bei einer Prüfsumme eher nicht der Fall ist. Nehmen wir z.B. eine MD5 Prüfsumme. Es kann völlig verschiedene Daten geben die trotzdem die selbe MD5 Prüfsumme ergeben, allerdings ist die Wahrscheinlichkeit gering und es nur mit hohem Aufwand möglich einen Datensatz zu erstellen der eine bestimmte MD5 Prüfsumme ergibt. Eine Prüfsumme ist nicht dazu gedacht einen Datensatz zu identifizieren. Sie ist nur dazu gedacht mit einer gewissen Wahrscheinlichkeit festzustellen ob zwei Datensätze gleich sind, also z.B. Datenübertragungsfehler zu identifizieren. Die ursprüngliche Frage ist also nicht klar zu beantworten. Eine "absolute" Klarheit gibt die Prüfsumme nicht (dabei ist es wirklich egal ob es ein MD5, SHA512 oder was auch immer Prüfsumme ist). Nur Der Datensatz zusammen mit der Prüfsumme ergibt eine klare Aussage. Generell kann man sagen das eine längere Prüfsumme eine höhere Wahrscheinlichkeit für eine "Eindeutigkeit" ergibt. Es ist also eher eine Frage wo Du die Grenze ziehen möchtest. Welche Wahrscheinlichkeit genügt Dir? Welche Aufwand für die Berechnung willst Du treiben? Eine Prüfsumme im HDLC-Protokoll, beispielsweise, kannst Du super einfach berechnen, das verbrät kaum Rechenzeit. Eine SHA512 Prüfsumme ist da schon deutlich aufwändiger.
vielleicht auch eine Moeglichkeit waeren die Algorithmen, die bei CD und DVD verwendet werden. Anstatt 8bit x 100 koenntest du deine Daten 4x8bit x 100/4 organisieren. Jetzt jeweils horizontal und vertikal eine ECC bilden (die 100/4=25 koenntest du auch auf 32 'padden' und haettest dann 2x32 ECC Werte ueber 32x32 Bit). Nur so als Gedankengang. Ein-Eindeutig unterscheiden wirst du natuerlich deine Daten nicht, es wird Aliase geben. Die Frage ist: Wieviele?
achso, nochwas als Ergaenzung zu meinem Post oben... Wenn du deine Daten nicht 8x100 sondern 2x400 anordnest, dann kannst du mit ECC mittels SECDED (single error correction, double error detection) mit einem weiteren 2x400bit Feld (==die ECC bits, ich nenne die mal 'horizontal') jeden Unterschied erkennen. Du brauchst dann auch die 2xECC ueber jeweils 400bit nicht. Aber daran erkennst du, dass du dann auch nix gewonnen hast, es ist Faktor 2 (worst-case). Mit ECC jeweils horizontal und vertikal ueber ein quadratisches Feld solltest du was rausholen koennen (mit moeglichst wenig Aliasen). Und bzgl. CRC: Diese Algorithmen haben als Intention die serielle Uebertragung ueber eine einzige Leitung. Die sind also (wenn richtig implementiert) recht gut, wenn z.B. ein 'Haenger' mit einem Burst von '0' oder '1' durchkommt. ECC dagegen hat diese Burstanfaelligkeit nicht, ist deshalb aber auch nicht so effizient wie CRC fuer den 'speziellen' Anwendungsfall.
Naja, wenn es um das Verhältnis Nutzbits vs. Prüfsumme geht, könnte man dann gleich Reed-Solomon nehmen. Bei DVB-S/T/C machen die zB. zu 188Bytes noch 16 dazu (die CD hat AFAIK auch RS). Damit kann man dann auch gleich max. 8 Byte-Fehler korrigieren und alles drüber hinaus mit guter Wahrscheinlichkeit erkennen. Dummerweise ist halt die Berechnung und Korrektur etwas aufwendiger als eine reine CRC. Wobei das aber eigentlich für alles gilt, was vernünftig korrigieren kann ;) Bei der Korrektur hängt es auch von der Art der Fehler ab. Wenn man noch Zugriff auf die analogen Werte vor der 0/1-Entscheidung hat, kann man mit Viterbi, LDPC oder Turbo-Codes eine Menge gewinnen. Dann gehen aber auch nicht mehr die nackten Daten über die Leitung. Ein weites Feld...
Leo schrieb: > Hmmmm, leider ist die Antwort nicht sehr hilfreich. Mir fehlen Zahlen Du lieferst ja auch keine. Das ist nämlich eine Frage der Wahrscheinlichkeit. Also wie wahrscheinlich es sein darf, dass zwei verschiedene Blöcke die gleiche Signatur haben. Ohne diese Angabe ist keine Antwort möglich.
A. K. schrieb: > Leo schrieb: >> Hmmmm, leider ist die Antwort nicht sehr hilfreich. Mir fehlen Zahlen > > Du lieferst ja auch keine. Das ist nämlich eine Frage der > Wahrscheinlichkeit. Also wie wahrscheinlich es sein darf, dass zwei > verschiedene Blöcke die gleiche Signatur haben. Ohne diese Angabe ist > keine Antwort möglich. du bringst es in den 4 Zeilen mal wieder genau auf den Punkt :o)
berndl schrieb: > du bringst es in den 4 Zeilen mal wieder genau auf den Punkt :o) Nicht wirklich. Denn wenn er noch ein wenig über die bizarre Aufgabenformulierung nachdenkt, dann könnte er feststellen, dass es ziemlich schwierig ist, 2^n beliebige Bits eindeutig in 2^(n-k) Bits zu codieren (k>0). ;-)
A. K. schrieb: > Nicht wirklich. Denn wenn er noch ein wenig über die bizarre > Aufgabenformulierung nachdenkt, dann könnte er feststellen, dass es > ziemlich schwierig ist, 2^n beliebige Bits eindeutig in 2^(n-k) Bits zu > codieren (k>0). ;-) oder anders rum: Er hat 8x100 Bit, also grob ein 32x32 Pixel Icon in Schwarzweiss. Und wenn jetzt ein anderes 32x32 Pixel Icon daher kommt mit einem Pixel Unterschied, das will er erkennen. Und zwar mit weniger als 32x32 Bit als Vergleichsmaske. Viel Erfolg...
>Er hat 8x100 Bit, also grob ein 32x32 Pixel Icon
Ok. Bleiben wir bei diesem Beispiel. Das Icon soll alle Farben eines
PC-Desktops annehmen können. Es soll nichts rekonstruierbar sein, einzig
und allein die Aussage, ob zwei Icons gleich sind oder nicht. Was für
eine
Prüfsumme wähle ich?
berndl, entnehme ich deiner "Schwar/Weiss"-Aussage, dass das nicht möglich ist bei Schwarz-Weiß?
Irgendwie kommen hier die Meisten vom Hundertsten ins Tausendste. Wenn ich die Fragestellung richtig verstanden habe, geht es einzig darum, mit sinnvollem Aufwand, zu überprüfen, ob Daten korrekt angekommen sind. Dabei scheint es egal zu sein, ob es sich um Daten aus einem Bild oder ein Ausschnitt aus einer komprimierten Sequenz handelt. Darüber hinaus ist auch keine Rekonstruktion vorgesehen. Dafür würde ich, bei normalen Anforderungen einen CRC verwenden. Diesen gibt es an vielen Stellen, als freien Sourcecode im Internet und er benötigt auch nicht viel Platz im Datenstrom. Ist auch bei so kurzen Blöcken sehr sicher. Benötigt aber etwas Grübelzeit.
> Was für eine Prüfsumme wähle ich?
Am einfachsten genau die 32*32*3-Byte Daten des Icons (allerhöchstens
noch durch eine Kompression durchgeschickt). Es gibt keine andere
Möglichkeit für Eindeutigkeit.
>Wenn ich die Fragestellung richtig verstanden habe, geht es einzig >darum, mit sinnvollem Aufwand, zu überprüfen, ob Daten korrekt >angekommen sind. Nein. Um beim Icon-Beispiel zu bleiben: Ich möchte anhand zweier Prüfsummen (die jeweils für ein Icon gebildet wurden) feststellen, ob die Icons gleich sind. Hier würde mich interessieren, wie ich die Prüfsumme in Abhängigkeit der Icon-Größe dimensionieren muss, um eine möglichst große Sicherheit bei der Aussage "Icon sind gleich /ungleich" zu erhalten.
>Am einfachsten genau die 32*32*3-Byte Daten des Icons
Redest Du von den Daten, die ich einer Prüfsummenberechnung unterziehen
muss?
Ich meine die Prüfsumme (24bit oder 32bit oder was auch immer).
Leo schrieb: > um eine möglichst große Sicherheit dann möglichst lang. Sag eine Zahl, wie groß soll die Fehlerwahrscheinlichkeit sein?
Programme, die z.B. Duplikate auf einer Festplatte suchen sollen, arbeiten oft Mehrstufig: 1. Dateien erfassen (Pfad und Länge). 2. Sortieren nach Länge, da nur Dateien, die gleich lang sind, auch gleich sein können. 3. Erstellen einer Prüfsumme für alle mehrfach vorkommenden Dateien. 4. Vergleichen der Prüfsummen. Dieses Verfahren hat den Vorteil, dass wenn eine "Länge" 100-fach vorkommt, nicht 100 Dateien mit den jeweils gleichgroßen verglichen werden müssen. Die Erstellung einer Prüfsumme aber erfordert nur den einmaligen Durchgang durch eine Datei und später werden nur noch Zahlen verglichen.
> Redest Du von den Daten, die ich einer Prüfsummenberechnung > unterziehen muss? Für absolute Sicherheit, ja. "möglichst große Sicherheit" hast du ja immer noch nicht spezifiziert.
Leo schrieb: > Ich möchte anhand zweier Prüfsummen (die jeweils für ein Icon gebildet > wurden) feststellen, ob die Icons gleich sind. Das geht nur, wenn du den Gesamtheit möglicher Icons kennst, oder mindestens die Anzahl, d.h. dich vorneweg auf N verschiedene Icons einschränkst. Dann benötigst du im Idealfall N Codes für die Icons und die Frage ist nur die Abbildung von Icon auf Code und ggf. die Wahrscheinlichkeit einer Fehlerkennnung. Wenn du jedoch 800 völlig beliebige Bits in weniger als 800 Bits eindeutig identifizieren willst, dann läuft das stark vereinfacht auf die Aufgabe hinaus, die Zahlen 1 bis 10 eindeutig in einem Bit speichern zu können. Klingelts jetzt? Prüfsummen und Signaturen sind dafür gebaut, die Daten zusammen damit identifizieren bzw. kontrollieren zu können. Ohne die Daten selbst sind sie sinnlos.
>dann läuft das stark vereinfacht auf >die Aufgabe hinaus, die Zahlen 1 bis 10 eindeutig in einem Bit speichern >zu können. Klingelts jetzt? Naja, der Vergleich hinkt ein wenig. Ich möchte ja nicht die Zahlen 1 bis 10 eindeutig abbilden, sondern ich möchte Folgen der Ziffern 1 bis 10 in einer Prüfsumme abbilden. Das sind doch zwei verschiedene Paar Schuhe!
Leo schrieb: > Naja, der Vergleich hinkt ein wenig. Ich möchte ja nicht die Zahlen 1 > bis 10 eindeutig abbilden, sondern ich möchte Folgen der Ziffern 1 bis > 10 in einer Prüfsumme abbilden. Das sind doch zwei verschiedene Paar > Schuhe! nein, der vergleich ist schon ok. Das ist genau das gleiche. Wenn du 100% Sicherheit brauchst, dann kannst du einfache eine CRC32 nehmen und bei gleicher Prüfsumme musst du die Daten extra noch vergleichen - anders geht es nicht.
Ok. Gibt es eine Formel, die mir ausrechnet wieviele Prüfsummen gleich sind, obwohl die Daten für die Prüfsummenberechnung unterschiedlich sind - in Abhängigkeit von Datenlänge und Prüfsummenbreite ? Damit könnte man dann eine Abwägung zwischen Aufwand und Wahrscheinlichkeit treffen...
Leo schrieb: > Gibt es eine Formel, die mir ausrechnet wieviele Prüfsummen gleich sind, > obwohl die Daten für die Prüfsummenberechnung unterschiedlich sind - in > Abhängigkeit von Datenlänge und Prüfsummenbreite ? kann man sich doch selber herleiten. Wenn die Daten 100bit sind, dann sind das 2^100 mögliche Daten. Wenn die Prüfsumme 10bit hat, dann sind das 2^10 mögliche Prüfsummen. Damist ist doch klar wie das verhätniss ist. Dabei muss man aber davon ausgehen das es gleichverteilt ist (was bei eine Prüfsumme der FAll sein sollte)
Man kanns auch mit der Gehässigkeit des Universums sehen (wie auch vieles andere an physikalischen Regeln): Wenn man eindeutig jeden beliebigen Datensatz von n Bits mit n-1 Bits beschreiben kann (nichts anderes wäre ein Vergleich der n-1 Bits als Prüfsumme), könnte man das rekursiv bis k=1 runter machen. Am Ende werden die n Bits mit nur noch einem Bit eindeutig beschrieben. Und das ist offensichtlich unmöglich ;)
Da brauchst du doch keine Formel für. Wenn du eine 8bit Prüfsumme ausrechnest hast du 256 verschieden Möglichkeiten. Bei einer 16 Bit schon 65536. Bei 2 hoch 800 verschieden Datensätzen, das will ich jetzt nicht ausrechnen, ist auf jeden fall verdammt viel :) wird es auch extrem viele gleiche Prüfsummen dafür geben. Grob überschlagen müssten eigentlich 2 hoch 784 Datensätze die gleiche 16Bit CRC ergeben. Bei 32 Bit sind es nur noch 2 hoch 768 :)
Gut, als Pragmatiker wird man dann hoffentlich feststellen, dass der Wertebereich möglicher Eingangskombinationen für die Prüfsummenberechnung wesentlich kleiner ist als der theoretische Wert. Somit steigt dann die Wahrscheinlichkeit einer korrekten Identitätsaussage dramatisch ;-) Vielen Dank für Eure Beiträge.
>Man kanns auch mit der Gehässigkeit des Universums sehen
Oder mit der meschlichen Gehässigkeit:
Versuch mal ein 32x32 Icon so zu belegen, dass du zweimal die gleiche
Prüfsumme (ähhhm sagen wir mal 16bit breit) erhälst ;-)
Leo schrieb: > Versuch mal ein 32x32 Icon so zu belegen, dass du zweimal die gleiche > Prüfsumme (ähhhm sagen wir mal 16bit breit) erhälst ;-) das ist nun kein Problem.
Wirklich nicht? Gut wenn Du natürlich programmiertechnisch in Brute-Force alle Kombinationen durchspielst, dann ja. Wenn Du aber als normaler Desktop-Benutzer das machst?
Leo schrieb: > Gut wenn Du natürlich programmiertechnisch in Brute-Force alle > Kombinationen > durchspielst, dann ja. klar so würde ich es machen. > Wenn Du aber als normaler Desktop-Benutzer das machst? spätestens wenn du mit allem Fertig bist, schafft es der erste DAU durch zufall genau das zu ereichen. Du kannst es nicht ausschließen also musst du damit umgehen können.
Schau Dir mal die Ausführungen zum CRC32 im Netz an. Der ist für so kleine Datenpakete auf jeden Fall ausreichend. Darüber hinaus ist er ausreichend, wissenschaftlich erforscht. Manche benutzen ihn sogar zur Abfrage der Authentizität.
>Du kannst es nicht ausschließen also musst du damit umgehen können.
ACK
Leo schrieb: >>Du kannst es nicht ausschließen also musst du damit umgehen können. > > ACK Hier auch ACK. D.h. was sind die Konsequenzen wenn 2 Objekte als gleich betrachtet werden, und nicht sind? Das einzige was Du machen kannst, um das auzuschliessen, ist nach jedem 'match' die Objekte vollständig zu vergleichen. Aber was ist eigentlich der Sinn? Willst Du wirklich 2 Icons, die sich nur in einem Punkt unterscheiden als verschieden betrachten? Was bringt das? Damit fallen die meisten Prüfsummen auch schon heraus.
A. K. schrieb: > Leo schrieb: ... > Prüfsummen und Signaturen sind dafür gebaut, die Daten zusammen damit > identifizieren bzw. kontrollieren zu können. Ohne die Daten selbst sind > sie sinnlos. mein reden ... einige Einträge vorher ...
dumdi dum schrieb: > Leo schrieb: >>>Du kannst es nicht ausschließen also musst du damit umgehen können. >> >> ACK > > Hier auch ACK. D.h. was sind die Konsequenzen wenn 2 Objekte als gleich > betrachtet werden, und nicht sind? So ist es. In der ursprünglichen Aufgabenstellung stand "klar identifizieren". Die Prüfsumme kann immer nur einen Hinweis darauf geben das die Datensätze gleich sind. Wegen der Abbildung von größeren Wertebereichen auf kleinere. Sicherheit kann man da per Definition nur duch den 1 zu 1 Vergleich der original Daten haben. > Das einzige was Du machen kannst, um das auzuschliessen, ist nach jedem > 'match' die Objekte vollständig zu vergleichen. so ist es. > Aber was ist eigentlich der Sinn? Willst Du wirklich 2 Icons, die sich > nur in einem Punkt unterscheiden als verschieden betrachten? Was bringt > das? Damit fallen die meisten Prüfsummen auch schon heraus. Der Wert des Ganzen ist in der Tat fraglich. Sinn kann es meiner Meinung nach nur machen wenn man eine große Anzahl an Datenblöcken hat und man Treffer daraus finden möchte. Große Tabellen mit Prüfsummen zu verwalten bedeutet aber wieder sich genau zu überlegen wie man das Beste Verhältnis zwischen Tabellengröße und Dichte der Nutzung der Tabelle erreichen kann. Für mich klingt das so als würde man die Prüfsumme als Index für eine Hashing Tabellen verwenden, was durchaus ok ist. Bei einer Hashing-Tabelle muss man aber auch immer mit Kollisionen rechnen und entsprechende Algorithmen zu deren Behandlung implementieren. Und immer benötigt man den original Datensatz damit man prüfen kann ob der Hash-Wert nicht doch für mehr als einen Datensatz gültig ist. Der Grund ist einfach das man einen Kompromiss bezüglich der verwendeten Speicherressourcen eigen muss. Wenn man das nicht müsste könnte man den Datensatz direkt als Index für die Hashing-Tabelle nutzen (es wäre dann natürlich keine mehr). Dann hat man aber keine Kollisionen, weil der Wertebereich nicht eingeschränkt wird. ... ich habe das Gefühl, langsam beginnen die Erklärungen etwas wirr zu werden ... ;-)
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.