Aufgaben:Aufgabe 2.10Z: Coderate und minimale Distanz: Unterschied zwischen den Versionen
Aus LNTwww
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 2: | Zeile 2: | ||
[[Datei:P_ID2526__KC_Z_2_10.png|right|frame|Die beiden Erfinder der Reed–Solomon–Codes]] | [[Datei:P_ID2526__KC_Z_2_10.png|right|frame|Die beiden Erfinder der Reed–Solomon–Codes]] | ||
| − | Die von [https://de.wikipedia.org/wiki/Irving_Stoy_Reed Irving Stoy Reed] und [https://de.wikipedia.org/wiki/Gustave_Solomon Gustave Solomon] Anfang der 1960er Jahre entwickelten Codes werden in diesem Tutorial wie folgt bezeichnet: | + | Die von »[https://de.wikipedia.org/wiki/Irving_Stoy_Reed Irving Stoy Reed]« und »[https://de.wikipedia.org/wiki/Gustave_Solomon Gustave Solomon]« Anfang der 1960er Jahre entwickelten Codes werden in diesem Tutorial wie folgt bezeichnet: |
:$${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$ | :$${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$ | ||
Die Codeparameter haben folgende Bedeutungen: | Die Codeparameter haben folgende Bedeutungen: | ||
| − | * $q = 2^m$ ist ein Hinweis auf die Größe des Galoisfeldes ⇒ ${\rm GF}(q)$, | + | * $q = 2^m$ ist ein Hinweis auf die <u>Größe des Galoisfeldes</u> ⇒ ${\rm GF}(q)$, |
| − | |||
| − | |||
| − | |||
| − | |||
| + | * $n = q - 1$ ist die <u>Codelänge</u> $($Symbolanzahl eines Codewortes$)$, | ||
| + | |||
| + | * $k$ gibt die <u>Dimension</u> an $($Symbolanzahl eines Informationsblocks$)$, | ||
| + | * $d_{\rm min}$ bezeichnet die <u>minimale Distanz</u> zwischen zwei Codeworten. | ||
| + | *Für jeden Reed–Solomon–Codes gilt | ||
| + | :$$d_{\rm min} = n - k + 1.$$ | ||
| + | '''Mit keinem anderen Code mit gleichem $k$ und $n$ ergibt sich ein größerer Wert'''. | ||
| Zeile 19: | Zeile 22: | ||
| + | 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"]]. | ||
| − | + | * Die für diese Aufgabe relevanten Informationen finden Sie auf der Seite [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Codebezeichnung_und_Coderate|"Codebezeichnung und Coderate"]]. | |
| − | |||
| − | * Die für diese Aufgabe relevanten Informationen finden Sie auf der Seite [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Codebezeichnung_und_Coderate|Codebezeichnung und Coderate]]. | ||
| Zeile 43: | Zeile 46: | ||
$d_{\rm min} \ = \ ${ 33 } | $d_{\rm min} \ = \ ${ 33 } | ||
| − | {Wieviele Bitfehler $(N_3)$ darf ein Empfangswort $\underline{y}$ maximal aufweisen, damit es <u>mit Sicherheit richtig decodiert wird</u>? | + | {Wieviele Bitfehler $(N_3)$ darf ein Empfangswort $\underline{y}$ maximal aufweisen, damit es <u>mit Sicherheit richtig decodiert wird</u>? |
|type="{}"} | |type="{}"} | ||
$N_{3} \ = \ $ { 16 } | $N_{3} \ = \ $ { 16 } | ||
| − | {Wieviele Bitfehler $(N_4)$ darf ein Empfangswort $\underline{y}$ im günstigsten Fall aufweisen, damit es noch <u>richtig decodiert werden könnte</u>? | + | {Wieviele Bitfehler $(N_4)$ darf ein Empfangswort $\underline{y}$ <u>im günstigsten Fall</u> aufweisen, damit es noch <u>richtig decodiert werden könnte</u>? |
|type="{}"} | |type="{}"} | ||
$N_{4} \ = \ $ { 128 } | $N_{4} \ = \ $ { 128 } | ||
| Zeile 54: | Zeile 57: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Aus der Codelänge $n = 255$ folgt $q \ \underline{= 256}$. | + | '''(1)''' Aus der Codelänge $n = 255$ folgt $q \ \underline{= 256}$. |
| − | Die Coderate ergibt sich zu $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$ | + | *Die Coderate ergibt sich zu $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$ |
| − | Die minimale Distanz beträgt $d_{\rm min} = n - k +1 = 255 - 223 +1 | + | *Die minimale Distanz beträgt $d_{\rm min} = n - k +1 = 255 - 223 +1 |
\hspace{0.15cm}\underline {=33}\hspace{0.05cm}.$ | \hspace{0.15cm}\underline {=33}\hspace{0.05cm}.$ | ||
| − | Damit können | + | *Damit können |
| − | * $e = d_{\rm min} - 1 \ \underline{= 32}$ Symbolfehler erkannt werden, und | + | :* $e = d_{\rm min} - 1 \ \underline{= 32}$ Symbolfehler erkannt werden, und |
| − | * $t = e/2$ (abgerundet), also $\underline{t = 16}$ Symbolfehler korrigiert werden. | + | |
| + | :* $t = e/2$ $($abgerundet$)$, also $\underline{t = 16}$ Symbolfehler korrigiert werden. | ||
| − | |||
| + | '''(2)''' Der Code $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ ist die Binärrepräsentation des unter (1) behandelten ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_{256}$ | ||
| + | *Dieser hat genau die gleiche Coderate $R \ \underline{= 0.8745}$ und ebenfalls gleiche Minimaldistanz $d_{\rm min} \ \underline{= 33}$. | ||
| − | + | *Hier werden pro Codesymbol $8$ Bit ⇒ $1$ Byte verwendet. | |
| − | |||
| − | |||
| − | '''(4)''' Der RS–Decoder kann 16 verfälschte Codesymbole korrigieren | + | |
| + | '''(3)''' Aus $d_{\rm min} = 33$ folgt wieder $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$. | ||
| + | *Ist in jedem Codesymbol genau ein Bit verfälscht, so bedeutet dies gleichzeitig auch $16$ Symbolfehler. | ||
| + | |||
| + | *Dies ist der maximale Wert, den der Reed–Solomon–Decoder noch verkraften kann. | ||
| + | |||
| + | |||
| + | |||
| + | '''(4)''' Der RS–Decoder kann $16$ verfälschte Codesymbole korrigieren. | ||
| + | *Dabei ist es egal, ob in einem Codesymbol nur ein Bit oder alle $m = 8$ Bit verfälscht wurden. | ||
| + | *Deshalb können bei der günstigsten Fehlerverteilung bis zu $N_4 = 8 \cdot 16 \ \underline{= 128}$ Bit verfälscht sein, ohne dass das Codewort falsch decodiert wird. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 12. Oktober 2022, 12:08 Uhr
Die beiden Erfinder der Reed–Solomon–Codes
Die von »Irving Stoy Reed« und »Gustave Solomon« Anfang der 1960er Jahre entwickelten Codes werden in diesem Tutorial wie folgt bezeichnet:
- $${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$
Die Codeparameter haben folgende Bedeutungen:
- $q = 2^m$ ist ein Hinweis auf die Größe des Galoisfeldes ⇒ ${\rm GF}(q)$,
- $n = q - 1$ ist die Codelänge $($Symbolanzahl eines Codewortes$)$,
- $k$ gibt die Dimension an $($Symbolanzahl eines Informationsblocks$)$,
- $d_{\rm min}$ bezeichnet die minimale Distanz zwischen zwei Codeworten.
- Für jeden Reed–Solomon–Codes gilt
- $$d_{\rm min} = n - k + 1.$$
Mit keinem anderen Code mit gleichem $k$ und $n$ ergibt sich ein größerer Wert.
Hinweise:
- Die Aufgabe gehört zum Kapitel "Definition und Eigenschaften von Reed–Solomon–Codes".
- Die für diese Aufgabe relevanten Informationen finden Sie auf der Seite "Codebezeichnung und Coderate".
Fragebogen
Musterlösung
(1) Aus der Codelänge $n = 255$ folgt $q \ \underline{= 256}$.
- Die Coderate ergibt sich zu $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$
- Die minimale Distanz beträgt $d_{\rm min} = n - k +1 = 255 - 223 +1 \hspace{0.15cm}\underline {=33}\hspace{0.05cm}.$
- Damit können
- $e = d_{\rm min} - 1 \ \underline{= 32}$ Symbolfehler erkannt werden, und
- $t = e/2$ $($abgerundet$)$, also $\underline{t = 16}$ Symbolfehler korrigiert werden.
(2) Der Code $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ ist die Binärrepräsentation des unter (1) behandelten ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_{256}$
- Dieser hat genau die gleiche Coderate $R \ \underline{= 0.8745}$ und ebenfalls gleiche Minimaldistanz $d_{\rm min} \ \underline{= 33}$.
- Hier werden pro Codesymbol $8$ Bit ⇒ $1$ Byte verwendet.
(3) Aus $d_{\rm min} = 33$ folgt wieder $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$.
- Ist in jedem Codesymbol genau ein Bit verfälscht, so bedeutet dies gleichzeitig auch $16$ Symbolfehler.
- Dies ist der maximale Wert, den der Reed–Solomon–Decoder noch verkraften kann.
(4) Der RS–Decoder kann $16$ verfälschte Codesymbole korrigieren.
- Dabei ist es egal, ob in einem Codesymbol nur ein Bit oder alle $m = 8$ Bit verfälscht wurden.
- Deshalb können bei der günstigsten Fehlerverteilung bis zu $N_4 = 8 \cdot 16 \ \underline{= 128}$ Bit verfälscht sein, ohne dass das Codewort falsch decodiert wird.
