Wiederholungscode ML-Projektio < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | A={0,1} und [mm] n\ge [/mm] 2 eine natürliche Zahl. Betrachte die Codierungsregel [mm] c:A^n. x\to [/mm] xxx***x (n-mal)
Sei C:=c(A)={000**0,111***1}der entsprechende Code. Er wird n-facher Wiederholungscode genannt.
Zeigen sie: wenn n gerade ist, dann gibt es mehrer Projektionen [mm] p:A^n\to [/mm] C, die die ML-Eigenschaft [mm] \parallel \underline{x},p(\underline{x}) \parallel= min\parallel \underline{x},\underline{y} \parallel [/mm] : [mm] \underline{y}\in [/mm] C
für alle [mm] \underline{x}\in A^n [/mm] erfüllen.
Wie viele solche ML-Projektionen gibt es insgesamt? |
Könnt ihr mir bei dieser Aufgabe helfen?
Ich verstehe nur Bahnhof!
was ein Wiederholungscode ist weiß ich aber ich komme hier nicht weiter.
MfG
Mathegirl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:22 Mi 18.04.2012 | | Autor: | felixf |
Moin!
> A={0,1} und [mm]n\ge[/mm] 2 eine natürliche Zahl. Betrachte die
> Codierungsregel [mm]c:A^n. x\to[/mm] xxx***x (n-mal)
> Sei C:=c(A)={000**0,111***1}der entsprechende Code. Er
> wird n-facher Wiederholungscode genannt.
>
> Zeigen sie: wenn n gerade ist, dann gibt es mehrer
> Projektionen [mm]p:A^n\to[/mm] C, die die ML-Eigenschaft [mm]\parallel \underline{x},p(\underline{x}) \parallel= min\parallel \underline{x},\underline{y} \parallel[/mm]
> : [mm]\underline{y}\in[/mm] C
> für alle [mm]\underline{x}\in A^n[/mm] erfüllen.
So steht das da sicher nicht. Aber ich denke ich weiss was gemeint ist.
> Wie viele solche ML-Projektionen gibt es insgesamt?
>
> Könnt ihr mir bei dieser Aufgabe helfen?
> Ich verstehe nur Bahnhof!
> was ein Wiederholungscode ist weiß ich aber ich komme
> hier nicht weiter.
Weisst du, was [mm] $\|\underline{x}, \underline{y}\|$ [/mm] ist? Was die ML-Eigenschaft ist? Mach dir das erstmal klar!
(Zum Beispiel anhand konkreter Beispiele: nimm den Wiederholungscode mit $n = 2$, und betrachte alle moeglichen Funktionen [mm] $A^2 \to [/mm] C$. Welche davon erfuellen die ML-Eigenschaft, welche nicht, und jeweils: warum?)
LG Felix
|
|
|
| |
|
nein, ich weiß leider gar nichts dazu. In der Vorlesung wurde dazu fast nichts erwähnt. ich weiß, dass es sich hier um eine Metrix handelt. x bedeutet gesendet, y empfangen.
Die Metrik zeigt die Anzahl der Übertragungsfehler darstellen.
und in Fachbüchern habe ich bisher auch noch nichts sinnvolles gefunden. Werde mal schauen ob ich über google was herausfinde!
Auch der Begriff ML_Projektion und ML-Eigenschaft ist bisher noch nicht gefallen. ML steht für Maximum-Likelehood???? (vermute ich mal) kann aber nichts damit anfangen.
Aber vielleicht kannst du mir das trotzdem mal erklären?
Wäre sehr nett.
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:46 Do 19.04.2012 | | Autor: | Mathegirl |
Könnt ihr mir erklären was ich hier wie machen muss? verstehe das leider nicht!
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Sa 21.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:06 Fr 20.04.2012 | | Autor: | Hummel89 |
Hallo,
ich habe es mal am konkreten Beispiel A² probiert:
Wenn ich die ML-Eigenschaft richtig verstehe, dann sind diejenigen Projektionen gesucht, bei denen das Anwenden der Codierungsregel mindestens so viele Übertragungsfehler liefert wie das unverschlüsselte Verfahren.
Wenn wir jetzt den Fall A² betrachten, wäre die Textlänge ja jeweils 2 und jedes Element wird verdoppelt.
Würde man nun den Code "1" verdoppeln, müsst am Ende "11", "10" oder "01" erscheinen, damit es als richtig erachtet wird. Ab 50 Prozent Abweichung wird ein Fehler angenommen, also würde bei "00", also zwei Übertragungsfehlern", entschieden werden, dass ein Fehler vorliegt.
Nun können "10" oder "01" aber bei einer Eingabe von "0" auch als richtig erachtet werden, sind also nicht wie bei einem ungeraden n klar einem Code zuzuordnen.
Wäre das schon mal in der richtigen Richtung oder habe ich die Aufgabe vollkommen falsch verstanden?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:03 Fr 20.04.2012 | | Autor: | chesn |
Und google mal "Hamming-Metrik". Das ist hier wohl gemeint.
Setz mich heute abend nochmal daran, wenn ich was rausfinde werde ich hier posten.
Edit: Schau mal ![[]](/images/popup.gif) hier ab Seite 12.
Lieben Gruß
chesn
|
|
|
| |
|
Ich habe das trotzdem noch nicht verstanden. Wie kriege ich das für gerade n raus? Mir ist noch immer nicht ganz klar was hier zu machen ist.
Wäre nett wenn mir das nochmal jemand erklären kann.
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:24 So 22.04.2012 | | Autor: | chesn |
Hallo Mathegirl!
Bin auch an der Aufgabe verzweifelt.. da morgen Abgabe ist werde ich jetzt einfach das abschreiben was hier steht, also warum die minimale Hamming-Distanz zw. zwei Wörtern ungerade sein muss (das ist wohl die gemeinte ML-Eigenschaft).
Gruß
chesn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:39 So 22.04.2012 | | Autor: | felixf |
Moin!
> ich habe es mal am konkreten Beispiel A² probiert:
>
> Wenn ich die ML-Eigenschaft richtig verstehe, dann sind
> diejenigen Projektionen gesucht, bei denen das Anwenden der
> Codierungsregel mindestens so viele Übertragungsfehler
> liefert wie das unverschlüsselte Verfahren.
Was genau verstehst du hier unter Codierungsregel?
ML-Eigenschaft sagt: ein Element $x$ aus [mm] $A^2$ [/mm] wird auf ein Element $c$ aus $C$ abgebildet, so dass die Hamming-Distanz [mm] $\|x [/mm] - [mm] c\|$ [/mm] minimal ist unter allen solchen Codewoertern $c [mm] \in [/mm] C$. Soll bedeuten: es gibt kein weiteres Codewort $c' [mm] \in [/mm] C$ mit [mm] $\|x [/mm] - [mm] c'\| [/mm] < [mm] \|x [/mm] - [mm] c\|$.
[/mm]
Wenn man z.B. Projektionen [mm] $\pi [/mm] : [mm] A^3 \to [/mm] C$ betrachtet (also $n = 3$), dann muss etwa [mm] $\pi(000) [/mm] = 000$ und [mm] $\pi(111) [/mm] = 111$ sein -- da $C = [mm] \{ 000, 111 \}$ [/mm] (das besagt die ML-Eigenschaft).
Das Element $001 [mm] \in A^3$ [/mm] hat jetzt z.B. den Abstand 1 zu $000 [mm] \in [/mm] C$ und den Abstand 2 zu $111 [mm] \in [/mm] C$. Deswegen muss wegen der ML-Eigenschaft [mm] $\pi(001) [/mm] = 000$ gelten. Genauso gilt [mm] $\pi(010) [/mm] = [mm] \pi(100) [/mm] = 000$.
Das Element $110 [mm] \in A^3$ [/mm] hat jetzt den Abstand 1 zu $111 [mm] \in [/mm] C$ und den Abstand 2 zu $000 [mm] \in [/mm] C$. Deswegen muss wegen der ML-Eigenschaft [mm] $\pi(110) [/mm] = 111$ gelten. Und genauso [mm] $\pi(101) [/mm] = [mm] \pi(011) [/mm] = 111$.
So. Und damit ist [mm] $\pi$ [/mm] im Fall $n = 3$ eindeutig bestimmt.
Ist $n$ ganz allgemein, so wird ein Wort mit $k$ Nullen und $n-k$ Einsen durch [mm] $\pi [/mm] : [mm] A^n \to [/mm] C$ auf $00...00$ abgeblidet, falls $k > n/2$ ist, und auf $11...11$, falls $k < n/2$ ist: das besagt ebenfalls die ML-Eigenschaft, da die Hamming-Distanz vom Wort zu $00...00$ gleich $n-k$ und die Hamming-Distanz vom Wort zu $11...11$ gleich $k$ ist.
Interessant bleibt also der Fall $k = n - k = [mm] \frac{n}{2}$, [/mm] der nur eintreten kann, wenn $n$ gerade ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:57 So 22.04.2012 | | Autor: | chesn |
Jetzt verstehe ich zumindest ansatzweise erstmal die Aufgabenstellung.. vielen Dank Felix! :)
Im Fall [mm] k=n-k=\bruch{n}{2} [/mm] gibt es also zwei Projektionen, einmal auf [mm] \{111...1\} [/mm] und auf [mm] \{000...0\} [/mm] wenn die Anzahl der Einsen und Nullen gleich ist.
D.h. wenn z.B. [mm] x=\{10101\} [/mm] dann ist [mm] \phi(x)=\{11111\} [/mm] mit Abstand [mm] ||x,\phi(x)||=2 [/mm] und min(||x,y||)=2 denn y ist entweder [mm] \{00000\} [/mm] oder [mm] \{11111\}.
[/mm]
Für gerade n gibt es dann z.B. [mm] x=\{010101\} [/mm] wobei [mm] \phi(x) [/mm] nicht eindeutig ist, es kann also [mm] \phi(x)=\{111111\} [/mm] oder [mm] \phi(x)=\{000000\} [/mm] sein.
Habe ich das so richtig verstanden???
Vielen Dank nochmal! :)
Liebe Grüße
chesn
Edit: Irgendwie hab ich grad phi und pi verwechselt aber macht ja nix. :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Di 24.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
