Aufgaben:Aufgabe 2.07Z: Reed–Solomon–Code (15, 5, 11) zur Basis 16: Unterschied zwischen den Versionen
(14 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 | + | [[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: | + | 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, \ ... \ , | + | 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}.$$ | ||
− | + | ||
− | + | ||
− | + | ||
+ | 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 29: | Zeile 33: | ||
{Wieviele Symbolfehler können korrigiert werden? | {Wieviele Symbolfehler können korrigiert werden? | ||
|type="{}"} | |type="{}"} | ||
− | $t \ = \ ${ 5 | + | $t \ = \ $ { 5 } |
− | {Wie lautet das Polynom $u(x)$ für $\underline{u} = (\alpha^3, \, 0, \, 0, \, 1, \, \alpha^{10})$? | + | {Wie lautet das Polynom $u(x)$ für $\underline{u} = (\alpha^3, \, 0, \, 0, \, 1, \, \alpha^{10})$? |
− | |type=" | + | |type="()"} |
- $u(x) = \alpha^3 + x + \alpha^{10} \cdot x^2$, | - $u(x) = \alpha^3 + x + \alpha^{10} \cdot x^2$, | ||
+ $u(x) = \alpha^3 + x^3 + \alpha^{10} \cdot x^4$, | + $u(x) = \alpha^3 + x^3 + \alpha^{10} \cdot x^4$, | ||
- $u(x) = 1 + x + x^2 + x^3 + x^4$. | - $u(x) = 1 + x + x^2 + x^3 + x^4$. | ||
− | {Wie lautet das Symbol $c_0$ des zugehörigen Codewortes $\underline{c}$? | + | {Wie lautet das Symbol $c_0$ des zugehörigen Codewortes $\underline{c}$? |
− | |type=" | + | |type="()"} |
- $c_0 = 1$, | - $c_0 = 1$, | ||
- $c_0 = \alpha^5$, | - $c_0 = \alpha^5$, | ||
Zeile 44: | Zeile 48: | ||
- $c_0 = \alpha^{14}$. | - $c_0 = \alpha^{14}$. | ||
− | {Wie lautet das Symbol $c_1$ des zugehörigen Codewortes $\underline{c}$? | + | {Wie lautet das Symbol $c_1$ des zugehörigen Codewortes $\underline{c}$? |
− | |type=" | + | |type="()"} |
- $c_1 = 1$, | - $c_1 = 1$, | ||
- $c_1 = \alpha^5$, | - $c_1 = \alpha^5$, | ||
Zeile 51: | Zeile 55: | ||
+ $c_1 = \alpha^{14}$. | + $c_1 = \alpha^{14}$. | ||
− | {Wie lautet das Symbol $c_{13}$ des zugehörigen Codewortes $\underline{c}$? | + | {Wie lautet das Symbol $c_{13}$ des zugehörigen Codewortes $\underline{c}$? |
− | |type=" | + | |type="()"} |
- $c_{13} = 1$, | - $c_{13} = 1$, | ||
+ $c_{13} = \alpha^5$, | + $c_{13} = \alpha^5$, | ||
Zeile 58: | Zeile 62: | ||
- $c_{13} = \alpha^{14}$. | - $c_{13} = \alpha^{14}$. | ||
− | {Wie lautet das letzte Symbol des zugehörigen Codewortes $\underline{c}$? | + | {Wie lautet das letzte Symbol des zugehörigen Codewortes $\underline{c}$? |
− | |type=" | + | |type="()"} |
- $c_{15} = 1$, | - $c_{15} = 1$, | ||
- $c_{14} = 1$, | - $c_{14} = 1$, | ||
Zeile 67: | Zeile 71: | ||
{Welche Aussagen treffen zu? | {Welche Aussagen treffen zu? | ||
|type="[]"} | |type="[]"} | ||
− | - Das Codesymbol & | + | - Das Codesymbol "$0$" ist beim $\rm RSC \, (15, \, 5, \, 11)_{16}$ nicht möglich. |
− | - Ein Codesymbol & | + | - 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 & | + | + Auch für $\underline{u} ≠ (0, \, 0, \, 0, \, 0, \, 0)$ kann es Codesymbole "$0$" geben. |
+ | <br><br> | ||
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Aus $n = 15$ und $k = 5$ folgt: | + | '''(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} | :$$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}.$$ | 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$: | + | '''(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(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}.$$ | 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. | + | *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)''' Es gilt $c_0 = u(\alpha^0) = u(1)$: | + | '''(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} | :$$c_0 = \alpha^{3} + 1 \cdot 1^3 + \alpha^{10} \cdot 1^{4} = (1000) + (0001) + (0111) = (1110)= \alpha^{11} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | Richtig ist somit der <u>Lösungsvorschlag 3</u>. | + | *Richtig ist somit der <u>Lösungsvorschlag 3</u>. |
− | '''(4)''' Aus $c_1 = u(\alpha)$ erhält man den <u>Lösungsvorschlag 4</u> | + | |
+ | '''(4)''' 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} | :$$c_1 = u(\alpha^{1}) =\alpha^{3} +1 \cdot \alpha^{3} + \alpha^{10} \cdot \alpha^{4} = \alpha^{14} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | '''(5)''' Für das vorletzte Symbol gilt $c_{13} = u(\alpha^{13})$: | + | '''(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} = | + | :$$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}$$ | |
− | \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. | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | Richtig ist <u>Lösungsvorschlag 2</u>. | + | *Richtig ist somit der <u>Lösungsvorschlag 2</u>. |
+ | |||
− | '''(6)''' Das letzte Codesymbol ist $c_{14} = u(\alpha^{14})$: | + | '''(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} = | + | :$$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} =$$ | \alpha^{3} + \alpha^{12} + \alpha^{6} =$$ | ||
− | :$$\ = \ \hspace{-0.15cm} (1000) + (1111) + (1100) = (1011) = \alpha^{7} | + | :$$\Rightarrow \hspace{0.3cm}c_{14} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}(1000) + (1111) + (1100) = (1011) = \alpha^{7} |
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | + | *Richtig ist somit der <u>Lösungsvorschlag 3</u>. | |
− | '''(7)''' Das Codesymbol & | + | '''(7)''' Das Codesymbol "$0$" tritt genau so oft auf wie alle anderen Symbole "$\alpha^i$" ⇒ <u>Lösungsvorschlag 3</u>. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
− | [[Category:Aufgaben zu Kanalcodierung|^2.3 | + | [[Category:Aufgaben zu Kanalcodierung|^2.3 Zu den Reed–Solomon–Codes^]] |
Aktuelle Version vom 9. Oktober 2022, 17:42 Uhr
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
Musterlösung
- $$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.