Aufgaben:Aufgabe 2.07Z: Reed–Solomon–Code (15, 5, 11) zur Basis 16

• Zurück zum Buch

$\rm GF(2^4)$  in Potenzen–, Polynom- und Koeffizientendarstellung

Die vorliegende Aufgabenstellung ist ähnlich wie diejenige bei der  "Aufgabe 2.7".  Wir beziehen uns hier aber nun auf das Galoisfeld  $\rm GF(2^4)$,  dessen Elemente nebenstehend sowohl in Potenzen– und Polynomdarstellung als auch durch den Koeffizientenvektor angegeben sind.  Weiter gilt in  $\rm GF(2^4)$:

$$\alpha^{16} = \alpha^{1}\hspace{0.05cm},\hspace{0.2cm} \alpha^{17} = \alpha^{2}\hspace{0.05cm},\hspace{0.2cm} \alpha^{18} = \alpha^{3}\hspace{0.05cm},\hspace{0.05cm}\text{...} $$

Zur Codierung des Informationsblockes der Länge  $k = 5$,

$$\underline{u} = (u_0,\ u_1,\ u_2,\ u_3,\ u_4)\hspace{0.05cm},$$

bilden wir das Polynom

$$u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2 + u_3 \cdot x^3 + u_4 \cdot x^4 $$

mit  $u_0, \hspace{0.05cm}\text{...} \hspace{0.1cm} , u_4 ∈ \rm GF(2^4)$.

Die  $n = 15$  Codeworte ergeben sich dann, wenn man in  $u(x)$  die Elemente von  $\rm GF(2^4) \ \backslash \ \{0\}$  einsetzt:

$$c_0 = u(\alpha^{0})\hspace{0.05cm},\hspace{0.2cm} c_1 = u(\alpha^{1})\hspace{0.05cm}, \hspace{0.2cm} c_2 = u(\alpha^{2})\hspace{0.05cm}, \hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.20cm} c_{14} = u(\alpha^{14})\hspace{0.05cm}.$$

Hinweis:  Die Aufgabe bezieht sich auf das Kapitel  "Definition und Eigenschaften von Reed–Solomon–Codes".

Fragebogen

1

Wieviele Symbolfehler können korrigiert werden?

$t \ = \ $

2

Wie lautet das Polynom  $u(x)$  für  $\underline{u} = (\alpha^3, \, 0, \, 0, \, 1, \, \alpha^{10})$?

	$u(x) = \alpha^3 + x + \alpha^{10} \cdot x^2$,
	$u(x) = \alpha^3 + x^3 + \alpha^{10} \cdot x^4$,
	$u(x) = 1 + x + x^2 + x^3 + x^4$.

3

Wie lautet das Symbol  $c_0$  des zugehörigen Codewortes  $\underline{c}$?

	$c_0 = 1$,
	$c_0 = \alpha^5$,
	$c_0 = \alpha^{11}$,
	$c_0 = \alpha^{14}$.

4

Wie lautet das Symbol  $c_1$  des zugehörigen Codewortes  $\underline{c}$?

	$c_1 = 1$,
	$c_1 = \alpha^5$,
	$c_1 = \alpha^{11}$,
	$c_1 = \alpha^{14}$.

5

Wie lautet das Symbol  $c_{13}$  des zugehörigen Codewortes  $\underline{c}$?

	$c_{13} = 1$,
	$c_{13} = \alpha^5$,
	$c_{13} = \alpha^{11}$,
	$c_{13} = \alpha^{14}$.

6

Wie lautet das letzte Symbol des zugehörigen Codewortes  $\underline{c}$?

	$c_{15} = 1$,
	$c_{14} = 1$,
	$c_{14} = \alpha^7$,
	$c_{14} = \alpha^{14}$.

7

Welche Aussagen treffen zu?

	Das Codesymbol  "$0$"  ist beim  $\rm RSC \, (15, \, 5, \, 11)_{16}$  nicht möglich.
	Ein Codesymbol  "$0$"  ergibt sich nur für  $\underline{u} = (0, \, 0, \, 0, \, 0, \, 0)$.
	Auch für  $\underline{u} ≠ (0, \, 0, \, 0, \, 0, \, 0)$  kann es Codesymbole  "$0$"  geben.

Musterlösung

Musterlösung

(1)  Aus  $n = 15$  und  $k = 5$  folgt:

$$d_{\rm min} = n - k +1 = 15 - 5 + 1 = 11 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} t = \frac{d_{\rm min}-1}{2}\hspace{0.15cm}\underline {=5}\hspace{0.05cm}.$$

(2)  Allgemein gilt für das gesuchte Polynom  $u(x)$  mit  $k = 5$:

$$u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i}= u_0 + u_1 \cdot x + u_2 \cdot x^2 + u_3 \cdot x^3 + u_4 \cdot x^4 \hspace{0.05cm}.$$

• Für   $u_0 = \alpha^3, \ u_1 = u_2 = 0, \ u_3 = 1$   und   $u_4 = \alpha^{10}$   erweist sich der  Lösungsvorschlag 2  als richtig.

(3)  Es gilt  $c_0 = u(\alpha^0) = u(1)$:

$$c_0 = \alpha^{3} + 1 \cdot 1^3 + \alpha^{10} \cdot 1^{4} = (1000) + (0001) + (0111) = (1110)= \alpha^{11} \hspace{0.05cm}.$$

• Richtig ist somit der  Lösungsvorschlag 3.

(4)  Aus  $c_1 = u(\alpha)$  erhält man den  Lösungsvorschlag 4:

$$c_1 = u(\alpha^{1}) =\alpha^{3} +1 \cdot \alpha^{3} + \alpha^{10} \cdot \alpha^{4} = \alpha^{14} \hspace{0.05cm}.$$

(5)  Für das vorletzte Symbol gilt  $c_{13} = u(\alpha^{13})$:

$$c_{13} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(\alpha^{13}) =\alpha^{3} + 1 \cdot \alpha^{13 \hspace{0.05cm}\cdot \hspace{0.05cm}3} + \alpha^{10} \cdot \alpha^{13 \hspace{0.05cm}\cdot \hspace{0.05cm}4} = \alpha^{3} + \alpha^{39}+ \alpha^{62} =\alpha^{3} + \alpha^{15 \hspace{0.05cm}\cdot \hspace{0.05cm}2} \cdot \alpha^{9}+ \alpha^{15 \hspace{0.05cm}\cdot \hspace{0.05cm}4} \cdot \alpha^{2} = \alpha^{3} + \alpha^{9} + \alpha^{2}$$

$$\Rightarrow \hspace{0.3cm}c_{13} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1000) + (1010) + (0100) = (0110) = \alpha^{5} \hspace{0.05cm}.$$

• Richtig ist somit der  Lösungsvorschlag 2.

(6)  Das letzte Codesymbol ist  $c_{14} = u(\alpha^{14})$:

$$c_{14} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(\alpha^{14}) =\alpha^{3} + 1 \cdot \alpha^{14 \hspace{0.05cm}\cdot \hspace{0.05cm}3} + \alpha^{10} \cdot \alpha^{14 \hspace{0.05cm}\cdot \hspace{0.05cm}4} = \alpha^{3} + \alpha^{42}+ \alpha^{66} =\alpha^{3} + \alpha^{15 \hspace{0.05cm}\cdot \hspace{0.05cm}2} \cdot \alpha^{12}+ \alpha^{15 \hspace{0.05cm}\cdot \hspace{0.05cm}4} \cdot \alpha^{6} = \alpha^{3} + \alpha^{12} + \alpha^{6} =$$

$$\Rightarrow \hspace{0.3cm}c_{14} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}(1000) + (1111) + (1100) = (1011) = \alpha^{7} \hspace{0.05cm}.$$

• Richtig ist somit der  Lösungsvorschlag 3.

(7)  Das Codesymbol  "$0$"  tritt genau so oft auf wie alle anderen Symbole  "$\alpha^i$"   ⇒   Lösungsvorschlag 3.