Exercise 2.08Z: Addition and Multiplication in GF(2 power 3)

$\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

Musterlösung

Solution

(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}.$$

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

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

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

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