Aufgaben:Aufgabe 2.09: Reed–Solomon–Parameter: Unterschied zwischen den Versionen
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 2: | Zeile 2: | ||
[[Datei:P_ID2523__KC_A_2_9_neu.png|right|frame|Einige Reed–Solomon–Codes]] | [[Datei:P_ID2523__KC_A_2_9_neu.png|right|frame|Einige Reed–Solomon–Codes]] | ||
− | Nebenstehend finden Sie eine unvollständige Liste möglicher Reed–Solomon–Codes, die bekanntlich auf einem Galoisfeld ${\rm GF}(q) = {\rm GF}(2^m)$ basieren. Der Parameter $m$ gibt an, mit wie vielen Bit ein RS–Codesymbol dargestellt wird. Es gilt: | + | Nebenstehend finden Sie eine unvollständige Liste möglicher Reed–Solomon–Codes, die bekanntlich auf einem Galoisfeld ${\rm GF}(q) = {\rm GF}(2^m)$ basieren. Der Parameter $m$ gibt an, mit wie vielen Bit ein RS–Codesymbol dargestellt wird. Es gilt: |
* $m = 4$ (rote Schrift), | * $m = 4$ (rote Schrift), | ||
+ | |||
* $m = 5$ (blaue Schrift), | * $m = 5$ (blaue Schrift), | ||
+ | |||
* $m = 6$ (grüne Schrift). | * $m = 6$ (grüne Schrift). | ||
Ein Reed–Solomon–Code wird allgemein wie folgt bezeichnet: ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$. | Ein Reed–Solomon–Code wird allgemein wie folgt bezeichnet: ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$. | ||
− | |||
Die Parameter haben folgende Bedeutung: | Die Parameter haben folgende Bedeutung: | ||
− | + | # $n$ gibt die Anzahl der Symbole eines Codewortes $\underline{c}$ an ⇒ <b>Länge</b> des Codes. | |
− | + | # $k$ gibt die Anzahl der Symbole eines Informationsblocks $\underline{u}$ an ⇒ <b>Dimension</b> des Codes. | |
− | + | # $d_{\rm min}$ kennzeichnet die <b>minimale Distanz </b> zwischen zwei Codeworten <br>$($bei allen Reed–Solomon–Codes gleich $n-k+1)$. | |
− | + | # $q$ gibt einen Hinweis auf die Verwendung des Galoisfeldes ${\rm GF}(q)$. | |
Rechts daneben ist die Binärrepräsentation des gleichen Codes angegeben: | Rechts daneben ist die Binärrepräsentation des gleichen Codes angegeben: | ||
− | + | # Bei dieser Realisierung eines RS–Codes wird jedes Informations– und Codesymbol durch $m$ Bit dargestellt. | |
− | + | # Beispielsweise erkennt man aus der ersten Zeile, dass die minimale Distanz hinsichtlich der Bits ebenfalls $d_{\rm min} = 5$ ist, wenn in ${\rm GF}(2^m)$ die minimale Distanz $d_{\rm min} = 5$ beträgt. | |
− | + | # Damit können bis zu $t = 2$ Bitfehler (oder Symbolfehler) korrigiert und bis zu $e = 4$ Bitfehler (oder Symbolfehler) erkannt werden. | |
Zeile 27: | Zeile 28: | ||
+ | Hinweise: | ||
+ | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes| "Definition und Eigenschaften von Reed–Solomon–Codes"]]. | ||
− | + | * Bezug genommen wird aber auch auf das Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| "Erweiterungskörper"]]. | |
− | |||
− | |||
− | * Bezug genommen wird aber auch auf das Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]]. | ||
Zeile 38: | Zeile 38: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | {Es gelte $c_i ∈ {\rm GF}(2^m)$. | + | {Es gelte $c_i ∈ {\rm GF}(2^m)$. Welche Codeparameter $n$ ergeben sich? |
|type="{}"} | |type="{}"} | ||
$m = 4 \text{:} \hspace{0.4cm} n \ = \ ${ 15 } | $m = 4 \text{:} \hspace{0.4cm} n \ = \ ${ 15 } | ||
Zeile 44: | Zeile 44: | ||
$m = 6 \text{:} \hspace{0.4cm} n \ = \ ${ 63 } | $m = 6 \text{:} \hspace{0.4cm} n \ = \ ${ 63 } | ||
− | {Im Folgenden werden zwei spezielle | + | {Im Folgenden werden zwei spezielle Reed–Solomon–Codes ${\rm RSC} \ 1 \ (m = 4, \ t = 4)$ und ${\rm RSC} \ 2 \ (m = 5, \ t = 8)$ betrachtet. <br>Mit welchem Parameter $k$ lassen sich genau $t$ Symbolfehler korrigeren? |
|type="{}"} | |type="{}"} | ||
${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ ${ 7 } | ${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ ${ 7 } | ||
Zeile 51: | Zeile 51: | ||
{Welche Bezeichnungen sind für $\rm RSC \ 1$ bzw. $\rm RSC \ 2$ richtig? | {Welche Bezeichnungen sind für $\rm RSC \ 1$ bzw. $\rm RSC \ 2$ richtig? | ||
|type="[]"} | |type="[]"} | ||
− | + $\rm RSC \ 1$ nennt man auch $\rm RSC \, (15, \, 7, \, 9)_{16}$. | + | + $\rm RSC \ 1$ nennt man auch "$\rm RSC \, (15, \, 7, \, 9)_{16}$". |
− | - $\rm RSC \ 1$ nennt man auch $\rm RSC \, (15, \, 7, \, 4)_4$. | + | - $\rm RSC \ 1$ nennt man auch "$\rm RSC \, (15, \, 7, \, 4)_4$". |
− | - $\rm RSC \ 2$ nennt man auch $\rm RSC \, (31, \, 17, \, 15)_{32}$. | + | - $\rm RSC \ 2$ nennt man auch "$\rm RSC \, (31, \, 17, \, 15)_{32}$". |
− | + $\rm RSC \ 2$ nennt man auch $\rm RSC \, (31, \, 15, \, 17)_{32}$. | + | + $\rm RSC \ 2$ nennt man auch "$\rm RSC \, (31, \, 15, \, 17)_{32}$". |
{Wieviele Symbolfehler $(e)$ können höchstens erkannt werden? | {Wieviele Symbolfehler $(e)$ können höchstens erkannt werden? | ||
Zeile 63: | Zeile 63: | ||
{Wie lauten die betrachteten Codes in Binärschreibweise? | {Wie lauten die betrachteten Codes in Binärschreibweise? | ||
|type="[]"} | |type="[]"} | ||
− | - $\rm RSC \ 1$ entspricht dem Code $\rm RSC \, (60, \, 28, \, 36)_2$. | + | - $\rm RSC \ 1$ entspricht dem Code "$\rm RSC \, (60, \, 28, \, 36)_2$". |
− | + $\rm RSC \ 1$ entspricht dem Code $\rm RSC \, (60, \, 28, \, 9)_2$. | + | + $\rm RSC \ 1$ entspricht dem Code "$\rm RSC \, (60, \, 28, \, 9)_2$". |
− | + $\rm RSC \ 2$ entspricht dem Code $\rm RSC \, (155, \, 75, \, 17)_2$. | + | + $\rm RSC \ 2$ entspricht dem Code "$\rm RSC \, (155, \, 75, \, 17)_2$". |
− | - $\rm RSC \ 2$ entspricht dem Code $\rm RSC \, (124, \, 60, \, 17)_2$. | + | - $\rm RSC \ 2$ entspricht dem Code "$\rm RSC \, (124, \, 60, \, 17)_2$". |
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Für die Codelänge der Reed–Solomon–Codes gilt allgemein | + | '''(1)''' Für die Codelänge der Reed–Solomon–Codes gilt allgemein: |
:$$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm}, | :$$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm}, | ||
\hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm} | \hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm} | ||
m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}. $$ | m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}. $$ | ||
− | '''(2)''' Um $t$ Symbolfehler korrigieren zu können, muss die minimale Distanz $d_{\rm min} = 2t + 1$ betragen. Der Reed–Solomon–Code ist ein sogenannter MDS–Code ( | + | |
+ | '''(2)''' Um $t$ Symbolfehler korrigieren zu können, muss die minimale Distanz mindestens $d_{\rm min} = 2t + 1$ betragen. | ||
+ | *Der Reed–Solomon–Code ist ein sogenannter MDS–Code ("Maximum Distance Separable"). Für diese gilt: | ||
:$$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}k = n -2t = 2^m - ( 2t+1) \hspace{0.05cm}. $$ | :$$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}k = n -2t = 2^m - ( 2t+1) \hspace{0.05cm}. $$ | ||
− | Damit erhält man für den | + | *Damit erhält man für den |
− | * $\rm RSC \ 1$ (mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$, | + | :* $\rm RSC \ 1$ $($mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$, |
− | * $\rm RSC \ 2$ (mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$. | + | :* $\rm RSC \ 2$ $($mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$. |
− | '''(3)''' Die Bezeichnung eines Reed–Solomon–Codes lautet ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ mit $q = 2^m = n + 1$. Richtig sind die <u>Lösungsvorschläge 1 und 4</u>: | + | |
+ | '''(3)''' Die Bezeichnung eines Reed–Solomon–Codes lautet ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ mit $q = 2^m = n + 1$. Richtig sind die <u>Lösungsvorschläge 1 und 4</u>: | ||
* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$, | * $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$, | ||
+ | |||
* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$. | * $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$. | ||
− | '''(4)''' Bezeichnet $d_{\rm min}$ die minimale Distanz eines Blockcodes, so können damit $e = d_{\rm min} - 1$ Symbolfehler erkannt und $t = e/2$ Symbolfehler korrigiert werden: | + | |
+ | '''(4)''' Bezeichnet $d_{\rm min}$ die minimale Distanz eines Blockcodes, so können damit $e = d_{\rm min} - 1$ Symbolfehler erkannt und $t = e/2$ Symbolfehler korrigiert werden: | ||
* ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$, | * ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$, | ||
+ | |||
* ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$. | * ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$. | ||
− | '''(5)''' Richtig sind die beiden mittleren <u>Lösungsvorschläge 2 und 3</u>: | + | |
− | * | + | '''(5)''' Richtig sind die beiden mittleren <u>Lösungsvorschläge 2 und 3</u>: |
+ | *Beim ${\rm RSC} \ 1 \, \, (m = 4)$ entsprechen $n = 15$ Codesymbole aus $\rm GF(2^5)$ gleich $60$ Bit und $k = 7$ Informationssymbole genau $28$ Bit: | ||
+ | |||
:* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$, | :* $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$, | ||
+ | |||
:* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$. | :* $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$. | ||
− | *Für die minimale Distanz auf Bitebene ⇒ $\rm GF(2)$ ergeben sich mit $d_{\rm min} = 9$ bzw. $d_{\rm min} = 17$ die gleichen Werte wie auf Symbolebene ⇒ $\rm GF(2^4)$ bzw. $\rm GF(2^5)$ (siehe [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Codebezeichnung_und_Coderate|Theorieteil]]). | + | |
+ | *Für die minimale Distanz auf Bitebene ⇒ $\rm GF(2)$ ergeben sich mit $d_{\rm min} = 9$ bzw. $d_{\rm min} = 17$ die gleichen Werte wie auf Symbolebene <br>⇒ $\rm GF(2^4)$ bzw. $\rm GF(2^5)$ $($siehe [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Codebezeichnung_und_Coderate|Theorieteil]]$)$. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 11. Oktober 2022, 13:59 Uhr
Nebenstehend finden Sie eine unvollständige Liste möglicher Reed–Solomon–Codes, die bekanntlich auf einem Galoisfeld ${\rm GF}(q) = {\rm GF}(2^m)$ basieren. Der Parameter $m$ gibt an, mit wie vielen Bit ein RS–Codesymbol dargestellt wird. Es gilt:
- $m = 4$ (rote Schrift),
- $m = 5$ (blaue Schrift),
- $m = 6$ (grüne Schrift).
Ein Reed–Solomon–Code wird allgemein wie folgt bezeichnet: ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$.
Die Parameter haben folgende Bedeutung:
- $n$ gibt die Anzahl der Symbole eines Codewortes $\underline{c}$ an ⇒ Länge des Codes.
- $k$ gibt die Anzahl der Symbole eines Informationsblocks $\underline{u}$ an ⇒ Dimension des Codes.
- $d_{\rm min}$ kennzeichnet die minimale Distanz zwischen zwei Codeworten
$($bei allen Reed–Solomon–Codes gleich $n-k+1)$. - $q$ gibt einen Hinweis auf die Verwendung des Galoisfeldes ${\rm GF}(q)$.
Rechts daneben ist die Binärrepräsentation des gleichen Codes angegeben:
- Bei dieser Realisierung eines RS–Codes wird jedes Informations– und Codesymbol durch $m$ Bit dargestellt.
- Beispielsweise erkennt man aus der ersten Zeile, dass die minimale Distanz hinsichtlich der Bits ebenfalls $d_{\rm min} = 5$ ist, wenn in ${\rm GF}(2^m)$ die minimale Distanz $d_{\rm min} = 5$ beträgt.
- Damit können bis zu $t = 2$ Bitfehler (oder Symbolfehler) korrigiert und bis zu $e = 4$ Bitfehler (oder Symbolfehler) erkannt werden.
Hinweise:
- Die Aufgabe gehört zum Kapitel "Definition und Eigenschaften von Reed–Solomon–Codes".
- Bezug genommen wird aber auch auf das Kapitel "Erweiterungskörper".
Fragebogen
Musterlösung
- $$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm}, \hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm} m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}. $$
(2) Um $t$ Symbolfehler korrigieren zu können, muss die minimale Distanz mindestens $d_{\rm min} = 2t + 1$ betragen.
- Der Reed–Solomon–Code ist ein sogenannter MDS–Code ("Maximum Distance Separable"). Für diese gilt:
- $$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}k = n -2t = 2^m - ( 2t+1) \hspace{0.05cm}. $$
- Damit erhält man für den
- $\rm RSC \ 1$ $($mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
- $\rm RSC \ 2$ $($mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.
(3) Die Bezeichnung eines Reed–Solomon–Codes lautet ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ mit $q = 2^m = n + 1$. Richtig sind die Lösungsvorschläge 1 und 4:
- $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
- $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.
(4) Bezeichnet $d_{\rm min}$ die minimale Distanz eines Blockcodes, so können damit $e = d_{\rm min} - 1$ Symbolfehler erkannt und $t = e/2$ Symbolfehler korrigiert werden:
- ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$,
- ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$.
(5) Richtig sind die beiden mittleren Lösungsvorschläge 2 und 3:
- Beim ${\rm RSC} \ 1 \, \, (m = 4)$ entsprechen $n = 15$ Codesymbole aus $\rm GF(2^5)$ gleich $60$ Bit und $k = 7$ Informationssymbole genau $28$ Bit:
- $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$,
- $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$.
- Für die minimale Distanz auf Bitebene ⇒ $\rm GF(2)$ ergeben sich mit $d_{\rm min} = 9$ bzw. $d_{\rm min} = 17$ die gleichen Werte wie auf Symbolebene
⇒ $\rm GF(2^4)$ bzw. $\rm GF(2^5)$ $($siehe Theorieteil$)$.