Minimaler Hamming-Abstand bei gegebenem n und l [Codierungstheorie]

22.07.2015, 03:44

spookylemon

Minimaler Hamming-Abstand bei gegebenem n und l [Codierungstheorie]

Hallo liebes Forum,

ich bin neu hier und hoffe mal, dass ich den richtigen Bereich für meine Frage gefunden habe. :)

Ich lerne gerade für meine Codierungstheorie-Klausur und habe eine Frage zum minimalen Hamming-Abstand eines Codes. Wie lässt sich der minimale Hamming-Abstand berechnen, wenn n und l des Codes vorgegeben sind? Ich habe das Gefühl, dass die Antwort eigentlich offensichtlich sein sollte, aber irgendwie fällt mir keine einfache Lösung ein.

Konkretes Beispiel: Ich habe einen Code mit $\begin{eqnarray*} n = 15 \end{eqnarray*}$ , $\begin{eqnarray*} l = 10 \end{eqnarray*}$ und $\begin{eqnarray*} k = n - l = 5 \end{eqnarray*}$ , gesucht ist $\begin{eqnarray*} d_{min} \end{eqnarray*}$ .

Das ist mein Lösungsweg:

Mir kam die Idee, in $\begin{eqnarray*} k \geq ld \sum\limits_{i=0}^{f_k} {n \choose i} \end{eqnarray*}$ einfach Werte für $\begin{eqnarray*} f_k \end{eqnarray*}$ durchzuprobieren, bis die Ungleichung nicht mehr erfüllt ist.

Für $\begin{eqnarray*} f_k = 1 \end{eqnarray*}$ ergibt sich
$\begin{eqnarray*} ld \sum\limits_{i=0}^{1} {n \choose i} = ld(\frac{15!}{15!} + \frac{15!}{14!}) = ld(1 + 15) = 4 \leq k \end{eqnarray*}$
und ist demnach wahr.

Für $\begin{eqnarray*} f_k = 2 \end{eqnarray*}$
$\begin{eqnarray*} ld \sum\limits_{i=0}^{2} {n \choose i} = ld(\frac{15!}{15!} + \frac{15!}{14!} + \frac{15!}{13!}) = ld(1 + 15 + 15 \cdot 14) = ld(226) = 7,8 \nleq k \end{eqnarray*}$
Die Ungleichung ist nicht erfüllt, daher weiß ich, dass $\begin{eqnarray*} f_k = 1 \end{eqnarray*}$ sein muss. Damit kann ich dann $\begin{eqnarray*} d_{min} \end{eqnarray*}$ berechnen:

Aus $\begin{eqnarray*} f_k = \lfloor{\frac{d_{min} - 1}{2}} \rfloor \end{eqnarray*}$ folgt, dass $\begin{eqnarray*} d_{min} = 3 \end{eqnarray*}$ oder $\begin{eqnarray*} d_{min} = 4 \end{eqnarray*}$ ist, was laut Lösung korrekt ist. Mein Problem ist nun, dass ich mir nicht vorstellen kann, dass mein Lösungsweg der richtige oder einfachste Weg ist. Also, geht das auch irgendwie einfacher?

Vielen Dank schon mal für jede Hilfe. :)

22.07.2015, 22:04

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

ich tu mich etwas schwer deine Ausführungen zu lesen, denn du erklärst nicht was deine Buchstaben bedeuten sollen.
Du betrachtest einen linearen, binären (n.l)-Code?

Zitat:

$\begin{eqnarray*} k \geq ld \sum\limits_{i=0}^{f_k} {n \choose i} \end{eqnarray*}$

Ich vermute, dass soll die Hamming/Kugelpackungsschranke sein?
Dann ist das durchaus ein sinnvoller Weg.

Zitat:

$\begin{eqnarray*} ld \sum\limits_{i=0}^{2} {n \choose i} = ld(\frac{15!}{15!} + \frac{15!}{14!} + \frac{15!}{13!}) \end{eqnarray*}$

Der dritte Summand im Logarithmus ist falsch. Bitte schlag nach wie Binomialkoeffizienten definiert sind.

Zitat:

der richtige oder einfachste Weg ist.

Es gibt praktisch nie so etwas wie "den" richtigen Weg. Viele Wege füren nach Rom.
Und wie viel einfacher als zwei kleine Gleichungen berechnen soll es denn werden?

23.07.2015, 19:03

spookylemon

Auf diesen Beitrag antworten »

Hallo Captain Kirk,

danke für die Antwort. :)

Zitat:

ich tu mich etwas schwer deine Ausführungen zu lesen, denn du erklärst nicht was deine Buchstaben bedeuten sollen. Du betrachtest einen linearen, binären (n.l)-Code?

Oh, entschuldige bitte, das wollte ich noch geschrieben haben, habe es aber offensichtlich vergessen. Ja, ein binärer (n,l)-Code. Ist es hier üblich, den Ausgangspost zu editieren, damit spätere Leser die Frage besser verstehen können?

Zitat:

$\begin{eqnarray*} k \geq ld \sum\limits_{i=0}^{f_k} {n \choose i} \end{eqnarray*}$

Ich vermute, dass soll die Hamming/Kugelpackungsschranke sein?
Dann ist das durchaus ein sinnvoller Weg.

Ja, die Hamming-Schranke.

Zitat:

$\begin{eqnarray*} ld \sum\limits_{i=0}^{2} {n \choose i} = ld(\frac{15!}{15!} + \frac{15!}{14!} + \frac{15!}{13!}) \end{eqnarray*}$

Der dritte Summand im Logarithmus ist falsch. Bitte schlag nach wie Binomialkoeffizienten definiert sind.

Stimmt, Flüchtigkeitsfehler. $\begin{eqnarray*} ld \sum\limits_{i=0}^{2} {n \choose i} = ld(\frac{15!}{15!} + \frac{15!}{14!} + \frac{15!}{2! \cdot 13!}) = ld(1 + 15 + 105) = ld(121) = 6,9 \nleq k \end{eqnarray*}$

Zitat:

Es gibt praktisch nie so etwas wie "den" richtigen Weg. Viele Wege füren nach Rom.
Und wie viel einfacher als zwei kleine Gleichungen berechnen soll es denn werden?

Nun ja. Es sind ja nur in diesem Fall zwei Gleichungen. Wenn die Hamming-Distanz größer wäre als in diesem Fall, müsste man ja noch deutlich mehr Werte für $\begin{eqnarray*} f_k \end{eqnarray*}$ durchprobieren.

In meinem Lehrbuch steht nur, dass ein direkter Zusammenhang zwischen der Hamming-Distanz und der Anzahl der Kontrollstellen $\begin{eqnarray*} k \end{eqnarray*}$ (im Verhältnis zur Gesamtlänge der Kodeworte) besteht, aber ich habe keine Formel gefunden, über die man $\begin{eqnarray*} d_{min} \end{eqnarray*}$ direkt aus $\begin{eqnarray*} k \end{eqnarray*}$ berechnen kann. Wenn die Hamming-Distanz beispielsweise 11 wäre, müsste man sechs Formeln durchprobieren, bis man $\begin{eqnarray*} f_k \end{eqnarray*}$ kennt und die Hamming-Distanz berechnen kann. Das funktioniert zwar offenbar, aber ich wollte halt gerne wissen, ob es einen direkten Weg gibt.

Neue Frage »

Antworten »

Minimaler Hamming-Abstand bei gegebenem n und l [Codierungstheorie]

Verwandte Themen