Kodierungstheorie / Code < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:27 Sa 16.08.2008 | | Autor: | Irmchen |
Hallo alle zusammen!
Ich habe angefangen mich für meine Diplomprüfung in Zahlentheorie ( Kodierungstheorie ) vorzubereiten und habe schon zu Anfang Verständnisproblem. Ich muss dazu sagen, dass ich nie einen Draht für Algebra und Zahlentheorie hatte und dementsprechend auch bei recht einfachen Sachen oft auf dem Schlauch stehe...
So, in den ersten Paragraphen der Vorlesung Kodierungstheorie wurde das Hauptproblem ( Sender / Empfänger ) folgendermaßen erläutert:
A will an B die Info [mm] I \in \mathbb F_2 = \mathbb Z /_{2 \mathbb Z } = \{0,1 \} [/mm] schicken. A hat dazu einen Sender S und B einen Empfänger E. S kann verktoren [mm] v \in \mathbb F_2^{n} [/mm] verschicken und E kann [mm] v \in \mathbb F_2^{n} [/mm] empfangen.
PROBLEM:
E empfängt nicht genau [mm] f(I) [/mm] sondern eine Vektor, der etwas verändert ist. Den nennen wir [mm] f(I) ' [/mm].
Finde Methode, so dass man aus [mm] f(I) ' [/mm] erkennen kann:
1. ob eine Fehler aufgetreten sit; wieviele aufgetreten sind.
2. wo die Fehler genau liegen.
LÖSUNG:
Wähle [mm] c \subseteq \mathbb f_2^n [/mm] (Teilmenge), so dass [mm] f( \mathbb f_2^k ) \subseteq C [/mm] .
Kommt ein [mm] f(I) ' [/mm] bei E an mit [mm] f(I) ' \notin C [/mm], dann ist ein Fehler passiert. C heißt Code .
Passieren nicht zu viele Fehler von [mm] f(I) [/mm] zu [mm] f(I) ' [/mm], so soll [mm] f(I) ' \notin C [/mm] gelten.
( Diesen Sachverhalt versteh ich nicht? Was ist denn viele Fehler passieren, dann ist das doch erst rechtnicht in C , oder? )
Aber meine eigentlichen Schwierigkeiten kommen nun in Beispiele und bei Anwendung von 2 Definitionen.
Beispiele:
1) [mm] C = \left\{ \vektor{ x_1 \\ x_2 \\ x_3 } \in \mathbb F_2^3 \mid \ x_1 + x_2 +x_3 = 0 \right\} \subseteq \mathbb F_2^3 [/mm]
[mm] \Rightarrow C_1 = \left\{ \vektor{0 \\ 0 \\ 0 } , \vektor{1 \\ 0 \\ 1 } , \vektor{0 \\ 1 \\ 1 }, \vektor{ 1 \\ 1 \\ 0 } \right\} [/mm]
Zum Beispiel ist [mm] \vektor{ 0 \\ 0 \\ 1 } \notin C [/mm]. Man weiß aber nicht , wo der Fehler liegt !
( Sehe ich das richtig, dass man deshalb nicht weiß wo der Fehler ist, da man die ersten 3 Vektoren von [mm] C_1 [/mm] jeweils mit einer Änderung so verändern kann und somit den Vektor zu erhalten? )
Definition :
[mm] C \subseteq \mathbb F_2^n [/mm] sei nicht leer Teilmenge.
[mm] D_1(C) := \max \{0\} \cup \{ l \in \mathbb N \ \mid \ [/mm] ist [mm] u \in C, 1 \le m \le l , v \in \mathbb F_2^n [/mm] ,der sich von u in genau m Eingängen unterscheidet, dann gilt [mm] v \notin C \} [/mm].
Dies soll wohl die Anzahl der Eingänge sein, die man max . verändern kann, so dass man aus C kommt
( Warum? )
Und dazu die folgenden Beispiele, die ich nicht verstehe:
1. [mm] D_1 ( \mathbb F_2^n ) = 0 [/mm]
2. [mm] D_1 ( C_1 ) = 1 [/mm]
Definition :
Ist [mm] D_1(C) = d [/mm], so sagt man, dass C bis zu d Fehler erkennen kann.
Frage: Ich sehe leider nicht den Zusammenhang zwischen den beiden Definitionen... :-(
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:33 Sa 16.08.2008 | | Autor: | piet.t |
Hallo,
das bisschen Codierungstheorie, das ich gemacht habe, ist jetzt auch schon ziemlich lange her, aber mal sehen, was ich noch dazu sagen kann...
>
> Finde Methode, so dass man aus [mm]f(I) '[/mm] erkennen kann:
> 1. ob eine Fehler aufgetreten sit; wieviele aufgetreten
> sind.
> 2. wo die Fehler genau liegen.
>
> LÖSUNG:
> Wähle [mm]c \subseteq \mathbb f_2^n[/mm] (Teilmenge), so dass [mm]f( \mathbb f_2^k ) \subseteq C[/mm]
> .
> Kommt ein [mm]f(I) '[/mm] bei E an mit [mm]f(I) ' \notin C [/mm], dann ist
> ein Fehler passiert. C heißt Code .
Damit legen wir erst mal fest: alle gültigen gesendeten Nachrichten müssen in C liegen. Ist die Übermittlung fehlerfrei, dann liegt folglich auch die empfangene Nachricht in C.
> Passieren nicht zu viele Fehler von [mm]f(I) [/mm] zu [mm]f(I) ' [/mm], so
> soll [mm]f(I) ' \notin C [/mm] gelten.
>
> ( Diesen Sachverhalt versteh ich nicht? Was ist denn viele
> Fehler passieren, dann ist das doch erst rechtnicht in C ,
> oder? )
Man kann einen Code immer so designen, dass eine nicht zu stark gestörte Nachricht sicher nicht mehr in C liegt. Passieren zu viele Fehler kann es aber durch einen dummen Zufall passieren, dass trotzdem wieder eine gültige Nachricht entsteht.
Betrachten wir mal euer C von unten und die Nachricht [mm] \vektor{0\\0\\0}. [/mm] Passier ein Fehler, d.h. wird genau eine Null zu einer 1, dann liegt das Ergebnis sicher nicht mehr in C. Bei zwei Fehlern erhalten wir aber wieder einen Vektor, der in C liegt. Wir merken in diesem Fall also gar nicht mehr, dass Fehler passiert sind, sondern halten die Nachricht fälschlicherweise für korrekt übermittelt.
>
> Aber meine eigentlichen Schwierigkeiten kommen nun in
> Beispiele und bei Anwendung von 2 Definitionen.
>
> Beispiele:
>
> 1) [mm]C = \left\{ \vektor{ x_1 \\ x_2 \\ x_3 } \in \mathbb F_2^3 \mid \ x_1 + x_2 +x_3 = 0 \right\} \subseteq \mathbb F_2^3 [/mm]
>
> [mm]\Rightarrow C_1 = \left\{ \vektor{0 \\ 0 \\ 0 } , \vektor{1 \\ 0 \\ 1 } , \vektor{0 \\ 1 \\ 1 }, \vektor{ 1 \\ 1 \\ 0 } \right\}[/mm]
>
> Zum Beispiel ist [mm]\vektor{ 0 \\ 0 \\ 1 } \notin C [/mm]. Man weiß
> aber nicht , wo der Fehler liegt !
>
> ( Sehe ich das richtig, dass man deshalb nicht weiß wo der
> Fehler ist, da man die ersten 3 Vektoren von [mm]C_1[/mm] jeweils
> mit einer Änderung so verändern kann und somit den Vektor
> zu erhalten? )
Genau das. Wenn wir annehmen, dass nicht mehr als ein Fehler passiert ist, dann kann jeder der ersten drei Vektoren die Ausgangsnachricht gewesen sein.
>
> Definition :
>
> [mm]C \subseteq \mathbb F_2^n[/mm] sei nicht leer Teilmenge.
> [mm]D_1(C) := \max \{0\} \cup \{ l \in \mathbb N \ \mid \[/mm] ist
> [mm]u \in C, 1 \le m \le l , v \in \mathbb F_2^n[/mm] ,der sich von
> u in genau m Eingängen unterscheidet, dann gilt [mm]v \notin C \} [/mm].
>
>
> Dies soll wohl die Anzahl der Eingänge sein, die man max .
> verändern kann, so dass man aus C kommt
...besser: "so dass man garantiert aus C kommt".
>
> ( Warum? )
Es geht hier um folgende Frage: Ab wie vielen Fehlern kann es passieren, dass in irgend einer blöden Konstellation wieder eine gültige - und damit scheinbar fehlerfrei empfangene - Nachricht entsteht?
> Und dazu die folgenden Beispiele, die ich nicht verstehe:
>
> 1. [mm]D_1 ( \mathbb F_2^n ) = 0[/mm]
Egal wie wenige Einträge ich in einem Vektor aus [mm] \IF_2^n [/mm] verändere, es bleibt immer ein Vektor aus [mm] \IF_2^n. [/mm] Damit ist in obigem Ausdruck der Teil rechts vom [mm] \cup [/mm] leer und es wird nur das Maximum über {0} gebildet - also ist [mm]D_1 ( \mathbb F_2^n ) = 0[/mm].
>
> 2. [mm]D_1 ( C_1 ) = 1[/mm]
Verändert man z.B. im Vektor [mm] \vektor{0\\0\\0} [/mm] 2 Einträge, dann erhält man wieder einen Vektor aus C. Daher muss [mm]D_1 ( C_1 ) < 2[/mm] gelten.
Für jeden Vektor in C gilt aber: änderet man genau eine Stelle ab, dann erhält man einen Vektor, der nicht mehr in C liegt - also ist 1 in der Menge rechts vom [mm] \cup [/mm] und auch das Maximum ist 1.
>
>
> Definition :
>
> Ist [mm]D_1(C) = d [/mm], so sagt man, dass C bis zu d Fehler
> erkennen kann.
>
> Frage: Ich sehe leider nicht den Zusammenhang zwischen den
> beiden Definitionen... :-(
Bleiben wir beim Beispiel C: Wird bei der Übertragung eine Stelle im Vektor "umgeschossen", dann erhalten wir einen Vektor, der nicht mehr in C liegt. Weil aber nur Vektoren aus C gesendet werden dürfen merkt der Empfänger, dass unterwegs etwas schiefgegangen ist.
Werden aber zwei Positionen geändert, dann kommt ja wieder ein Vektor aus C an, und dann muss der Empfänger davon ausgehen, dass die Nachricht auch so vom Sender gesendet worden ist.
Das steckt auch der Zusammenhang zwischen den Definitionen. [mm] D_1(C) [/mm] gibt die maximale Anzahl Fehler an, die passieren dürfen, dass man - ausgehend von einem Vektor in C - sicher nicht mehr in C landet. Passieren also bei einer Übertragung nicht mehr als [mm] D_1(C) [/mm] Fehler, dann kommt beim Empfänger eine ungültige Nachricht an und er erkennt, dass es bei der Übertragung Probleme gegeben hat. Bei mehr als [mm] D_1(C) [/mm] Fehlern kann es passieren, dass eine falsche aber trotzdem gültige Nachricht beim Empfänger ankommt und er daher nicht merkt, dass überhaupt ein Fehler passiert ist.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:05 So 17.08.2008 | | Autor: | Irmchen |
Hallo!
Vielen Dank für die ausführliche Antwort!
Das habe ich nun verstanden, aber eine Definition habe ich gestern noch entdeckt, die ich auch nicht wirklich verstehe und wieder bei ihrer Anwendung Probleme auftreten.
Definition :
[mm] D_2 (C) := \max \{ 0 \} \cup \{ l \in \mathbb N \ \mid [/mm] ist [mm] v \notin C, \ 1 \le m \le l [/mm], dann gibt es höchstens ein [mm] u \in C [/mm], dass sich von v um genau m Eingänge unterscheidet. Zwei veschiedene [mm] u_1, u_2 \in C [/mm] unterscheiden sich an mind. l Stellen [mm] \} [/mm].
Ist [mm] D_2 (C) = d [/mm], so sagt man, dass C bis zu d Fehler korrigieren kann.
( Leider verstehe ich das nicht wirklich.... )
Beispiele dazu waren:
1) [mm] D_2( \mathbb F_2^n ) = 0 [/mm]
2) [mm] D_2( C_1) = 0 [/mm]
Vielleicht kann mir jemand anhand dieser Beipiele diese Definition versuchen zu erläutern...
Vielen Dank!
Viele Grüße
Irmchen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:24 So 17.08.2008 | | Autor: | piet.t |
Hallo,
an den Beispielen ist das schwierig zu erklären, weil diese Codes ja keine Fehler korrigieren können [mm] (D_2=0).
[/mm]
Betrachten wir das erst mal allgemein: Nehmen wir mal an wir sind Empfänger und es kommt ein [mm] $v\not\in [/mm] C$ an. Dann ist klar, dass irgend welche Übertragungsfehler passiert sein müssen. Und nehmen wir weiter an, dass genau [mm] m
Auf diese Weise konnten wir also Übertragungsfehler in m Stellen korrigeren.
Ein einfaches Beispiel habe ich jetzt leider gerade nciht bei der Hand, und auf die Schnelle will ich mir jetzt auch keines aus den Fingern saugen, weil das garantiert schief geht. Aber vielleicht helfen ja auch die allgemeinen Erläuterungen schon etwas.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:30 So 17.08.2008 | | Autor: | Irmchen |
Vielen Dank!
Ich denke, dass ich das nun verstanden habe, und mit den beiden Definitionen umgehen kann.
Ganz nebenbei, gibt es ein nettes Buch, welches man empfehlen könnte??
Viele Grüße Irmchen
|
|
|
|
