linearer Code [n,k,d] Code < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:40 Sa 12.05.2007 | | Autor: | alexmart |
| Aufgabe | Es sei C ein linearer [n,k,d]-Code C mit Erzeugermatrix G.
Zeigen sie:
Genau dann ist C ein MDS-Code, wenn je k Spalten von G linear unabhängig sind. |
Hallo,
also ich bin Informatikstudent und wir machen gerade Codierungtheorie in Mathematik.
Bei dieser Aufgabe verstehe ich net den Zusammenhang zwischen der linearen unabhängigkeit und MDS Codes.
Ich habe keine Idee wie ich das zeigen soll.
Vielleicht kann mir hier jemand helfen?
Wäre auf jeden Fall sehr nett!
MFG
Alexander
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:43 Sa 12.05.2007 | | Autor: | felixf |
Hallo Alexander.
> Es sei C ein linearer [n,k,d]-Code C mit Erzeugermatrix G.
>
> Zeigen sie:
> Genau dann ist C ein MDS-Code, wenn je k Spalten von G
> linear unabhängig sind.
$G$ ist eine $k [mm] \times [/mm] n$-Matrix ueber [mm] $\IK$ [/mm] und $C = [mm] \{ x G \mid x \in \KI^k \} \subseteq \IK^n$, [/mm] oder?
Dann ist $C$ ja genau dann ein MDS-Code, wenn $d(C) = n - k + 1$ ist (wobei $d(C) = [mm] \min\{ w(c) \mid c \in C \setminus \{ 0 \} \}$ [/mm] ist, wobei $w(c)$ das Hamming-Gewicht von $c [mm] \in \IK^n$ [/mm] ist). Nach der Singleton-Schranke gilt sowieso $d(C) [mm] \le [/mm] n - k + 1$.
Es reicht also zu zeigen, dass $C$ genau dann MDS ist, wenn das einzige Codewort $c [mm] \in [/mm] C$ mit $w(c) < n - k + 1$ das Nullcodewort ist (also $c = 0$).
Jedes Codewort $c [mm] \in [/mm] C$ ist nun von der Form $c = [mm] \sum_{i=1}^k \lambda_i v_i$, [/mm] wobei [mm] $v_i$ [/mm] die $i$-te Zeile von $G$ ist und [mm] $\lambda_i \in \IK$.
[/mm]
Sei $c [mm] \in [/mm] C$ mit $w(c) < n - k + 1$, also mit $w(c) [mm] \le [/mm] n - k$. Schreibe $c = [mm] \sum_{i=1}^k \lambda_i v_i$. [/mm] Da $w(c) [mm] \le [/mm] n - k$ gibt es mindestens $k$ Indices [mm] $i_\ell$, $\ell [/mm] = 1, [mm] \dots, [/mm] k$, mit [mm] $c_{i_\ell} [/mm] = 0$, $1 [mm] \le \ell \le [/mm] k$. Sei $G'$ die Matrix, die aus den Spalten [mm] $i_1, \dots, i_k$ [/mm] von $G$ besteht. Dann ist [mm] $(\lambda_1, \dots, \lambda_k) [/mm] G' = 0$.
Die Bedingung ``je $k$ Spalten von $G$ sind linear unabhaengig'' ist nun dazu aequivalent, dass jedes solche $G'$ vollen Rang hat, dass also zu jedem solchen $c = [mm] \sum_{i=1}^k \lambda_i v_i \in [/mm] C$ mit $w(c) [mm] \le [/mm] n - k$ folgt, dass [mm] $(\lambda_1, \dots, \lambda_k) [/mm] = (0, [mm] \dots, [/mm] 0)$ ist (das ist ja gerade dazu aequivalent, dass $G'$ vollen Rang hat) und somit $c = 0$ ist.
LG Felix
|
|
|
|
