Wie in der [[Aufgaben:2.2_Eigenschaften_von_Galoisfeldern|Aufgabe 2.2]] betrachten wir einen endlichen Körper der Ordnung $q = 5$ und damit das Galoisfeld
Wie in der [[Aufgaben:2.2_Eigenschaften_von_Galoisfeldern|"Aufgabe 2.2"]] betrachten wir einen endlichen Körper der Ordnung $q = 5$ und damit das Galoisfeld
Über die Elemente werden weiter keine Aussagen getroffen. Es können sowohl ganze Zahlen sein oder irgendwelche mathematische Ausdrücke.
Über die Elemente werden weiter keine Aussagen getroffen. Es können sowohl ganze Zahlen sein oder irgendwelche mathematischen Ausdrücke.
Das Galoisfeld wird ausschließlich bestimmt durch
Das Galoisfeld wird ausschließlich bestimmt durch
* eine Additionstabelle modulo 5,
* eine Additionstabelle modulo 5,
* eine Multiplikationstabelle modulo 5,
* eine Multiplikationstabelle modulo 5.
Die wichtigsten Eigenschaften eines Galoisfeldes sind auf der [[Kanalcodierung/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes|ersten Theorieseite]] zusammengestellt. In dieser Aufgabe wird Bezug genommen auf
Die wichtigsten Eigenschaften eines Galoisfeldes sind auf der [[Kanalcodierung/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes|ersten Theorieseite]] zusammengestellt. Hier wird Bezug genommen auf
* das Kommutativ– und das Distributivgesetz,
* das Kommutativ– und das Distributivgesetz,
* die neutralen Elemente von Addition und Multiplikation,
* die neutralen Elemente von Addition und Multiplikation,
* die inversen Elemente von Addition und Multiplikation, sowie
* die inversen Elemente von Addition und Multiplikation, sowie
* die Bestimmung primitiver Elemente.
* die Bestimmung primitiver Elemente.
Im vorliegenden Beispiel wäre $\beta$ ein primitives Element, wenn $\beta^2, \ \beta^3$ und $\beta^4$ (allgemein: $\beta^{q-1})$ die übrigen Elemente des Galoisfeldes $\rm GF(5)$ mit Ausnahme des Nullelementes ergeben.
Im vorliegenden Beispiel wäre $\beta$ ein primitives Element, wenn $\beta^2, \ \beta^3$ und $\beta^4$ $($allgemein: $\beta^{q-1})$ die übrigen Elemente des Galoisfeldes $\rm GF(5)$ mit Ausnahme des Nullelementes ergeben.
Hinweis: Die Aufgabe bezieht ich auf das Kapitel [[Kanalcodierung/Einige_Grundlagen_der_Algebra| "Einige Grundlagen der Algebra"]].
''Hinweise:''
* Die Aufgabe bezieht ich auf das Themengebiet des Kapitels [[Kanalcodierung/Einige_Grundlagen_der_Algebra| Einige Grundlagen der Algebra]].
* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Zeile 33:
Zeile 35:
<quiz display=simple>
<quiz display=simple>
{Bestimmen Sie das neutrale Element der Addition.
{Bestimmen Sie das neutrale Element der Addition.
|type="[]"}
|type="()"}
- $N_{\rm A} = a$,
- $N_{\rm A} = \rm a$,
- $N_{\rm A} = b$,
- $N_{\rm A} = \rm b$,
- $N_{\rm A} = c$,
- $N_{\rm A} = \rm c$,
+ $N_{\rm A} = d$,
+ $N_{\rm A} = \rm d$,
- $N_{\rm A} = e$.
- $N_{\rm A} = \rm e$.
{Bestimmen Sie das neutrale Element der Multiplikations
{Bestimmen Sie das neutrale Element der Multiplikation.
|type="[]"}
|type="()"}
- $N_{\rm M} = a$,
- $N_{\rm M} = \rm a$,
- $N_{\rm M} = b$,
- $N_{\rm M} = \rm b$,
+ $N_{\rm M} = c$,
+ $N_{\rm M} = \rm c$,
- $N_{\rm M} = d$,
- $N_{\rm M} = \rm d$,
- $N_{\rm M} = e$.
- $N_{\rm M} = \rm e$.
{Ist das Kommutativgesetz erfüllt,
{Ist das Kommutativgesetz erfüllt,
|type="[]"}
|type="[]"}
+ hinsichtlich Addition, zum Beispiel $a + b = b + a, \hspace{0.05cm}\text{ ...} \hspace{0.1cm}, \ d + e = e + d$,
+ hinsichtlich Addition, zum Beispiel $\rm a + b = b + a, \hspace{0.05cm}\text{ ...} \hspace{0.1cm}, \ d + e = e + d$,
+ hinstichtlich Multiplikation, zum Beispiel $a \cdot b = b \cdot a, \hspace{0.05cm}\text{ ...} \hspace{0.1cm}, \ d \cdot e = e \cdot d$.
+ hinsichtlich Multiplikation, zum Beispiel $\rm a \cdot b = b \cdot a, \hspace{0.05cm}\text{ ...} \hspace{0.1cm}, \ d \cdot e = e \cdot d$.
{Für welche Ausdrücke ist das Distributivgesetz erfüllt?
{Für welche Ausdrücke ist das Distributivgesetz erfüllt?
|type="[]"}
|type="[]"}
+ $a \cdot (b + c) = a \cdot b + a \cdot c$,
+ $\rm a \cdot (b + c) = a \cdot b + a \cdot c$,
+ $d \cdot (b + c) = d \cdot b + d \cdot c$,
+ $\rm d \cdot (b + c) = d \cdot b + d \cdot c$,
+ $e \cdot (a + b) = e \cdot a + e \cdot b$.
+ $\rm e \cdot (a + b) = e \cdot a + e \cdot b$.
{Ersetzen Sie $a, \ b, \ c, \ d, \ e$ durch Elemente der Zahlenmenge $\{0, \, 1, \, 2, \, 3, \, 4\}$, so dass sich gleiche Operationstabellen ergeben.
{Ersetzen Sie $\rm a, \ b, \ c, \ d, \ e$ durch Elemente der Zahlenmenge $\{0, \, 1, \, 2, \, 3, \, 4\}$, so dass sich gleiche Operationstabellen ergeben.
|type="{}"}
|type="{}"}
$a \hspace{0.2cm} = \ ${ 3 }
$\rm a \hspace{0.15cm} = \ ${ 3 }
$b \hspace{0.25cm} = \ ${ 2 }
$\rm b \hspace{0.15cm} = \ ${ 2 }
$c \hspace{0.25cm} = \ ${ 1 }
$\rm c \hspace{0.15cm} = \ ${ 1 }
$d \hspace{0.2cm} = \ ${ 0. }
$d \hspace{0.15cm} = \ ${ 0. }
$e \hspace{0.2cm} = \ ${ 4 }
$e \hspace{0.15cm} = \ ${ 4 }
{Welche Aussagen gelten hinsichtlich der inversen Elemente?
{Welche Aussagen gelten hinsichtlich der inversen Elemente?
|type="[]"}
|type="[]"}
+ Für alle $z_i ∈ \{0, \, 1, \, 2, \, 3, \, 4\}$ gibt es eine additive Inverse.
+ Für alle $z_i ∈ \{0, \, 1, \, 2, \, 3, \, 4\}$ gibt es eine additive Inverse.
- Nur für $z_i ∈ \{1, \, 2, \, 3, \, 4\}$ gibt es eine additive Inverse.
- Nur für $z_i ∈ \{1, \, 2, \, 3, \, 4\}$ gibt es eine additive Inverse.
- Für alle $z_i ∈ \{0, \, 1, \, 2, \, 3, \, 4\}$ gibt es eine multiplikative Inverse.
- Für alle $z_i ∈ \{0, \, 1, \, 2, \, 3, \, 4\}$ gibt es eine multiplikative Inverse.
+ Nur für $z_i ∈ \{1, \, 2, \, 3, \, 4\}$ gibt es eine multiplikative Inverse.
+ Nur für $z_i ∈ \{1, \, 2, \, 3, \, 4\}$ gibt es eine multiplikative Inverse.
{Welche der Elemente sind primitiv?
{Welche der Elemente sind primitiv?
|type="[]"}
|type="[]"}
+ $a = 3$.
+ $\rm a = 3$.
+ $b = 2$,
+ $\rm b = 2$,
- $e = 4$.
- $\rm e = 4$.
</quiz>
</quiz>
===Musterlösung===
===Musterlösung===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)''' Das neutrale Element hinsichtlich Addition (genannt $N_{\rm A}$) muss für alle Elemente $z_i (i = 0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q-1)$ die folgende Gleichung erfüllen:
'''(1)''' Das neutrale Element hinsichtlich Addition $($genannt $N_{\rm A})$ muss für alle Elemente $z_i (i = 0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q-1)$ die folgende Gleichung erfüllen:
Aus der Additionstabelle folgt $N_{\rm A} \ \underline{= d}$.
*Aus der Additionstabelle folgt $N_{\rm A} \ \underline{= \rm d}$.
'''(2)''' Dagegen erfüllt das neutrale Element der Multiplikation $(N_{\rm M})$ für alle Elemente $z_i (i = 1,\hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q-1)$ die folgende Bedingung:
'''(2)''' Dagegen erfüllt das neutrale Element der Multiplikation $(N_{\rm M})$ für alle Elemente $z_i (i = 1,\hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q-1)$ die folgende Bedingung:
'''(3)''' Das Kommutativgesetz ist bei diesem Galoisfeld in <u>beiden Fällen</u> (Addition und Multiplikation) erfüllt, <br> da Additionstabelle und Multiplikationstabelle jeweils symmetrisch zur Tabellendiagonalen sind.
'''(4)''' Betrachten wir zunächst den ersten Ausdruck.
*Bei Gültigkeit des Distributivgesetzes muss gelten:
:$$\rm a \cdot (b+c) = a \cdot b+ a \cdot c \hspace{0.05cm}.$$
*Für die linke Seite erhält man:
:$$\rm a \cdot (b+c) = a \cdot a =e \hspace{0.05cm},$$
:und für die rechte Seite:
:$$\rm a \cdot b+ a \cdot c = c + a = e\hspace{0.05cm}.$$
*Das Distributivgesetz ist hier ebenso erfüllt wie auch bei den beiden anderen vorgegebenen Ausdrücken:
:$$\rm d \cdot (b+c) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} d \cdot a =d \hspace{0.05cm}, \hspace{0.5cm}d \cdot b+ d \cdot c = d + d = d\hspace{0.05cm},$$
:$$\rm e \cdot (a+c) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} e \cdot e =c \hspace{0.05cm}, \hspace{0.5cm}e \cdot a+ e \cdot c = b + e = c\hspace{0.05cm}.$$
'''(3)''' Das Kommutativgesetz ist bei diesem Galoisfeld in <u>beiden Fällen</u> (Addition und Multiplikation) erfüllt, da Additionstabelle und Multiplikationstabelle jeweils symmetrisch zur Tabellendiagonalen sind.
<u>Alle Lösungsvorschläge</u> treffen zu.
'''(4)''' Betrachten wir zunächst den ersten Ausdruck. Bei Gültigkeit des Distributivgesetzes muss gelten:
:$$a \cdot (b+c) = a \cdot b+ a \cdot c \hspace{0.05cm}.$$
:$$a \cdot (b+c) = a \cdot a =e \hspace{0.05cm},$$
'''(5)'''
Das Nullelement $N_{\rm A} = \rm d$ wird zu $N_{\rm A} = 0 \ \Rightarrow \ d = 0$, das Einselelement $N_{\rm M} = c$ zu $N_{\rm M} = 1 \ \Rightarrow \ \rm c = 1$.
*Die weiteren Elemente $\rm a, \ b$ und $\rm e$ können modulo $5$ aus der Additionstabelle oder der Multiplikationstabelle bestimmt werden.
und für die rechte Seite:
*Zum Beispiel folgt aus der ersten Zeile der Additionstabelle
:$$a \cdot b+ a \cdot c = c + a = e\hspace{0.05cm}.$$
:$$\rm (a + b) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = d = 0 \hspace{0.05cm}.$$
Das Distributivgesetz ist hier ebenso erfüllt wie auch bei den beiden anderen vorgegebenen Ausdrücken:
*Da sowohl $\rm a$ als auch $\rm b$ nicht $0$ oder $1$ sein können (da diese bereits für $\rm c$ und $\rm d$ vergeben sind), ergibt sich als Folgerung:
:$$d \cdot (b+c) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} d \cdot a =d \hspace{0.05cm}, \hspace{0.5cm}d \cdot b+ d \cdot c = d + d = d\hspace{0.05cm},$$
:$$\rm a = 2, \hspace{0.3cm} b = 3 \hspace{0.5cm}{\rm oder}\hspace{0.5cm} a = 3, \hspace{0.3cm} b = 2\hspace{0.05cm}.$$
:$$e \cdot (a+c) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} e \cdot e =c \hspace{0.05cm}, \hspace{0.5cm}e \cdot a+ e \cdot c = b + e = c\hspace{0.05cm}.$$
<u>Alle Lösungsvorschläge</u> treffen zu.
*Aus der zweiten Zeile der Additionstabelle folgt beispielsweise:
:$$\rm (b + b) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = e \hspace{0.05cm}.$$
*Aus $\rm b = 3$ ergäbe sich $\rm e = 1$. Dies ist aber wiederum nicht möglich, da bereits $\rm c = 1$ festgelegt wurde.
'''(5)''' [[Datei:P_ID2495__KC_Z_2_2e.png|right|frame|Umgewandelte Additions– und Multiplikationstabellen]] Das Nullelement $N_{\rm A} = d$ wird zu $N_{\rm A} = 0 \Rightarrow d = 0$, das Einselelement $N_{\rm M} = c$ zu $N_{\rm M} = 1 \Rightarrow c = 1$. Die weiteren Elemente $a, \ b$ und $e$ können modulo $5$ aus der Additionstabelle oder der Multiplikationstabelle bestimmt werden. Zum Beispiel folgt aus der ersten Zeile der Additionstabelle
*Also erhält man als Endergebnis:
:$$(a + b) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = d = 0 \hspace{0.05cm}.$$
'''(6)''' Zutreffend sind die <u>Aussagen 1 und 4</u>:
*Die multiplikative Inverse erkennt man in der Multiplikationstabelle durch den Eintrag $\rm c = 1$. Die multiplikativen Inversen lauten wie folgt:
*Man erkennt in der Additionstabelle in jeder Zeile und Spalte genau ein $d = 0$. Das heißt: Für alle $z_i ∈ \{0, \, 1, \, 2, \, 3, \, 4\}$ existiert eine eindeutige additive Inverse.
Von der Menge $Z_5 = \{0, \, 1, \, 2, \, 3, \, 4\}$ sind „$2$” und „$3$” primitive Elemente ⇒ <u>Lösungsvorschläge 1 und 2</u>.
*Von der Menge $Z_5 = \{0, \, 1, \, 2, \, 3, \, 4\}$ sind „$2$” und „$3$” primitive Elemente ⇒ <u>Lösungsvorschläge 1 und 2</u>.
{{ML-Fuß}}
{{ML-Fuß}}
Zeile 157:
Zeile 171:
[[Category:Aufgaben zu Kanalcodierung|^2.1 Einige Grundlagen der Algebra^]]
[[Category:Aufgaben zu Kanalcodierung|^2.1 Einige Grundlagen der Algebra^]]
Über die Elemente werden weiter keine Aussagen getroffen. Es können sowohl ganze Zahlen sein oder irgendwelche mathematischen Ausdrücke.
Das Galoisfeld wird ausschließlich bestimmt durch
eine Additionstabelle modulo 5,
eine Multiplikationstabelle modulo 5.
Die wichtigsten Eigenschaften eines Galoisfeldes sind auf der ersten Theorieseite zusammengestellt. Hier wird Bezug genommen auf
das Kommutativ– und das Distributivgesetz,
die neutralen Elemente von Addition und Multiplikation,
die inversen Elemente von Addition und Multiplikation, sowie
die Bestimmung primitiver Elemente.
Im vorliegenden Beispiel wäre $\beta$ ein primitives Element, wenn $\beta^2, \ \beta^3$ und $\beta^4$ $($allgemein: $\beta^{q-1})$ die übrigen Elemente des Galoisfeldes $\rm GF(5)$ mit Ausnahme des Nullelementes ergeben.
(1) Das neutrale Element hinsichtlich Addition $($genannt $N_{\rm A})$ muss für alle Elemente $z_i (i = 0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q-1)$ die folgende Gleichung erfüllen:
Aus der Additionstabelle folgt $N_{\rm A} \ \underline{= \rm d}$.
(2) Dagegen erfüllt das neutrale Element der Multiplikation $(N_{\rm M})$ für alle Elemente $z_i (i = 1,\hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q-1)$ die folgende Bedingung:
Aus der Multiplikationstabelle erkennt man $N_{\rm M} \ \underline{= \rm c}$.
(3) Das Kommutativgesetz ist bei diesem Galoisfeld in beiden Fällen (Addition und Multiplikation) erfüllt, da Additionstabelle und Multiplikationstabelle jeweils symmetrisch zur Tabellendiagonalen sind.
(4) Betrachten wir zunächst den ersten Ausdruck.
Bei Gültigkeit des Distributivgesetzes muss gelten:
$$\rm a \cdot (b+c) = a \cdot b+ a \cdot c \hspace{0.05cm}.$$
Für die linke Seite erhält man:
$$\rm a \cdot (b+c) = a \cdot a =e \hspace{0.05cm},$$
und für die rechte Seite:
$$\rm a \cdot b+ a \cdot c = c + a = e\hspace{0.05cm}.$$
Das Distributivgesetz ist hier ebenso erfüllt wie auch bei den beiden anderen vorgegebenen Ausdrücken:
$$\rm d \cdot (b+c) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} d \cdot a =d \hspace{0.05cm}, \hspace{0.5cm}d \cdot b+ d \cdot c = d + d = d\hspace{0.05cm},$$
$$\rm e \cdot (a+c) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} e \cdot e =c \hspace{0.05cm}, \hspace{0.5cm}e \cdot a+ e \cdot c = b + e = c\hspace{0.05cm}.$$
Alle Lösungsvorschläge treffen zu.
Umgewandelte Operationstabellen
(5)
Das Nullelement $N_{\rm A} = \rm d$ wird zu $N_{\rm A} = 0 \ \Rightarrow \ d = 0$, das Einselelement $N_{\rm M} = c$ zu $N_{\rm M} = 1 \ \Rightarrow \ \rm c = 1$.
Die weiteren Elemente $\rm a, \ b$ und $\rm e$ können modulo $5$ aus der Additionstabelle oder der Multiplikationstabelle bestimmt werden.
Zum Beispiel folgt aus der ersten Zeile der Additionstabelle
$$\rm (a + b) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = d = 0 \hspace{0.05cm}.$$
Da sowohl $\rm a$ als auch $\rm b$ nicht $0$ oder $1$ sein können (da diese bereits für $\rm c$ und $\rm d$ vergeben sind), ergibt sich als Folgerung:
$$\rm a = 2, \hspace{0.3cm} b = 3 \hspace{0.5cm}{\rm oder}\hspace{0.5cm} a = 3, \hspace{0.3cm} b = 2\hspace{0.05cm}.$$
Aus der zweiten Zeile der Additionstabelle folgt beispielsweise:
$$\rm (b + b) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = e \hspace{0.05cm}.$$
Aus $\rm b = 3$ ergäbe sich $\rm e = 1$. Dies ist aber wiederum nicht möglich, da bereits $\rm c = 1$ festgelegt wurde.
