Aufgaben:Aufgabe 2.08Z: „Plus” und „Mal” in GF(2 hoch 3)

• Zurück zum Buch

$\rm GF(2^3)$:  Unvollständige Additions– und Multiplikationstabellen

Die Grafik zeigt die Additions– und Multiplikationstabelle für den endlichen Körper  $\rm GF(2^3)$.  Die Tabellen sind nicht vollständig.  Einige (farblich hervorgehobene) Felder sollen Sie ergänzen.

Die Elemente sind sowohl

• in der Exponentendarstellung  $($mit roter Beschriftung,  links und oben$)$  als auch
• in der Koeffizientendarstellung  $($graue Schrift,  rechts und unten$)$ 

angegeben.  Aus dieser Zuordnung erkennt man bereits das zugrunde liegende irreduzible Polynom  $p(\alpha)$.

• Additionen  $($und Subtraktionen$)$  führt man am besten in der Koeffizientendarstellung  $($oder mit den damit fest verknüpften Polynomen$)$  durch.

• Für Multiplikationen ist dagegen die Exponentendarstellung günstiger.

Hinweise:

• Die Aufgabe gehört zum Kapitel  "Definition und Eigenschaften von Reed–Solomon–Codes".

• Bezug genommen wird aber auch auf das Kapitel  "Erweiterungskörper".

Fragebogen

1

Für welches Element steht das  "$\rm A$"  in der Additionstabelle?

	$\rm A = 0$,
	$\rm A = 1$,
	$\rm A = \alpha^1$,

2

Für welches Element steht das  "$\rm B$"  in der Additionstabelle?

	$\rm B = 0$,
	$\rm B = 1$,
	$\rm B = \alpha^1$.

3

Für welches Element steht das  "$\rm C$"  in der Additionstabelle?

	$\rm C = \alpha^2$,
	$\rm C = \alpha^3$,
	$\rm C = \alpha^4$.

4

Für welches Element steht das  "$\rm D$"  in der Additionstabelle?

	$\rm D = \alpha^2$,
	$\rm D = \alpha^3$,
	$\rm D = \alpha^4$.

5

Welche Zuordnungen gelten in der Multiplikationstabelle?

	$\rm E = \alpha^5$,
	$\rm F = \alpha^1$,
	$\rm G = \alpha^6$.

6

Welches irreduzible Polynom liegt diesen Tabellen zugrunde?

	$p(\alpha) = \alpha^2 + \alpha + 1$,
	$p(\alpha) = \alpha^3 + \alpha^2 + 1$,
	$p(\alpha) = \alpha^3 + \alpha + 1$.

Musterlösung

Musterlösung

(1)  Die Addition eines jeden Elements eines Erweiterungskörpers,  der auf  $\rm GF(2)$  basiert,  mit sich selbst ergibt stets  $0$,  wie man anhand der Koeffizientendarstellung leicht erkennt,  zum Beispiel:

$$\alpha^3 + \alpha^3 = (011) + (011) = (000) = 0 \hspace{0.05cm}.$$

• Das heißt:   "$\rm A$"  steht für das Nullelement   ⇒   Lösungsvorschlag 1.

(2)  "$\rm B$"  ist das Ergebnis der Addition von  $\alpha^5$  und  $\alpha^6$   ⇒   Lösungsvorschlag 3:

$$\alpha^5 + \alpha^6 = (111) + (101) = (010) = \alpha^1 \hspace{0.05cm}.$$

• Man hätte dieses Ergebnis auch einfacher finden können,  da in jeder Zeile und Spalte jedes Element genau einmal vorkommt.

• Nachdem  $\rm A = 0$  festliegt,  fehlt in der letzten Zeile und der letzten Spalte genau nur noch das Element  $\alpha^1$.

(3)  "$\rm C$"  ist das Ergebnis der Summe von  $\alpha^1$  und  $\alpha^2$   ⇒   Lösungsvorschlag 3:

$$\alpha^1 + \alpha^2 = (010) + (100) = (110) = \alpha^4 \hspace{0.05cm}.$$

(4)  "$\rm D$"  ist das Ergebnis von  $\alpha^3$  und  $\alpha^5$    ⇒   Lösungsvorschlag 1:

$$\alpha^3 + \alpha^5 = (011) + (111) = (100) = \alpha^2 \hspace{0.05cm}.$$

(5)  Alle Lösungsvorschläge  sind richtig,  wie man aus der Zeile 2  ("Multiplikation mit dem Einselelement")  erkennt:

$\rm GF(2^3)$: Vollständige Additions– und Multiplikationstabellen

• Nebenstehend sehen Sie die vollständigen Tabellen für die Addition und die Multiplikation.

• Aufgrund der Gültigkeit von  $\alpha^i \cdot \alpha^j = \alpha^{(i+j)\hspace{0.1cm} {\rm mod}\hspace{0.1cm} 7} $  ergibt sich bei der Multiplikation eine Symmetrie,  die man zur Lösung nutzen könnte.

(6)  Richtig ist hier der  Lösungsvorschlag 3:

• Alle Polynome sind zwar irreduzibel.  Man benötigt aber für  $\rm GF(2^3)$  ein Grad–3–Polynom.
• Der dritte Lösungsvorschlag ergibt sich aus der Beziehung

$$\alpha^3 = \alpha + 1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p(\alpha) = \alpha^3 + \alpha + 1 = 0 \hspace{0.05cm}.$$