Difference between revisions of "Aufgaben:Exercise 2.07: Reed-Solomon Code (7, 3, 5) to Base 8"

From LNTwww
m (Text replacement - "”" to """)
(12 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes}}
  
[[File:P_ID2522__KC_A_2_7.png|right|frame|$\rm GF(2^3)$ in Exponential–, Polynom– und Koeffizientendarstellung]]
+
[[File:P_ID2522__KC_A_2_7.png|right|frame|$\rm GF(2^3)$–Darstellung als Potenzen, Polynome, Vektoren]]
Der hier betrachtete Reed–Solomon–Code mit der Bezeichnung $\rm RSC \, (7, \, 3, \, 5)_8$
+
Der hier betrachtete Reed–Solomon–Code mit der Bezeichnung  $\rm RSC \, (7, \, 3, \, 5)_8$
* codiert einen Informationsblock $\underline{u} = (u_0, \, u_1, \, u_2)$ von $k = 3$ Symbolen, wobei $u_0, \, u_1, \, u_2 ∈ \rm GF(2^3)$ gilt,
+
* codiert einen Informationsblock  $\underline{u} = (u_0, \, u_1, \, u_2)$  von  $k = 3$  Symbolen, wobei  $u_0, \, u_1, \, u_2 ∈ \rm GF(2^3)$  gilt, also keine Bits, sondern Symbole darstellen;
* erzeugt ein Codewort $\underline{c} = (c_0, \, c_1, \, ... \, , \, c_6)$ der Länge $n = 7$ mit Codesymbolen $c_i$ ebenfalls aus $\rm GF(2^3)$,
+
* erzeugt ein Codewort  $\underline{c} = (c_0, \, c_1,\hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6)$  der Länge  $n = 7$  mit Codesymbolen  $c_i$  ebenfalls aus dem Galoisfeld  $\rm GF(2^3)$,
* besitzt die freie Distanz $d_{\rm min} = n - k + 1 = 5$, so dass bis zu $e = 4$ Symbolfehler erkannt und bis zu $t = 2$ Symbolfehler korrigiert werden können.
+
* besitzt die freie Distanz  $d_{\rm min} = n - k + 1 = 5$, so dass bis zu  $e = 4$  Symbolfehler erkannt und bis zu  $t = 2$  Symbolfehler korrigiert werden können.
  
  
Line 17: Line 17:
 
\hspace{0.1cm}\}\hspace{0.05cm}.  $$
 
\hspace{0.1cm}\}\hspace{0.05cm}.  $$
  
Diese Elemente lassen sich entsprechend der Grafik auch als Polynome oder als Koeffizientenvektoren darstellen. Man erkennt aus obiger Tabelle, dass alle $u_i ∈ \rm GF(2^3)$ und alle $c_i ∈ \rm GF(2^3)$ auch durch $m = 3 \ \rm Bit$ charakterisiert werden können, zum Beispiel $\alpha^4$ durch „$110$”. Sie sollen in dieser Aufgabe für die binäre Eingangsfolge
+
Diese Elemente lassen sich entsprechend der Grafik auch als Polynome oder als Koeffizientenvektoren darstellen.  
:$$110 \hspace{0.09cm}001\hspace{0.09cm} 011\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 111 \, ... $$
+
 
 +
Man erkennt aus obiger Tabelle, dass alle  $u_i ∈ \rm GF(2^3)$  und alle  $c_i ∈ \rm GF(2^3)$  auch durch  $m = 3 \ \rm Bit$  charakterisiert werden können, zum Beispiel  $\alpha^4$  durch "$110$".  
 +
 
 +
Sie sollen in dieser Aufgabe für die binäre Eingangsfolge
 +
:$$110 \hspace{0.09cm}001\hspace{0.09cm} 011\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 111 \hspace{0.05cm} \text{...} $$
  
 
den Codiervorgang nachvollziehen. Beachten Sie dabei:
 
den Codiervorgang nachvollziehen. Beachten Sie dabei:
* Der Reed–Solomon–Coder arbeitet blockweise. Im ersten Codierschritt werden aus den drei ersten Informationssymbolen die Codesymbole $c_0, \ ... \, , \, c_6$ erzeugt, im zweiten Schritt dann aus dem Informationsblock $\underline{u} = (u_3, \, u_4, \, u_5)$ die Symbole $(c_7, \ ... \ , \ c_{13})$ des zweiten Codewortes, usw.
+
* Der Reed–Solomon–Coder arbeitet blockweise. Im ersten Codierschritt werden aus den drei ersten Informationssymbolen die Codesymbole  $c_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6$  erzeugt, im zweiten Schritt dann aus dem Informationsblock  $\underline{u} = (u_3, \, u_4, \, u_5)$  die Symbole  $(c_7, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_{13})$  des zweiten Codewortes, usw.
* Man beschreibt den Informationsblock $\underline{u}$ durch das Polynom $u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2$ vom Grad 2. Allgemein ergibt sich für das Galoisfeld $\rm GF(2^m)$ der Grad des Polynoms zu $m - 1$.
+
* Man beschreibt den Informationsblock  $\underline{u}$  durch das Polynom  $u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2$  vom Grad  $2$. Allgemein ergibt sich für das Galoisfeld  $\rm GF(2^m)$  der Grad des Polynoms zu  $m - 1$.
* Die Codesymbole $c_0, \ ... \ , \ c_6$ erhält man, indem in das Polynom $u(x)$ für $x$ alle Elemente von $\rm GF(2^3)$ mit Ausnahme des Nullelementes eingesetzt werden:
+
* Die Codesymbole  $c_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6$  erhält man, indem in das Polynom  $u(x)$  für  $x$  alle Elemente von  $\rm GF(2^3)$  mit Ausnahme des Nullelementes eingesetzt werden:
 
:$${\rm GF}(2^3)\hspace{-0.01cm}\setminus \hspace{-0.01cm}\{ 0\} = \{\hspace{0.1cm}\alpha^{0}\hspace{0.05cm},\hspace{0.1cm}
 
:$${\rm GF}(2^3)\hspace{-0.01cm}\setminus \hspace{-0.01cm}\{ 0\} = \{\hspace{0.1cm}\alpha^{0}\hspace{0.05cm},\hspace{0.1cm}
 
\alpha^1\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}
 
\alpha^1\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}
Line 32: Line 36:
 
\hspace{0.1cm}\}\hspace{0.05cm}. $$
 
\hspace{0.1cm}\}\hspace{0.05cm}. $$
  
Formal lässt sich der $\rm RSC \, (7, \, 3, \, 5)_8$ wie folgt beschreiben:
+
Formal lässt sich der  $\rm RSC \, (7, \, 3, \, 5)_8$  wie folgt beschreiben:
 
:$$C_{\rm RS} = \Big \{ \underline {c} =  \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}u(\alpha^{2})\hspace{0.1cm}  \big )
 
:$$C_{\rm RS} = \Big \{ \underline {c} =  \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}u(\alpha^{2})\hspace{0.1cm}  \big )
 
  \hspace{0.1cm} \big | \hspace{0.2cm} u(x) = \sum_{i = 0}^{2} u_i \cdot x^{i}\hspace{0.05cm},\hspace{0.2cm} u_i \in {\rm GF}(2^3)
 
  \hspace{0.1cm} \big | \hspace{0.2cm} u(x) = \sum_{i = 0}^{2} u_i \cdot x^{i}\hspace{0.05cm},\hspace{0.2cm} u_i \in {\rm GF}(2^3)
 
\Big \}  \hspace{0.05cm}.$$
 
\Big \}  \hspace{0.05cm}.$$
 +
 +
 +
 +
 +
 +
 +
  
 
''Hinweise:''
 
''Hinweise:''
* Die vorliegende Aufgabe behandelt die Thematik des Kapitels [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| Definition und Eigenschaften von Reed–Solomon–Codes]].
+
* Die vorliegende Aufgabe gehört zum Kapitel  [[Channel_Coding/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| Definition und Eigenschaften von Reed–Solomon–Codes]].
* Die [[Aufgaben:2.08_RS%E2%80%93Generatorpolynome|Aufgabe A2.8]] ist ähnlich strukturiert wie diese. Zur Generierung eines Codewortes $\underline{c}$ soll dann aber die Generatormatrix $\mathbf{G}$ herangezogen werden.
+
* Die  [[Aufgaben:Aufgabe_2.08:_Generatorpolynome_für_Reed-Solomon|Aufgabe 2.8]]  ist ähnlich strukturiert wie diese, aber zur Generierung eines Codewortes  $\underline{c}$  wird dann die Generatormatrix  $\mathbf{G}$  herangezogen.
  
  
Line 48: Line 59:
 
<quiz display=simple>
 
<quiz display=simple>
 
{Wie lautet der binäre Informationsblock im ersten Codierschritt?
 
{Wie lautet der binäre Informationsblock im ersten Codierschritt?
|type="[]"}
+
|type="()"}
 
- $\underline{u}_{\rm bin} = (110)$,
 
- $\underline{u}_{\rm bin} = (110)$,
+ $\underline{u}_{\rm bin} = (110001011)$,
+
+ $\underline{u}_{\rm bin} = (110_|001_|011)$,
- $\underline{u}_{\rm bin} = (1100010)$.
+
- $\underline{u}_{\rm bin} = (110_|001_|0)$.
  
 
{Wie lauten die Informationssymbole im ersten Codierschritt?
 
{Wie lauten die Informationssymbole im ersten Codierschritt?
Line 62: Line 73:
 
- $u_2 = \alpha^2$.
 
- $u_2 = \alpha^2$.
  
{Wie lautet der Informationsblock als Polynom $u(x)$?
+
{Wie lautet der Informationsblock als Polynom&nbsp; $u(x)$?
|type="[]"}
+
|type="()"}
 
- $u(x) = \alpha^3 \cdot x + x^2 + \alpha^4 \cdot x^3$,
 
- $u(x) = \alpha^3 \cdot x + x^2 + \alpha^4 \cdot x^3$,
 
- $u(x) = \alpha^3 + x + \alpha^4 \cdot x^2$,
 
- $u(x) = \alpha^3 + x + \alpha^4 \cdot x^2$,
 
+ $u(x) = \alpha^4 + x + \alpha^3 \cdot x^2$.
 
+ $u(x) = \alpha^4 + x + \alpha^3 \cdot x^2$.
  
{Wie lauten die Codesymbole $c_0, \ ... \ , \ c_6$ für den ersten Codierschritt.
+
{Wie lauten die Codesymbole&nbsp; $c_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} ,\ c_6$&nbsp; für den ersten Codierschritt.
 
|type="[]"}
 
|type="[]"}
 
+ $c_0 = \alpha^2$,
 
+ $c_0 = \alpha^2$,
Line 78: Line 89:
 
+ $c_6 = 1$.
 
+ $c_6 = 1$.
  
{Wie lautet das binäre Codewort? Genau ein Vorschlag ist richtig.
+
{Wie lautet das binäre Codewort?  
 
|type="()"}
 
|type="()"}
 
+ $\underline{c}_{\rm bin} = 100_|011_|011_|001_|110_|100_|001$,
 
+ $\underline{c}_{\rm bin} = 100_|011_|011_|001_|110_|100_|001$,
 
- $\underline{c}_{\rm bin} = 011_|011_|001_|110_|100_|001_|100$,
 
- $\underline{c}_{\rm bin} = 011_|011_|001_|110_|100_|001_|100$,
- $\underline{c}_{\rm bin} = 1001110$.
+
- $\underline{c}_{\rm bin} = 100_|111_|0$.
  
 
{Welche Aussagen gelten für den zweiten Codierschritt?
 
{Welche Aussagen gelten für den zweiten Codierschritt?
 
|type="[]"}
 
|type="[]"}
+ Es gilt $u_0 = u_1 = u_2 = 0$.
+
+ Es gilt&nbsp; $u_0 = u_1 = u_2 = 0$.
- Es gilt $u(x) = 1$.
+
- Es gilt&nbsp; $u(x) = 1$.
+ Das Codewort $\underline{c} &#8712; \rm GF(2^3)$ besteht aus sieben Nullsymbolen.
+
+ Das Codewort&nbsp; $\underline{c} &#8712; \rm GF(2^3)$&nbsp; besteht aus sieben Nullsymbolen.
+ Das binäre Codewort besteht aus 21 Nullen.
+
+ Das binäre Codewort &nbsp; $\underline{c}_{\rm bin} &#8712; \rm GF(2)$&nbsp; besteht aus 21 Nullen.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Alle Informationssymbole entstammen hier dem Galoisfeld $\rm GF(2^3)$. In Binärschreibweise wird jedes Symbol durch drei Binärzeichen dargestellt. Aufgrund des RS&ndash;Codeparameters $k = 3$ besteht ein Informationsblock aus drei Informationssymbolen: $\underline{u} = (u_0, \, u_1, \, u_2)$. Dementsprechend beinhaltet der binäre Informationsblock $\underline{u}_{\rm bin}$ genau $3 \cdot 3 = 9 \ \rm Bit$ &nbsp;&#8658;&nbsp; <u>Lösungsvorschlag 2</u>.
+
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
*Alle Informationssymbole entstammen hier dem Galoisfeld $\rm GF(2^3)$. In Binärschreibweise wird jedes Symbol durch drei Bit dargestellt.  
 +
*Aufgrund des RS&ndash;Codeparameters $k = 3$ besteht ein Informationsblock aus drei Informationssymbolen: $\underline{u} = (u_0, \, u_1, \, u_2)$.  
 +
*Dementsprechend beinhaltet der binäre Informationsblock $\underline{u}_{\rm bin}$ genau $3 \cdot 3 = 9$ Bit.
  
  
Line 102: Line 116:
 
  (011) \hspace{0.1cm} \Rightarrow  \hspace{0.2cm} u_2 = \alpha^{3}\hspace{0.05cm}. $$
 
  (011) \hspace{0.1cm} \Rightarrow  \hspace{0.2cm} u_2 = \alpha^{3}\hspace{0.05cm}. $$
  
Richtig sind also die <u>Lösungsvorschläge 1, 4 und 5</u>, und der Informationsblock im ersten Codierschritt lautet $\underline{u} = (\alpha^4, \, 1, \, \alpha^3)$.
+
*Richtig sind also die <u>Lösungsvorschläge 1, 4 und 5</u>.
 +
*Der Informationsblock im ersten Codierschritt lautet $\underline{u} = (\alpha^4, \, 1, \, \alpha^3)$.
 +
 
  
  
Line 108: Line 124:
 
:$$u(x) =  u_0 + u_1 \cdot x + u_2 \cdot x^2 = \alpha^{4} + x + \alpha^{3}\cdot x^2 \hspace{0.05cm}. $$
 
:$$u(x) =  u_0 + u_1 \cdot x + u_2 \cdot x^2 = \alpha^{4} + x + \alpha^{3}\cdot x^2 \hspace{0.05cm}. $$
  
Richtig ist demnach der <u>Lösungsvorschlag 3</u>. Der erste Lösungsvorschlag kann schon allein deshalb nicht stimmen, da der Polynomgrad höchstens 2 sein kann, wenn alle Informations&ndash; und Codesymbole aus $\rm GF(2^3)$ entstammen.
+
*Richtig ist demnach der <u>Lösungsvorschlag 3</u>.  
 +
*Der erste Lösungsvorschlag kann schon allein deshalb nicht stimmen, da der Polynomgrad höchstens 2 sein kann, wenn alle Informations&ndash; und Codesymbole aus $\rm GF(2^3)$ entstammen.
 +
 
  
  
Line 127: Line 145:
 
  (\alpha^{2} + \alpha) + (\alpha^2 +1) + \alpha = 1 \hspace{0.05cm}.$$
 
  (\alpha^{2} + \alpha) + (\alpha^2 +1) + \alpha = 1 \hspace{0.05cm}.$$
  
Richtig sind also die <u>Lösungsvorschläge 1, 2, 3, 4, 7</u>. Die Lösungen zu 5 und 6 sind genau vertauscht.
+
*Richtig sind also die <u>Lösungsvorschläge 1, 2, 3, 4, 7</u>.  
 +
*Die Lösungen zu 5 und 6 sind genau vertauscht.
 +
 
  
  
'''(5)'''&nbsp; Richtig ist der <u>erste Lösungsvorschlag</u>. Dieser ergibt sich aus dem Ergebnis der Teilaufgabe (4) und der Zuordnung
+
'''(5)'''&nbsp; Richtig ist der <u>erste Lösungsvorschlag</u>:
 +
*Dieser ergibt sich aus dem Ergebnis der Teilaufgabe '''(4)''' und der Zuordnung
 
:$$\alpha^2 &#8596 100, \ \alpha^3 &#8596 011, \ \alpha^3 &#8596 011, \ 1 &#8596 001, \ \alpha^4 &#8596 110, \ \alpha^2 &#8596 100, \ 1 &#8596 001. $$
 
:$$\alpha^2 &#8596 100, \ \alpha^3 &#8596 011, \ \alpha^3 &#8596 011, \ 1 &#8596 001, \ \alpha^4 &#8596 110, \ \alpha^2 &#8596 100, \ 1 &#8596 001. $$
 +
*Der letzte Lösungsvorschlag kann schon allein deshalb nicht stimmen, da das binäre Codewort aus $n \cdot m = 7 \cdot 3 = 21$  Bit bestehen muss.
 +
* Selbst wenn Sie in der Teilaufgabe '''(4)''' nur das Ergebnis $c_0 = \alpha^2$ ermittelt haben, so wissen Sie schon, dass auch der Vorschlag 2 nicht der richtige sein kann.
  
Der letzte Lösungsvorschlag kann schon allein deshalb nicht stimmen, da das binäre Codewort aus $n \cdot m = 7 \cdot 3 = 21 \ \rm Bit$ bestehen muss. Selbst wenn Sie in der Teilaufgabe (4) nur das Ergebnis $c_0 = \alpha^2$ ermittelt haben, so wissen Sie schon, dass auch der Lösungsvorschlag 2 nicht der richtige sein kann.
 
  
  
'''(6)'''&nbsp; Die <u>Aussagen 1, 2, 4</u> sind richtig. Die Bit 10, ... , 18 der Eingangssequenz sind alle $0$ und damit auch die Informationssymbole $u_0, \ u_1, \ u_2 &#8712; \rm GF(2^3)$. Dementsprechend ist auch $u(x) = 0$, so dass alle Codesymbole $c_i = u(x = \alpha^i)$ dem Nullsymbol entsprechen (Index: $0 &#8804; i &#8804; 6$). Die binäre Codefolge besteht somit aus $n \cdot m = 21$ Nullen.
+
'''(6)'''&nbsp; Die <u>Aussagen 1, 3, 4</u> sind richtig:
 +
*Die Bit 10, ... , 18 der Eingangssequenz sind alle $0$ und damit auch die Informationssymbole $u_0, \ u_1, \ u_2 &#8712; \rm GF(2^3)$.
 +
*Dementsprechend ist auch $u(x) = 0$, so dass alle Codesymbole $c_i = u(x = \alpha^i)$ dem Nullsymbol entsprechen (Index: $0 &#8804; i &#8804; 6$).  
 +
*Die binäre Codefolge besteht somit aus $n \cdot m = 21$ Nullen.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
[[Category:Aufgaben zu  Kanalcodierung|^2.3 Definition und Eigenschaften von Reed–Solomon–Codes^]]
+
[[Category:Channel Coding: Exercises|^2.3 Zu den Reed–Solomon–Codes^]]

Revision as of 15:23, 28 May 2021

$\rm GF(2^3)$–Darstellung als Potenzen, Polynome, Vektoren

Der hier betrachtete Reed–Solomon–Code mit der Bezeichnung  $\rm RSC \, (7, \, 3, \, 5)_8$

  • codiert einen Informationsblock  $\underline{u} = (u_0, \, u_1, \, u_2)$  von  $k = 3$  Symbolen, wobei  $u_0, \, u_1, \, u_2 ∈ \rm GF(2^3)$  gilt, also keine Bits, sondern Symbole darstellen;
  • erzeugt ein Codewort  $\underline{c} = (c_0, \, c_1,\hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6)$  der Länge  $n = 7$  mit Codesymbolen  $c_i$  ebenfalls aus dem Galoisfeld  $\rm GF(2^3)$,
  • besitzt die freie Distanz  $d_{\rm min} = n - k + 1 = 5$, so dass bis zu  $e = 4$  Symbolfehler erkannt und bis zu  $t = 2$  Symbolfehler korrigiert werden können.


Die Elemente des zugrunde liegenden Galoisfeldes lauten:

$${\rm GF}(2^3) = \{\hspace{0.1cm} 0\hspace{0.05cm},\hspace{0.1cm} 1 \hspace{0.05cm},\hspace{0.1cm} \alpha\hspace{0.05cm},\hspace{0.1cm} \alpha^{2} \hspace{0.05cm},\hspace{0.1cm} \alpha^{3} \hspace{0.05cm},\hspace{0.1cm} \alpha^{4} \hspace{0.05cm},\hspace{0.1cm} \alpha^{5} \hspace{0.05cm},\hspace{0.1cm} \alpha^{6} \hspace{0.1cm}\}\hspace{0.05cm}. $$

Diese Elemente lassen sich entsprechend der Grafik auch als Polynome oder als Koeffizientenvektoren darstellen.

Man erkennt aus obiger Tabelle, dass alle  $u_i ∈ \rm GF(2^3)$  und alle  $c_i ∈ \rm GF(2^3)$  auch durch  $m = 3 \ \rm Bit$  charakterisiert werden können, zum Beispiel  $\alpha^4$  durch "$110$".

Sie sollen in dieser Aufgabe für die binäre Eingangsfolge

$$110 \hspace{0.09cm}001\hspace{0.09cm} 011\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 000\hspace{0.09cm} 111 \hspace{0.05cm} \text{...} $$

den Codiervorgang nachvollziehen. Beachten Sie dabei:

  • Der Reed–Solomon–Coder arbeitet blockweise. Im ersten Codierschritt werden aus den drei ersten Informationssymbolen die Codesymbole  $c_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6$  erzeugt, im zweiten Schritt dann aus dem Informationsblock  $\underline{u} = (u_3, \, u_4, \, u_5)$  die Symbole  $(c_7, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_{13})$  des zweiten Codewortes, usw.
  • Man beschreibt den Informationsblock  $\underline{u}$  durch das Polynom  $u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2$  vom Grad  $2$. Allgemein ergibt sich für das Galoisfeld  $\rm GF(2^m)$  der Grad des Polynoms zu  $m - 1$.
  • Die Codesymbole  $c_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} , c_6$  erhält man, indem in das Polynom  $u(x)$  für  $x$  alle Elemente von  $\rm GF(2^3)$  mit Ausnahme des Nullelementes eingesetzt werden:
$${\rm GF}(2^3)\hspace{-0.01cm}\setminus \hspace{-0.01cm}\{ 0\} = \{\hspace{0.1cm}\alpha^{0}\hspace{0.05cm},\hspace{0.1cm} \alpha^1\hspace{0.05cm},\hspace{0.1cm} \alpha^{2} \hspace{0.05cm},\hspace{0.1cm} \alpha^{3} \hspace{0.05cm},\hspace{0.1cm} \alpha^{4} \hspace{0.05cm},\hspace{0.1cm} \alpha^{5} \hspace{0.05cm},\hspace{0.1cm} \alpha^{6} \hspace{0.1cm}\}\hspace{0.05cm}. $$

Formal lässt sich der  $\rm RSC \, (7, \, 3, \, 5)_8$  wie folgt beschreiben:

$$C_{\rm RS} = \Big \{ \underline {c} = \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}u(\alpha^{2})\hspace{0.1cm} \big ) \hspace{0.1cm} \big | \hspace{0.2cm} u(x) = \sum_{i = 0}^{2} u_i \cdot x^{i}\hspace{0.05cm},\hspace{0.2cm} u_i \in {\rm GF}(2^3) \Big \} \hspace{0.05cm}.$$





Hinweise:



Fragebogen

1

Wie lautet der binäre Informationsblock im ersten Codierschritt?

$\underline{u}_{\rm bin} = (110)$,
$\underline{u}_{\rm bin} = (110_|001_|011)$,
$\underline{u}_{\rm bin} = (110_|001_|0)$.

2

Wie lauten die Informationssymbole im ersten Codierschritt?

$u_0 = \alpha^4$,
$u_0 = 0$,
$u_1 = \alpha^6$,
$u_1 = \alpha^0$,
$u_2 = \alpha^3$,
$u_2 = \alpha^2$.

3

Wie lautet der Informationsblock als Polynom  $u(x)$?

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

4

Wie lauten die Codesymbole  $c_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} ,\ c_6$  für den ersten Codierschritt.

$c_0 = \alpha^2$,
$c_1 = \alpha^3$,
$c_2 = \alpha^3$,
$c_3 = 1$,
$c_4 = \alpha^2$,
$c_5 = \alpha^4$,
$c_6 = 1$.

5

Wie lautet das binäre Codewort?

$\underline{c}_{\rm bin} = 100_|011_|011_|001_|110_|100_|001$,
$\underline{c}_{\rm bin} = 011_|011_|001_|110_|100_|001_|100$,
$\underline{c}_{\rm bin} = 100_|111_|0$.

6

Welche Aussagen gelten für den zweiten Codierschritt?

Es gilt  $u_0 = u_1 = u_2 = 0$.
Es gilt  $u(x) = 1$.
Das Codewort  $\underline{c} ∈ \rm GF(2^3)$  besteht aus sieben Nullsymbolen.
Das binäre Codewort   $\underline{c}_{\rm bin} ∈ \rm GF(2)$  besteht aus 21 Nullen.


Musterlösung

(1)  Richtig ist der Lösungsvorschlag 2:

  • Alle Informationssymbole entstammen hier dem Galoisfeld $\rm GF(2^3)$. In Binärschreibweise wird jedes Symbol durch drei Bit dargestellt.
  • Aufgrund des RS–Codeparameters $k = 3$ besteht ein Informationsblock aus drei Informationssymbolen: $\underline{u} = (u_0, \, u_1, \, u_2)$.
  • Dementsprechend beinhaltet der binäre Informationsblock $\underline{u}_{\rm bin}$ genau $3 \cdot 3 = 9$ Bit.


(2)  Entsprechend der Tabelle auf der Angabenseite besteht folgender Zusammenhang zwischen dem Koeffizientenvektor und der Exponentialdarstellung:

$$(110) \hspace{0.1cm} \Rightarrow \hspace{0.2cm} u_0 = \alpha^{4}\hspace{0.05cm},\hspace{0.6cm} (001) \hspace{0.1cm} \Rightarrow \hspace{0.2cm} u_1 = \alpha^{0} = 1\hspace{0.05cm},\hspace{0.6cm} (011) \hspace{0.1cm} \Rightarrow \hspace{0.2cm} u_2 = \alpha^{3}\hspace{0.05cm}. $$
  • Richtig sind also die Lösungsvorschläge 1, 4 und 5.
  • Der Informationsblock im ersten Codierschritt lautet $\underline{u} = (\alpha^4, \, 1, \, \alpha^3)$.


(3)  In Polynomdarstellung ergibt sich für den Informationsblock $\underline{u} = (\alpha^4, \, 1, \, \alpha^3)$:

$$u(x) = u_0 + u_1 \cdot x + u_2 \cdot x^2 = \alpha^{4} + x + \alpha^{3}\cdot x^2 \hspace{0.05cm}. $$
  • Richtig ist demnach der Lösungsvorschlag 3.
  • Der erste Lösungsvorschlag kann schon allein deshalb nicht stimmen, da der Polynomgrad höchstens 2 sein kann, wenn alle Informations– und Codesymbole aus $\rm GF(2^3)$ entstammen.


(4)  Für die Codesymbole erhält man mit der Polynomdarstellung entsprechend der Angabenseite:

$$c_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{0} = 1) = \alpha^{4} + 1 + \alpha^{3}\cdot 1^2 = (110) + (001) + (011)= (100) = \alpha^{2} \hspace{0.05cm},$$
$$c_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{1}) = \alpha^{4} + \alpha + \alpha^{5}= (110) + (010) + (111) = (011) = \alpha^{3} \hspace{0.05cm},$$
$$c_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{2}) = \alpha^{4} + \alpha^{2} + \alpha^{7}= (110) + (100) + (001) = (011) = \alpha^{3} \hspace{0.05cm},$$
$$c_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{3}) = \alpha^{4} + \alpha^{3} + \alpha^{9}= (110) + (011) + (100) = (001) = 1 \hspace{0.05cm},$$
$$c_4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{4}) = \alpha^{4} + \alpha^{4} + \alpha^{11} = \alpha^{4} \hspace{0.05cm},$$
$$c_5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{5}) = \alpha^{4} + \alpha^{5} + \alpha^{13}= (110) + (111) + (101) = (100) = \alpha^{2} \hspace{0.05cm},$$
$$c_6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u(x = \alpha^{6}) = \alpha^{4} + \alpha^{6} + \alpha^{15}= (\alpha^{2} + \alpha) + (\alpha^2 +1) + \alpha = 1 \hspace{0.05cm}.$$
  • Richtig sind also die Lösungsvorschläge 1, 2, 3, 4, 7.
  • Die Lösungen zu 5 und 6 sind genau vertauscht.


(5)  Richtig ist der erste Lösungsvorschlag:

  • Dieser ergibt sich aus dem Ergebnis der Teilaufgabe (4) und der Zuordnung
$$\alpha^2 ↔ 100, \ \alpha^3 ↔ 011, \ \alpha^3 ↔ 011, \ 1 ↔ 001, \ \alpha^4 ↔ 110, \ \alpha^2 ↔ 100, \ 1 ↔ 001. $$
  • Der letzte Lösungsvorschlag kann schon allein deshalb nicht stimmen, da das binäre Codewort aus $n \cdot m = 7 \cdot 3 = 21$ Bit bestehen muss.
  • Selbst wenn Sie in der Teilaufgabe (4) nur das Ergebnis $c_0 = \alpha^2$ ermittelt haben, so wissen Sie schon, dass auch der Vorschlag 2 nicht der richtige sein kann.


(6)  Die Aussagen 1, 3, 4 sind richtig:

  • Die Bit 10, ... , 18 der Eingangssequenz sind alle $0$ und damit auch die Informationssymbole $u_0, \ u_1, \ u_2 ∈ \rm GF(2^3)$.
  • Dementsprechend ist auch $u(x) = 0$, so dass alle Codesymbole $c_i = u(x = \alpha^i)$ dem Nullsymbol entsprechen (Index: $0 ≤ i ≤ 6$).
  • Die binäre Codefolge besteht somit aus $n \cdot m = 21$ Nullen.