http://www.heise.de/newsticker/meldung/60734

Hm…

Stelle ich mir das richtig vor, dass man Linearkombinationen hier folgendermassen bildet?

Bei einer Datei, die in n Pakete zerteilt wird gibt es:

x1 * p1 + x2 * p2 … xn * pn = p.

Wobei xi aus { 0, 1 } sind, und pi die Datenpakete darstellen.
+ soll zB XOR sein, oder eine Funktion mit entsprechenden Eigenschaften.

Hat man nun eine Datei, die in 3 Pakete zerteilt wird, so kann man simpel:

(1,0,0) = p1, (0,1,0) = p2, (0,0,1) = p3 an Peers versenden, aber halt auch Dinge wie:
(1, 1, 0) = p1 XOR p2. Wenn jemand p1 schon hat kann er daraus dann p2 errechnen: (1,1,0) XOR (1,0,0) = (0,1,0) = p2.

Da man immer versucht, linear unabhaengige Mengen von Linearkombinationen runterzuladen, muss man eine unwesentlich groessere Datenmenge herunterladen, als wuerde man bloss Pakete laden (Eine Linearkombination ist ein Datenpaket + die Information, welcher Vektor benutzt wurde.) Allerdings wird die Menge der zur Uebermittlung moeglichen Pakete von n auf 2^n - 1 (Der Nullvektor ist linear abhaengig) aufgeblaeht.

Ich bin echt am Ueberlegen, ob das jetzt wirklich besser ist, oder nicht… Und wenn ja, warum?

Meint jemand, mir das erklaeren zu koennen? Ich find das echt interessant.

Mo

Technisch (mathematisch) erklaeren kann ich es nicht, aber nach dem Lesen des Artikels finde ich, dass es sich so anhoert wie diese Forward Error Correction: Die Daten von 10 Paketen werden dergestalt auf z.B. 14 Pakete verteilt, dass der Empfang von *beliebigen* 10 Paketen ausreicht, um alle Daten dazuhaben.

So wird es nicht noetig, ein bestimmtes Paket zu bekommen, um die Originaldaten komplett zu haben – es muessten schon mehrere Pakete komplett fehlen, damit es zum GAU kommt. Ausserdem ergibt sich hierdurch eine Umgehung des Flaschenhalses, dass alle das selbe Paket haben wollen, das nur einer anbietet – wenn man die Wahl zwischen mehreren komplettierenden Paketen hat, ist das Verteilungsproblem kleiner.

Wenn es nur einen Node mit einem Paket pn gibt, dann ist dieses ein rares Paket. Das bleibt es auch mit Linearkombinationen.

Nur dieser eine Node mit pn kann naemlich LKs rausschicken, die pn enthalten. Wie verringert das das Verteilungsproblem?

Hm. Desweiteren ist es nicht immer egal, welche Pakete Du empfaengst. Zusaetzliche Informationen bekommst Du nur, wenn das zusaetzlich empfangene Paket linear unabhaengig mit den anderen schon vorhandenen Paketen ist.

Wird die Datei in n Pakete zerlegt, sind nur Gruppen (Mengen) von maximal n Linearkombinationen linear unabhaengig. Und um eine Datei vollstaendig zu empfangen, brauchst Du genau n unabhaengige Linearkombinationen.

Und wenn Du eine Datei in 10 Pakete zerteilst, dann blaehst Du die Menge der moeglichen Pakete nicht auf 14 auf, sondern auf 2^n - 1 = 1023.
Und eine Datenredundanz ist *eigentlich* nicht vorhanden, ausser Du empfaengst abhaengige Linearkombinationen. Die kannst Du benutzen, um auf Fehler zu pruefen, aber Du erhaeltst keinerlei neue Informationen. (Da gibt es bessere Methoden)

Mo

Also ich hab mir das Paper nicht ganz durchgelesen, aber
ungefähr so habe ich das verstanden:

Wenn es nur einen Node mit einem Paket pn gibt, dann ist dieses ein rares Paket. Das bleibt es auch mit Linearkombinationen.

Nur dieser eine Node mit pn kann naemlich LKs rausschicken, die pn enthalten. Wie verringert das das Verteilungsproblem?

Das verringert sich dadurch, dass keine raren Pakete entstehen,
weil immer eine zufällige LK aller vorhandenen Blöcke erzeugt
wird. So kommt jedes Paket in Umlauf und die Verteilung ist
gleichmäßiger (als bei anderen Systemen, die in Abhängigkeit
von (nicht besonders relevanter) lokaler Information über
Verfügbarkeit die Pakete versenden).

Und das andere Problem, dass man nämlich auf ein bestimmtes Paket
lange wartet, das einem noch fehlt, wird dadurch gelöst, dass man
am Ende nicht eine bestimmte Linearkombination benötigt, sondern
eine beliebige, die nur linear unabhängig zum bisherigen Bestand
sein muss.

Und das andere Problem, dass man nämlich auf ein bestimmtes Paket
lange wartet, das einem noch fehlt, wird dadurch gelöst, dass man
am Ende nicht eine bestimmte Linearkombination benötigt, sondern
eine beliebige, die nur linear unabhängig zum bisherigen Bestand
sein muss.

Annahme: n = 10 (Eine Datei in 10 Paketen)
Mein Client hat Pakete 1-9. 10 Fehlt.

Ohne Linearkombinationen kann ich mit 1/10 aller moeglichen (es sind 10 moeglich) Pakete etwas anfangen. (Naemlich mit Paket 10).

Mit Linearkombinationen kann ich mit 2^9 aller moeglichen Pakete etwas anfangen (Naemlich alle Linearkombinationen mit enthaltenem 10 Paket.)
Moegliche Linearkombinationen gibt es 2^10 -1 = 1023
2^9 = 512 sind nuetzlich.
(Edit:)
512/1023 > 1/2

Respekt! Wow. Hier erklaert eine Rechnung schon einen Vorteil.

Mo

1023/512 > 1/2

und sogar > 2!

scnr

Mit Linearkombinationen kann ich mit 2^9 aller moeglichen Pakete etwas anfangen (Naemlich alle Linearkombinationen mit enthaltenem 10 Paket.)
Moegliche Linearkombinationen gibt es 2^10 -1 = 1023
2^9 = 512 sind nuetzlich.

So kannst du nur rechnen, wenn dir bereits, wie in anderen Systemen,
alle Pakete 1,…,9 vorliegen. Nur dann kannst du mit beliebigen
Vektoren, die die 10 enthalten, etwas anfangen. Das ist aber im
allgemeinen bei LKen nicht der Fall: wenn du n-1 Vektoren empfangen
hast, kann es sein, dass das Gleichungssystem, das sich daraus
für die Pakete 1,…,n-1 ergibt, noch nicht eindeutig lösbar ist
(dass das bereits eindeutig ist, kann auch vorkommen, muss aber
nicht). Bei n-1 empfangenen Vektoren wartest du also auf einen,
mit dem alle zusammen linear unababhängig sind.

Mal sehen, wieviele es davon gibt: die schreiben von
endlichen Körpern, etwa der Ordnung k. Die n-1 empfangenen
Vektoren sind linear unabhängig und ein Vektor, der mit diesen
linear unabhängig ist, muss aus dem Komplementraum U des von
den n-1 Vektoren aufgespannten Raumes ausgewählt werden.
Und jeder Vektor ungleich 0 aus U kann gewählt werden. Und U
hat Dimension 1, wird also von einem Vektor v aufgespannt,
d.h. genau die Vielfachen von v sind in der Situation nützlich.
Da der Körper Ordnung k hat, helfen hier k-1 Vektoren,
in deinem Beispiel, (wo du ja k=2 und den Körper [img]http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BZ%7D%2F2%5Cmathbb%7BZ%7D[/img]
verwendet hast), also nur genau 1 Vektor. Deshalb sollte man hier
wohl auch etwas größere Körper nehmen (auch schon deshalb, damit
die Wahrscheinlichkeit, einen Vektor mehrfach zu versenden
(und damit linear abhängige Vektoren) geringer wird).

EDIT: In dem Paper steht ja, dass in der Praxis wohl Körper
der Größe 2^16 eingesetzt werden, also sind 2^16-1 Vektoren
nützlich. Interessanterweise hängt die Zahl der nützlichen
Vektoren im letzten Schritt nicht von der Zahl der Blöcke ab.

1023/512 > 1/2

und sogar > 2!

nein.

scnr

Mit Linearkombinationen kann ich mit 2^9 aller moeglichen Pakete etwas anfangen (Naemlich alle Linearkombinationen mit enthaltenem 10 Paket.)
Moegliche Linearkombinationen gibt es 2^10 -1 = 1023
2^9 = 512 sind nuetzlich.

So kannst du nur rechnen, wenn dir bereits, wie in anderen Systemen,
alle Pakete 1,…,9 vorliegen. Nur dann kannst du mit beliebigen
Vektoren, die die 10 enthalten, etwas anfangen. Das ist aber im
allgemeinen bei LKen nicht der Fall: wenn du n-1 Vektoren empfangen
hast, kann es sein, dass das Gleichungssystem, das sich daraus
für die Pakete 1,…,n-1 ergibt, noch nicht eindeutig lösbar ist
(dass das bereits eindeutig ist, kann auch vorkommen, muss aber
nicht). Bei n-1 empfangenen Vektoren wartest du also auf einen,
mit dem alle zusammen linear unababhängig sind.

In der Tat kann ich so nur in einem Spezialfall rechnen. Ich frage mich aber, ob nicht dieser Spezialfall gleich dem Allgemeinfall ist.

mit n-1 empfangenen linear unabhaengigen Vektoren kann ich selbst wiederrum 2^(n-1)-1 verschiedene Linearkombinationen bilden.
Das ist aber wiederrum genau die Haelfte -1. Also: Wenn die Datei in 10 Pakete unterteilt ist, und ich 9 Linearkombinationen schon habe, dann sind wieder (2^10-1) - (2^9-1) = 512 nuetzlich fuer mich.

QED

Uebrigens: In einem n-dimensionalen Vektorraum brauchst Du n linear unabhaengige Vektoren, um den Raum aufzuspannen.
Wenn Du nicht n linear unabhaengige Vektoren hast, dann kannst Du das homogene Gleichungssystem auch nicht eindeutig loesen. (Wobei… Wie ist denn das bei dem binaeren Koerper… *gruebel*)

Mo

Mal sehen, wieviele es davon gibt: die schreiben von
endlichen Körpern, etwa der Ordnung k. Die n-1 empfangenen
Vektoren sind linear unabhängig und ein Vektor, der mit diesen
linear unabhängig ist, muss aus dem Komplementraum U des von
den n-1 Vektoren aufgespannten Raumes ausgewählt werden.
Und jeder Vektor ungleich 0 aus U kann gewählt werden. Und U
hat Dimension 1, wird also von einem Vektor v aufgespannt,
d.h. genau die Vielfachen von v sind in der Situation nützlich.
Da der Körper Ordnung k hat, helfen hier k-1 Vektoren,
in deinem Beispiel, (wo du ja k=2 und den Körper [img]http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BZ%7D%2F2%5Cmathbb%7BZ%7D[/img]
verwendet hast), also nur genau 1 Vektor.

aeh. Nicht nur alle Vielfachen ki*v != 0, sondern auch fuer alle i,j ki*v + LKj. Wobei LKj alle Linearkombinationen aus dem schon bekannten Raum sind, und ki*v != 0 sein muss.

Beispiel fuer den binaeren Koerper und n = 3:
Es gibt 2^3 = 8 Linearkombinationen. Wenn ich schon 2 unabhaengige davon habe, kann ich mir 2^2 = 4 schon errechnen.

Angenommen ich habe schon
(1,0,0) und (0,1,0), so kann ich noch mit
(0,0,1) oder (1,0,1) oder (1,1,1) oder (0,1,1) etwas anfangen. (Also mit 4 ;) Und 4 != 1)
In diesem trivialen Fall kann man also sehen, dass das 3 Bit gesetzt sein muss.

Mo

Und: Was ist eigentlich ein Komplementaerraum? Der Gesamtraum Minus den Untervektorraum? Das ergibt selbst keinen Vektorraum mehr. (Der Nullvektor fehlt).

Und wenn Du diesen anderen Raum der Dimension 1 in dem Beispiel unten wirklich meinst (Der Raum steht senkrecht auf dem anderen, richtig?), wieso muss dann daraus der Vektor gewaehlt werden? Es gibt wesentlich mehr unabhaengige moegliche LKs.

Mo

Und: Was ist eigentlich ein Komplementaerraum? Der Gesamtraum Minus den Untervektorraum? Das ergibt selbst keinen Vektorraum mehr. (Der Nullvektor fehlt).

Der Komplementärraum zu einem Untervektorraum ist ein UVR derart, dass
- beide haben bis auf den Nullvektor keine gemeinsamen Elemente
- gemeinsam spannen sie den gasamten VR auf.

…. Die n-1 empfangenen
Vektoren sind linear unabhängig und ein Vektor, der mit diesen
linear unabhängig ist, muss aus dem Komplementraum U des von
den n-1 Vektoren aufgespannten Raumes ausgewählt werden.
…

aeh. Nicht nur alle Vielfachen ki*v != 0, sondern auch fuer alle i,j ki*v + LKj. Wobei LKj alle Linearkombinationen aus dem schon bekannten Raum sind, und ki*v != 0 sein muss.

Achja, natürlich. Da hast du recht. (Alle Vektoren aus U sind
nützlich, aber es gibt auch nützliche außerhalb von U).
Es sind genau die nützlich, die man aus den n-1
Vektoren nicht erzegen kann, also [img]http://mokrates.de/cgi-bin/texstring?k%5En-k%5E%7Bn-1%7D%3Dk%5E%7Bn-1%7D(k-1)[/img]
Stück. Das Verhältnis der nützlichen Vektoren zu allen ist also
[img]http://mokrates.de/cgi-bin/texstring?%5Cfrac%7Bk%5E%7Bn-1%7D(k-1)%7D%7Bk%5En%7D%3D%5Cfrac%7Bk-1%7D%7Bk%7D[/img].
Im Fall k=2 nützt einem also tatsächlich die Hälfte. Und bei
größeren Körpern sogar noch mehr.

Angenommen ich habe schon
(1,0,0) und (0,1,0), so kann ich noch mit
(0,0,1) oder (1,0,1) oder (1,1,1) oder (0,1,1) etwas anfangen. (Also mit 4 ;) Und 4 != 1)
In diesem trivialen Fall kann man also sehen, dass das 3 Bit gesetzt sein muss.

Ja, in dem Fall ist es sowohl richtig, dass jeder nützliche Vektor
das 3. Bit gesetzt hat als auch, dass jeder Vektor mit gesetztem 3.
Bit nützlich ist. Das ist aber natürlich nicht immer so (oder was
wolltest du damit sagen?), denn das Beispiel
(1,1,0), (1,0,1)
zeigt, dass dir dort (0,1,1) wenig bringt (denn der läßt sich
bereits erzeugen). Dieses Beispiel zeigt auch, dass es keine
Position mit der Eigenschaft gibt, dass lineare Unabhängigkeit
erreicht ist, sobald dort eine 1 steht, denn jeder Vektor, der
zwei Einsen enthält, läßt sich bereits erzeugen.

Und wenn Du diesen anderen Raum der Dimension 1 in dem Beispiel unten wirklich meinst (Der Raum steht senkrecht auf dem anderen, richtig?),

Ja, den meinte ich. Ein Komplementärraum von V muss nicht senkrecht
auf V stehen, der Orthogonalraum ist nur ein möglicher Komplementär-
raum. Bei obigem Beispiel (1,1,0), (1,0,1) ist der von (1,0,0)
aufgespannte Raum U komplementär (denn (1,0,0) ist linear
unabhängig mit den anderen), aber (1,0,0) steht im Standard-
Skalarprodukt nicht senkrecht auf den anderen.

Uebrigens: In einem n-dimensionalen Vektorraum brauchst Du n linear unabhaengige Vektoren, um den Raum aufzuspannen.
Wenn Du nicht n linear unabhaengige Vektoren hast, dann kannst Du das homogene Gleichungssystem auch nicht eindeutig loesen.
(Wobei… Wie ist denn das bei dem binaeren Koerper… *gruebel*)

Das ist bei jedem Körper so: hat man n'<n linear unabhängige
Vektoren, dann spannen sie einen n'-dimensionalen Raum auf,
d.h. der Bildraum der Matrix, die das Gleichungssystem beschreibt,
hat Dimension n'. Die Dimension des Lösungsraums und die des
Bildraums addieren sich aber zu n (Dimensionsformel für lineare
Abbildungen), d.h. der Lösungsraum hat Dimension n-n'>0. Also
gibt es mehrere Lösungen für das homogene Gleichungssystem
(das zu dem inhomogenen, das man eigentlich behandelt, gehört).

1023/512 > 1/2

und sogar > 2!

nein.

scnr

… und ich hab ungefähr hundertmal draufgekuckt und nachgerechnet, bevor ich das gepostet hab …

Tjaja,… Weil Du wahrscheinlich verstanden hast, was ich eigentlich gemeint habe, und dann vergessen hast das > umzudrehen ;))

Mo