Cod. - Theorie/ min. Distanz < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:56 So 17.08.2008 | | Autor: | Irmchen |
Guten Tag alle zusammen!
Ich habe hier zwei "Baustellen" , bei denen ich kleinere und auch größere Probleme habe.
1. Hier ist ein Beispiel, zu dem ich nur zwei kurze Frage habe.
Bespiel :
[mm] K =\mathbb F_2 [/mm]
[mm] C_1 := \left \{ \vektor{ x_1 \\ x_2 \\ x_3 } \ \mid \ x_1 + x_2 + x_3 = 0 \right \} [/mm]
Dimension von [mm] C_1 [/mm] ist 2 und Minimaldistanz [mm] md ( C_1 ) = 2 [/mm] .
( Frage: Warum ist die Dimension so groß? Und wie kann ich denn schon sagen, wie groß die Minimaldistanz ist, wenn ich keine konkreten 2 Vektoren habe?)
[mm] C_2 := \left \{ \vektor{ 0 \\ 0 \\ 0 } , \vektor{1 \\ 1 \\ 1 } \right \} \subseteq \mathbb F_2^3 , \ md( C_2 ) = 3 [/mm]
( Frage: Ich verstehe wieder nicht ,warum hier die Minimaldistanz 3 ist. Ich denke, dass ist die minimale Anzahl der Einträge, in denen sich die beiden Vektoren unterscheiden, und hier unterschieden sich sich doch auf allen 3 Positionen, müsste da nicht md = 1 sein? )
2. Hier habe ich einen Satz, dessen Bedeutung ist nicht nachvollziehen kann und leider auch als Beweis wir nur ein " offensichtlich" stehen haben und ich mir somit damit nicht helfen kann.
Das einzige, was ich dabei als Tipp stehen habe, ist dass die folgende Definition eine Rolle im Zusammenhang spielt.
Definition :
[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]
Satz :
[mm] C \subseteq K^n [/mm] sei ein Code mit [mm] md ( C ) = d [/mm]. Ist
[mm] u \in C [/mm] und [mm] v \in K^n [/mm] mit [mm] 1 \le d(u,v) \le d-1 [/mm]. Dann gilt [mm] v \notin C [/mm]
( Das d(u,v ) ist hier der Hamming - Abstand )
Ich hoffe jemand kann mir helfen und erklären, was es mit diesem Satz auf sich hat.
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
Zum ersten Problem:
Ohne einschränkende Bedingung wäre [mm] C_1 [/mm] 3dimensional. Du hast eine einschränkende Bedingung und "verlierst" dadurch 1 Dimension. Bleiben 2.
Minimalabstand: Schreib dir mal alle Möglichkeiten hin, es sind ja nur 4. Entweder sind alle Einträge 0 oder zwei sind 1 und der verbleibende 0. Wenn du an einer Stelle etwas änderst, dann musst du auch an einer anderen Stelle etwas ändern, damit die Summe wieder stimmt. Daher md=2.
Der Satz ist tatsächlich offensichtlich, denn wenn in C ein Minimalabstand von d gilt, dann haben alle Elemente dieser Menge einen Abstand [mm] \ge [/mm] d. Hast du dann einen Vektor, der zu einem Element von C einen kleineren Abstand hat, kann er nicht in C liegen, denn sonst müsste der Minimalabstand ja kleiner sein.
|
|
|
|
