Kontrollmatrix < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei die Kontrollmatrix
[mm] H:=\pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 1&1&0&0&0&1&1 } \in [/mm] Mat (3, 7; [mm] \IF_{2}) [/mm]
und der zugehörige lineare Code
C:={ x [mm] \in \IF^7_{2}: [/mm] x * [mm] H^t [/mm] = 0}
a) Bestimmen Sie eine Basis von C.
b) Bestimmen Sie den Minimalabstand d(C).
c) Konstruieren Sie eine Syndromtabelle für C.
d) Decodieren Sie w:=(1001011) [mm] \in \IF^7_{2} [/mm] nach dem Prinzip des nächsten Nachbarn (Minimum-Distance-Decoding). |
a) C:={ x [mm] \in \IF^7_{2}: [/mm] x * [mm] H^t [/mm] = 0}
Aus [mm] H:=\pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 1&1&0&0&0&1&1 }
[/mm]
wird erst mal das hier: 3.reihe - 1.reihe
[mm] \pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 0&1&1&0&1&0&1 }
[/mm]
dann 3.reihe - 2.reihe
[mm] \pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 0&0&1&1&0&1&1 }
[/mm]
und zuletzt 1.reihe - 3.reihe
[mm] \pmat{ 1&0&0&1&1&0&1 \\ 0&1&0&1&1&1&0 \\ 0&0&1&1&0&1&1 }
[/mm]
daraus ergibt sich:
[mm] x_{1} [/mm] = [mm] x_{4}+x_{5}+x_{7}
[/mm]
[mm] x_{2} [/mm] = [mm] x_{4}+x_{5}+x_{6}
[/mm]
[mm] x_{3} [/mm] = [mm] x_{4}+x_{6}+x_{7}
[/mm]
nun kommt mein Problem...ich weiß nicht wie ich auf [mm] x_{4},x_{5},x_{6},x_{7} [/mm] komme
[mm] x_{4}=(1111000) [/mm] + [mm] x_{5}*(1100100) [/mm] + [mm] x_{6}*(0110010) [/mm] + [mm] x_{7}*(1010001) [/mm]
[mm] G=\pmat{ 1&1&1&1&0&0&0 \\ 1&1&0&0&1&0&0 \\ 0&1&1&0&0&1&0 \\ 1&0&1&0&0&0&1 } [/mm]
Und damit: k = dim(c) = 4
Das G ergibt sich aus eben diesen [mm] x_{4},x_{5},x_{6},x_{7} [/mm] und ich weiß nicht wie man darauf kommt
b) Satz: Es sei C ein q-närer linearer Code der Länge n mit dim(c) = k und Paritätsprüfungsmatrix H [mm] \in [/mm] Mat(n-k, n, [mm] \IF_{q}). [/mm] Dann sind äquivalent:
- d = d(c)
- Je d-1 Spalten von H sind linear unabhängig, aber es existieren d linear abhängige Spalten.
Bei uns: d = 3
Zu b) habe ich keine Fragen...
c) [mm] S(\vec{a}) [/mm] = [mm] \vec{a} [/mm] * [mm] H^t
[/mm]
wir erhalten folgende Tabelle:
[mm] \vec{a} S(\vec{a})
[/mm]
0000000 000
0000001 001
0001000 010
0100000 011
0010000 100
1000000 101
0000100 110
0000010 111
meine Frage zu c) ist.
Woher bekomme ich dieses [mm] \vec{a} [/mm] und [mm] S(\vec{a}) [/mm] in der Tabelle? Wie erkenne ich es?
d) Gegeben: [mm] \vec{w} [/mm] = (1001011). Dann ergibt sich:
[mm] \vec{w} [/mm] * [mm] H^t [/mm] = (1001011) * [mm] \pmat{ 1&0&1 \\ 0&1&1 \\ 1&0&0 \\ 0&1&0 \\ 1&1&0 \\ 1&1&1 \\ 0&0&1 } [/mm] = 001 [mm] \not\in [/mm] C
Bei uns [mm] S(\vec{a} [/mm] = 001). Dann
[mm] \vec{c_*} [/mm] = [mm] \vec{w} [/mm] - [mm] \vec{a_2} [/mm] = (1001011) - (0000001) = (1001010) = [mm] \vec{c_1} [/mm] + [mm] \vec{c_3}
[/mm]
Definition: Es sei C ein q-närer (n,M,d)-Code und t = max{e [mm] \in \IN_0 [/mm] : 2e + 1sd}. C heißt perfekter Code wenn gilt:
[mm] q^n [/mm] = M * [mm] \summe_{v=0}^{t}\vektor{n \\ v} [/mm] * [mm] (q-1)^v
[/mm]
Bei uns: v = 3 [mm] \to [/mm] t = 1; M = |C| = [mm] q^k [/mm] = [mm] 2^k [/mm] - 16 bei k = dim(c) = 4. Dann also n = 7. Und [mm] q^n [/mm] = [mm] 2^7 [/mm] = 128. Es ergibt sich:
M * [mm] \summe_{v=0}^{t}\vektor{n \\ v} [/mm] * [mm] (q-1)^v [/mm] = 16 * [mm] (\summe_{v=0}^{1} \vektor{7 \\ v}) [/mm] = 16 * (1 + 17) = 128
zu d) habe ich auch keine Fragen...
Danke schonmal im Voraus für eure Hilfen...
Diese Frage wurde in keinem anderen Forum gestellt...
Mit freundlichen Grüßen
[mm] DARKMAN_X
[/mm]
|
|
| |
|
Hallo DARKMAN_X,
> Gegeben sei die Kontrollmatrix
>
> [mm]H:=\pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 1&1&0&0&0&1&1 } \in[/mm]
> Mat (3, 7; [mm]\IF_{2})[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> und der zugehörige lineare Code
> C:={ x [mm]\in \IF^7_{2}:[/mm] x * [mm]H^t[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= 0}
>
>
> a) Bestimmen Sie eine Basis von C.
> b) Bestimmen Sie den Minimalabstand d(C).
> c) Konstruieren Sie eine Syndromtabelle für C.
> d) Decodieren Sie w:=(1001011) [mm]\in \IF^7_{2}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
nach dem
> Prinzip des nächsten Nachbarn
> (Minimum-Distance-Decoding).
> a) C:={ x [mm]\in \IF^7_{2}:[/mm] x * [mm]H^t[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= 0}
>
> Aus [mm]H:=\pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 1&1&0&0&0&1&1 }[/mm]
>
> wird erst mal das hier: 3.reihe - 1.reihe
> [mm]\pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 0&1&1&0&1&0&1 }[/mm]
>
> dann 3.reihe - 2.reihe
> [mm]\pmat{ 1&0&1&0&1&1&0 \\ 0&1&0&1&1&1&0 \\ 0&0&1&1&0&1&1 }[/mm]
>
> und zuletzt 1.reihe - 3.reihe
> [mm]\pmat{ 1&0&0&1&1&0&1 \\ 0&1&0&1&1&1&0 \\ 0&0&1&1&0&1&1 }[/mm]
>
> daraus ergibt sich:
> [mm]x_{1}[/mm] = [mm]x_{4}+x_{5}+x_{7}[/mm]
> [mm]x_{2}[/mm] = [mm]x_{4}+x_{5}+x_{6}[/mm]
> [mm]x_{3}[/mm] = [mm]x_{4}+x_{6}+x_{7}[/mm]
>
> nun kommt mein Problem...ich weiß nicht wie ich auf
> [mm]x_{4},x_{5},x_{6},x_{7}[/mm] komme
>
> [mm]x_{4}=(1111000)[/mm] + [mm]x_{5}*(1100100)[/mm] + [mm]x_{6}*(0110010)[/mm] +
> [mm]x_{7}*(1010001)[/mm]
>
> [mm]G=\pmat{ 1&1&1&1&0&0&0 \\ 1&1&0&0&1&0&0 \\ 0&1&1&0&0&1&0 \\ 1&0&1&0&0&0&1 }[/mm]
> Und damit: k = dim(c) = 4
>
> Das G ergibt sich aus eben diesen [mm]x_{4},x_{5},x_{6},x_{7}[/mm]
> und ich weiß nicht wie man darauf kommt
>
Führe künstliche Variablen ein:
[mm]x_{4}=r, \ x_{5}=s, \ x_{6}=t., \ x_{7]=u[/mm]
Dann kannst Du die Lösungsmenge in der Form
[mm]\pmat{x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7}}=r*\pmat{... \\ ... \\ ... \\ 1 \\ 0 \\ 0 \\ 0}+s*\pmat{... \\ ... \\ ... \\ 0 \\ 1 \\ 0 \\ 0}+t*\pmat{... \\ ... \\ ... \\ 0 \\ 0 \\ 1 \\ 0}+u*\pmat{... \\ ... \\ ... \\ 0 \\ 0 \\ 0 \\ 1}[/mm]
schreiben.
> b) Satz: Es sei C ein q-närer linearer Code der Länge n
> mit dim(c) = k und Paritätsprüfungsmatrix H [mm]\in[/mm] Mat(n-k,
> n, [mm]\IF_{q}).[/mm] Dann sind äquivalent:
> - d = d(c)
> - Je d-1 Spalten von H sind linear unabhängig, aber es
> existieren d linear abhängige Spalten.
> Bei uns: d = 3
> Zu b) habe ich keine Fragen...
>
> c) [mm]S(\vec{a})[/mm] = [mm]\vec{a}[/mm] * [mm]H^t[/mm]
>
> wir erhalten folgende Tabelle:
>
> [mm]\vec{a} S(\vec{a})[/mm]
> 0000000 000
> 0000001 001
> 0001000 010
> 0100000 011
> 0010000 100
> 1000000 101
> 0000100 110
> 0000010 111
>
> meine Frage zu c) ist.
> Woher bekomme ich dieses [mm]\vec{a}[/mm] und [mm]S(\vec{a})[/mm] in der
> Tabelle? Wie erkenne ich es?
>
Für die Erzeugung der Syndromtabelle siehe hier: ![[]](/images/popup.gif) Lineare Codes - Syndromtabelle
( URL:http://matheplanet.com/default3.html?call=viewtopic.php
?topic=143098&ref=http://www.google.de/search?hl=de&source=hp
&q=syndromtabelle&aq=f&aqi=g1&aql=&oq= )
> d) Gegeben: [mm]\vec{w}[/mm] = (1001011). Dann ergibt sich:
> [mm]\vec{w}[/mm] * [mm]H^t[/mm] = (1001011) * [mm]\pmat{ 1&0&1 \\ 0&1&1 \\ 1&0&0 \\ 0&1&0 \\ 1&1&0 \\ 1&1&1 \\ 0&0&1 }[/mm]
> = 001 [mm]\not\in[/mm] C
>
> Bei uns [mm]S(\vec{a}[/mm] = 001). Dann
> [mm]\vec{c_*}[/mm] = [mm]\vec{w}[/mm] - [mm]\vec{a_2}[/mm] = (1001011) - (0000001) =
> (1001010) = [mm]\vec{c_1}[/mm] + [mm]\vec{c_3}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> Definition: Es sei C ein q-närer (n,M,d)-Code und t =
> max{e [mm]\in \IN_0[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
: 2e + 1sd}. C heißt perfekter Code wenn
> gilt:
> [mm]q^n[/mm] = M * [mm]\summe_{v=0}^{t}\vektor{n \\ v}[/mm] * [mm](q-1)^v[/mm]
>
> Bei uns: v = 3 [mm]\to[/mm] t = 1; M = |C| = [mm]q^k[/mm] = [mm]2^k[/mm] - 16 bei k =
> dim(c) = 4. Dann also n = 7. Und [mm]q^n[/mm] = [mm]2^7[/mm] = 128. Es ergibt
> sich:
> M * [mm]\summe_{v=0}^{t}\vektor{n \\ v}[/mm] * [mm](q-1)^v[/mm] = 16 *
> [mm](\summe_{v=0}^{1} \vektor{7 \\ v})[/mm] = 16 * (1 + 17) = 128
>
> zu d) habe ich auch keine Fragen...
>
> Danke schonmal im Voraus für eure Hilfen...
> Diese Frage wurde in keinem anderen Forum gestellt...
>
> Mit freundlichen Grüßen
>
> [mm]DARKMAN_X[/mm]
Gruss
MathePower
|
|
|
|
