wie viele Punkte liegen in der Hammingkugel B3(0,F7^4)?

Question

Aufgabe:

a) Welche Vektoren des R² liegen in der Menge

B₁ (  \( \begin{pmatrix} 0\\0 \end{pmatrix} \) ,R²) ∩ B₁(\( \begin{pmatrix} 1\\1 \end{pmatrix} \) ,R₂)

bezüglich der Metrik, die durch die 1-Norm induziert wird?

b) Wieviele Punkte liegen in der Hammingkugel B₃(0,(F₇)⁴), wobei 0 = (0,0,0,0)?

c) Sei p eine Primzahl und n ∈ N. Zeigen Sie, dass für die Hammingkugeln eines beliebigen Paares von

Vektoren v,w ∈ (F_p)ⁿ stets gilt

        |B₁ (v, (F_p)ⁿ) ∩ B₁ (w, (F_p)ⁿ) |∈ {0,2,p,1 + n·(p−1)}.

Problem/Ansatz:

F_{7} = (0,1,2,3,4,5,6) und die Tupel sollen ja aus 4  Elementen bestehen.

7^4= 2401 mögliche Kombinationen

Jetzt suchen wir jedoch die Anzahl der Tupel, die höchstens einen Hemmingabstand von 3 haben und wissen nicht wie man das berechnet.

Comments

a) Es gilt d (x,z) < r, d.h. zwei Punkte x und y sind beide positiv und in der Kugel sind x + y < r, also x + y < 1.

Daraus ergibt sich x = 1 - y und y = 1 - x.

Dann hat @lul freundlicherweise für mich geschlussfolgert, dass die Lösung "alle Vektoren (r, 1 - ) mit 0 ≤ r ≤ 1 sein müssen.

b) Anzahl Elemente in der Kugel = # alle Elemente - # Elemente die den Hemmingabstand 4 haben

# alle Elemente => 74

  = 2401 (das hat der User Darstellungsmatrix herausgefunden)

# Elemente, die den Hemmingabstand 4 haben -> Elemente, die an allen 4 Stellen keine 0 haben -> alle 4er-Kombinationen aus (1,2,3,4,5,6) => 64

Kombinationen

Lösung: #Elemente in der Kugel = 74
- 64

= 1105.
c) Hier weiß ich selbst nicht weiter, aber unser Tutor hat uns folgenden Hinweis gegeben

F3² = { \( \begin{pmatrix} 0\\0 \end{pmatrix} \) , \( \begin{pmatrix} 1\\0 \end{pmatrix} \) , \( \begin{pmatrix} 2\\0 \end{pmatrix} \) ,\( \begin{pmatrix} 0\\1 \end{pmatrix} \) , \( \begin{pmatrix} 0\\2 \end{pmatrix} \) , \( \begin{pmatrix} 1\\2 \end{pmatrix} \) , \( \begin{pmatrix} 2\\1 \end{pmatrix} \)  , \( \begin{pmatrix} 2\\2 \end{pmatrix} \)  , \( \begin{pmatrix} 1\\1 \end{pmatrix} \)  },

wobei dann gilt

\( \begin{pmatrix} 0\\3 \end{pmatrix} \)  = \( \begin{pmatrix} 0\\0 \end{pmatrix} \)

und

\( \begin{pmatrix} 3\\3 \end{pmatrix} \) =  \( \begin{pmatrix} 0\\0 \end{pmatrix} \)

und

\( \begin{pmatrix} 1\\0 \end{pmatrix} \)  + \( \begin{pmatrix} 2\\0 \end{pmatrix} \)  = \( \begin{pmatrix} 0\\0 \end{pmatrix} \)  in F3²

Keine Ahnung warum, vielleicht weil 1 +2 = 3 ergibt und 3 den Rest 0 zu 3 hat.

Wie gesagt: ab hier bin ich selbst überfordert

Answer 1

Hi,

der gute Mann heißt Hamming. Ich gehe mal davon aus, dass eure Kugel abgeschlossen ist.

Jetzt suchen wir jedoch die Anzahl der Tupel, die höchstens einen Hemmingabstand von 3 haben und wissen nicht wie man das berechnet

Es ist der Abstand vom Element (0,0,0,0) gemeint. Die Anzahl der Elemente in der Kugel entspricht der Anzahl aller Elemente minus aller Elemente, die den Hamming-Abstand 4 haben. Elemente, die den Hamming-Abstand 4 von (0,0,0,0) haben sind Elemente, die an allen 4 Stellen keine Null haben.

Gruß,

Comments

Rechtschreibung korrigiert

https://www.mathelounge.de/631001/hammingkugel-von-vektoren

---

Vielen Dank erstmal. Ich weiß nicht wie man auf diese Zahl kommt. Auf die Tupel, die an allen vier stellen keine 0 haben. Kannst du mir bitte einen Tipp geben wie man da berechnet?

---

Also ist gefragt nach allen möglichen Kombinationen von einem Tupel, das an allen 4 Stellen keine 0 hat und somit aus den Elementen 1 bis 6 besteht.

Also

(1,1,1,2)

(1,1,2,1)

(1,2,1,1)

(2,1,1,1)

(1,1,2,2)

(1,2,1,2)

....

(6,6,6,5)

(6,6,6,6)

?

---

Anzahl Elemente in der Kugel = # alle Elemente - # Elemente die den Hemmingabstand 4 haben

# alle Elemente => \( 7^{4} \)  = 2401 (habt ihr ja schon gesagt=

# Elemente, die den Hemmingabstand 4 haben -> Elemente, die an allen 4 Stellen keine 0 haben -> alle 4er-Kombinationen aus (1,2,3,4,5,6) => \( 6^{4} \) Kombinationen

Lösung: #Elemente in der Kugel = \( 7^{4} \) - \( 6^{4} \) = 1105.

Richtig, oder Kakolores?

---

Das ist richtig.