Quelltext der Seite Aufgaben:Aufgabe 2.6: GF(P hoch m). Welches P, welches m?

{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}}

[[Datei:P_ID2510__KC_A_2_6_neu.png|right|frame|Zugrunde liegende Tabellen für Addition und Multiplikation]]
Es soll ein Galoisfeld&nbsp; ${\rm GF}(q)$&nbsp; mit&nbsp; $q = P^m$&nbsp; Elementen analysiert werden,&nbsp; das durch die nebenstehenden Tabellen definiert ist 
*für Addition&nbsp; (gekennzeichnet mit &bdquo;$+$&rdquo;),&nbsp; und 

*für Multiplikation&nbsp; (gekennzeichnet mit &bdquo;$\hspace{0.05cm}\cdot\hspace{0.05cm}$&rdquo;). 


Dieses Galoisfeld&nbsp; ${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.05cm}  \text{...} , \hspace{0.1cm}z_{q-1}\}$&nbsp; erfüllt alle Anforderungen an einen endlichen Körper,&nbsp; die im Kapitel&nbsp; [[Kanalcodierung/Einige_Grundlagen_der_Algebra|"Einige Grundlagen der Algebra"]]&nbsp; aufgeführt sind.&nbsp; So werden auch Kommutativ&ndash;, Assoziativ&ndash; und Distributivgesetz erfüllt. 

Weiterhin gibt es
* ein neutrales Element hinsichtlich Addition &nbsp; &#8658; &nbsp; $N_{\rm A}$:
:$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:}
\hspace{0.25cm}z_i + z_j = z_i \hspace{0.3cm} \Rightarrow \hspace{0.3cm} z_j = N_{\rm A}   \hspace{0.25cm}{\rm (Nullelement)}
\hspace{0.05cm},$$
* ein neutrales Element hinsichtlich Multiplikation &nbsp; &#8658; &nbsp; $N_{\rm M}$:
:$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:}
\hspace{0.25cm}z_i \cdot z_j  = z_i \hspace{0.3cm} \Rightarrow \hspace{0.3cm}  z_j = N_{\rm M}  \hspace{0.25cm}{\rm (Einselement)}
\hspace{0.05cm},$$
* für alle Elemente&nbsp; $z_i$&nbsp; eine additive Inverse &nbsp; &#8658; &nbsp; ${\rm Inv_A}(z_i)$:
:$$\forall \hspace{0.15cm}  z_i \in {\rm GF}(q)\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q)\text{:}$$
::$$z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {\rm "0"}\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz}\text{:}\hspace{0.15cm}
{\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}, $$
* für alle Elemente&nbsp; $z_i$&nbsp; mit Ausnahme des Nullelements eine multiplikative Inverse &nbsp;&#8658;&nbsp; ${\rm Inv_M}(z_i)$:
:$$\forall \hspace{0.15cm}  z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A} \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:}$$
::$$z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {\rm "1"}
\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz}\text{:}\hspace{0.15cm}
{\rm Inv_M}(z_i) = z_i^{-1}
\hspace{0.05cm}. $$




Hinweise:
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Erweiterungsk%C3%B6rper| "Erweiterungskörper"]].
 
* In den Tabellen sind die Elemente&nbsp; $z_0, \hspace{0.05cm}  \text{...}  \hspace{0.1cm} , \ z_8$&nbsp; als Koeffizientenvektoren bezeichnet. Zum Beispiel steht &bdquo;$2\hspace{0.03cm}1$&rdquo; für &bdquo;$2 \cdot \alpha + 1$&rdquo;.
 




===Fragebogen===
<quiz display=simple>
{Geben Sie die Parameter des hier betrachteten Galoisfeldes an.
|type="{}"}
$P \ = \ ${ 3 }
$m \ = \ ${ 2 }
$q \ = \ ${ 9 }

{Wie lautet das neutrale Element für die Addition?
|type="()"}
+ Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ &bdquo;$0\hspace{0.03cm}0$&rdquo;,
- Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ &bdquo;$0\hspace{0.03cm}1$&rdquo;.

{Wie lautet das neutrale Element für die Multiplikation?
|type="()"}
- Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ &bdquo;$0\hspace{0.03cm}0$&rdquo;,
+ Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ &bdquo;$0\hspace{0.03cm}1$&rdquo;.

{Welche Aussagen gelten hinsichtlich der additiven Inversen?
|type="[]"}
+ Es gilt&nbsp; ${\rm Inv_A}  ($&bdquo;$0\hspace{0.03cm}2$&rdquo;)  $\, = \, $ &bdquo;$0\hspace{0.03cm}1$&rdquo;,
+ Es gilt&nbsp; ${\rm Inv_A} ($&bdquo;$1\hspace{0.03cm}1$&rdquo;) $\, = \, $ &bdquo;$2\hspace{0.03cm}2$&rdquo;,
- Es gilt&nbsp; ${\rm Inv_A} ($&bdquo;$2\hspace{0.03cm}2$&rdquo;) $\, = \, $ &bdquo;$0\hspace{0.03cm}0$&rdquo;.

{Welche der folgenden Aussagen treffen für die Multiplikation zu?
|type="()"}
- Die Multiplikation erfolgt modulo&nbsp; $p(\alpha) = \alpha^2 + 2$.
+ Die Multiplikation erfolgt modulo&nbsp; $p(\alpha) = \alpha^2 + 2\alpha + 2$.

{Welche Aussagen gelten hinsichtlich der multiplikativen Inversen?
|type="[]"}
- Es gibt für alle Elemente&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; eine multiplikative Inverse.
+ Es gilt&nbsp; ${\rm Inv_M}  ($&bdquo;$1\hspace{0.03cm}2$&rdquo;) $\, = \, $ &bdquo;$1\hspace{0.03cm}0$&rdquo;.
- Es gilt&nbsp; ${\rm Inv_A}  ($&bdquo;$2\hspace{0.03cm}1$&rdquo;) $\, = \, $ &bdquo;$1\hspace{0.03cm}2$&rdquo;.

{Gilt (&bdquo;$2\hspace{0.03cm}0$&rdquo; $\, + \,$ &bdquo;$1\hspace{0.03cm}2$&rdquo;) $\, \cdot\, $ &bdquo;$1\hspace{0.03cm}2$&rdquo; $\, = \, $&bdquo;$2\hspace{0.03cm}0$&rdquo; $\, \cdot\, $ &bdquo;$1\hspace{0.03cm}2$&rdquo; $\, + \, $&bdquo;$1\hspace{0.03cm}2$&rdquo;  $\, \cdot\, $ &bdquo;$1\hspace{0.03cm}2$&rdquo;?
|type="()"}
+ Ja.
- Nein.
</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''&nbsp; Jedes Element besteht aus zwei Ternärzahlen &nbsp; &#8658; &nbsp; $\underline{P = 3}, \ \underline{m = 2}$.&nbsp; Es gibt $q = P^m = 3^8 = \underline{9 \ \rm Elemente}$.


'''(2)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 1</u>:
*Das neutrale Element der Addition&nbsp; $(N_{\rm A})$&nbsp; erfüllt für alle&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; die Bedingung&nbsp; $z_i + N_{\rm A} = z_i$.
 
*Aus der Additionstabelle kann abgelesen werden,&nbsp; dass&nbsp; &bdquo;$0\hspace{0.03cm}0$&rdquo;&nbsp; diese Bedingung erfült.


'''(3)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 2</u>:
*Das neutrale Element der Multiplikation&nbsp; $(N_{\rm M})$&nbsp; muss stets die Bedingung&nbsp; $z_i \cdot N_{\rm M} = z_i$&nbsp; erfüllen.
 
*Aus der Multiplikationstabelle ergibt sich&nbsp; $N_{\rm M} = \, &bdquo;0\hspace{0.03cm}1&rdquo;$.

* In der Polynomschreibweise entspricht dies mit&nbsp; $k_1 = 0$&nbsp; und&nbsp; $k_0 = 1$:
:$$k_1 \cdot \alpha + k_0 = 1 \hspace{0.05cm}.$$


'''(4)'''&nbsp; Mit der Polynomdarstellung ergeben sich folgende Berechnungen:
:$${\rm Inv_A}(&bdquo;\hspace{-0.05cm}0\hspace{0.03cm}2&rdquo;) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(2) = (-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 = 1 \hspace{0.25cm}\Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}&bdquo;\hspace{-0.05cm}0\hspace{0.03cm}1&rdquo;\hspace{0.05cm},$$
:$${\rm Inv_A}(&bdquo;\hspace{-0.05cm}1\hspace{0.03cm}1&rdquo;)\hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(\alpha + 1) = \big[(-\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] + 
\big[(-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] =2\alpha + 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}&bdquo;\hspace{-0.05cm}2\hspace{0.03cm}2&rdquo;\hspace{0.05cm},$$
:$${\rm Inv_A}(&bdquo;\hspace{-0.05cm}2\hspace{0.03cm}2&rdquo;)\hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(2\alpha + 2) = \big[(-2\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] + 
\big[(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] =\alpha + 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}&bdquo;\hspace{-0.05cm}1\hspace{0.03cm}1&rdquo;\hspace{0.05cm}.$$

Demzufolge sind nur die <u>beiden ersten Lösungsvorschläge</u> richtig. 

Die Aufgabe kann aber auch ohne Rechnung allein anhand der Additionstabelle gelöst werden. 
*Beispielsweise findet man die Inverse zu &bdquo;$2\hspace{0.03cm}2$&rdquo;,&nbsp; indem man in der letzten Zeile die Spalte mit dem Eintrag&nbsp; &bdquo;$0\hspace{0.03cm}0$&rdquo;&nbsp; sucht.
 
*Man findet die mit&nbsp; &bdquo;$1\hspace{0.03cm}1$&rdquo;&nbsp; bezeichnete Spalte und damit&nbsp; ${\rm Inv_A}(&bdquo;2\hspace{0.03cm}2&rdquo;) = \, &bdquo;1\hspace{0.03cm}1&rdquo;$.


'''(5)'''&nbsp; Die Multiplikation von&nbsp; $\alpha$&nbsp; $($Vektor &bdquo;$1\hspace{0.03cm}0$&rdquo;$)$&nbsp; mit sich selbst ergibt&nbsp; $\alpha^2$.
* Würde der erste Lösungsvorschlag gültig sein,&nbsp; so müsste sich aus der Bedingung&nbsp; $\alpha^2 + 2 = 0$&nbsp; und damit&nbsp; $\alpha^2 = (-2) \, {\rm mod} \, 3 = 1$&nbsp; ergeben,&nbsp; also der Vektor &bdquo;$0\hspace{0.03cm}1$&rdquo;.

* Geht man vom zweiten Lösungsvorschlag aus,&nbsp; so folgt aus der Bedingung&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; in der Polynomschreibweise
:$$\alpha^2 = [(-2\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] + [(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] = \alpha + 1 $$
:und damit der Koeffizientenvektor&nbsp; &bdquo;$1\hspace{0.03cm}1$&rdquo;.

In der Multiplikationstabelle findet man in Zeile 4, Spalte 4 genau den Eintrag &bdquo;$1\hspace{0.03cm}1$&rdquo; &nbsp; &rArr; &nbsp; Richtig ist also der&nbsp; <u>Lösungsvorschlag 2</u>.


'''(6)'''&nbsp; Die multiplikative Inverse zu&nbsp; &bdquo;$1\hspace{0.03cm}2$&rdquo;&nbsp; findet man in der Zeile 6 der Multiplikationstabelle als diejenige Spalte mit dem Eintrag &bdquo;$0\hspace{0.03cm}1$&rdquo; &nbsp;<br>&#8658;&nbsp; Der&nbsp; <u>Lösungsvorschlag 2</u>&nbsp; ist also richtig im Gegensatz zu Vorschlag 3.&nbsp; Es gilt nämlich ${\rm Inv_M}(&bdquo;21&rdquo;) = \, &bdquo;2\hspace{0.03cm}0&rdquo;$.

Wir überprüfen diese Ergebnisse unter Berücksichtigung von&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; durch Multiplikationen:
:$$&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}2&rdquo; \hspace{0.05cm}\cdot \hspace{0.05cm}&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}0&rdquo; \hspace{0.15cm}  \Rightarrow  \hspace{0.15cm} (\alpha + 2) \cdot \alpha = \alpha^2 + 2\alpha = (-2\alpha-2) + 2\alpha = -2 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 =  1 \hspace{0.15cm} \Rightarrow  \hspace{0.15cm} {\rm Vektor}\hspace{0.15cm}&bdquo;\hspace{-0.1cm}0\hspace{0.03cm}1&rdquo; \hspace{0.15cm} \Rightarrow  \hspace{0.15cm}{\rm multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$
:$$&bdquo;\hspace{-0.1cm}2\hspace{0.03cm}1&rdquo; \hspace{0.05cm}\cdot \hspace{0.05cm}&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}2&rdquo;
 \hspace{0.15cm}  \Rightarrow  \hspace{0.15cm} (2\alpha + 1) \cdot (\alpha + 2) = 2 \alpha^2 + \alpha + 4\alpha  + 2 =  2 \alpha^2 + 5\alpha  + 2 = 2 \cdot (-2\alpha  - 2) + 5\alpha  + 2 = (\alpha  - 2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 =  \alpha  +1 $$
:$$\hspace{2.725cm} \Rightarrow \ {\rm Vektor}\hspace{0.15cm}&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}1&rdquo; \hspace{0.15cm} \Rightarrow  \hspace{0.15cm}{\rm keine \hspace{0.15cm}multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$

Der Lösungsvorschlag 1 ist deshalb nicht richtig, weil es für &bdquo;$00$&rdquo; keine multiplikative Inverse gibt.


'''(7)'''&nbsp; Die beiden Ausdrücke stimmen überein &nbsp; &#8658; &nbsp; <u>JA</u>,&nbsp; wie die folgenden Berechnungen zeigen:
:$$(&bdquo;\hspace{-0.1cm}20&rdquo; + \ &bdquo;\hspace{-0.1cm}12&rdquo;) \ \cdot \ &bdquo;\hspace{-0.1cm}12&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}02&rdquo;\cdot \ &bdquo;\hspace{-0.1cm}12&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}21&rdquo;\hspace{0.05cm},$$
:$$&bdquo;\hspace{-0.1cm}20&rdquo; \cdot  \ &bdquo;\hspace{-0.1cm}12&rdquo; + \ &bdquo;\hspace{-0.1cm}12&rdquo; \cdot \ &bdquo;\hspace{-0.1cm}12&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}02&rdquo; + \ &bdquo;\hspace{-0.1cm}22&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}21&rdquo;\hspace{0.05cm}.$$

Das bedeutet: &nbsp; Das Distributivgesetz wurde zumindest an einem einzigen Beispiel nachgewiesen.
{{ML-Fuß}}



[[Category:Aufgaben zu  Kanalcodierung|^2.2 Erweiterungskörper^]]