Dimension eines zyklischen Codes

03.12.2021, 16:03	Studentu	Auf diesen Beitrag antworten »
Dimension eines zyklischen Codes Meine Frage: Hallo, ich hätte eine Frage, für die wir den Begriff des zyklischen Codes benötigen: Ein zyklischer Code C ist ein Unterraum eines Vektorraumes über einem Körper A, der erfüllt, dass $\begin{eqnarray} (c_0, \dotsc, c_{n-1}) \in C \Rightarrow (c_{n-1}, c_0, \dotsc, c_{n-2}) \in C \end{eqnarray}$ . Ein zyklischer Code der Länge n über einem Körper A entspricht in eindeutiger Weise einem Ideal $\begin{eqnarray} A[x]/(x^n-1) \end{eqnarray}$ . Das normierte Polynom ungleich dem Nullypolynom minimalen Grades in C nennt man Generatorpolynom. Es ist immer ein Teiler von $\begin{eqnarray} x^n-1 \end{eqnarray}$ . Die Behauptung ist nun, dass für die Dimension k eines zyklischen Codes gilt: $\begin{eqnarray} k = n - grad g(x) \end{eqnarray}$ , wobei g das Generatorpolynom des Codes sei. Meine Ideen: Als Begründung dafür ist angegeben, dass $\begin{eqnarray} f(x) \mapsto f(x)g(x) \end{eqnarray}$ für $\begin{eqnarray} grad f(x) < n - grad g(x) \end{eqnarray}$ eine bijektive Zuordnung zwischen $\begin{eqnarray} A^k \end{eqnarray}$ und $\begin{eqnarray} C\subseteq A^n \end{eqnarray}$ ist und daher $\begin{eqnarray} k = n - grad g(x) \end{eqnarray}$ folgt. Ich kann diese Begründung aber nicht nachvollziehen. Könnte mir jemand erklären, wie man die letzte Folgerung begründet? Danke im Voraus!
03.12.2021, 20:30	Studentu	Auf diesen Beitrag antworten »
Ein Beweis für die von mir gesuchte Aussage ist z.B. auch hier https://www.uni-ulm.de/fileadmin/website...heorie/CT14.pdf auf S.40-41 ausgeführt. Ich verstehe in diesem nicht, wieso aus $\begin{eqnarray} grad f(x) \leq k-1 \end{eqnarray}$ folgt, dass $\begin{eqnarray} dim_{F_q} C \leq k \end{eqnarray}$ sein muss.
03.12.2021, 20:44	IfindU	Auf diesen Beitrag antworten »
Der Raum der Polynome $\begin{eqnarray} f \end{eqnarray}$ mit $\begin{eqnarray} \mathrm{deg}(f) \leq k-1 \end{eqnarray}$ bildet einen $\begin{eqnarray} k \end{eqnarray}$ -dimensionalen Unterraum. Nach Definition erzeugt $\begin{eqnarray} g \end{eqnarray}$ den Unterraum $\begin{eqnarray} C \end{eqnarray}$ und damit haben alle Elemente in $\begin{eqnarray} C \end{eqnarray}$ die Form $\begin{eqnarray} fg \end{eqnarray}$ für ein $\begin{eqnarray} f \end{eqnarray}$ mit $\begin{eqnarray} \mathrm{deg}(f) \leq k-1 \end{eqnarray}$ Damit kann $\begin{eqnarray} C \end{eqnarray}$ höchstens $\begin{eqnarray} k \end{eqnarray}$ -dimensional sein.
05.12.2021, 15:39	Studentu	Auf diesen Beitrag antworten »
Danke für deine Antwort, IfindU! Diese Information bringt mich schon ein kleines Verständnnisstück weiter, zumindest was den Beweis aus meiner zweiten Nachricht betrifft. Aber zum ersten Beweis: Wenn $\begin{eqnarray} g \end{eqnarray}$ den Raum erzeugt, wieso begründen wir dann mit der Dimesnion von $\begin{eqnarray} f \end{eqnarray}$ ? Wieso wird die Dimension als $\begin{eqnarray} k=n-grad(g(x)) \end{eqnarray}$ berechnet und nicht als $\begin{eqnarray} k=grad(g(x))+1 \end{eqnarray}$ ? Und eine allgemeine Verständnisfrage: wenn ein Raum aus Polynomen, die sich als Produkte $\begin{eqnarray} m(x)n(x) \end{eqnarray}$ ergeben, besteht, ist die Dimension des Raumes dann das Maximum der Grade von m und n plus 1?
05.12.2021, 16:01	IfindU	Auf diesen Beitrag antworten »
Du betrachtest Polynome mit Grad kleiner/gleich $\begin{eqnarray} n-1 \end{eqnarray}$ , das sind Polynome der Form $\begin{eqnarray} P(X) = \sum_{k=0}^{n-1} a_k X^K \end{eqnarray}$ . D.h. du hast $\begin{eqnarray} a_0, a_1, \ldots, a_{n-1} \in \mathbb R \end{eqnarray}$ als Freiheitsgrade. Und das sind $\begin{eqnarray} n \end{eqnarray}$ Stück und damit der Raum $\begin{eqnarray} n \end{eqnarray}$ -dimensional. Extrembeispiel: Der Raum der konstanten Polynome (Grad 0) ist eindimensional. Nun setzen wir fest: Wir betrachten nur noch Polynome, welche a) Grad kleiner/gleich $\begin{eqnarray} n-1 \end{eqnarray}$ haben, b) von der Form $\begin{eqnarray} fg \end{eqnarray}$ sind. Hier ist $\begin{eqnarray} g \end{eqnarray}$ eine feste Funktion, damit wollen wir wissen "wie viele" $\begin{eqnarray} f \end{eqnarray}$ denn in Frage kommen. Wichtig ist, dass $\begin{eqnarray} fg \end{eqnarray}$ als Produkt weiterhin Grad kleiner/gleich $\begin{eqnarray} n-1 \end{eqnarray}$ haben. Wenn $\begin{eqnarray} g \end{eqnarray}$ bereits Grad $\begin{eqnarray} n-1 \end{eqnarray}$ hat, darf $\begin{eqnarray} f \end{eqnarray}$ nur eine Konstante sein. Sobald $\begin{eqnarray} f(X)= X \end{eqnarray}$ wäre, so wäre $\begin{eqnarray} fg \end{eqnarray}$ von Grad $\begin{eqnarray} n \end{eqnarray}$ und damit unzulässig. D.h. je höher der Grad von $\begin{eqnarray} g \end{eqnarray}$ ist, desto niedriger muss der Grad von $\begin{eqnarray} f \end{eqnarray}$ sein, damit das Produkt den Grad $\begin{eqnarray} n-1 \end{eqnarray}$ nicht überschreitet. Da $\begin{eqnarray} \mathrm{deg}(fg) = \mathrm{deg}(f) + \mathrm{deg}(g) \end{eqnarray}$ gilt (mit der Konvention $\begin{eqnarray} \mathrm{deg}(0) = -\infty \end{eqnarray}$ , ergibt sich also $\begin{eqnarray} n-1\geq \mathrm{deg}(fg) = \mathrm{deg}(f) + \mathrm{deg}(g) \end{eqnarray}$ bzw. umgestellt $\begin{eqnarray} n-1 - \mathrm{deg}(g)\geq \mathrm{deg}(f) \end{eqnarray}$
08.12.2021, 23:16	Studentu	Auf diesen Beitrag antworten »
Danke für deine ausführliche Antwort, IfindU! Warum wir für f nur Polynome vom Grad kleiner-gleich n -1 - grad g(x) betrachten dürfen, hatte ich schon verstanden. Und wenn ich dich richtig verstanden habe, ist dann der von diesen als f infrage kommenden Polynomen ein n - 1 - grad g(x) + 1 = n - grad g(x) - dimensionaler Unterraum. Und die Feststellung, dass die Dimension des Unterraumes, der von Polynomen vom Grad höchstens k aufgespannt wird, gleich k+1 ist, folgt daraus, dass wir die Koeffizienten all dieser Polynome als k+1-dimensionale Vektoren auffassen können. Habe ich das richtig verstanden?
Anzeige

09.12.2021, 14:32	IfindU	Auf diesen Beitrag antworten »
Ich würde leicht anders argumentieren: Die Polynome mit höchstens Grad $\begin{eqnarray} n \end{eqnarray}$ bilden einen Vektorraum. Eine mögliche Basis ist $\begin{eqnarray} \{ x^0, x^1, x^2, \ldots, x^n\} \end{eqnarray}$ . Und das sind $\begin{eqnarray} n+1 \end{eqnarray}$ Stück, d.h. der Raum ist $\begin{eqnarray} n+1 \end{eqnarray}$ -dimensional.
13.12.2021, 12:23	Studentu	Auf diesen Beitrag antworten »
Okay, alles klar. Danke für deine Hilfe, IfindU! Meine Frage ist somit geklärt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »