Zyklische Codes < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:23 Di 15.01.2013 | | Autor: | Uzaku |
| Aufgabe | | Finden Sie den kleinsten Zyklischen (9,k)-Linearcode über [mm] \IZ_3, [/mm] der das Element 002220000 enthällt. Bestimmen Sie dim C, die Anzahl der Elemente von C und eine Basis von C. |
Hey,
erst mal entschuldigung, falls ich das falsche Unterforum erwischt habe, ich bin mir nicht sicher, ob das wirklich das richtige ist.
Jetzt zu meinem Problem mit der Aufgabe. Ich weiß, dass die Anzahl der elemente 3^(dim C) sein wird (und dim C = k ist), und wenn ich erst mal das Generatorpolynom g(x) kenne, wird es auch nicht mehr schwer, k linear unabhängige Vekotren für die Basis zu finden.
Aber das Generatorpolynom bereitet mir Kopfzerbrechen. Wenn das vorgegebene Codewort nicht wäre würde ich einfach [mm] x^3+1 [/mm] oder so nehmen. Aber ich weiß nicht, wie ich es machen kann, dass das Codewort im Code enthalten ist. Erst wollte ich [mm] 2*x^4+2*x^3+2*x^2 [/mm] nehmen (weil Polynomschreibweise des Codeworts), aber das teilt [mm] x^9-1 [/mm] ärgerlicherweise nicht.
Und ich habe noch eine Frage:
Da der Code Zyklisch sein muss, und schon ein Codewort gegeben ist, würde das nicht automatisch bedeuten, dass es nur 9 Codewörter geben kann? Weil man durch verschiebung nur auf 9 verschiedene Worte kommen kann? Dann wäre die dimension, und somit k=2. Und das Generatorpolynom müsste den Grad 7 haben, aber wie finde ich dann das Generatorpolynom (außer indem ich [mm] x^9-1 [/mm] testweise durch alle Polynome 2ten Grades teile, was bei Grad 2 gerade noch ginge, aber auch dann wüsste ich nicht, ob es auch das gegebene Codewort erzeugt)
Also ihr seht das Chaos in meinem Kopf, wie löse ich jetzt diese Aufgabe?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:13 Do 17.01.2013 | | Autor: | felixf |
Moin!
> Finden Sie den kleinsten Zyklischen (9,k)-Linearcode über
> [mm]\IZ_3,[/mm] der das Element 002220000 enthällt. Bestimmen Sie
> dim C, die Anzahl der Elemente von C und eine Basis von C.
>
>
> Hey,
> erst mal entschuldigung, falls ich das falsche Unterforum
> erwischt habe, ich bin mir nicht sicher, ob das wirklich
> das richtige ist.
Ich denke, das ist hier schon richtig.
> Jetzt zu meinem Problem mit der Aufgabe. Ich weiß, dass
> die Anzahl der elemente 3^(dim C) sein wird (und dim C = k
> ist), und wenn ich erst mal das Generatorpolynom g(x)
> kenne, wird es auch nicht mehr schwer, k linear
> unabhängige Vekotren für die Basis zu finden.
> Aber das Generatorpolynom bereitet mir Kopfzerbrechen. Wenn
> das vorgegebene Codewort nicht wäre würde ich einfach
> [mm]x^3+1[/mm] oder so nehmen. Aber ich weiß nicht, wie ich es
> machen kann, dass das Codewort im Code enthalten ist. Erst
> wollte ich [mm]2*x^4+2*x^3+2*x^2[/mm] nehmen (weil
> Polynomschreibweise des Codeworts), aber das teilt [mm]x^9-1[/mm]
> ärgerlicherweise nicht.
Du weisst doch sicher, dass zyklische Codes $C [mm] \subseteq \IF_3^9$ [/mm] gerade die Ideale in [mm] $\IF_3[x]/(x^9-1)$ [/mm] sind. Du musst also das kleinste Ideal in dem Ring bestimmen, welches das von dir aufgeschriebene Polynom umfasst.
Um das Ideal zu bestimmen kannst du auch erstmal das kleinste Ideal in [mm] $\IF_3[x]$ [/mm] anschauen, welches dieses Polynom und [mm] $x^9 [/mm] - 1$ umfasst. Dies ist ein Hauptideal und du kannst recht einfach einen Erzeuger finden, der automatisch ein Teiler von [mm] $x^9 [/mm] - 1$ ist. Dieser Erzeuger erzeugt dann in [mm] $\IF_3[x]/(x^9-1)$ [/mm] das kleinste Ideal, welches das gesuchte Codewort umfasst.
> Und ich habe noch eine Frage:
> Da der Code Zyklisch sein muss, und schon ein Codewort
> gegeben ist, würde das nicht automatisch bedeuten, dass es
> nur 9 Codewörter geben kann? Weil man durch verschiebung
> nur auf 9 verschiedene Worte kommen kann?
Das waer dann aber kein linearer Code; allein schon weil der Nullvektor nicht drinnen ist. Du musst auch beliebige Linearkombinationen dieser 9 Woerter zulassen. (Ueberlege dir, dass das Ergebnis davon ein zyklischer Code ist. Dies liefert dir eine weitere Moeglichkeit, den gesuchten Code zu bestimmen, indem du eine Basis von ihm bestimmst.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:41 Do 17.01.2013 | | Autor: | Uzaku |
> Du weisst doch sicher, dass zyklische Codes [mm]C \subseteq \IF_3^9[/mm]
> gerade die Ideale in [mm]\IF_3[x]/(x^9-1)[/mm] sind. Du musst also
> das kleinste Ideal in dem Ring bestimmen, welches das von
> dir aufgeschriebene Polynom umfasst.
Ich kannte die Bedeutung von Ideal in dem Zusammenhang nicht, wenn ich das richtig verstanden habe, meinst du damit, dass die Zyklischen Codes eine Untergruppe des 9 Dimensionalen Vektorraums über GF(3) sind, oder?
> Um das Ideal zu bestimmen kannst du auch erstmal das
> kleinste Ideal in [mm]\IF_3[x][/mm] anschauen, welches dieses
> Polynom und [mm]x^9 - 1[/mm] umfasst.
Nach allem was ich bisher gelernt habe, kann ein (9,k)-Linearcode gar nicht das wort zu [mm]x^9-1[/mm] enthalten, weil das ja die 10te Stelle wäre, und der Code nur 9 Stellen enthällt, von daher verwirrt mich das etwas
> Das waer dann aber kein linearer Code; allein schon weil
> der Nullvektor nicht drinnen ist. Du musst auch beliebige
> Linearkombinationen dieser 9 Woerter zulassen. (Ueberlege
> dir, dass das Ergebnis davon ein zyklischer Code ist. Dies
> liefert dir eine weitere Moeglichkeit, den gesuchten Code
> zu bestimmen, indem du eine Basis von ihm bestimmst.)
Aber bedeutet nicht das Zyklisch nicht, dass der komplette Code aus jedem Codewort erzeugbar ist, in dem man es einfach verschiebt?
Sorry, dass ich mich gerade etwas Begriffsstutzig anstelle
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:13 Fr 18.01.2013 | | Autor: | felixf |
Moin!
> > Du weisst doch sicher, dass zyklische Codes [mm]C \subseteq \IF_3^9[/mm]
> > gerade die Ideale in [mm]\IF_3[x]/(x^9-1)[/mm] sind. Du musst also
> > das kleinste Ideal in dem Ring bestimmen, welches das von
> > dir aufgeschriebene Polynom umfasst.
>
> Ich kannte die Bedeutung von Ideal in dem Zusammenhang
> nicht, wenn ich das richtig verstanden habe, meinst du
Hmm, wie habt ihr denn die Klassifikation von zyklischen Codes mit Generatorpolynom etc. gemacht, wenn der Begriff eines Ideals gar nicht gefallen ist?
> damit, dass die Zyklischen Codes eine Untergruppe des 9
> Dimensionalen Vektorraums über GF(3) sind, oder?
Es ist eine Untergruppe, die abgeschlossen bzgl. Multiplikation ist, wenn man [mm] $GF(3)^9$ [/mm] mit [mm] $GF(3)[x]/(x^9 [/mm] - 1)$ identifiziert.
> > Um das Ideal zu bestimmen kannst du auch erstmal das
> > kleinste Ideal in [mm]\IF_3[x][/mm] anschauen, welches dieses
> > Polynom und [mm]x^9 - 1[/mm] umfasst.
>
> Nach allem was ich bisher gelernt habe, kann ein
> (9,k)-Linearcode gar nicht das wort zu [mm]x^9-1[/mm] enthalten,
Es ist auch kein Codewort. Ich rede hier vom Polynomring $GF(3)[x]$. Der Quotient davon modulo [mm] $x^9-1$ [/mm] ist isomorph zu [mm] $GF(3)^9$ [/mm] und erlaubt, die zyklischen Codes sehr einfach zu beschreiben.
> weil das ja die 10te Stelle wäre, und der Code nur 9
> Stellen enthällt, von daher verwirrt mich das etwas
Wenn du das mit Idealen nicht kennst, geh am besten so vor:
> > Das waer dann aber kein linearer Code; allein schon weil
> > der Nullvektor nicht drinnen ist. Du musst auch beliebige
> > Linearkombinationen dieser 9 Woerter zulassen. (Ueberlege
> > dir, dass das Ergebnis davon ein zyklischer Code ist. Dies
> > liefert dir eine weitere Moeglichkeit, den gesuchten Code
> > zu bestimmen, indem du eine Basis von ihm bestimmst.)
>
> Aber bedeutet nicht das Zyklisch nicht, dass der komplette
> Code aus jedem Codewort erzeugbar ist, in dem man es
> einfach verschiebt?
Nein. Das Ergebnis ist i.A. kein linearer Code! (Es sei denn du nimmst das Wort, was nur aus Nullen besteht.)
Du sollst den kleinsten linearen zyklischen Code finden. Zyklisch bedeutet, dass jedes Codewort verschoben wieder im Code liegt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:10 Fr 18.01.2013 | | Autor: | Uzaku |
Hmm, wie habt ihr denn die Klassifikation von zyklischen Codes mit Generatorpolynom etc. gemacht, wenn der Begriff eines Ideals gar nicht gefallen ist?
Also dazu weiß ich, dass alle Polynome eines Zyklischen Linearcodes C Vielfache des Generatorpolynoms sind, und dass das Generatorpolynom dementsprechend das Polynom in C mit dem kleinsten Grad ist, und dass das Generatorpolynom [mm] x^n-1 [/mm] teilen muss.
Da fällt mir auf, dass Ich wenn ich [mm] 2x^4+2x^3+2x^2 [/mm] und [mm] x^9-1 [/mm] faktorisiere auf jeden fall auch das Generatorpolynom habm, weil es ja der kleinste gemeinsame Teiler sein müsste, aber um [mm] x^9-1 [/mm] zu zerlegen brauche ich ewig, und das is keinesfalls eine Vorgehensweise, die ich in einer Klausur nutzen könnte.
Den 2ten Ansatz, den du mir gegeben hast, habe ich jetzt glaube ich verstanden. Ich nehme (002220000), und alle seine verschiebungen, und fange an, das beliebig zu addieren, und multiplizieren (mod 3 natürlich), solange bis ich auch diese Art keine neuen Elemente mehr erzeugen kann.
Allerdings scheint mir dass auch nicht der geeignete Lösungsweg zu sein, denn der Code hat [mm] 3^n [/mm] Elemente, und es sind schonmal definitiv mehr als 9. Da auch in der Aufgabenstellung nciht gefragt ist, alle Codewörter anzugeben, denke ich nicht, dass das der erwartete Lösungsweg ist, sondern dass ich stattdessen irgendwie vom Codewort auf das Generatorpolynom kommen muss.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:45 Fr 18.01.2013 | | Autor: | felixf |
Moin!
> Hmm, wie habt ihr denn die Klassifikation von zyklischen
> Codes mit Generatorpolynom etc. gemacht, wenn der Begriff
> eines Ideals gar nicht gefallen ist?
>
> Also dazu weiß ich, dass alle Polynome eines Zyklischen
> Linearcodes C Vielfache des Generatorpolynoms sind, und
> dass das Generatorpolynom dementsprechend das Polynom in C
> mit dem kleinsten Grad ist, und dass das Generatorpolynom
> [mm]x^n-1[/mm] teilen muss.
Wenn man das ganze mit Idealen formuliert, ist es noch etwas schoener. Es sei denn man mag Algebra nicht 
> Da fällt mir auf, dass Ich wenn ich [mm]2x^4+2x^3+2x^2[/mm] und
> [mm]x^9-1[/mm] faktorisiere auf jeden fall auch das Generatorpolynom
> habm, weil es ja der kleinste gemeinsame Teiler sein
> müsste, aber um [mm]x^9-1[/mm] zu zerlegen brauche ich ewig, und
> das is keinesfalls eine Vorgehensweise, die ich in einer
> Klausur nutzen könnte.
Verwende doch einfach den euklidischen Algorithmus. Der ist eh viel effizienter als alles erst in Primfaktoren zu zerlegen (es sei denn man hat Baby-Beispiele). Und zwar sowohl in [mm] $\IZ$ [/mm] wie auch in Polynomringen ueber Koerpern.
> Den 2ten Ansatz, den du mir gegeben hast, habe ich jetzt
> glaube ich verstanden. Ich nehme (002220000), und alle
> seine verschiebungen, und fange an, das beliebig zu
> addieren, und multiplizieren (mod 3 natürlich), solange
> bis ich auch diese Art keine neuen Elemente mehr erzeugen
> kann.
> Allerdings scheint mir dass auch nicht der geeignete
> Lösungsweg zu sein, denn der Code hat [mm]3^n[/mm] Elemente, und es
> sind schonmal definitiv mehr als 9. Da auch in der
> Aufgabenstellung nciht gefragt ist, alle Codewörter
> anzugeben, denke ich nicht, dass das der erwartete
> Lösungsweg ist, sondern dass ich stattdessen irgendwie vom
> Codewort auf das Generatorpolynom kommen muss.
Nun, so kompliziert musst du es auch nicht machen, wenn du in der linearen Algebra gut aufgepasst hast :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:57 Fr 18.01.2013 | | Autor: | Uzaku |
> Wenn man das ganze mit Idealen formuliert, ist es noch
> etwas schoener. Es sei denn man mag Algebra nicht
Ich finde Algebra eigentlich ganz nett, aber ich bin nicht besonders gut darin so mathematische Formulierungen zu verstehen, und schon gar nicht darin sie zu verwenden^^
> Verwende doch einfach den euklidischen Algorithmus. Der ist
> eh viel effizienter als alles erst in Primfaktoren zu
> zerlegen (es sei denn man hat Baby-Beispiele). Und zwar
> sowohl in [mm]\IZ[/mm] wie auch in Polynomringen ueber Koerpern.
Euklides ... stimmt, da war mal was. Danke für den Tipp, ich glaube ich habs jetzt. Also, für den Euklidischen Algoritmus bei Polynomen muss man ja die Polynomdivision benutzen, oder?
[mm] (x^9-1):(2x^4+2x^3+2x^2) [/mm] hat den Rest x-1. Das dürfte dann ja direkt das Generator-Polynom sein, oder?
Daraus würde sich ergeben, dass dim(C) = 8 ist, und der Code [mm] 3^8 [/mm] Elemente hat.
Aber wenn ich da jetzt 8 Vektoren erzeuge, brauche ich ne halbe Ewigkeit um zu prüfen ob die linear unabhängig sind, und falls sies nicht sind, muss ich nen Weiteren nehmen, und nochmal prüfen. Hast du was das angeht vielleicht noch nen Tipp?
Ansonsten schonmal danke für deine Geduld und Hilfe :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:19 Sa 19.01.2013 | | Autor: | felixf |
Moin!
> > Wenn man das ganze mit Idealen formuliert, ist es noch
> > etwas schoener. Es sei denn man mag Algebra nicht
>
> Ich finde Algebra eigentlich ganz nett, aber ich bin nicht
> besonders gut darin so mathematische Formulierungen zu
> verstehen, und schon gar nicht darin sie zu verwenden^^
Nun, Uebung hilft da :)
> > Verwende doch einfach den euklidischen Algorithmus. Der ist
> > eh viel effizienter als alles erst in Primfaktoren zu
> > zerlegen (es sei denn man hat Baby-Beispiele). Und zwar
> > sowohl in [mm]\IZ[/mm] wie auch in Polynomringen ueber Koerpern.
>
> Euklides ... stimmt, da war mal was. Danke für den Tipp,
> ich glaube ich habs jetzt. Also, für den Euklidischen
> Algoritmus bei Polynomen muss man ja die Polynomdivision
> benutzen, oder?
Genau.
> [mm](x^9-1):(2x^4+2x^3+2x^2)[/mm] hat den Rest x-1. Das dürfte
> dann ja direkt das Generator-Polynom sein, oder?
Also bei mir hat [mm] $x^9 [/mm] - 1$ bei Division durch [mm] $x^4+x^3+x^2$ [/mm] den Rest [mm] $x^3 [/mm] - 1$. Der ggT ist schliesslich ein Polynom vom Grad 2.
> Daraus würde sich ergeben, dass dim(C) = 8 ist, und der
> Code [mm]3^8[/mm] Elemente hat.
Wenn tatsaechlich $x - 1$ herauskommen wuerde, dann waer das richtig.
> Aber wenn ich da jetzt 8 Vektoren erzeuge, brauche ich ne
> halbe Ewigkeit um zu prüfen ob die linear unabhängig
> sind, und falls sies nicht sind, muss ich nen Weiteren
> nehmen, und nochmal prüfen. Hast du was das angeht
> vielleicht noch nen Tipp?
Nun, du weisst doch sicher, wie man aus dem Generatorpolynom eine Basis bekommt? Das geht sehr einfach und du brauchst dann nichts nachzupruefen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:57 Sa 19.01.2013 | | Autor: | Uzaku |
Ok, ich bins jetzt nochmal durchgegangen, und hab als Generatorpolynom: [mm] 2x^2+2x+2 [/mm] dim(c) = 7, und ich kenne kein Verfahren, aber ich vermute, dass man als Basis einfach das Generatorpolynom und seine [mm] x^n [/mm] - Fachen nimmt, das geht ja genau auf.
Nochmal vielen Dank :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:00 So 20.01.2013 | | Autor: | felixf |
Moin!
> Ok, ich bins jetzt nochmal durchgegangen, und hab als
> Generatorpolynom: [mm]2x^2+2x+2[/mm] dim(c) = 7,
Genau.
> und ich kenne kein
> Verfahren, aber ich vermute, dass man als Basis einfach das
> Generatorpolynom und seine [mm]x^n[/mm] - Fachen nimmt, das geht ja
> genau auf.
Exakt. Ist [mm] $\deg [/mm] f = k$ und $f$ teilt [mm] $x^n [/mm] - 1$, so ist $f, x f, [mm] x^2 [/mm] f, [mm] \dots, x^{n-k} [/mm] f$ eine Basis vom zyklischen Code mit Generatorpolynom $f$.
LG Felix
|
|
|
|
