Difference between revisions of "Aufgaben:Exercise 2.10Z: Code Rate and Minimum Distance"
From LNTwww
m (Textersetzung - „* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „“) |
|||
| Line 2: | Line 2: | ||
[[File:P_ID2526__KC_Z_2_10.png|right|frame|Die beiden Erfinder der Reed–Solomon–Codes]] | [[File: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 | + | 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 Größe des Galoisfeldes ⇒ ${\rm GF}(q)$, |
| − | * $n = q - 1$ ist die Codelänge (Symbolanzahl eines Codewortes), | + | * $n = q - 1$ ist die Codelänge (Symbolanzahl eines Codewortes), |
| − | * $k$ gibt die Dimension an (Symbolanzahl eines Informationsblocks), | + | * $k$ gibt die Dimension an (Symbolanzahl eines Informationsblocks), |
| − | * $d_{\rm min}$ bezeichnet die minimale Distanz zwischen zwei Codeworten. Für | + | * $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. | + | *Mit keinem anderen Code mit gleichem $k$ und $n$ ergibt sich ein größerer Wert. |
| + | |||
| + | |||
| + | |||
| + | |||
| Line 17: | Line 21: | ||
''Hinweise:'' | ''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 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 | + | * 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]]. |
| Line 26: | Line 30: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Geben Sie die Kenngrößen des ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_q$ an. | + | {Geben Sie die Kenngrößen des ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_q$ an. |
|type="{}"} | |type="{}"} | ||
$q \hspace{0.2cm} = \ ${ 256 } | $q \hspace{0.2cm} = \ ${ 256 } | ||
| Line 34: | Line 38: | ||
$d_{\rm min} \ = \ ${ 33 } | $d_{\rm min} \ = \ ${ 33 } | ||
| − | {Geben Sie die Kenngrößen des $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ an. | + | {Geben Sie die Kenngrößen des $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ an. |
|type="{}"} | |type="{}"} | ||
$R \hspace{0.2cm} = \ ${ 0.8745 3% } | $R \hspace{0.2cm} = \ ${ 0.8745 3% } | ||
$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}$ im günstigsten Fall aufweisen, damit es noch <u>richtig decodiert werden könnte</u>? |
|type="{}"} | |type="{}"} | ||
$N_{4} \ = \ $ { 128 } | $N_{4} \ = \ $ { 128 } | ||
Revision as of 16:39, 22 May 2019
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, \, 33)_{256}$ mit genau der gleichen Coderate $R \ \underline{= 0.8745}$ und ebenfalls gleicher Minimaldistanz $d_{\rm min} \ \underline{= 33}$ wie dieser. 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, wobei es egal ist, 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.
