Minimalgewicht eines Codes bestimmen

10.03.2025, 20:02

Malcang

Minimalgewicht eines Codes bestimmen

Hallo Leute,

meine Fragen beziehen sich ja aktuell nur noch auf Kryptografie und Kodierungstheorie. Ich hoffe es ist in Ordnung, wenn ich jedesmal einen eigenen Thread zu einer Frage erstelle. Ansonsten: Gebt mir bitte Bescheid.

Ich habe diese Erzeugermatrix für den Code $\begin{eqnarray*} C\subset \mathbb Z_2^6 \end{eqnarray*}$ gegeben:
[attach]58182[/attach]

Nun soll ich aus einer Kontrollmatrix das Minimalgewicht bestimmen. Die Kontrollmatrix habe ich raus:
$\begin{eqnarray*} H = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1& 0&0&0&1 \end{pmatrix} \end{eqnarray*}$

Laut Definition ist[attach]58183[/attach]

Aber hier muss ich mich doch wundern. Ich würde gerne die erste Zeile -mit min - verstehen. Ist dieses Minimum denn nicht immer $\begin{eqnarray*} 1 \end{eqnarray*}$ , sobald ich überhaupt linear abhängige Spalten finde?

11.03.2025, 12:47

IfindU

Auf diesen Beitrag antworten »

Wenn du kolineare Spalten findest ja, das Gewicht ist dann 1. Es ist zugegeben etwas ungenau geschrieben. Man meint: "Es gibt eine Menge mit $\begin{eqnarray*} k \end{eqnarray*}$ Elementen aus den Spaltenvektoren und diese Menge ist linear abhängig".

Beispiel: Stell dir vor du hast die $\begin{eqnarray*} n \times n \end{eqnarray*}$ Einheitsmatrix und noch eine weitere (nicht-null) Spalte. Dann ist das Minimalgewicht immer $\begin{eqnarray*} n+1 \end{eqnarray*}$ .

11.03.2025, 18:08

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Es ist zugegeben etwas ungenau geschrieben. Man meint: "Es gibt eine Menge mit $\begin{eqnarray*} k \end{eqnarray*}$ Elementen aus den Spaltenvektoren und diese Menge ist linear abhängig".

Beispiel: Stell dir vor du hast die $\begin{eqnarray*} n \times n \end{eqnarray*}$ Einheitsmatrix und noch eine weitere (nicht-null) Spalte. Dann ist das Minimalgewicht immer $\begin{eqnarray*} n+1 \end{eqnarray*}$ .

Das verstehe ich, aber was meinst du mit

Zitat:

Original von IfindU
Wenn du kolineare Spalten findest ja, das Gewicht ist dann 1.

ich finde ja $\begin{eqnarray*} k \end{eqnarray*}$ kolineare Spalten verwirrt

11.03.2025, 18:20

IfindU

Auf diesen Beitrag antworten »

Ich dachte es kommt von co und linear. Aber offenbar wird es mit 2 L geschrieben: kollinear Hammer

Aber nicht der schlimmste Fehler von mir: Bei Kollinearität ist das Gewicht 1 oder 2.

Wenn es den Nullvektor gibt, dann ist das Gewicht 1. Wenn es das nicht gibt, und zwei Vektoren Kollinear sind, dann ist das Gewicht 2.

Kollinear heißt, es gibt zwei (Spalten-)vektoren $\begin{eqnarray*} v,w \end{eqnarray*}$ und $\begin{eqnarray*} \lambda \end{eqnarray*}$ mit $\begin{eqnarray*} v = \lambda w \end{eqnarray*}$ . Und bei dir ist es nicht der Fall. Keine Spalte ist Vielfache einer anderen Spalte. Man kann bei deinem Beispiel zeigen, dass das Gewicht $\begin{eqnarray*} 3 \end{eqnarray*}$ ist.

11.03.2025, 19:25

Malcang

Auf diesen Beitrag antworten »

Achso, ich dachte wenn ich beispielsweise 3 linear abhängige Spalten finde, dann sind diese drei kollinear.

23.03.2025, 13:30

Malcang

Auf diesen Beitrag antworten »

Hallo nochmal,

ich muss noch eine Frage stellen zu diesem Thema.
Ich habe die drei Erzeugermatrizen gegeben über $\begin{eqnarray*} \mathbb Z_5 \end{eqnarray*}$ .
[attach]58208[/attach]

Nun wollte ich die Minimalgewichte bestimmen. Die Kontrollmatrizen sind
$\begin{eqnarray*} H_1 = \begin{pmatrix} 3 & 3 & 1 & 0 \\ 1 & 4 & 0 & 1\end{pmatrix}, H_2 = \begin{pmatrix} 4 & 2 & 1 & 0 \\ 1 & 3 & 0 & 1\end{pmatrix}, H_3 = \begin{pmatrix} 4 & 4 & 1 & 0 \\ 3 & 4 & 0 & 1\end{pmatrix} \end{eqnarray*}$

Ich weiß das $\begin{eqnarray*} w(C_1) = w(C_3) = 3 \end{eqnarray*}$ und $\begin{eqnarray*} w(C_2) = 2 \end{eqnarray*}$ ist.
Das heißt, ich sollte also in $\begin{eqnarray*} C_2 \end{eqnarray*}$ drei linear abhängige Spalten finden. Aber ich habe doch ohnehin die Spalten $\begin{eqnarray*} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{eqnarray*}$ und $\begin{eqnarray*} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{eqnarray*}$ , damit ist jede weitere doch ohnehin linear abhängig verwirrt

23.03.2025, 18:07

IfindU

Auf diesen Beitrag antworten »

Nein. $\begin{eqnarray*} w(C_2) = 2 \end{eqnarray*}$ bedeutet, dass ein Vektor das Vielfache eines anderen Vektors ist. In dem Fall ist die erste Spalte das doppelte der zweiten Spalte von $\begin{eqnarray*} H_2 \end{eqnarray*}$ .

Natürlich hat jede $\begin{eqnarray*} n \times k \end{eqnarray*}$ Matrix ein Gewicht von höchstens $\begin{eqnarray*} \min (n, k) +1 \end{eqnarray*}$ . In dem Fall ist also Gewicht 3 schon das höchste was es geben kann. Und natürlich kannst du alle Vektoren nehmen und für jeden Fall $\begin{eqnarray*} n \neq k \end{eqnarray*}$ hast du $\begin{eqnarray*} k \end{eqnarray*}$ linear abhängige Vektoren gefunden. Es geht hier darum die kleinste Menge an Vektoren zu finden, welche bereits linear abhängig sind.

23.03.2025, 19:11

Malcang

Auf diesen Beitrag antworten »

Hi IfindU, vielen Dank, das hat mir sofort weitergerholfen! smile

Neue Frage »

Antworten »

Minimalgewicht eines Codes bestimmen

Verwandte Themen