Richtige Prüfsumme ermitteln

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.

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é

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.

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.

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)

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.

>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).

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.

>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)

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