Zeilenstufenform bilden

15.03.2025, 17:18

Malcang

Zeilenstufenform bilden

Guten Abend smile

ich habe aus der Kodieruntgstheorie diese Aufgabe:
[attach]58192[/attach]

Für Aufgabenteil a) muss ich die Matrix in (reduzierte) Zeilenstufenform bringen; Zeilentauschen ist erlaubt. Also im linken $\begin{eqnarray*} 4\times 4 \end{eqnarray*}$ Block die Einheitsmatrix $\begin{eqnarray*} E_4 \end{eqnarray*}$ bilden. Aber daran scheitere ich immer wieder...
Ich habe es mit Gauß-Algorithmus versucht. Vertauschen der ersten beiden Zeilen:
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} \end{eqnarray*}$

Addition der ersten zur vierten:
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

Addition der zweiten zur vierten:
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

Aber nun hänge ich unglücklich

Ich sehe nicht wie ich $\begin{eqnarray*} 0\; 0 \; 0 \; 1 \; x \; x \; x \end{eqnarray*}$ bilden könnte, ohne die bisher erreichte Einheitsmatrix wieder zu zerstören.
Wie kann ich hier weitermachen?

15.03.2025, 21:32

URL

Auf diesen Beitrag antworten »

RE: Zeilenstufenform bilden
Ich würde noch die vierte Zeile zur ersten addieren und anschließend vierte und fünfte Komponente vertauschen. Letztlich bekommst du durch die Permutation der Komponenten einen äquivalenten Code.
Dessen Kontrollmatrix $\begin{eqnarray*} \tilde H \end{eqnarray*}$ kann man ablesen und wenn ich mich nicht verrechnet habe, ist $\begin{eqnarray*} H=\tilde H S^T \end{eqnarray*}$ , wobei $\begin{eqnarray*} S \end{eqnarray*}$ die Permutationsmatrix ist, die die Vertauschung der Komponenten beschreibt.

16.03.2025, 11:43

Malcang

Auf diesen Beitrag antworten »

RE: Zeilenstufenform bilden
Guten morgen URL,

danke für deine Antwort, ich sehe nun die Einheitmatrix auf der linken Seite. Schätze das ich mich verrechnet habe, aber wo verwirrt

Denn mit deinen Ausführungen erhalte ich die Matrix
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

Nun vierte und fünfte Spalte tauschen:
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

und dritte zur ersten Zeile addieren:
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

Damit ist die Kontrollmatrix $\begin{eqnarray*} H = \begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

Aber leider ergibt mir $\begin{eqnarray*} H\cdot G^t \end{eqnarray*}$ nicht die Nullmatrix.

Zitat:

Original von URL
Ich würde noch die vierte Zeile zur ersten addieren und anschließend vierte und fünfte Komponente vertauschen. Letztlich bekommst du durch die Permutation der Komponenten einen äquivalenten Code.
Dessen Kontrollmatrix $\begin{eqnarray*} \tilde H \end{eqnarray*}$ kann man ablesen und wenn ich mich nicht verrechnet habe, ist $\begin{eqnarray*} H=\tilde H S^T \end{eqnarray*}$ , wobei $\begin{eqnarray*} S \end{eqnarray*}$ die Permutationsmatrix ist, die die Vertauschung der Komponenten beschreibt.

Ich habe vergessen die vierte und fünfte Spalte wieder zu tauschen Finger1

Mit der damit erhaltenen Matrix kommt in der Tat die Nullmatrix raus.

Vielen Dank URL, das hat mir sehr geholfen.
Leider habe ich bei diesem Vorgehen immer noch den Eindruck, dass ich die richtigen Zeilen oder Spalten "sehen" muss. Aber durch die Tauscherei gibt es zu viele Möglichkeiten, da verliere ich den Blick. Gibt es nicht einen Algorithmus?

16.03.2025, 12:16

Malcang

Auf diesen Beitrag antworten »

URL, könntest du mir zu den anderen Aufgaben auch sagen, ob es so korrekt ist?

b)
Die Nullspalte ist nicht enthalten, also ist das Gewicht nicht 1.
Je zwei Spalten sind nicht kollinear, also ist das Gewicht auch nicht 2.
Ich finde aber drei linear abhängige Spalten, z.B. die letzten drei. Damit ist ist $\begin{eqnarray*} d(C) = 3. \end{eqnarray*}$

c)
Ich stelle eine Tabelle auf mit der linken Spalte $\begin{eqnarray*} v \end{eqnarray*}$ (Führer der Nebenklasse) und der rechten Spalte $\begin{eqnarray*} H\cdot v^t \end{eqnarray*}$ (Syndrome). Damit erhalte ich:

$\begin{eqnarray*} 0 0 0 0 0 0 1 \;\;\; 0 0 1 \end{eqnarray*}$
$\begin{eqnarray*} 0 0 0 0 0 1 0 \;\;\; 0 1 0 \end{eqnarray*}$
$\begin{eqnarray*} 0 0 0 0 1 0 0 \;\;\; 0 1 1 \end{eqnarray*}$
$\begin{eqnarray*} 0 0 0 1 0 0 0 \;\;\; 1 0 0 \end{eqnarray*}$
$\begin{eqnarray*} 0 0 1 0 0 0 0 \;\;\; 1 0 1 \end{eqnarray*}$
$\begin{eqnarray*} 0 1 0 0 0 0 0 \;\;\; 1 1 0 \end{eqnarray*}$
$\begin{eqnarray*} 1 0 0 0 0 0 0 \;\;\; 1 1 1 \end{eqnarray*}$
$\begin{eqnarray*} 0 0 0 0 0 0 0 \;\;\; 0 0 0 \end{eqnarray*}$

d)
Es ist $\begin{eqnarray*} H\cdot(1100000)^t = 001 \end{eqnarray*}$ . Aus der Tabelle entnehme ich dazu den Führer $\begin{eqnarray*} 0000001 \end{eqnarray*}$ und bilde nun $\begin{eqnarray*} 1100000 - 0000001 = 1100001. \end{eqnarray*}$ Dies ist die MD-Dekodierung für $\begin{eqnarray*} 1100000 \end{eqnarray*}$ .

Analog erhalte ich die Dekodierung $\begin{eqnarray*} 1111000 \end{eqnarray*}$ für das Wort $\begin{eqnarray*} 1111100 \end{eqnarray*}$

16.03.2025, 14:44

URL

Auf diesen Beitrag antworten »

Zitat:

Leider habe ich bei diesem Vorgehen immer noch den Eindruck, dass ich die richtigen Zeilen oder Spalten "sehen" muss. Aber durch die Tauscherei gibt es zu viele Möglichkeiten, da verliere ich den Blick. Gibt es nicht einen Algorithmus?

Systematisch kann man das mit dem Gaußschen Algorithmus machen, wobei man in jeder Pivotspalte alles unterhalb und oberhalb des Pivotelementes zu Null macht. Dann ist eindeutig, wie man die Spalten vertauschen muss, um im linken Teil auf die Einheitsmatrix $\begin{eqnarray*} E_k \end{eqnarray*}$ zu kommen, wobei $\begin{eqnarray*} k \end{eqnarray*}$ der Rang der Matrix ist.

Aufgabenteile b) und c) sehen richtig aus.
Bei d) kann ich den Anfang nachvollziehen, hätte aber als schlussendliche Dekodierung etwas aus $\begin{eqnarray*} \mathbb Z _2 ^4 \end{eqnarray*}$ erwartet, im ersten Fall $\begin{eqnarray*} 0011 \end{eqnarray*}$ .

16.03.2025, 14:56

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Systematisch kann man das mit dem Gaußschen Algorithmus machen, wobei man in jeder Pivotspalte alles unterhalb und oberhalb des Pivotelementes zu Null macht. Dann ist eindeutig, wie man die Spalten vertauschen muss, um im linken Teil auf die Einheitsmatrix $\begin{eqnarray*} E_k \end{eqnarray*}$ zu kommen, wobei $\begin{eqnarray*} k \end{eqnarray*}$ der Rang der Matrix ist.

Aber muss ich dann nicht vorher eventuell die Spalten tauschen so, dass ich in der linken $\begin{eqnarray*} 4\times 4 \end{eqnarray*}$ -Teilmatrix vollen Rang erhalte?

Zitat:

Original von URL
Bei d) kann ich den Anfang nachvollziehen, hätte aber als schlussendliche Dekodierung etwas aus $\begin{eqnarray*} \mathbb Z _2 ^4 \end{eqnarray*}$ erwartet, im ersten Fall $\begin{eqnarray*} 0011 \end{eqnarray*}$ .

Hm, woher kommt deine Erwartung, URL?
Ich glaube das haben wir so nicht gemacht. Ich zeige dir einmal ein Beispiel aus dem Skript.
[attach]58196[/attach]
Hier sind die Ergebnisse ja genauso lang wie die Syndrome, also in dem Falle aus $\begin{eqnarray*} \mathbb Z_2^5 \end{eqnarray*}$

16.03.2025, 15:02

URL

Auf diesen Beitrag antworten »

Die Spaltenvertauschung ändert doch nichts am Rang der Matrix.
Sie dient einzig dazu, links die Einheitsmatrix zu erzeugen. Also kann man die Spaltenvertauschung auch erst am Schluss machen.
Ich habe mich von dem Begriff Dekodierung leiten lassen. Für mich ist da bisher nur eine Fehlerkorrektur passiert. Aber da mag meine Interpretation auch falsch sein. Im Beispiel wird ja von "dekodiert den Vektor[...]" gesprochen.

16.03.2025, 15:04

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Die Spaltenvertauschung ändert doch nichts am Rang der Matrix.
Sie dient einzig dazu, links die Einheitsmatrix zu erzeugen. Also kann man die Spaltenvertauschung auch erst am Schluss machen.

Aber wenn ich bei der Matrix aus dem Eingangspost direkt mit dem Gauß-Algorithmus loslege, dann erhalte ich ja eine Nullzeile im linken $\begin{eqnarray*} 4\times 4 \end{eqnarray*}$ Block. Dieser Block hat also Rang 3. Dann müsste ich also Spalten tauschen so, dass die fehlende 1 an der richtigen Stelle steht. Damit bekomme ich dann dort Rang 4. Aber dann kann es ja sein, das ich danach wieder oberhalb dieser 1 Elemente eliminieren muss.
So meinte ich das.

Zitat:

Original von URL
Ich habe mich von dem Begriff Dekodierung leiten lassen. Für mich ist da bisher nur eine Fehlerkorrektur passiert. Aber da mag meine Interpretation auch falsch sein. Im Beispiel wird ja von "dekodiert den Vektor[...]" gesprochen

Ich schaue nochmal in eine Übungsaufgabe und würde auch diese hier einmal präsentieren

16.03.2025, 15:08

URL

Auf diesen Beitrag antworten »

Deswegen sagte ich "Gaußschen Algorithmus machen, wobei man in jeder Pivotspalte alles unterhalb und oberhalb des Pivotelementes zu Null macht.". Bei anschließender Spaltenvertauschung schleppst du nur Nullen mit.

Inzwischen habe ich gelernt, dass meine Interpretation von Dekodierung von den Begriffen encoding/decoding bei Verschlüsselung getrübt war smile

16.03.2025, 15:10

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Bei anschließender Spaltenvertauschung schleppst du nur Nullen mit.

Ah ich glaube das ist der Punkt den ich nicht bedacht habe! smile

Zitat:

Inzwischen habe ich gelernt, dass meine Interpretation von Dekodierung von den Begriffen encoding/decoding bei Verschlüsselung getrübt war smile

Das heißt, meine Lösung war so korrekt?

16.03.2025, 15:11

URL

Auf diesen Beitrag antworten »