0 Daumen
288 Aufrufe

ich habe folgende Teilproblemstellung:

Es existiere ein Punkt X in einem N-dimensionalen Raum. Wie viele Punkte L
liegen in der Umgebung des Punktes X, wobei die "Reichweite" der Umgebung
als Hamming-Distanz d definiert ist. (Jeder Punkt ist als in der Umgebung
definiert, welcher nicht weiter als der Hamming-Distanz d von Punkt X
entfernt ist.

Gesucht ist also eine Funktion num(N,d) = ??

Für den 2-dimensionalen Fall bin ich zum Beispiel bereits auf folgende Formel
gekommen (N=2):

num = 2(d^2 + d)

Und für den 1-dimensionalen Fall wäre es (N=1):

num = 2*d

1. Aber wie könnte die Formel für N=3 bzw. N=4 aussehen?

2. Wie sieht die allgemeine Formel für num(N,d) aus?

von

1 Antwort

0 Daumen

Für einen Hamming-Abstand von \(m\) müssen \(m\) Komponenten ersetzt werden. Es gibt \(\begin{pmatrix}n\\m\end{pmatrix}\) Möglichkeiten, die zu ersetzenden Komponenten auszuwählen. Es gibt \((|\Sigma|-1)^m\) Möglickeiten, die ausgewählten Komponenten durch andere zu ersetzen. Also gibt es \(\begin{pmatrix}n\\m\end{pmatrix}\cdot(|\Sigma|-1)^m\) Elemente mit Hamming-Abstand \(m\).

Soll der Hamming-Abstand \(\leq d\) sein, dann gibt es \(\sum_{i=0}^d \begin{pmatrix}n\\i\end{pmatrix}\cdot (|\Sigma|-1)^i\) Elemente.

von 77 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community