0 Daumen
475 Aufrufe

Aufgabe:

Wir betrachten Codes \( C \subset H\left(6, \mathbb{F}_{2}\right) \), dh. Codes der Länge 6 über \( \mathbb{F}_{2}(q=2) \).

(i) Wie groß muss der Minimalabstand \( d_{\min } \) mindestens sein, damit ein Code einen Fehler erkennt, bzw. ein Code einen Fehler korrigiert?
(ii) Für \( e=1 \) bestimme man die Anzahl der Elemente im Ball \( B_{e}(v) \) um \( v \in H\left(6, \mathbb{F}_{2}\right) \). Hinweis: Die Anzahl der Elemente des Balls vom Radius \( e \) ist gegeben als:
\( \left|B_{e}(v)\right|=\sum \limits_{i=0}^{e}\left(\begin{array}{l} n \\ i \end{array}\right)(q-1)^{i} \)
(iii) Lässt sich für \( e=1 \) ein perfekter Code in \( H\left(6, \mathbb{F}_{2}\right) \) finden?
Lösung. (i) Nach Bemerkung \( 9.1 .8 \) erkennt ein Code \( d-1 \) Fehler, wenn der Minimalabstand \( d \) ist. Für unseren Fall muss also \( d_{\min } \geq 2 \) gelten, dh. der Minimalabstand muss mindestens 2 betragen.
Ein Code korrigiert \( e \) Fehler, falls \( d_{\min } \geq 2 e+1 \) gilt (ebenfalls laut Bemerkung 9.1.8). Der Minimalabstand muss also mindestens 3 sein.
(ii) Mit \( q=2, n=6 \) und \( e=1 \) gilt
\( \left|B_{1}(v)\right|=\sum \limits_{i=0}^{1}\left(\begin{array}{l} 6 \\ i \end{array}\right)(2-1)^{i}=\left(\begin{array}{l} 6 \\ 0 \end{array}\right)+\left(\begin{array}{l} 6 \\ 1 \end{array}\right)=1+6=7 \)
(iii) Für einen perfekten Code muss gelten \( |H(n, q)|=|C| \cdot\left|B_{e}(c)\right| \). Da \( \left|B_{1}(c)\right|=7 \) nicht \( H\left(6, \mathbb{F}_{2}\right)=64 \) teilt, kann es keinen perfekten Code geben.


Problem/Ansatz:

Mir geht es primär um die ii). Die Variablenbelegungen sind soweit nachvollziehbar. Ich habe eine Frage zur Rechnung:

Wie berechne ich diese übergestellten Zahlen? Also wieso ist 6 über 0 = 1? und 6 über 1 = 6?

Falls jemand noch was zur iii) sagen könnte wäre das auch super, so wirklich verstehe ich die Lösung nicht. Insbesondere wie man da auf die 64 kommt.

Avatar von

Zu den "übergestellten" Zahlen: Informieren Dich über "Binomialkoeffizienten"

Zur Zahl 64: Schreib doch mal eine Code'Wort aus diesem Code hierhin.

Ok mache ich.

Zu iii)

Ein Codewort wäre 000000. Oder aber auch 000111. Oder auch 010101. Worauf willst du hinaus?

Du hast für das Code-Wort 6 Positionen. Auf jede Position kannst Du eine 0 oder eine 1 setzen.

Wenn Du alle Code-Wörter aufschreiben willst: Für die erste Position hast Du 2 Möglichkeiten: 0 oder 1. Wenn Du dann die 2. Position besetzt, kannst Du jeder der beiden Wort-Anfänge durch 0 oder 1 ergänzen; das liefert insgesamt 2*2 Wörter. Bei der 3. Position kannst Du jeden der bisherigen Wortanfänge durch 0 oder 1 ergänzen, macht 2*2*2 ....

Insgesamt hast Du so 2^6 Möglichkeiten.

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Erklärung zu den Binomialkoeffizienten (übergestellten Zahlen):

Die "übergestellten Zahlen" sind Binomialkoeffizienten und werden als \(\binom{n}{k}\) notiert. Sie geben die Anzahl der Möglichkeiten an, \(k\) Elemente aus einer Menge von \(n\) Elementen auszuwählen, ohne Berücksichtigung der Reihenfolge.

Die allgemeine Formel für den Binomialkoeffizienten lautet:
\( \binom{n}{k} = \frac{n!}{k! (n-k)!} \)
wobei \(n!\) (n-Fakultät) das Produkt aller positiven Ganzzahlen bis \(n\) ist.

Für \(n=6\) und \(k=0\):
\( \binom{6}{0} = \frac{6!}{0! (6-0)!} = \frac{6!}{0! 6!} = 1 \)
Da \(0!\) per Definition 1 ist, ergibt sich:
\( \frac{6!}{6!} = 1 \)

Für \(n=6\) und \(k=1\):
\( \binom{6}{1} = \frac{6!}{1! (6-1)!} = \frac{6!}{1! 5!} = 6 \)
Hier kürzen sich alle Faktoren des \(6!\) bis auf die 6 im Zähler:
\( \frac{6 \cdot 5!}{1 \cdot 5!} = 6 \)

Als Python-Code zur Berechnung der Binomialkoeffizienten:

python
import math

def binomial_coefficient(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

# Beispiel
n = 6
k_values = [0, 1]
coefficients = [binomial_coefficient(n, k) for k in k_values]
print(coefficients)
# Output: [1, 6]


Beantwortung der Teilaufgabe (ii):

Der Ball um einen Codewort \(v\) mit Radius \(e\) enthält alle Worte, die sich mit bis zu \(e\) Fehlern von \(v\) unterscheiden. Die Anzahl der Elemente im Ball \( B_{e}(v) \) wird durch die gegebene Formel berechnet:

\( \left|B_{e}(v)\right|=\sum \limits_{i=0}^{e}\binom{n}{i}(q-1)^{i} \)

Für \( e = 1, n = 6, q = 2 \):
\( \left|B_{1}(v)\right|=\sum \limits_{i=0}^{1}\binom{6}{i}(2-1)^{i} = \binom{6}{0} + \binom{6}{1} \)

Setzen wir die berechneten Binomialkoeffizienten ein:
\( \binom{6}{0} = 1 \)
\( \binom{6}{1} = 6 \)

Ergibt:
\( \left|B_{1}(v)\right| = 1 + 6 = 7 \)

Interpretation von Teil (iii):

Ein perfekter Code \(C\) in \( H(n, \mathbb{F}_2) \) muss die Bedingung erfüllen, dass die Anzahl der Elemente im Hamming-Raum \( |H(n, q)| \) genau durch die Anzahl der Kugeln \( B_e \) (Bälle) geteilt wird, die jeden möglichen Vektor \(v\) abdecken, ohne Überlappungen und Lücken.

Der Hamming-Raum \( H(6, \mathbb{F}_2) \) hat \( 2^6 = 64 \) Elemente, weil er alle möglichen Binärworte der Länge 6 enthält:

\( |H(6, \mathbb{F}_2)| = q^n = 2^6 = 64 \)

Um einen perfekten Code für \( e = 1 \) zu erhalten, müsste \( |H(6, \mathbb{F}_2)| \) durch \( \left|B_{1}(c)\right| = 7 \) teilbar sein:

\( 64 \div 7 = 9 \quad \text{R} 1 \)

Da 64 nicht durch 7 teilbar ist (es bleibt ein Rest von 1), kann kein perfekter Code existieren, da sich die Kugeln im Hamming-Raum überlappen oder leere Positionen lassen würden.

Ich hoffe, diese ausführliche Erklärung hilft dir weiter.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community