Kugeln im {0,1}^3

23.05.2016, 13:06

darius92

Auf diesen Beitrag antworten »

Kugeln im {0,1}^3

Hi

vielleicht kann mir ja jemand von euch bei meiner Aufgabe helfen, ich selbst blicke da momentan nicht so durch.

Es geht um Kugeln im Hamming Raum.Als Kugel wird hier die Menge aller Codeworte bezeichnet, die höchstens einen Hamming Abstand d von dem Kugelmittelpunkt y haben.

Ein der Aufgaben lautet: Finden Sie eine möglichst große Menge an Kugeln im {0,1}^3,sodass jeder Kugelmittelpunkt in keiner weiteren Kugel liegt.Zeigen Sie, dass ihre Auswahl maximal groß ist.
Versteht das jemand? Wäre über Hilfe sehr dankbar!

23.05.2016, 13:21

Elvis

Auf diesen Beitrag antworten »

Die Kugel um 000 mit Hamming Abstand 1 hat den Mittelpunkt 000 und die Punkte 001,010,100 . Schreibe alle Kugeln um alle 8 Elemente von {0,1}^3 auf, der Hamming Abstand kann nur 0,1,2 oder 3 sein. Wähle daraus eine maximale Menge von Kugeln, deren Mittelpunkte nicht in anderen Kugeln liegen. (Vielleicht ist das auch nur eine Scherzfrage: Für d=0 gibt es 8 Kugeln, deren Mittelpunkte nicht in anderen Kugeln liegen, mehr kann es nicht geben.)

23.05.2016, 13:33

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Die Kugel um 000 mit Hamming Abstand 1 hat den Mittelpunkt 000 und die Punkte 001,010,100 .

Wenn die Kugeln wie in der Topologie üblich nur aus den Punkten bestehen, deren Abstand vom Mittelpunkt kleiner als der Radius ist, dann würde diese Kugel nur ihren Mittelpunkt enthalten.

Könnte man nicht einfach um alle Elemente eine Kugel von einem Radius $\begin{align*} \leq 1 \end{align*}$ wählen? Jede solche Kugel würde nur ihren Mittelpunkt enthalten.

Zitat:

Original von Elvis
(Vielleicht ist das auch nur eine Scherzfrage: Für d=0 gibt es 8 Kugeln, deren Mittelpunkte nicht in anderen Kugeln liegen, mehr kann es nicht geben.)

Das war auch mein Gedanke (siehe oben). Allerdings wird für den Kugelradius in der Topologie ein Wert $\begin{align*} >0 \end{align*}$ vorausgesetzt, jedenfalls üblicherweise. Es kann natürlich sein, daß man das in der Informatik anders sieht.

23.05.2016, 13:36

darius92

Auf diesen Beitrag antworten »

Hi danke für deine Antwort,

also ich habe vergessen hinzuschreiben, dass ich eine maximale Menge von Kugeln mit Radius 1 suche. Das heißt doch, dass ich schomal keine Kugeln verwenden darf, wo der Hammingabstand der Mittelpunkte 1 beträgt, da ja dann jeweils die Mittelpunkte auf dem Rand der anderen Kugel liegen würden. Die Lösung hierbei wäre demnach die maximale Anzahl von Wörtern aus {0,1}^3, die einen Hammingabstand>=2 zueinander haben? Ich habe das Gefühl, dass kann nicht stimmen...

23.05.2016, 13:46

Leopold

Auf diesen Beitrag antworten »

Damit wir hier nicht raten müssen (siehe meinen und Elvis' vorigen Beitrag), wäre es hilfreich, wenn du uns mitteiltest, wie ihr in der Vorlesung eine Kugel präzise definiert habt: Abstand der Punkte $\begin{align*} \leq r \end{align*}$ oder $\begin{align*} <r \end{align*}$ ?

23.05.2016, 13:53

darius92

Auf diesen Beitrag antworten »

Hi,

wir haben die Kugeln in der Vorlesung so definiert:

$\begin{eqnarray*} K(y,p):= \left\{z\in \left\{0,1\right\}^n | d(y,z)<=p \right\} \end{eqnarray*}$

die Funktion d() ist der Hamming-Abstand und p in meinem Fall 1 smile

smile

Anzeige

23.05.2016, 16:20

Leopold

Auf diesen Beitrag antworten »

Man kann die Menge $\begin{align*} \{0,1\}^3 \end{align*}$ zu einer additiven Gruppe machen. Dazu identifiziert sie mit der additiven zyklischen Gruppe $\begin{align*} \mathbb{Z}_2 = \{0,1\} \end{align*}$ der Ordnung 2 und bildet das direkte Produkt $\begin{align*} G = {\mathbb{Z}_2}^3 \end{align*}$ .

Von einem Element $\begin{align*} y \in G \end{align*}$

* hat genau 1 Element den Abstand 0, nämlich $\begin{align*} y \end{align*}$
* haben genau 3 Elemente den Abstand 1, nämlich $\begin{align*} y+100,y+010,y+001 \end{align*}$
* haben genau 3 Elemente den Abstand 2, nämlich $\begin{align*} y+110,y+101,y+011 \end{align*}$
* hat genau 1 Element den Abstand 3, nämlich $\begin{align*} y+111 \end{align*}$

Insbesondere ist

$\begin{align*} K(y,1) = \left\{ y,y+100,y+010,y+001 \right\} \end{align*}$

Und das Komplement hiervon:

$\begin{align*} K(y,1)^c = \left\{ y+110,y+101,y+011,y+111 \right\} \end{align*}$

Jetzt ist auch $\begin{align*} K(y,1)^c \end{align*}$ eine Kugel vom Radius 1. Was ist deren Mittelpunkt?

23.05.2016, 16:58

darius92

Auf diesen Beitrag antworten »

Hey Leopold,

was genau meinst du mit "y+100" usw, kommt das nicht darauf an, welches y wir als Mittelpunkt wählen?.

Und warum genau ist jetzt das Komplement der ersten Kugel auch eine Kugel mit Radius 1?
Sorry, ich stehe bei dieser Aufgabe irgendwie auf dem Schlauch unglücklich

unglücklich

23.05.2016, 17:15

Leopold

Auf diesen Beitrag antworten »

Die Addition erfolgt bitweise nach der Regel 0+0=1+1=0 und 0+1=1+0=1

Beispiel:

011+101=110

Die Addition von 101 bewirkt eine Änderung im ersten und dritten Bit.

111+010=101

Die Addition von 010 bewirkt eine Änderung im zweiten Bit.

Will man also genau 1 Änderung haben (der Hamming-Abstand ist also 1), muß man entweder 100 oder 010 oder 001 addieren.

Will man genau 2 Änderungen haben (der Hamming-Abstand ist also 2), muß man entweder 110 oder 101 oder 011 addieren.

Will man genau 3 Änderungen haben (der Hamming-Abstand ist also 3), muß man 111 addieren.

Jede Kugel vom Radius 1 besitzt daher 4 Elemente. Und die restlichen Elemente bilden auch eine Kugel. Nach deren Mittelpunkt habe ich gefragt. Das wäre allerdings noch nicht die Lösung der Aufgabe. Es wird ja nicht verlangt, daß die Kugeln disjunkt sind, sondern nur, daß ihre Mittelpunkte nicht in einer der anderen Kugeln liegen.

23.05.2016, 17:51

darius92

Auf diesen Beitrag antworten »

Hey Leopold,

vielen Dank für deine mathematischen Ansätze.
Ich werde mir das nachher nochmal genauer angucken und bei Bedarf nochmal in diesem Thread Rückmelden.

Mfg

23.05.2016, 21:33

darius92

Auf diesen Beitrag antworten »

Also der Mittelpunkt des Kompementes müsste dann y+111 sein, korrekt?
Aber was bedeutet das jetzt für mich und die Aufgabe?

Das gleiche Spiel (Radius 1, maximal Große Auswahl Kugeln) soll ich auch nochmal machen, sodass die Kugeln alle disjunkt liegen. Hätte man in dem Fall nicht nur 2 Kugeln zur Auswahl nämlich y und y+111?
Zur ursprünglichen Aufgabe(Maximale Anzahl Kugeln mit Radius 1, sodass jeder Mittelpunkt in keiner weiteren Kugel liegt) wäre dann nach wie vor meine Idee, dass man alle Kugeln nimmt, deren Mittelpunkte einen Hammingabstand von mindestens 2 haben?
also y,y+110,y+101,y+011 und y+111.

23.05.2016, 22:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von darius92
dass man alle Kugeln nimmt, deren Mittelpunkte einen Hammingabstand von mindestens 2 haben?
also y,y+110,y+101,y+011 und y+111.

Das mit dem "mindestens 2" muss aber auch untereinander gelten. Hat denn y+111 von den drei Punkten y+110, y+101, y+011 diesen Mindestabstand?

23.05.2016, 22:28

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von darius92
Zur ursprünglichen Aufgabe(Maximale Anzahl Kugeln mit Radius 1, sodass jeder Mittelpunkt in keiner weiteren Kugel liegt) wäre dann nach wie vor meine Idee, dass man alle Kugeln nimmt, deren Mittelpunkte einen Hammingabstand von mindestens 2 haben?
also y,y+110,y+101,y+011 und y+111.

Sollen das die Mittelpunkte der Kugeln sein? Bitte drücke dich genauer aus.

$\begin{align*} K_1 = K(y,1) = \{ y, y+100, y+010, y+001 \} \end{align*}$

$\begin{align*} K_2 = K(y+110,1) = \{ y+110, (y+110)+100, (y+110)+010, (y+110)+001 \} = \{ y+110, y+010, y+100, y+111 \} \end{align*}$

Wir stellen erleichtert fest, daß der Mittelpunkt $\begin{align*} y \end{align*}$ von $\begin{align*} K_1 \end{align*}$ nicht in $\begin{align*} K_2 \end{align*}$ liegt und der Mittelpunkt $\begin{align*} y+110 \end{align*}$ von $\begin{align*} K_2 \end{align*}$ nicht in $\begin{align*} K_1 \end{align*}$ .

$\begin{align*} K_3 = K(y+111,1) = \{ y+111, (y+111)+100, (y+111)+010, (y+111)+001 \} = \{ y+111, y+011, y+101, y+110 \} \end{align*}$

Der Mittelpunkt $\begin{align*} y+110 \end{align*}$ von $\begin{align*} K_2 \end{align*}$ liegt aber in $\begin{align*} K_3 \end{align*}$ (und der von $\begin{align*} K_3 \end{align*}$ in $\begin{align*} K_2 \end{align*}$ )! Die Kugel $\begin{align*} K_3 \end{align*}$ stört ...

24.05.2016, 08:12

darius92

Auf diesen Beitrag antworten »

Okay danke schonmal,

auf diese Weise kann man das ja super überprüfen.
Für den Fall dass die Kugeln disjunkt dein sollen, wäre die Lösung von mir oben dann richtig?

24.05.2016, 10:46

Leopold

Auf diesen Beitrag antworten »

Der Teil mit den disjunkten Kugeln stimmt.
Und was ist nun die Lösung der anderen Aufgabe?

24.05.2016, 11:08

darius92

Auf diesen Beitrag antworten »

Hi danke für die Antwort,

das müsste dann die Menge $\begin{eqnarray*} M=\left\{ K(y,1),K(y+101,1),K(y+110,1),K(y+011,1)\right\} \end{eqnarray*}$ sein, oder?

24.05.2016, 11:26

Leopold

Auf diesen Beitrag antworten »

So sehe ich das auch.
Jetzt mußt du noch überlegen, wie du alles präsentierst. Und wie du argumentierst, daß es genau vier Kugeln gibt. Bezeichnungen und Strukturen, die nicht im Kontext der Vorlesung klar sind, mußt du präzise einführen und definieren. Sonst versteht man deine Lösung nicht.

24.05.2016, 11:46

HAL 9000

Auf diesen Beitrag antworten »

Ist zwar nicht zwingend nötig, aber manchem hilft die "räumliche" Vorstellung bzw. Einbettung:

Die acht Punkte aus $\begin{align*} \{0,1\}^3 \end{align*}$ kann man sich als Eckpunkte eines Würfels veranschaulichen, der Hamming-Abstand zweier Punkte ist dann die Anzahl Würfelkanten des kürzesten Weges zwischen zwei Punkten. Die vier Punkte einer maximalen Konfiguration mit Hammingabstand >2 bilden dann ein (reguläres) Tetraeder innerhalb dieses Würfels.

24.05.2016, 17:29

Leopold

Auf diesen Beitrag antworten »

[attach]41754[/attach]

24.05.2016, 18:58

darius92

Auf diesen Beitrag antworten »

Wow, ich danke euch beiden vielmals smile

smile

Ihr habt mir sehr geholfen Freude

Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »