Code Fehler erkennen / korrigi < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:09 Fr 31.10.2008 | | Autor: | Irmchen |
Hallo alle zusammen!
Ich habe ganz am Anfang der Codierungstheorie - Vorlesung eine Sache nicht wirklich vertstanden.... Es geht sich dabei um 2 Mengen , deren Inhalt ich nicht nachvollziehen kann.
Einma die Menge
[mm] D_1 (C) := \max ( \{0 \} \cup \{ l \in \mathbb N \ | \ ist \ u \in C \ und 1 \le m \le l \ und \ v \in \mathbb F_2^{n} , \ der \ sich \ von \ u \in \genau m \ Eingängen \ unterschidet, \dann \ v \notin C \} [/mm]
C bezeichnet hier einen Code.
(*) Ist [mm] D_1(C) = d [/mm] so sagt man, dass C bis zu d Fehler erkennen kann.
Ich kann aus der oben definierten Menge nicht auf die Aussage (*) schließen. Warum kann C da Fehler erkennen?
Und die zweite Menge:
[mm] D_2 (C) := \max ( \{0 \} \cup \{ l \in \mathbb N \ | \ ist \ v \notin C \ und 1 \le m \le l \ Dann \ gibt \ es \ höchstens \ ein \ u \in C , \ das \ sich \ von \ v \ um \ genau m \ Eingängen \ unterschidet. \Zwei \ verschiedene \ u_1, u_2 \in C \ unterscheiden \ sich \ um \mind. \ l \ Stellen \} [/mm]
(**) Ist [mm] D_(C) = d [/mm] , so sagt man, dass C bis zu d Fehler korrigieren kann.
Bei dieser zweiten Menge habe ich gleicht Probleme , wie oben. Ich sehe nicht den Zusammenhang zwischen der Menge und dem "Fehler korrigieren" .
Auch zu diese folgende Bemerkung, die anscheinend auch mit einer der Mengen zutun hat, finde ich keine Draht...
Bemerkung:
Es gilt [mm] D_1(C) \ge md(C) -1 [/mm] , wobei md die Minimaldiatanz bezeichnet.
Das bedeutet:
C kann weniger als md(C) - 1 Fehler erkennen.
[red] Soll ich da einfach so als eine Tatsache hinnehmen, oder kann man dies irgendwie erklären? Welche Rolle spielt denn überhaupt die Minimaldistanz? Sie gibt doch den minimalsten Hemming- Abstand von Vektoren im Code..., oder?
Ich hoffe, dass mir jemand helfen kann, denn irgendwie versuche ich das länger zu verstehen, aber ohne Erfolg!
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:43 Sa 01.11.2008 | | Autor: | rainerS |
Hallo Irmchen!
> Hallo alle zusammen!
>
> Ich habe ganz am Anfang der Codierungstheorie - Vorlesung
> eine Sache nicht wirklich vertstanden.... Es geht sich
> dabei um 2 Mengen , deren Inhalt ich nicht nachvollziehen
> kann.
Ich glaube, es wird einfacher, wenn du dir vorstellst, wie so ein Code benutzt wird. Du hast eine gewisse Anzahl von (binären) Eingängen. Die möglichen Bitmuster auf den Eingängen sind entweder erlaubte Elemente des Codes [mm] ($u\in [/mm] C$) oder sie sind es nicht [mm] ($v\notin [/mm] C$). Offensichtlich kann der Code erlaubte von nicht erlaubten Elementen unterscheiden. Der Zweck der Sache ist unter anderem, Fehler zu erkennen und möglichst auch zu korrigieren. Also: im ersten Fall zu sagen: dieses Muster ist fehlerhaft, und im zweiten Fall: dieses Muster ist fehlerhaft, aber das korrekte Muster ist so-und-so.
Die Mengendefinitionen beschäftigen sich mit dem Unterschied zwischen erlaubten und nicht erlaubten.
> Einma die Menge
>
> [mm]D_1 (C) := \max ( \{0 \} \cup \{ l \in \mathbb N \mid \text{ ist $u \in C$ und $1 \le m \le l$ und $v \in \mathbb F_2^{n}$ , der sich von u in genau m Eingängen unterscheidet, dann $v \notin C$ \}[/mm]
>
> C bezeichnet hier einen Code.
>
> (*) Ist [mm]D_1(C) = d[/mm] so sagt man, dass C bis zu d Fehler
> erkennen kann.
>
> Ich kann aus der oben definierten Menge nicht auf die
> Aussage (*) schließen. Warum kann C da Fehler erkennen?
[mm] $D_1(C)$ [/mm] ist das Maximum des Abstands der nicht erlaubten Elemente [mm] $v\notin [/mm] C$ von allen [mm] $u\in [/mm] C$.
Es geht hier darum, wie sich diese (nicht erlaubten) v von den Elementen in C unterscheiden. Wenn die Menge mehr als nur das 0-Elemente enthält, so muss sich jedes solche v in mindestens einem Eingang von allen [mm] $u\in [/mm] C$ unterscheiden. Da es sich hier sozusagen um nur einen fehlerhaften Eingang handelt, so kann man sagen, dass der Code im Bitmuster v 1 Fehler erkennt. (Das einfachste Beispiel hierfür ist ein Paritätsbit.)
Wenn es nun solche v gibt, die sich in m Eingängen von allen [mm] $u\in [/mm] C$ unterscheiden, dann sagt man analog, dass der Code in v m Fehler erkennt. Ist d die größte dieser Zahlen, so sagt man, dass C bis zu d Fehler erkennen kann.
> Und die zweite Menge:
>
> [mm]D_2 (C) := \max ( \{0 \} \cup \{ l \in \mathbb N \mid \text{ ist $v \notin C$ und $1 \le m \le l$. Dann gibt es höchstens ein $u \in C$, das sich von v um genau m Eingängen unterschidet. Zwei verschiedene $u_1, u_2 \in C$ unterscheiden sich um mind. l Stellen} \}[/mm]
>
> (**) Ist [mm]D_(C) = d[/mm] , so sagt man, dass C bis zu d Fehler
> korrigieren kann.
>
> Bei dieser zweiten Menge habe ich gleicht Probleme , wie
> oben. Ich sehe nicht den Zusammenhang zwischen der Menge
> und dem "Fehler korrigieren" .
Hier geht es darum, wie ich von einem fehlerhaften Bitmuster auf das richtige Bitmuster schließen kann. Die Idee ist hier, dass durch Störungen bei einer Datenübertragung Fehler auftreten, aber nur in begrenzter Anzahl. Damit rühren die (fehlerhaften) v von [mm] $u\in [/mm] C$ her, und zwar durch Veränderung auf einer gewissen Anzahl von Eingängen.
Nehmen wir einmal an, dass bei solchen Veränderungen höchsten zwei Eingänge modifiziert werden.
Wenn zum Beispiel sich ein solches v in 2 Eingängen von einem bestimmten [mm] $u_1\in [/mm] C$ unterscheidet, aber in mehr als 2 Eingängen von allen anderen [mm] $u\in [/mm] C$, dann kann es unter dieser Annahme nur von diesem [mm] $u_1$ [/mm] herkommen. Also kann ich es durch [mm] $u_1$ [/mm] ersetzen und habe damit den Fehler korrigiert.
> Auch zu diese folgende Bemerkung, die anscheinend auch mit
> einer der Mengen zutun hat, finde ich keine Draht...
>
> Bemerkung:
>
> Es gilt [mm]D_1(C) \ge md(C) -1[/mm] , wobei md die Minimaldiatanz bezeichnet. Das bedeutet:
> C kann weniger als md(C) - 1 Fehler erkennen.
>
> Soll ich da einfach so als eine Tatsache hinnehmen, oder
> kann man dies irgendwie erklären? Welche Rolle spielt denn
> überhaupt die Minimaldistanz? Sie gibt doch den minimalsten
> Hemming- Abstand von Vektoren im Code..., oder?
Ja, und der Abstand zweier Elemente [mm] $u_1,u_2\in [/mm] C$ ist die Anzahl der unterschiedlichen Eingänge.
Und [mm] $D_1(C)$ [/mm] ist, wie ich schon schrieb das Maximum des Abstands der nicht erlaubten Elemente [mm] $v\notin [/mm] C$ von allen [mm] $u\in [/mm] C$.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:05 Sa 01.11.2008 | | Autor: | Irmchen |
Hallo Rainer!
Viele vielen lieben Dank für Deine Mühe!
Jetzt habe ich dies endlich in dem Kontext verstanden!
Viele liebe Grüße
Irmchen
|
|
|
|
