diskrete Mathematik < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi Ihr!
Wieder zwei für mich bedingt verständliche Aufgaben brechen mir meine Geduld.
Vileeicht darf ich eure wieder beasten?
wär super.
1. Ein linearer (n,k)-Code C heiße t-perfekt: [mm] \gdw [/mm] : es gibt für [mm] y\in [/mm] V n genau ein [mm] c\in [/mm] C: d(y,c)<= t.
a) Warum kann es keinen 1-pe3rfekten linearen (3,2)-Code geben?
b) Welche notwendige Bedingung müssen n und k erfüllen, damit ein linearer (n,k)-Code eine Chance auf 1 Perfektheit besitzt? (Hinweis: Eine der folgenden Bedingungen für [mm] n\in \IN [/mm] ist richtig: n=2 r oder
n=2 r-1 mit [mm] r\in \IN [/mm] oder n Primzahl)
c) Beweise oder widerlege: n=23 und k= 12 erfüllen die notwendige Bedingung für die Existenz eines 3-perfekten Codes.
2. Zur Eulerschen Phi-Funktion: [mm] \IN [/mm] geht zu [mm] \IN [/mm] , phi(n):=|[1 kleiner gleich k kleiner gleich n | ggt(k,n)=1]|:
a) Gesucht sind vier verschiedene [mm] n\in \IN [/mm] mit phi(n)=4
b) Gesucht sind Primzahlen p und q mit pq=14803 und phi(pq)=14560
Ich hoffe ihr könnt mir irgendwie wieder weiterhelfen.
Vielen Dank!!!!
Euer Björn
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:32 Sa 17.01.2004 | | Autor: | Stefan |
Hallo Björn,
zu 1. muss ich erst was in dem Beutelspacher-Buch nachlesen.
Zu 2., das ist elementare Zahlentheorie, kann ich jetzt schon was sagen:
a) Einfach mal ausprobieren! Es geht zum Beispiel für [mm]n=5[/mm], [mm]n=8[/mm], [mm]n=10[/mm] und [mm]n=12[/mm].
Oder verstehst du die Definition von [mm]\phi(n)[/mm] nicht? Dann frage bitte nach.
b) Für eine Primzahl [mm]p[/mm] gilt:
[mm]\phi(p)=p-1[/mm]. (Warum? Überlege dir das bitte! Oder frage nach.)
Daher müssen die beiden folgenden Gleichungen erfüllt sein:
(I) [mm] p\cdot q = 14803[/mm]
(II) [mm](p-1)\cdot (q-1) = 14560[/mm]
Multipliziere (II) aus:
[mm]p\cdot q - p - q + 1 = 14560[/mm]
Zieht man die beiden Gleichungen voneinander ab und löst nach [mm]p[/mm] auf, so erhält man:
[mm]p=244-q[/mm].
Setze dies nun in (I) ein. Dann erhältst du zwei Lösungen für [mm]p[/mm] (und damit auch zwei Lösungen für [mm]q[/mm]). Die beiden Lösungen sind aber sozusagen symmetrisch, so dass du für das Problem eine Lösung erhältst.
Welche?
Melde dich mal mit einem Lösungsvorschlag...
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:14 So 18.01.2004 | | Autor: | Stefan |
Hallo Björn,
leider kenne ich hier die Definitionen nicht. Ich wollte sie im Beutelspacher nachlesen, aber sie stehen dort nicht. Benutzt ihr mittlerweile ein anderes Buch als Grundlage? Wenn ja, welches?
Vielleicht kannst du uns ja mal alle Dinge hier definieren. Dann bin ich mir sicher, dass Marc und ich (und vielleicht auch andere) die Aufgabe locker hinkriegen. (Jedenfalls dann, wenn sich der Schwierigkeitsgrad dieser Aufgabe im Bereich eurer bisherigen Aufgaben bewegt.) Hier meine Fragen:
1) Was ist ein (n,k)-Code? (falls es das alleine gibt)
2) Was ist ein linearer (n,k)-Code?
3) Was ist V?
4) Was ist d(y,c)? Ist dies eine Metrik? Wie ist sie definiert?
Sobald wir alle Definitionen haben, werden wir die Lösung hoffentlich (ich bin so vermessen zu sagen: mit Sicherheit) hinkriegen.
Aber hellsehen, was diese Begriffe bedeuten, kann ich leider nicht. 
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:46 So 18.01.2004 | | Autor: | phymastudi |
Hi Stefan!
Klar! Sorry!
Also.
1. Jeder k-dimensionaler Untervektorraum von V [mm] n={(a1,...,an)|ai\in {0,1}} [/mm] heisst linearer (n,k)-Code.
2. Ein (n,k)-Code ist ein Code mit Codewortlänge n und Dimension k. Beispiel. (3,1)-Code ist: {(o,o,o),(1,1,1)}. Dieser Code ist sogar ein Linearcode.
3. V ist ein Vektorraum
4. d ist der Hammingabstnad zweier Codewörter.
Seien x=(x1,...,xn) und y=(y1,...,yn) Codewörter eines beliebigen Codes. Dann heisst d(x,y):= [mm] |{i\in 71,...,n0
Bemerkung.
Das wired vermutlivch irgendwie mit einer Generatormatrix lösbar sein.
Vielen Dank für eure Mühen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:10 So 18.01.2004 | | Autor: | Stefan |
Hallo Björn!
Weitere Verständnisfragen:
1) Ist es richtig, dass [mm]V[/mm] einfach der [mm]\IZ_2^n[/mm] ist, mit der üblichen Addition und skalaren Multiplikation?
2) Zu dieser Definition vonr dir:
> 1. Ein linearer (n,k)-Code C heiße [mm] t-perfekt:\gdw [/mm] : es gibt für [mm] y\in [/mm] V n
> genau [mm] einc\in [/mm] C: d(y,c)<= t.
habe ich eine Frage: Muss es für jedes [mm]y \in V[/mm] ein von [mm]y[/mm] unabhängiges [mm]c \in C[/mm] mit [mm]d(y,c) \le t[/mm] geben oder darf [mm]c[/mm] von [mm]y[/mm] abhängen?
3) Was ist in diesem Fall eine Generatormatrix? Schreibe uns mal ein komplettes Beispiel dazu hier ins Forum.
Mir ist die ganze Struktur noch nicht so klar (dir, Marc?), von daher kann ich mich mit der Aufgabe auch noch nicht so richtig beschäftigen. Wir brauchen erst einmal alle Infos um das Drumherum. Du solltest es so erklären, dass jemand, der nie in der Vorlesung war, versteht, worum es geht. Versuche bitte erst einmal die Fragen 1)-3) zu beantworten.
Es wäre nett, wenn du unsere mathematische Eingabehilfe korrekt benutzen würdest, dann kann man deine Texte auch besser lesen.
Wir helfen dir dann weiter, sobald alle Fragen geklärt sind.
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:17 So 18.01.2004 | | Autor: | Marc |
Hallo zusammen,
> 1) Ist es richtig, dass [mm]V[/mm] einfach der [mm]\IZ_2^n[/mm] ist, mit der
> üblichen Addition und skalaren Multiplikation?
Ich vermute (auch), ja.
> 2) Zu dieser Definition vonr dir:
>
> > 1. Ein linearer (n,k)-Code C heiße [mm] t-perfekt:\gdw [/mm] : es
> gibt für [mm] y\in [/mm] V n
> > genau [mm] einc\in [/mm] C: d(y,c)<= t.
>
> habe ich eine Frage: Muss es für jedes [mm]y \in V[/mm] ein von [mm]y[/mm]
> unabhängiges [mm]c \in C[/mm] mit [mm]d(y,c) \le t[/mm] geben oder darf [mm]c[/mm] von
> [mm]y[/mm] abhängen?
Das kann im Hinblick auf die 1. Frage doch nicht so schwierig herzuleiten sein (als Ansporn für mich gedacht), denn V hat doch nur 8 Vektoren:
{000, 001, 010, 011, 100, 101, 110, 111}
Und diese 2-dim Untervektorräume:
{000, 001, 010, 011}
{000, 001, 100, 110}
{000, 010, 100, 110}
{000, 001, 100, 110}
{000, 111, 001, 110}
{000, 111, 010, 101}
{000, 111, 100, 011}
{000, 110, 011, 101}
(Gibt es mehr?)
Davon rechne ich gleich mal die Hammingabstände aus...
> 3) Was ist in diesem Fall eine Generatormatrix? Schreibe
> uns mal ein komplettes Beispiel dazu hier ins Forum.
Keine Ahnung.
Bis gleich,
Marc.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:44 So 18.01.2004 | | Autor: | Marc |
Hallo zusammen,
aus dem Bauch heraus würde ich sagen, dass das c für jedes y einzeln zu finden sein muß und dass dabei noch wichtig ist, dass es nur genau ein c gibt.
Denn V enthält ja Wörter, die möglich sind, C nur solche, die tatsächlich gültig sind. Ein 1-perfekter Code würde dann für jedes mögliche Wort aus V, das nur einen (Übertragungs-) Fehler enthält, eindeutig auf das gültige Wort c schließen lassen, also zur Fehlererkennung wäre auch noch eine Korrektur möglich.
Ein 2-perfekter Code erlaubt sogar zwei Fehler, da diese erkannt und sogar verbessert werden können.
Das ist aber sehr vage von mir vermutet/geraten.
Ich bleibe dran,
Marc.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:59 So 18.01.2004 | | Autor: | Marc |
Hallo zusammen,
> V={000, 001, 010, 011, 100, 101, 110, 111}
>
> Und diese 2-dim Untervektorräume:
> {000, 001, 010, 011}
> {000, 001, 100, 110}
> {000, 010, 100, 110}
> {000, 001, 100, 110}
>
> {000, 111, 001, 110}
> {000, 111, 010, 101}
> {000, 111, 100, 011}
Alle diese Unterräume kommen für C nicht in Frage, da sie Vektoren enthalten, die nur genau eine 1 haben; für diesen Vektor gilt dann
d(000,001)=d(000,010)=d(000,100)=1
Da aber sowieso gilt
d(000,000)=0
gibt es bei all diesen Vektorräumen für 000 kein eindeutig bestimmtes c mit d(000,c)<=1.
> {000, 110, 011, 101}
000: d(000,000)=0, d(000,110)=2, d(000,011)=2, d(000,101)=2 (c eindeutig bestimmt)
001: d(001,000)=1, d(001,110)=3, d(001,011)=1 (c nicht eindeutig bestimmt)
Also gibt es keinen (3,2)-Code, der 1-perfekt ist.
Bin mal gespannt, welche Empörungsstürme jetzt auf mich niedergehen...
Marc.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:40 So 18.01.2004 | | Autor: | Stefan |
Lieber Marc,
aha, so langsam kapiere selbst ich den Witz hier.
Kling logisch, ja.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:54 So 18.01.2004 | | Autor: | Stefan |
Hallo zusammen,
ich habe 1b) und 1c) gelöst.
Hallo Björn, schaue doch nachher einfach noch mal ins Forum. 
Bin gerade noch am Telefonieren...
Bis nachher!
Alles Gute
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:30 So 18.01.2004 | | Autor: | Stefan |
Hallo Björn,
jetzt habe ich dank Marc die Aufgabenstellung endlich verstanden. Damit war, wie bereits vermutet, das größte Problem aus dem Weg geräumt, der Rest war dann mehr oder weniger eine kombinatorische Fingerübung.
zu b) Wieviel Elemente haben [mm]V[/mm] und [mm]C[/mm] ?
[mm]V[/mm] hat [mm]2^n[/mm] und [mm]C[/mm] hat [mm]2^k[/mm] Elemente. Die Elemente aus [mm]V[/mm] lassen sich jetzt aber auf eineindeutige Weise den Elementen aus [mm]C[/mm] zuordnen. Jedes [mm]x \in V[/mm] orden wir demjenigen (nach Voraussetzung eindeutig bestimmten!) [mm]c(x)[/mm] aus [mm]C[/mm] zu, so dass [mm]d(x,c(x))\le 1[/mm] gilt. Damit haben wir eine Partition der Menge [mm]V[/mm] gefunden.
[mm]V[/mm] lässt sich als disjunkte Vereinigung darstellen:
[mm]V = M(c_1) \cup \ldots \cup M(c_{2^k})[/mm],
wobei [mm]x \in M(c_i)[/mm] genau dann gilt, wenn [mm]d(x,c_i) \le 1[/mm] gilt.
Jedes [mm]M(c_i)[/mm] ist jedoch gleichmächtig. Denn in [mm]M(c_i)[/mm] liegen neben [mm]c_i[/mm] selbst (also dem Element aus [mm]V[/mm], das zu [mm]c_i[/mm] den Abstand 0 hat) alle Elemente aus [mm]V[/mm], die zu [mm]c_i[/mm] den Abstand 1 haben. Aber klar ist: Diese erreicht man genau dadurch, dass man genau eine Komponente von [mm]c_i[/mm] verändert. Da [mm]c_i[/mm] genau [mm]n[/mm] Komponenten hat, gilt:
[mm]|M(c_i)| = 1 + n[/mm] für alle [mm]i=1,\ldots, 2^k[/mm].
Es muss also notwendigerweise die Beziehung
[mm]|C| \cdot |M(c_i)| = |V|[/mm],
also:
[mm]2^k \cdot (1+n) = 2^n[/mm]
gelten, also
[mm]n = 2^{n-k} - 1[/mm].
(Insbesondere muss [mm]n[/mm] notwendigerweise ungerade sein.)
Rückblick auf a):
Es kann keinen 1-perfekten (3,2)-Code geben, da
[mm]3 \ne 1 = 2^{3-2}-1[/mm]
gilt.
Nun zu c):
Die Argumentation geht wie in b):
[mm]V[/mm] lässt sich als disjunkte Vereinigung darstellen:
[mm]V = M(c_1) \cup \ldots \cup M(c_{2^k})[/mm],
wobei [mm]x \in M(c_i)[/mm] genau dann gilt, wenn [mm]d(x,c_i) \le 3[/mm] gilt.
Jedes [mm]M(c_i)[/mm] ist jedoch gleichmächtig. Denn in [mm]M(c_i)[/mm] liegen neben [mm]c_i[/mm] selbst (also dem Element aus [mm]V[/mm], das zu [mm]c_i[/mm] den Abstand 0 hat) alle Elemente aus [mm]V[/mm], die zu [mm]c_i[/mm] den Abstand 1, 2 oder 3 haben. Aber klar ist: Diese erreicht man genau dadurch, dass man genau eine Komponente von [mm]c_i[/mm], genau zwei Komponenten und genau drei Komponenten verändert. Dafür gibt es genau [mm]n[/mm], [mm]{n \choose 2}[/mm] und [mm]{n \choose 3}[/mm] Möglichkeiten. Es folgt also in diesem Fall (systematisch aufgeschrieben, damit du das System erkennst):
[mm]|M(c_i)| = {n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3} = 1 + n + {n \choose 2} + {n \choose 3}[/mm]
für alle [mm]i=1,\ldots, 2^k[/mm].
Es muss also notwendigerweise die Beziehung
[mm]|C| \cdot |M(c_i)| = |V|[/mm],
also:
[mm]2^k \cdot (1+n+ {n \choose 2} + {n \choose 3}) = 2^n[/mm]
gelten,
also:
[mm]1+n+ {n \choose 2} + {n \choose 3} = 2^{n-k}[/mm].
Diese notwendige Bedingung ist für [mm]n=23[/mm] und [mm]k=12[/mm] erfüllt, denn
[mm]1 + 23 + {23 \choose 2} + {23 \choose 3} = 2048 = 2^{11} = 2^{23-12}[/mm].
Gute Nacht!
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:27 Mo 19.01.2004 | | Autor: | phymastudi |
Hallo Stefan, Hallo MArc!
Erneut erstmal vielen Dank für eure Hilfe. Wenn man erstmal die Lösung vor Augen hat sieht alles so logich aus.
Manchmal denke ich, ich bin einfach zu blöd, aber dann habe ich auch wieder Sternstunden, bei denen ich schwere Aufgaben ganz allein lösen kann.
Ich habe mittlerweile ein ziemlich schlechtes Gewissen, weil ich nur mit Fragen auftrete und mich doch auch gern mal produktiv einbringen möchte. Doch ich bin in meiner Mathematik, iwe ihr ja merkt, selbst noch sehr unsicher und Fragen zu anderen Klassenstufen sind immer schon beantwortet, ehe man sich beteiligen kann.
Daher hoffe ich nicht, dass ihr mir allzu böse seid.
Gruß Björn
|
|
|
|
