Difference between revisions of "Aufgaben:Exercise 2.10Z: Code Rate and Minimum Distance"
From LNTwww
| Line 1: | Line 1: | ||
| − | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Definition_and_Properties_of_Reed-Solomon_Codes}} |
| − | [[File:P_ID2526__KC_Z_2_10.png|right|frame| | + | [[File:P_ID2526__KC_Z_2_10.png|right|frame|The two inventors of the Reed-Solomon codes]] |
| − | + | The codes developed by [https://en.wikipedia.org/wiki/Irving_S._Reed "Irving Stoy Reed"] and [https://en.wikipedia.org/wiki/Gustave_Solomon "Gustave Solomon"] in the early 1960s are referred to in this tutorial as follows: | |
:$${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$ | :$${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$ | ||
| − | + | The code parameters have the following meanings: | |
| − | * $q = 2^m$ | + | * $q = 2^m$ is an indication of the size of the Galois field ⇒ ${\rm GF}(q)$, |
| − | * $n = q - 1$ | + | * $n = q - 1$ is the code length (symbol number of a code word), |
| − | * $k$ | + | * $k$ indicates the dimension (symbol number of an information block), |
| − | * $d_{\rm min}$ | + | * $d_{\rm min}$ denotes the minimum distance between two codewords. For any Reed-Solomon code, $d_{\rm min} = n - k + 1$. |
| − | * | + | *No other code with the same $k$ and $n$ yields a larger value. |
| Line 19: | Line 19: | ||
| + | Hints: | ||
| + | * The exercise belongs to the chapter [[Channel_Coding/Definition_and_Properties_of_Reed-Solomon_Codes| "Definition and properties of Reed–Solomon Codes"]]. | ||
| + | * Information relevant to this exercise can be found on the [[Channel_Coding/Definition_and_Properties_of_Reed-Solomon_Codes#Code_name_and_code_rate|Code name and code rate]] page. | ||
| − | |||
| − | |||
| − | |||
| − | + | ===Questions=== | |
| − | === | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | {Specify the characteristics of the ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_q$ . |
|type="{}"} | |type="{}"} | ||
$q \hspace{0.2cm} = \ ${ 256 } | $q \hspace{0.2cm} = \ ${ 256 } | ||
| Line 38: | Line 37: | ||
$d_{\rm min} \ = \ ${ 33 } | $d_{\rm min} \ = \ ${ 33 } | ||
| − | { | + | {Specify the characteristics of the $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ . |
|type="{}"} | |type="{}"} | ||
$R \hspace{0.2cm} = \ ${ 0.8745 3% } | $R \hspace{0.2cm} = \ ${ 0.8745 3% } | ||
$d_{\rm min} \ = \ ${ 33 } | $d_{\rm min} \ = \ ${ 33 } | ||
| − | { | + | {How many bit errors $(N_3)$ may a received word $\underline{y}$ have at most, so that it is <u>certainly decoded correctly</u>? |
|type="{}"} | |type="{}"} | ||
$N_{3} \ = \ $ { 16 } | $N_{3} \ = \ $ { 16 } | ||
| − | { | + | {How many bit errors $(N_4)$ may a received word $\underline{y}$ have in the best case so that it could still be <u>correctly decoded</u>? |
|type="{}"} | |type="{}"} | ||
$N_{4} \ = \ $ { 128 } | $N_{4} \ = \ $ { 128 } | ||
</quiz> | </quiz> | ||
| − | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' | + | '''(1)''' From the code length $n = 255$ follows $q \ \underline{= 256}$. |
| − | * | + | *The code rate is given by $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$ |
| − | * | + | *The minimum distance is $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}.$ | ||
| − | * | + | *This allows |
| − | :* $e = d_{\rm min} - 1 \ \underline{= 32}$ | + | :* $e = d_{\rm min} - 1 \ \underline{= 32}$ symbol errors can be detected, and. |
| − | :* $t = e/2$ ( | + | :* $t = e/2$ (rounded down), so $\underline{t = 16}$ symbol errors can be corrected. |
| − | |||
| − | |||
| + | '''(2)''' The code $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ is the binary representation of the ${\rm RSC} discussed in (1) \, (255, \, 223, \, 33)_{256}$ with exactly the same code rate $R \ \underline{= 0.8745}$ and also the same minimum distance $d_{\rm min} \ \underline{= 33}$ as this one. Here $8$ bits (1 byte) are used per code symbol. | ||
| − | |||
| − | |||
| − | |||
| + | '''(3)''' From $d_{\rm min} = 33$ follows again $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$. | ||
| + | *If exactly one bit is corrupted in each code symbol, this also means 16 symbol errors. | ||
| + | *This is the maximum value that the Reed–Solomon decoder can still handle. | ||
| − | '''(4)''' | + | '''(4)''' The RS decoder can correct 16 corrupted code symbols, |
| − | * | + | *whereby it does not matter whether in a code symbol only one bit or all $m = 8$ bits have been corrupted. |
| − | * | + | *Therefore, with the most favorable error distribution, up to $N_4 = 8 \cdot 16 \ \underline{= 128}$ bits can be corrupted without the code word being incorrectly decoded. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Revision as of 19:19, 2 September 2022
The two inventors of the Reed-Solomon codes
The codes developed by "Irving Stoy Reed" and "Gustave Solomon" in the early 1960s are referred to in this tutorial as follows:
- $${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$
The code parameters have the following meanings:
- $q = 2^m$ is an indication of the size of the Galois field ⇒ ${\rm GF}(q)$,
- $n = q - 1$ is the code length (symbol number of a code word),
- $k$ indicates the dimension (symbol number of an information block),
- $d_{\rm min}$ denotes the minimum distance between two codewords. For any Reed-Solomon code, $d_{\rm min} = n - k + 1$.
- No other code with the same $k$ and $n$ yields a larger value.
Hints:
- The exercise belongs to the chapter "Definition and properties of Reed–Solomon Codes".
- Information relevant to this exercise can be found on the Code name and code rate page.
Questions
Solution
(1) From the code length $n = 255$ follows $q \ \underline{= 256}$.
- The code rate is given by $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$
- The minimum distance is $d_{\rm min} = n - k +1 = 255 - 223 +1 \hspace{0.15cm}\underline {=33}\hspace{0.05cm}.$
- This allows
- $e = d_{\rm min} - 1 \ \underline{= 32}$ symbol errors can be detected, and.
- $t = e/2$ (rounded down), so $\underline{t = 16}$ symbol errors can be corrected.
(2) The code $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ is the binary representation of the ${\rm RSC} discussed in (1) \, (255, \, 223, \, 33)_{256}$ with exactly the same code rate $R \ \underline{= 0.8745}$ and also the same minimum distance $d_{\rm min} \ \underline{= 33}$ as this one. Here $8$ bits (1 byte) are used per code symbol.
(3) From $d_{\rm min} = 33$ follows again $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$.
- If exactly one bit is corrupted in each code symbol, this also means 16 symbol errors.
- This is the maximum value that the Reed–Solomon decoder can still handle.
(4) The RS decoder can correct 16 corrupted code symbols,
- whereby it does not matter whether in a code symbol only one bit or all $m = 8$ bits have been corrupted.
- Therefore, with the most favorable error distribution, up to $N_4 = 8 \cdot 16 \ \underline{= 128}$ bits can be corrupted without the code word being incorrectly decoded.
