[HaBo]

valenterry

Anzeige

Bei Winrar gibt es die Option (wenn man eine Datei in mehrere Archive splittet) ein oder mehrere Rekonstruktionsarchive zu erstellen.
Wenn man nun 5 Dateien hat (1.rar 2.rar 3.rar ...), ein Rekonstruktionsarchiv hat und nun eine der 5 Dateien verloren geht, (z.B. 2.rar) kann man dieses Archiv als Ersatz benutzen. Dabei ist es völlig egal, ob 1.rar 2.rar oder welches Archiv auch immer verloren gegangen ist. Allerdings braucht man für jedes verloren gegangene Archiv auch ein Rekonstruktionsarchiv. Man kann also nicht nur ein Rekonstruktionsarchiv benutzen, wenn man 1.rar und 3.rar verloren hat. In diesem Fall braüchte man ein zweites Rekonstruktionsarchiv, was erstellt wurde.
Meine Frage ist nun, wie das mathematisch überhaupt möglich ist.

Heinzelotto

z.B. so:

hier drei archive mit jeweils 5 bit und ein rekonstruktionsarchiv:

1 2 3 | r

0 0 1 | 1
1 1 1 | 1
0 1 0 | 1
0 1 0 | 1
1 0 1 | 0

im rekonstruktionsarchiv wird jeweils die quersumme gespeichert. Wenn jetzt eins verloren geht, kann man so herausfinden, was das bit an einer beliebigen stelle im kaputten/verlorenen archiv war.
wenn z.B. archiv 2 fehlt:

z.B. bit 1:
die quersumme von bit 1 der zwei verbleibenden archive und das nicht bekannte bit 1 von archiv 2 muss ja das gleiche wie das bit 1 des rekonstruktionsarchiv sein.
also: 0 + ? + 1 = 1
dieser fall tritt nur ein, wenn das bit 1 von archiv 2 gleich 0 ist, das fehlende bit ist also 0.

und so muss mit allen bits verfahren werden

valenterry

[quote]Original von Heinzelotto
z.B. so:

hier drei archive mit jeweils 5 bit und ein rekonstruktionsarchiv:

1 2 3 | r

0 0 1 | 1
1 1 1 | 1
0 1 0 | 1
0 1 0 | 1
1 0 1 | 0

im rekonstruktionsarchiv wird jeweils die quersumme gespeichert.[quote]
Meinst du:

1 2 3 | r

0 0 1 | 1 -> 1 ist die Quersumme -> logisch
1 1 1 | 1 -> 1 ist die Quersumme -> hää? Müsste das jetzt nicht 3 sein? also eigentlich "11"?

Okay, aber wie geht das jetzt beim zweiten bit?
Kann es sein, dass du nicht die Quersumme sondern etwas anderes meinst?
Nimm doch mal bitte dezimale Zahlen, damit kann ich besser rechnen.
Und noch etwas: wie funktioniert das jetzt, wenn man 5 Archive hat, 2 Rek. Archive und 2 von den 5 normalen Archiven sind verlorengegangen?

Heinzelotto

im dezimalsystem wäre es blödsinn, weil die daten sowieso nur im dualsystem gespeichert werden.
und bei der quersumme habe ich mich nicht ganz richtig ausgedrückt, denn wenn du die quersumme hast und sie aus mehreren Ziffern besteht, dann nimmt man einfach nur die letzte Ziffer.

ich versuche es nochmal anders zu erklären:

aus einem bit (ich nenne en jetzt mal das n-te bit) der archive wird ein prüfbit errechnet, das dann an der stelle n im rekonstruktionsarchiv gespeichert wird.
d.h. zu jeweils einem bit aus allen archiven gibt es ein prüfbit im rekonstruktionsarchiv.
das bit wird folgendermaßen berechnet:
als beispiel wird das erste bit aus allen archiven genommen und das erste prüfbit erstellt:
es werden erst alle bits genommen, aus denen die "quersumme" berechnet werden soll. dann werden die darin vorkommenden einsen gezählt. wenn also die jeweils ersten bits 1001000100 sind, dann wären es 3 einsen. wenn nun die daraus entstehende zahl (3) ungerade ist, ist das prüfbit eine 1, sonst eine null (man prüft also, ob die quersumme ungerade ist. die letzte ziffer der quersumme im binärformat entscheidet über ungeradheit). so verfährt man mit allen bits der archive, man liest jeweils ein bit aus jedem archiv ein und errechnet dann die prüfsumme.

wenn jetzt ein archiv fehlt errechnet man aus den verbleibenden archiven nach der obigen methode die "quersumme" und vergleicht sie mit der quersumme aus dem rekonstruktionsarchiv. wenn sie übereinstimmt, muss das fehlende bit eine 0 gewesen sein, da eine 0 ja die quersumme nicht verändert, wenn die quersummen nicht übereinstimmen, muss es eine eins gewesen sein, wenn man sich die quersumme dann nochmal ausrechnet (mit der 1), kommt das richtige raus.

war diese erklärung besser?

valenterry

Ja, danke, viel besser! jetzt hab ichs verstanden.
Bleibt nur noch die zweite Frage, die ich gestellt habe. Diese Methode (Gerade oder ungerade) lässt sich nur durchführen, wenn man nur ein unbekanntes bit hat, sprich wenn nur ein Archiv fehlt. Wie macht es Winrar aber, dass 2 Archive fehlen und man diese mit 2 Rek. Archiven ausgleichen kann?
Deine Technik kann man ja dann so nicht mehr anwenden. Höchstens verändert.
Hier hast du mal ein vorgefertigtes Beispiel. Und nun fehlen 2 Archive (kannste dir aussuchen welche)
Wie sieht dann Rek. Archiv Nr.2 aus?

1 2 3 4 5 | R1 R2
1 1 0 1 0 | 1
0 1 0 0 0 | 1
1 1 0 0 0 | 0
1 0 1 1 1 | 0
0 0 1 1 0 | 0

0wnZ

@Heinzelotto:
Ich hoffe ich hab das jetzt richtig verstanden.
Also es wird aus jeder Datei unteranderem das erste Bit genommen und dann verglichen.
Wenn der Einsen-"Gehalt" ungerade ist, wird im Rekonstruktionsarchiv eine Eins dafür gesetzt. Wenn der Einsen-"Gehalt" gerade ist, eine Null.
Nun nehmen wir folgenden Bsp.:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 ||RA|
|---|---|---|---|---|---|---|---|---|----||----| <- 7 Einsen = 1 im RA ( Rekonstruktionsarchiv).
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 || 1 |
etc.
So jetzt ist irgend ein "unexpected error" aufegetreten, den aber keiner bemerkt. Danach sieht das Teil so aus:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 ||RA|
|---|---|---|---|---|---|---|---|---|----||----| <- 5 Einsen = 1 im RA*
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 || 1 |

* und das, obwohl die 3. und 8. Datei beschädigt sind. Dann würde aber das Rekonsturktionsarchiv denken, dass alles in Butter ist.

Wie wird das gelöst ?

Mit freundlichen Grüßen

0wnZ

valenterry

Naja, wir haben ja jetzt den Fall behandelt, dass man weiß, dass ein Archiv zerstört oder verloren gegangen ist.
Das RA soll gar nicht denken können, dass muss der User selbst können.
Wenn man eine Datei gepackt hat, in 10 Archive und Winrar meldet beim fünften Archiv einen CRC Fehler, ist mit dem Packet etwas nicht in Ordnung. Dann nimmt man das RA und setzt dieses an Stelle des fünften Archivs ein.
Das RA soll also nicht auf Fehler überprüfen, sondern nur im Falle eines vom User bemerkten Fehler, eingesetzt werden, um den Fehler zu korrigieren.

t3rr0r.bYt3

http://de.wikipedia.org/wiki/Parit%C3%A4tsbit
http://en.wikipedia.org/wiki/Parity_bit

das mal als information zum prinzip von parity bits.

was winrar da jetzt wirklich verwendet, weiß ich nicht, aber es wird bestenfalls auch nur eine weiterentwicklung dessen sein. zumindest dem hilfe-text nach hört sich das für mich sehr nach http://parchive.sourceforge.net/ an.