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

From LNTwww
m (Text replacement - "”" to """)
(4 intermediate revisions by 2 users not shown)
Line 19: Line 19:
 
Diese Elemente lassen sich entsprechend der Grafik auch als Polynome oder als Koeffizientenvektoren darstellen.  
 
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$”.  
+
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
 
Sie sollen in dieser Aufgabe für die binäre Eingangsfolge
Line 49: Line 49:
  
 
''Hinweise:''
 
''Hinweise:''
* Die vorliegende Aufgabe gehört zum Kapitel  [[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: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.
 
* 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 116: 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>. 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 122: 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 141: 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>:  
 
'''(5)'''&nbsp; Richtig ist der <u>erste Lösungsvorschlag</u>:  
*Dieser ergibt sich aus dem Ergebnis der Teilaufgabe (4) und der Zuordnung
+
*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.
 
*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 Lösungsvorschlag 2 nicht der richtige sein kann.
+
* 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.
 +
 
  
  
Line 158: Line 165:
  
  
[[Category:Aufgaben zu  Kanalcodierung|^2.3 Zu den 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.