Aufgaben:Aufgabe 2.2: Eigenschaften von Galoisfeldern: Unterschied zwischen den Versionen
Aus LNTwww
| (4 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Einige Grundlagen der Algebra}} | {{quiz-Header|Buchseite=Kanalcodierung/Einige Grundlagen der Algebra}} | ||
| − | [[Datei:P_ID2492__KC_A_2_2.png|right|frame| | + | [[Datei:P_ID2492__KC_A_2_2.png|right|frame|Addition / Multiplikation für $q = 5$ und $q = 6$]] |
Wir betrachten hier die Zahlenmengen | Wir betrachten hier die Zahlenmengen | ||
* $Z_5 = \{0, \, 1, \, 2, \, 3, \, 4\} \ \Rightarrow \ q = 5$, | * $Z_5 = \{0, \, 1, \, 2, \, 3, \, 4\} \ \Rightarrow \ q = 5$, | ||
| + | |||
* $Z_6 = \{0, \, 1, \, 2, \, 3, \, 4,\, 5\} \ \Rightarrow \ q = 6$. | * $Z_6 = \{0, \, 1, \, 2, \, 3, \, 4,\, 5\} \ \Rightarrow \ q = 6$. | ||
| − | In nebenstehender Grafik sind die (teilweise unvollständigen) Additions– und Multiplikationstabellen für $q = 5$ und $q = 6$ angegeben, wobei sowohl die Addition („$+$”) als auch die Multiplikation („$\cdot$”) modulo $q$ zu verstehen sind. | + | In nebenstehender Grafik sind die (teilweise unvollständigen) Additions– und Multiplikationstabellen für $q = 5$ und $q = 6$ angegeben, wobei sowohl die Addition („$+$”) als auch die Multiplikation („$\hspace{0.05cm}\cdot\hspace{0.05cm}$”) modulo $q$ zu verstehen sind. |
| − | Zu überprüfen ist, ob die Zahlenmengen $Z_5$ und $Z_6$ alle Bedingungen eines Galoisfeldes $\rm GF(5)$ bzw. $\rm GF(6)$ erfüllen. | + | Zu überprüfen ist, ob die Zahlenmengen $Z_5$ und $Z_6$ alle Bedingungen eines Galoisfeldes $\rm GF(5)$ bzw. $\rm GF(6)$ erfüllen. |
| − | + | Im [[Kanalcodierung/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes|"Theorieteil"]] werden acht Bedingungen genannt, die alle erfüllt sein müssen. Sie sollen nur zwei dieser Bedingungen überprüfen: | |
| − | :$$\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{:} | + | |
| − | + | $\rm(D)$ Für alle Elemente gibt es eine <b>additive Inverse</b> (Inverse for „$+$”): | |
| + | :$$\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{:}\hspace{0.5cm}z_i + {\rm Inv_A}(z_i) = 0 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} | ||
{\rm Inv_A}(z_i) = -z_i \hspace{0.05cm}.$$ | {\rm Inv_A}(z_i) = -z_i \hspace{0.05cm}.$$ | ||
| − | + | $\rm(E)$ Alle Elemente haben eine <b>multiplikative Inverse</b> (Inverse for „$\hspace{0.05cm}\cdot\hspace{0.05cm}$”): | |
| − | :$$\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne 0, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:} | + | :$$\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne 0, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:}\hspace{0.5cm}z_i \cdot {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} |
| − | |||
{\rm Inv_M}(z_i) = z_i^{-1}\hspace{0.05cm}.$$ | {\rm Inv_M}(z_i) = z_i^{-1}\hspace{0.05cm}.$$ | ||
| − | Die weiteren Bedingungen für ein Galoisfeld, nämlich | + | Die weiteren Bedingungen für ein Galoisfeld, nämlich |
* Closure, | * Closure, | ||
* Existenz von Null– und Einselelement, | * Existenz von Null– und Einselelement, | ||
| − | * Gültigkeit von Kommutativ–, Assoziativ– und Distributivgesetz | + | * Gültigkeit von Kommutativ–, Assoziativ– und Distributivgesetz |
| − | |||
| − | |||
| + | werden sowohl von $Z_5$ als auch von $Z_6$ erfüllt. | ||
| − | + | Hinweis: Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Einige_Grundlagen_der_Algebra| "Einige Grundlagen der Algebra"]]. | |
| − | |||
| − | |||
| Zeile 42: | Zeile 40: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Ergänzen Sie die Additionstabelle für $q = 5$. Geben Sie folgende Werte ein: | + | {Ergänzen Sie die Additionstabelle für $q = 5$. Geben Sie folgende Werte ein: |
|type="{}"} | |type="{}"} | ||
$A_{04} \ = \ ${ 4 } | $A_{04} \ = \ ${ 4 } | ||
| Zeile 48: | Zeile 46: | ||
$A_{44} \ = \ ${ 3 } | $A_{44} \ = \ ${ 3 } | ||
| − | {Ergänzen Sie die Multiplikationstabelle für $q = 5$. Geben Sie folgende Werte ein: | + | {Ergänzen Sie die Multiplikationstabelle für $q = 5$. Geben Sie folgende Werte ein: |
|type="{}"} | |type="{}"} | ||
$M_{04} \ = \ ${ 0. } | $M_{04} \ = \ ${ 0. } | ||
| Zeile 54: | Zeile 52: | ||
$M_{44} \ = \ ${ 1. } | $M_{44} \ = \ ${ 1. } | ||
| − | {Erfüllt die Menge $Z_5$ die Bedingungen eines Galoisfeldes? | + | {Erfüllt die Menge $Z_5$ die Bedingungen eines Galoisfeldes? |
|type="[]"} | |type="[]"} | ||
+ Ja. | + Ja. | ||
| − | - Nein, es gibt nicht für alle Elemente $(0, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 4)$ eine additive Inverse. | + | - Nein, es gibt nicht für alle Elemente $(0, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 4)$ eine additive Inverse. |
| − | - Nein, die Elemente $1, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 4$ haben nicht alle eine multiplikative Inverse. | + | - Nein, die Elemente $1, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 4$ haben nicht alle eine multiplikative Inverse. |
| − | {Erfüllt die Menge $Z_6$ die Bedingungen eines Galoisfeldes? | + | {Erfüllt die Menge $Z_6$ die Bedingungen eines Galoisfeldes? |
|type="[]"} | |type="[]"} | ||
- Ja. | - Ja. | ||
| − | - Nein, es gibt nicht für alle Elemente $(0, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 5)$ eine additive Inverse. | + | - Nein, es gibt nicht für alle Elemente $(0, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 5)$ eine additive Inverse. |
| − | + Nein, die Elemente $1, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 5$ haben nicht alle eine multiplikative Inverse. | + | + Nein, die Elemente $1, \hspace{0.05cm}\text{...} \hspace{0.1cm}, 5$ haben nicht alle eine multiplikative Inverse. |
| − | {Die Zahlenmengen $Z_2, \ Z_3, \ Z_5$ und $Z_7$ ergeben ein Galoisfeld, die Mengen $Z_4, \ Z_6, \ Z_8, \ Z_9$ dagegen nicht. Was folgern Sie daraus? | + | {Die Zahlenmengen $Z_2, \ Z_3, \ Z_5$ und $Z_7$ ergeben ein Galoisfeld, die Mengen $Z_4, \ Z_6, \ Z_8, \ Z_9$ dagegen nicht. Was folgern Sie daraus? |
|type="[]"} | |type="[]"} | ||
| − | - $Z_{10} = \{0, \, 1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7, \, 8, \, 9\}$ ist ein Galoisfeld? | + | - $Z_{10} = \{0, \, 1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7, \, 8, \, 9\}$ ist ein Galoisfeld? |
| − | + $Z_{11} = \{0, \, 1, \, 2, \, 3, \, 4, \,5, \, 6, \, 7, \, 8, \, 9, \, 10\}$ ist ein Galoisfeld? | + | + $Z_{11} = \{0, \, 1, \, 2, \, 3, \, 4, \,5, \, 6, \, 7, \, 8, \, 9, \, 10\}$ ist ein Galoisfeld? |
| − | - $Z_{12} = \{0, \, 1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7, \, 8, \, 9, \, 10, \, 11\}$ ist ein Galoisfeld? | + | - $Z_{12} = \{0, \, 1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7, \, 8, \, 9, \, 10, \, 11\}$ ist ein Galoisfeld? |
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Allgemein gilt für $0 ≤ \mu ≤ 4 \text{:} \hspace{0.2cm} A_{\mu 4} = (\mu + 4) \, {\rm mod} \, 5$. Daraus folgt: | + | '''(1)''' Allgemein gilt für $0 ≤ \mu ≤ 4 \text{:} \hspace{0.2cm} A_{\mu 4} = (\mu + 4) \, {\rm mod} \, 5$. Daraus folgt: |
:$$A_{04} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 4}\hspace{0.05cm},\hspace{0.2cm}A_{14}=(1+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}A_{24}=(2+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},$$ | :$$A_{04} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 4}\hspace{0.05cm},\hspace{0.2cm}A_{14}=(1+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}A_{24}=(2+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},$$ | ||
:$$A_{34} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (3+4)\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5= 2\hspace{0.05cm},\hspace{0.2cm}A_{44}=(4+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$ | :$$A_{34} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (3+4)\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5= 2\hspace{0.05cm},\hspace{0.2cm}A_{44}=(4+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$ | ||
| Zeile 85: | Zeile 83: | ||
| − | '''(2)''' Nun gilt $M_{\mu 4} = (\mu \cdot 4) \, {\rm mod} \, 5$ und man erhält: | + | |
| + | '''(2)''' Nun gilt $M_{\mu 4} = (\mu \cdot 4) \, {\rm mod} \, 5$ und man erhält: | ||
:$$M_{04} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}M_{14}=(1\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 4}\hspace{0.05cm},\hspace{0.2cm}M_{24}=(2\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3\hspace{0.05cm},$$ | :$$M_{04} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}M_{14}=(1\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 4}\hspace{0.05cm},\hspace{0.2cm}M_{24}=(2\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3\hspace{0.05cm},$$ | ||
:$$M_{34} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (3\cdot4)\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2\hspace{0.05cm},\hspace{0.2cm}M_{44}=(4\cdot 4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$ | :$$M_{34} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (3\cdot4)\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2\hspace{0.05cm},\hspace{0.2cm}M_{44}=(4\cdot 4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$ | ||
| − | Da die Multiplikation ebenfalls kommutativ ist, stimmt auch in der Multiplikationstabelle die letzte Spalte wieder mit der letzten Zeile überein. | + | Da die Multiplikation ebenfalls kommutativ ist, stimmt auch in der Multiplikationstabelle die letzte Spalte wieder mit der letzten Zeile überein. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | * In der Multiplikationstabelle lassen wir das Nullelement (erste Zeile und erste Spalte) außer Betracht. In allen anderen Zeilen und Spalten der unteren Tabelle gibt es tatsächlich jeweils genau eine Eins. Aus der Bedingung $[z_i \cdot {\rm Inv}_{\rm M}(z_i)] \, {\rm mod} \, 5 = 1$ erhält man: | + | [[Datei:P_ID2493__KC_A_2_2c.png|right|frame|Tabellen für $q = 5$]] |
| + | '''(3)''' Die Grafik zeigt die vollständigen Additions– und Multiplikationstabellen für $q = 5$. Man erkennt: | ||
| + | * In der Additionstabelle gibt es in jeder Zeile (und auch in jeder Spalte) genau eine Null. | ||
| + | |||
| + | *Zu jedem $z_i ∈ Z_5$ gibt es also ein ${\rm Inv}_{\rm A} (z_i)$, das die Bedingung $[z_i + {\rm Inv}_{\rm A}(z_i)] \, {\rm mod} \, 5 = 0$ erfüllt: | ||
| + | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 0\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = 0 \hspace{0.05cm},$$ | ||
| + | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 4 \hspace{0.05cm},$$ | ||
| + | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3 \hspace{0.05cm},$$ | ||
| + | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 3\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-3) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2 \hspace{0.05cm},$$ | ||
| + | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 4\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm}.$$ | ||
| + | |||
| + | * In der Multiplikationstabelle lassen wir das Nullelement (erste Zeile und erste Spalte) außer Betracht. | ||
| + | |||
| + | *In allen anderen Zeilen und Spalten der unteren Tabelle gibt es tatsächlich jeweils genau eine Eins. | ||
| + | |||
| + | *Aus der Bedingung $[z_i \cdot {\rm Inv}_{\rm M}(z_i)] \, {\rm mod} \, 5 = 1$ erhält man: | ||
:$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 1\hspace{0.05cm},$$ | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 1\hspace{0.05cm},$$ | ||
:$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 3 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 6 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm},$$ | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 3 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 6 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm},$$ | ||
| Zeile 107: | Zeile 113: | ||
:$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 4 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 4 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm}.$$ | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 4 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 4 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm}.$$ | ||
| − | Da sowohl die erforderlichen additiven als auch die multiplikativen Inversen existieren beschreibt $Z_5$ ein Galoisfeld $\rm GF(5)$ ⇒ Richtig ist der <u>Lösungsvorschlag 1</u>. | + | *Da sowohl die erforderlichen additiven als auch die multiplikativen Inversen existieren beschreibt $Z_5$ ein Galoisfeld $\rm GF(5)$ ⇒ Richtig ist der <u>Lösungsvorschlag 1</u>. |
| − | |||
| − | Eine multiplikative Inverse ${\rm Inv}_{\rm M}(z_i)$ gibt es dagegen nur für $z_i = 1$ und $z_i = 5$, nämlich | + | '''(4)''' Aus der blauen Additionstabelle auf der Angabenseite erkennt man, dass alle Zahlen $0, \, 1, \, 2, \, 3, \, 4, \, 5$ der Menge $Z_6$ eine additive Inverse besitzen ⇒ in jeder Zeile (und Spalte) gibt es genau eine Null. |
| + | |||
| + | *Eine multiplikative Inverse ${\rm Inv}_{\rm M}(z_i)$ gibt es dagegen nur für $z_i = 1$ und $z_i = 5$, nämlich | ||
:$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 1\hspace{0.05cm},$$ | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 1\hspace{0.05cm},$$ | ||
:$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 5 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 5 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 25 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 6 = 1 \hspace{0.05cm}.$$ | :$$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 5 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 5 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 25 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 6 = 1 \hspace{0.05cm}.$$ | ||
| − | Für $z_i = 2, \ z_i = 3$ und $z_i = 4$ findet man dagegen kein Element $z_j$, so dass $(z_i \cdot z_j) \, {\rm mod} \, 6 = 1$ ergibt. Richtig ist also der <u>Lösungsvorschlag 3</u> ⇒ | + | *Für $z_i = 2, \ z_i = 3$ und $z_i = 4$ findet man dagegen kein Element $z_j$, so dass $(z_i \cdot z_j) \, {\rm mod} \, 6 = 1$ ergibt. |
| + | |||
| + | *Richtig ist also der <u>Lösungsvorschlag 3</u> ⇒ die blauen Tabellen für $q = 6$ ergeben <u>kein</u> Galoisfeld $\rm GF(6)$. | ||
| + | |||
| − | '''(5)''' Richtig ist der <u>Lösungsvorschlag 2</u>: | + | '''(5)''' Richtig ist der <u>Lösungsvorschlag 2</u>: |
| − | *Eine endliche Zahlenmenge $Z_q = \{0, \, 1, \hspace{0.05cm} \text{...} \hspace{0.1cm} , \, q-1\}$ natürlicher Zahlen führt nur dann zu einem „endlichen Zahlenkörper” (dies ist die deutsche Bezeichnung für ein Galoisfeld), wenn $q$ eine Primzahl ist. | + | *Eine endliche Zahlenmenge $Z_q = \{0, \, 1, \hspace{0.05cm} \text{...} \hspace{0.1cm} , \, q-1\}$ natürlicher Zahlen führt nur dann zu einem „endlichen Zahlenkörper” (dies ist die deutsche Bezeichnung für ein Galoisfeld), wenn $q$ eine Primzahl ist. |
| − | *Von den oben genannten Zahlenmengen trifft dies nur | + | |
| + | *Von den oben genannten Zahlenmengen trifft dies nur für $Z_{11}$ zu. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
[[Category:Aufgaben zu Kanalcodierung|^2.1 Einige Grundlagen der Algebra^]] | [[Category:Aufgaben zu Kanalcodierung|^2.1 Einige Grundlagen der Algebra^]] | ||
Aktuelle Version vom 28. August 2022, 14:39 Uhr
Addition / Multiplikation für $q = 5$ und $q = 6$
Wir betrachten hier die Zahlenmengen
- $Z_5 = \{0, \, 1, \, 2, \, 3, \, 4\} \ \Rightarrow \ q = 5$,
- $Z_6 = \{0, \, 1, \, 2, \, 3, \, 4,\, 5\} \ \Rightarrow \ q = 6$.
In nebenstehender Grafik sind die (teilweise unvollständigen) Additions– und Multiplikationstabellen für $q = 5$ und $q = 6$ angegeben, wobei sowohl die Addition („$+$”) als auch die Multiplikation („$\hspace{0.05cm}\cdot\hspace{0.05cm}$”) modulo $q$ zu verstehen sind.
Zu überprüfen ist, ob die Zahlenmengen $Z_5$ und $Z_6$ alle Bedingungen eines Galoisfeldes $\rm GF(5)$ bzw. $\rm GF(6)$ erfüllen.
Im "Theorieteil" werden acht Bedingungen genannt, die alle erfüllt sein müssen. Sie sollen nur zwei dieser Bedingungen überprüfen:
$\rm(D)$ Für alle Elemente gibt es eine additive Inverse (Inverse for „$+$”):
- $$\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{:}\hspace{0.5cm}z_i + {\rm Inv_A}(z_i) = 0 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_A}(z_i) = -z_i \hspace{0.05cm}.$$
$\rm(E)$ Alle Elemente haben eine multiplikative Inverse (Inverse for „$\hspace{0.05cm}\cdot\hspace{0.05cm}$”):
- $$\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne 0, \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q)\text{:}\hspace{0.5cm}z_i \cdot {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = z_i^{-1}\hspace{0.05cm}.$$
Die weiteren Bedingungen für ein Galoisfeld, nämlich
- Closure,
- Existenz von Null– und Einselelement,
- Gültigkeit von Kommutativ–, Assoziativ– und Distributivgesetz
werden sowohl von $Z_5$ als auch von $Z_6$ erfüllt.
Hinweis: Die Aufgabe bezieht sich auf das Kapitel "Einige Grundlagen der Algebra".
Fragebogen
Musterlösung
(1) Allgemein gilt für $0 ≤ \mu ≤ 4 \text{:} \hspace{0.2cm} A_{\mu 4} = (\mu + 4) \, {\rm mod} \, 5$. Daraus folgt:
- $$A_{04} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 4}\hspace{0.05cm},\hspace{0.2cm}A_{14}=(1+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}A_{24}=(2+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1\hspace{0.05cm},$$
- $$A_{34} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (3+4)\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5= 2\hspace{0.05cm},\hspace{0.2cm}A_{44}=(4+4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$
Aufgrund des Kommutativgesetzes der Addition,
- $$z_i + z_j = z_j + z_i \hspace{0.5cm} {\rm f\ddot{u}r \hspace{0.2cm}alle\hspace{0.2cm} } z_i, z_j \in Z_5\hspace{0.05cm},$$
ist natürlich die letzte Spalte der Additionstabelle identisch mit der letzten Zeile der gleichen Tabelle.
(2) Nun gilt $M_{\mu 4} = (\mu \cdot 4) \, {\rm mod} \, 5$ und man erhält:
- $$M_{04} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}M_{14}=(1\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 4}\hspace{0.05cm},\hspace{0.2cm}M_{24}=(2\cdot4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3\hspace{0.05cm},$$
- $$M_{34} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (3\cdot4)\hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2\hspace{0.05cm},\hspace{0.2cm}M_{44}=(4\cdot 4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}.$$
Da die Multiplikation ebenfalls kommutativ ist, stimmt auch in der Multiplikationstabelle die letzte Spalte wieder mit der letzten Zeile überein.
Tabellen für $q = 5$
(3) Die Grafik zeigt die vollständigen Additions– und Multiplikationstabellen für $q = 5$. Man erkennt:
- In der Additionstabelle gibt es in jeder Zeile (und auch in jeder Spalte) genau eine Null.
- Zu jedem $z_i ∈ Z_5$ gibt es also ein ${\rm Inv}_{\rm A} (z_i)$, das die Bedingung $[z_i + {\rm Inv}_{\rm A}(z_i)] \, {\rm mod} \, 5 = 0$ erfüllt:
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 0\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = 0 \hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 4 \hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 3 \hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 3\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-3) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 2 \hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 4\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Inv_A}(z_i) = (-4) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm}.$$
- In der Multiplikationstabelle lassen wir das Nullelement (erste Zeile und erste Spalte) außer Betracht.
- In allen anderen Zeilen und Spalten der unteren Tabelle gibt es tatsächlich jeweils genau eine Eins.
- Aus der Bedingung $[z_i \cdot {\rm Inv}_{\rm M}(z_i)] \, {\rm mod} \, 5 = 1$ erhält man:
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 1\hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 3 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 6 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 3 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 6 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 4 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 4 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 16 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 5 = 1 \hspace{0.05cm}.$$
- Da sowohl die erforderlichen additiven als auch die multiplikativen Inversen existieren beschreibt $Z_5$ ein Galoisfeld $\rm GF(5)$ ⇒ Richtig ist der Lösungsvorschlag 1.
(4) Aus der blauen Additionstabelle auf der Angabenseite erkennt man, dass alle Zahlen $0, \, 1, \, 2, \, 3, \, 4, \, 5$ der Menge $Z_6$ eine additive Inverse besitzen ⇒ in jeder Zeile (und Spalte) gibt es genau eine Null.
- Eine multiplikative Inverse ${\rm Inv}_{\rm M}(z_i)$ gibt es dagegen nur für $z_i = 1$ und $z_i = 5$, nämlich
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 1\hspace{0.05cm},$$
- $$z_i \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 5 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} {\rm Inv_M}(z_i) = 5 \hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_i \cdot {\rm Inv_M}(z_i) = 25 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 6 = 1 \hspace{0.05cm}.$$
- Für $z_i = 2, \ z_i = 3$ und $z_i = 4$ findet man dagegen kein Element $z_j$, so dass $(z_i \cdot z_j) \, {\rm mod} \, 6 = 1$ ergibt.
- Richtig ist also der Lösungsvorschlag 3 ⇒ die blauen Tabellen für $q = 6$ ergeben kein Galoisfeld $\rm GF(6)$.
(5) Richtig ist der Lösungsvorschlag 2:
- Eine endliche Zahlenmenge $Z_q = \{0, \, 1, \hspace{0.05cm} \text{...} \hspace{0.1cm} , \, q-1\}$ natürlicher Zahlen führt nur dann zu einem „endlichen Zahlenkörper” (dies ist die deutsche Bezeichnung für ein Galoisfeld), wenn $q$ eine Primzahl ist.
- Von den oben genannten Zahlenmengen trifft dies nur für $Z_{11}$ zu.
