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

Aus LNTwww
Wechseln zu:Navigation, Suche
(16 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes}}
  
[[Datei: P_ID2534__KC_Z_2_7.png|right|frame|$\rm GF(2^4)$ in Exponenten–, Polynom- und Koeffizientendarstellung]]
+
[[Datei: P_ID2534__KC_Z_2_7.png|right|frame|$\rm GF(2^4)$  in Potenzen–, Polynom- und Koeffizientendarstellung]]
Die vorliegende Aufgabenstellung ist ähnlich wie diejenige bei der [[Aufgaben:2.07_Reed%E2%80%93Solomon%E2%80%93Code_(7,_3,_5)(Base_8)|Aufgabe A2.7]]. Wir beziehen uns hier aber nun auf das Galoisfeld $\rm GF(2^4)$, dessen Elemente nebenstehend sowohl in Exponenten– und Polynomdarstellung als auch durch den Koeffizientenvektor angegeben sind. Weiter gilt in $\rm GF(2^4)$:
+
Die vorliegende Aufgabenstellung ist ähnlich wie diejenige bei der  [[Aufgaben:Aufgabe_2.07:_Reed–Solomon–Code_(7,_3,_5)_zur_Basis_8|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^{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}...$$
+
  \alpha^{18} = \alpha^{3}\hspace{0.05cm},\hspace{0.05cm}\text{...} $$
  
Zur Codierung des Informationsblockes der Länge $k = 5$,  
+
Zur Codierung des Informationsblockes der Länge  $k = 5$,  
:$$\underline{u} = (u_0,u_1,u_2,u_3,u_4)\hspace{0.05cm},$$
+
:$$\underline{u} = (u_0,\ u_1,\ u_2,\ u_3,\ u_4)\hspace{0.05cm},$$
  
 
bilden wir das Polynom
 
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 $$
 
:$$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, \ ... \ , \ 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:
+
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},
 
:$$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.2cm}  c_2 = u(\alpha^{2})\hspace{0.05cm},
Zeile 18: Zeile 20:
 
  c_{14} = u(\alpha^{14})\hspace{0.05cm}.$$
 
  c_{14} = u(\alpha^{14})\hspace{0.05cm}.$$
  
''Hinweise:''
+
 
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| Definition und Eigenschaften von Reed–Solomon–Codes]].
+
 
* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
+
 
 +
 
 +
 
 +
 
 +
''Hinweis:''
 +
* Die Aufgabe bezieht sich auf das Kapitel  [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| Definition und Eigenschaften von Reed–Solomon–Codes]].
 +
  
  
Zeile 27: Zeile 35:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Input-Box Frage
+
{Wieviele Symbolfehler können korrigiert werden?
 
|type="{}"}
 
|type="{}"}
$xyz \ = \ ${ 5.4 3% } $ab$
+
$t \ = \ $ { 5 }
  
{Multiple-Choice
+
{Wie lautet das Polynom&nbsp; $u(x)$&nbsp; für&nbsp; $\underline{u} = (\alpha^3, \, 0, \, 0, \, 1, \, \alpha^{10})$?
|type="[]"}
+
|type="()"}
+ correct
+
- $u(x) = \alpha^3 + x + \alpha^{10} \cdot x^2$,
- false
+
+ $u(x) = \alpha^3 + x^3 + \alpha^{10} \cdot x^4$,
 +
- $u(x) = 1 + x + x^2 + x^3 + x^4$.
  
{Multiple-Choice
+
{Wie lautet das Symbol&nbsp; $c_0$&nbsp; des zugehörigen Codewortes&nbsp; $\underline{c}$?
|type="[]"}
+
|type="()"}
+ correct
+
- $c_0 = 1$,
- false
+
- $c_0 = \alpha^5$,
 +
+ $c_0 = \alpha^{11}$,
 +
- $c_0 = \alpha^{14}$.
  
{Multiple-Choice
+
{Wie lautet das Symbol&nbsp; $c_1$&nbsp; des zugehörigen Codewortes&nbsp; $\underline{c}$?
|type="[]"}
+
|type="()"}
+ correct
+
- $c_1 = 1$,
- false
+
- $c_1 = \alpha^5$,
 +
- $c_1 = \alpha^{11}$,
 +
+ $c_1 = \alpha^{14}$.
  
{Multiple-Choice
+
{Wie lautet das Symbol&nbsp; $c_{13}$&nbsp; des zugehörigen Codewortes&nbsp; $\underline{c}$?
|type="[]"}
+
|type="()"}
+ correct
+
- $c_{13} = 1$,
- false
+
+ $c_{13} = \alpha^5$,
 +
- $c_{13} = \alpha^{11}$,
 +
- $c_{13} = \alpha^{14}$.
  
{Multiple-Choice
+
{Wie lautet das letzte Symbol des zugehörigen Codewortes&nbsp; $\underline{c}$?
|type="[]"}
+
|type="()"}
+ correct
+
- $c_{15} = 1$,
- false
+
- $c_{14} = 1$,
 +
+ $c_{14} = \alpha^7$,
 +
- $c_{14} = \alpha^{14}$.
  
{Multiple-Choice
+
{Welche Aussagen treffen zu?
 
|type="[]"}
 
|type="[]"}
+ correct
+
- Das Codesymbol &bdquo;$0$&rdquo; ist beim&nbsp; $\rm RSC \, (15, \, 5, \, 11)_{16}$&nbsp; nicht möglich.
- false
+
- Ein Codesymbol &bdquo;$0$&rdquo; ergibt sich nur für&nbsp; $\underline{u} = (0, \, 0, \, 0, \, 0, \, 0)$.
 +
+ Auch für&nbsp; $\underline{u} &ne; (0, \, 0, \, 0, \, 0, \, 0)$ kann es Codesymbole &bdquo;$0$&rdquo; geben.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp;  
+
'''(1)'''&nbsp; Aus $n = 15$ und $k = 5$ folgt:
'''(2)'''&nbsp;  
+
:$$d_{\rm min} = n - k +1 = 15 - 5 + 1 = 11 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
'''(3)'''&nbsp;  
+
t = \frac{d_{\rm min}-1}{2}\hspace{0.15cm}\underline {=5}\hspace{0.05cm}.$$
'''(4)'''&nbsp;  
+
 
'''(5)'''&nbsp;  
+
 
 +
 
 +
'''(2)'''&nbsp; 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 <u>Lösungsvorschlag 2</u> als richtig.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; 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 <u>Lösungsvorschlag 3</u>.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Aus $c_1 = u(\alpha)$ erhält man den <u>Lösungsvorschlag 4</u>.
 +
:$$c_1 = u(\alpha^{1}) =\alpha^{3} +1 \cdot  \alpha^{3} + \alpha^{10} \cdot \alpha^{4} =  \alpha^{14}
 +
\hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(5)'''&nbsp; 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  <u>Lösungsvorschlag 2</u>.
 +
 
 +
 
 +
 
 +
'''(6)'''&nbsp; 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  <u>Lösungsvorschlag 3</u>.
 +
 
 +
 
 +
'''(7)'''&nbsp; Das Codesymbol &bdquo;$0$&rdquo; tritt genau so oft auf wie alle anderen Symbole &bdquo;$\alpha^i$&rdquo; &nbsp;&#8658;&nbsp; <u>Lösungsvorschlag 3</u>.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^2.3 Definition und Eigenschaften von Reed–Solomon–Codes^]]
+
[[Category:Aufgaben zu  Kanalcodierung|^2.3 Zu den Reed–Solomon–Codes^]]

Version vom 21. Mai 2019, 17:32 Uhr

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



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

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