Exercise 2.5: Three Variants of GF(2 power 4)

Potenzen zweier Erweiterungskörper über $\rm GF(2^4)$ – nicht ganz vollständig

Irreduzible und primitive Polynome haben große Bedeutung für die Beschreibung von Verfahren zur Fehlerkorrektur. In LN97 findet man zum Beispiel die folgenden irreduziblen Polynome vom Grad $m = 4$:

$p(x) = x^4 + x +1$,
$p(x) = x^4 + x^3 + 1$,
$p(x) = x^4 + x^3 + x^2 + x + 1$.

Die beiden ersten Polynome sind auch primitiv. Dies erkennt man aus den Potenztabellen, die rechts angegeben sind – die untere Tabelle (B) allerdings nicht ganz vollständig. Aus beiden Tabellen erkennt man, dass alle Potenzen $\alpha^i$ für $1 ≤ i ≤ 14$ in der Polynomdarstellung ungleich $1$ sind. Erst für $i = 15$ ergibt sich

$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Koeffizientenvektor\hspace{0.15cm} 0001} \hspace{0.05cm}.$$

Nicht angegeben wird, ob sich die rot hinterlegte Tabelle (A) aus dem Polynom $x^4 + x + 1$ oder aus $x^4 + x^3 + 1$ ergibt. Diese Zuordnungen sollen Sie in den Teilaufgaben (1) und (2) treffen. In der Teilaufgabe (3) sollen Sie zudem die fehlenden Potenzen $\alpha^5, \ \alpha^6, \ \alpha^7$ und $\alpha^8$ in der Tabelle (B) ergänzen.

Die Teilaufgabe (4) bezieht sich auf das ebenfalls irreduzible Polynom $p(x) = x^4 + x^3 + x^2 + x +1$. Entsprechend den oben genannten Kriterien sollen Sie entscheiden, ob dieses Polynom primitiv ist oder nicht.

Hinweis:

Die Aufgabe gehört ebenfalls zum Themengebiet des Kapitels Erweiterungskörper.

Fragebogen

Musterlösung

Solution

(1) (2) (3) (4) (5)

	$\alpha^5 = \alpha^3 + \alpha + 1 \ \Rightarrow \ \rm Koeffizientenvektor „1011”$,
	$\alpha^6 = \alpha^2 + 1 \ \Rightarrow \ \rm Koeffizientenvektor „0111”$,
	$\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1 \ \Rightarrow \ \rm Koeffizientenvektor „1111”$,
	$\alpha^8 = \alpha^3 + \alpha^2 + \alpha \ \Rightarrow \ \rm Koeffizientenvektor „1110”$.

	Ja.
	Nein.