Lineare Codierung < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:17 Sa 17.12.2011 | | Autor: | Amiaz |
| Aufgabe | (Lineare Codierung) Zur Verschlüsselung von Information, die als langer Strom von
Nullen und Einsen gegeben ist, fasst man je n aufeinander folgende Bits zu einem x [mm] \in \IF_{2} [/mm] (n) (wie bekomm ich das n hinter das F hochgestellt?)
zusammen
und codiert die Spalte x als F(x) := Ax mit einer festen Matrix A [mm] \in \IF_{2} [/mm] m x n
. Natürlich möchte man
korrekt decodieren können, d.h. eine Abbildung F' : [mm] \IF_{2} [/mm] (m)--> [mm] \IF_{2} [/mm] (n)
haben mit F' [mm] \circ [/mm] F = [mm] id\IF_{2} [/mm] (n)
a) Bestimmen Sie zu
(0111)
A= (1110)
(0100)
(1011)
eine Matrix A' [mm] \in \IF_{2} [/mm] (4x4) so dass F'(y):= die gewünschte Eigenschaft hat.
b) Zeigen Sie: Eine lineare Abbildung F' wie oben gibt es genau dann, wenn rg(A) = n gilt.
(Sie k¨onnen nicht m = n voraussetzen. Zum Beispiel haben in Codes zur Fehlerkorrektur die
Codewörter immer eine größere Länge als die Informationswörter, d.h. hier ist m > n.) |
Kann mir da jemand vielleicht sagen wie ich da ansetzen soll?! Hab da irgendwie voll keine Ahnung!
|
|
| |
|
> (Lineare Codierung)
> Zur Verschlüsselung von Information, die als langer Strom von
> Nullen und Einsen gegeben ist, fasst man je n aufeinander
> folgende Bits zu einem x [mm]\in \IF_{2}[/mm] (n) (wie bekomm ich
> das n hinter das F hochgestellt?)
anstatt mit Tiefstrich (_) tiefstellen mit Hoch-Symbol (^) hochstellen.
> zusammen
> und codiert die Spalte x als F(x) := Ax mit einer festen
> Matrix A [mm]\in \IF_{2}[/mm] m x n
> . Natürlich möchte man
> korrekt decodieren können, d.h. eine Abbildung F' :
> [mm]\IF_{2}[/mm] (m)--> [mm]\IF_{2}[/mm] (n)
> haben mit F' [mm]\circ[/mm] F = [mm]id\IF_{2}[/mm] (n)
> a) Bestimmen Sie zu
>
> $\ A\ =\ [mm] \pmat{0&1&1&1\\ 1&1&1&0\\0&1&0&0\\1&0&1&1}$
[/mm]
> eine Matrix A' [mm]\in \IF_{2}[/mm] (4x4) so dass F'(y):= die
> gewünschte Eigenschaft hat.
In diesem Fall (m=n) müsste dies einfach die zu A inverse Matrix sein.
> b) Zeigen Sie: Eine lineare Abbildung F' wie oben gibt es
> genau dann, wenn rg(A) = n gilt.
> (Sie können nicht m = n voraussetzen. Zum Beispiel haben
> in Codes zur Fehlerkorrektur die
> Codewörter immer eine größere Länge als die
> Informationswörter, d.h. hier ist m > n.)
> Kann mir da jemand vielleicht sagen wie ich da ansetzen
> soll?! Hab da irgendwie voll keine Ahnung!
Im Fall m>n und rg(A)=n müsste man wohl eine Menge
von genau n linear unabhängigen Zeilenvektoren der
Matrix A herauspicken und zu einer [mm] n\times{n} [/mm] - Matrix C
zusammenfassen, um darauf bauend eine inverse
Abbildung zu bestimmen.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:06 So 18.12.2011 | | Autor: | Amiaz |
> In diesem Fall (m=n) müsste dies einfach die zu A inverse
> Matrix sein.
Habe ich durch Zeilenumformungen etc nun rausbekommen :)
> > b) Zeigen Sie: Eine lineare Abbildung F' wie oben gibt es
> > genau dann, wenn rg(A) = n gilt.
> > (Sie können nicht m = n voraussetzen. Zum Beispiel
> haben
> > in Codes zur Fehlerkorrektur die
> > Codewörter immer eine größere Länge als die
> > Informationswörter, d.h. hier ist m > n.)
> > Kann mir da jemand vielleicht sagen wie ich da ansetzen
> > soll?! Hab da irgendwie voll keine Ahnung!
>
> Im Fall m>n und rg(A)=n müsste man wohl eine Menge
> von genau n linear unabhängigen Zeilenvektoren der
> Matrix A herauspicken und zu einer [mm]n\times{n}[/mm] - Matrix C
> zusammenfassen, um darauf bauend eine inverse
> Abbildung zu bestimmen.
>
> LG Al-Chw.
>
Irgendwie seh ich noch nicht wie ich das zeigen soll...
Ich greif mir nun einfach n-beliebig viele linear unabhängige Vektoren, schreib die in eine Matrix und mach dann das in a? Und was genau bewirkt, dass m > n ist?
|
|
|
| |
|
>
> > In diesem Fall (m=n) müsste dies einfach die zu A inverse
> > Matrix sein.
>
> Habe ich durch Zeilenumformungen etc nun rausbekommen :)
> > > b) Zeigen Sie: Eine lineare Abbildung F' wie oben gibt es
> > > genau dann, wenn rg(A) = n gilt.
> > > (Sie können nicht m = n voraussetzen. Zum Beispiel
> > haben
> > > in Codes zur Fehlerkorrektur die
> > > Codewörter immer eine größere Länge als die
> > > Informationswörter, d.h. hier ist m > n.)
> > > Kann mir da jemand vielleicht sagen wie ich da
> ansetzen
> > > soll?! Hab da irgendwie voll keine Ahnung!
> >
> > Im Fall m>n und rg(A)=n müsste man wohl eine Menge
> > von genau n linear unabhängigen Zeilenvektoren der
> > Matrix A herauspicken und zu einer [mm]n\times{n}[/mm] - Matrix
> C
> > zusammenfassen, um darauf bauend eine inverse
> > Abbildung zu bestimmen.
> >
> > LG Al-Chw.
> >
> Irgendwie seh ich noch nicht wie ich das zeigen soll...
> Ich greif mir nun einfach n-beliebig viele linear
> unabhängige Vektoren, schreib die in eine Matrix und mach
> dann das in a? Und was genau bewirkt, dass m > n ist?
Machen wir am besten ein Beispiel, etwa mit m=7 und n=4
und der Matrix
$ \ A\ =\ [mm] \pmat{\red{0} & \red{1} & \red{1} & \red{1}\\ 1&1&1&1\\ \red{1}&\red{1}&\red{1}&\red{0}\\ \red{0}&\red{1}&\red{1}&\red{0}\\1&0&0&0\\ 0&1&0&1\\ \red{1}&\red{1}&\red{0}&\red{0}} [/mm] $
Ich habe darin vier Zeilen rot markiert (die erste, dritte,
vierte und siebte), die linear unabhängig sind. Zu einer
Matrix B zusammengefasst:
$ \ B\ =\ [mm] \pmat{\red{0} & \red{1} & \red{1} & \red{1}\\ \red{1}&\red{1}&\red{1}&\red{0}\\ \red{0}&\red{1}&\red{1}&\red{0}\\ \red{1}&\red{1}&\red{0}&\red{0}} [/mm] $
Die dazu inverse Matrix ist
$ \ [mm] B^{-1}\ [/mm] =\ [mm] \pmat{0&1&-1&0\\0&-1&1&1\\0&1&0&-1\\1&0&-1&0} [/mm] $
Da wir in [mm] \IF_2 [/mm] rechnen, ist dies natürlich gleichbedeutend
mit
$ \ [mm] B^{-1}\ [/mm] =\ [mm] \pmat{0&1&1&0\\0&1&1&1\\0&1&0&1\\1&0&1&0} [/mm] $
Erhalten wir nun eine codierte Bitsequenz wie z.B.
100111010011010011001
so teilen wir diese zunächst in Siebnergruppen ein (m=7) :
1001110 1001101 0011001 (***)
Von diesen Gruppen brauchen wir für die Decodierung (ohne
Fehlerkontrolle oder gar Fehlerkorrektur) wegen der obigen
Auswahl der unabhängigen Zeilenvektoren jeweils nur das
erste, dritte, vierte und siebte Bit:
1010 1011 0111
Nun werden diese Vektoren mittels [mm] B^{-1} [/mm] zurücktransformiert:
[mm] $\pmat{0&1&1&0\\0&1&1&1\\0&1&0&1\\1&0&1&0}*\pmat{1\\0\\1\\0}\ [/mm] =\ [mm] \pmat{1\\1\\0\\0}\ [/mm] =\ [mm] v_1$
[/mm]
[mm] $\pmat{0&1&1&0\\0&1&1&1\\0&1&0&1\\1&0&1&0}*\pmat{1\\0\\1\\1}\ [/mm] =\ [mm] \pmat{1\\0\\1\\0}\ [/mm] =\ [mm] v_2$
[/mm]
[mm] $\pmat{0&1&1&0\\0&1&1&1\\0&1&0&1\\1&0&1&0}*\pmat{0\\1\\1\\1}\ [/mm] =\ [mm] \pmat{0\\1\\0\\1}\ [/mm] =\ [mm] v_3$
[/mm]
Aneinandergefügt ergeben diese Vektoren die Ur-Bitfolge:
110010100101
(die z.B. in Hex-Darstellung auch als "CA5" geschrieben werden könnte)
Zur Kontrolle:
$\ [mm] A*v_1\ [/mm] =\ [mm] \pmat{1&0&0&1&1&1&0 }^T$ [/mm]
$\ [mm] A*v_2\ [/mm] =\ [mm] \pmat{1&0&0&1&1&0&1 }^T$ [/mm] ( siehe (***) ! )
$\ [mm] A*v_3\ [/mm] =\ [mm] \pmat{0&0&1&1&0&0&1 }^T$
[/mm]
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:57 So 18.12.2011 | | Autor: | NeverGod |
Mit anderen Worten, selbst wenn wir eine Matrix bekommen, dessen Rang am Anfang größer scheint als die Spaltenzahl, so muss es möglich sein in der reduzierten Zeilenstufenform (Gauss-Elimination) in eine quadratische Matrix zu kommen. Die Nullzeilen fallen dabei weg. Die Zeilennummer der wegfallenden Zeilen ist jedoch wichtig, da der verschlüsselte code länger ist, als unsere reduzierte matrix. Daher muss der code in "m" abschnitte unterteilt werden und an der stelle der nullzeile die zahl rausgestrichen werden. Zum entschlüsseln wird die inverse matrix benötigt. Hierzu am besten Lös(A|E) solange umformen, bis du [mm] (E|A^{-1}) [/mm] erhälst.
Bitte um feedback, ob ich das richtig verstanden habe, auch ggf. ob es effizienter geht, das inverse zu finden.
|
|
|
| |
|
> Mit anderen Worten, selbst wenn wir eine Matrix bekommen,
> dessen deren Rang am Anfang größer scheint als die Spaltenzahl, ![[haee]](/images/smileys/haee.gif "[haee]")
Der Rang kann nicht höher als die Spaltenzahl sein !
Nur die Zeilenzahl ist größer als die Spaltenzahl.
Es wird vorausgesetzt, dass der Rang maximal,
also gleich der Anzahl n der Spalten ist.
> so muss es möglich sein in der reduzierten
> Zeilenstufenform (Gauss-Elimination) in eine quadratische
> Matrix zu kommen. Die Nullzeilen fallen dabei weg. Die
> Zeilennummer der wegfallenden Zeilen ist jedoch wichtig, da
> der verschlüsselte code länger ist, als unsere reduzierte
> matrix. Daher muss der code in "m" abschnitte unterteilt
> werden
besser: in Abschnitte der Länge m
> und an der stelle der nullzeile die zahl
> rausgestrichen werden. Zum entschlüsseln wird die inverse
> matrix benötigt. Hierzu am besten Lös(A|E) solange
> umformen, bis du [mm](E|A^{-1})[/mm] erhältst.
> Bitte um feedback, ob ich das richtig verstanden habe,
Ich denke, ja.
> auch ggf. ob es effizienter geht, das Inverse zu finden.
Zur Bestimmung der inversen Matrix gibt es verschiedene
Verfahren. Ohne besondere Hilfsmittel ist wohl dein Weg
OK. Es gibt aber auch online-Hilfsmittel wie etwa:
http://www.arndt-bruenner.de/mathe/scripts/inversematrix.htm
Bei deinen Beispielen in [mm] \IF_2 [/mm] musst du dann natürlich die
Reduktion aufs Binärsystem selber vornehmen. Das ist aber
einfach:
gerade Zahl ---> 0
ungerade Zahl ---> 1
Ich habe aber gerade noch etwas gemerkt: Eine nur
aus Nullen und Einsen bestehende quadratische
Matrix ist über [mm] \IF_2 [/mm] nicht unbedingt invertierbar,
falls die genau gleich aussehende Matrix über [mm] \IQ
[/mm]
invertierbar ist !
Beispiel:
[mm] $\pmat{0&1&1\\1&0&1\\1&1&0}$ [/mm] ist über [mm] \IQ [/mm] regulär und damit invertierbar,
aber über [mm] \IF_2 [/mm] ist die dritte Zeile die Summe aus der
ersten und zweiten, d.h. die Zeilenvektoren sind
linear abhängig und deshalb die Matrix nicht in-
vertierbar.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:00 So 18.12.2011 | | Autor: | NeverGod |
Heyho,
ich habe die gleiche aufgabe und da wir uns im [mm] \IF_2 [/mm] Körper befinden gibt es ja nur die elemente 1 und 0. Habe nun einmal das Inverse gebildet von der ersten Matrix A (nicht die aus deinem Beispiel, aus seiner Aufgabe. Und bekomme raus : [mm] A^{-1} [/mm] = [mm] \pmat{ -1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & -2 & -1 \\ 0 & -1 & 1 & 1 }
[/mm]
entspricht das im [mm] \IF_2 A^{-1} [/mm] = [mm] \pmat{ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 }
[/mm]
|
|
|
| |
|
> Heyho,
>
> ich habe die gleiche aufgabe und da wir uns im [mm]\IF_2[/mm]
> Körper befinden gibt es ja nur die elemente 1 und 0. Habe
> nun einmal das Inverse gebildet von der ersten Matrix A
> (nicht die aus deinem Beispiel, aus seiner Aufgabe. Und
> bekomme raus : [mm]A^{-1}[/mm] = [mm]\pmat{ -1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & -2 & -1 \\ 0 & -1 & 1 & 1 }[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
>
> entspricht das im [mm]\IF_2\qquad A^{-1}[/mm] = [mm]\pmat{ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 }[/mm]
Genau.
Ob es stimmt, kannst du ja auch durch zurückmultiplizieren
(nach den Rechenregeln in [mm] \IF_2) [/mm] kontrollieren.
Wären bei [mm] A^{-1} [/mm] (über [mm] \IQ) [/mm] zum Beispiel echte Brüche aufgetreten oder
z.B. Zeilen oder Spalten aus lauter geraden Zahlen, so würde
dies bedeuten, dass die Matrix A über [mm] \IF_2 [/mm] nicht invertierbar
sein kann.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mo 19.12.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
