Difference between revisions of "Aufgaben:Exercise 2.10Z: Code Rate and Minimum Distance"
From LNTwww
| (2 intermediate revisions by 2 users not shown) | |||
| Line 12: | Line 12: | ||
* $k$ indicates the "dimension" $($symbol number of an information block$)$, | * $k$ indicates the "dimension" $($symbol number of an information block$)$, | ||
| − | * $d_{\rm min}$ denotes the "minimum distance" between two | + | * $d_{\rm min}$ denotes the "minimum distance" between two code words. |
*For any Reed-Solomon code: | *For any Reed-Solomon code: | ||
| Line 33: | Line 33: | ||
===Questions=== | ===Questions=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Specify the characteristics of the ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_q$ | + | {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 57: | Line 57: | ||
===Solution=== | ===Solution=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' From the code length $n = 255$ follows $q \ \underline{= 256}$. | + | '''(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 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 | + | *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 | + | *This allows: |
| − | :* $e = d_{\rm min} - 1 \ \underline{= 32}$ symbol errors can be detected, and | + | :* $e = d_{\rm min} - 1 \ \underline{= 32}$ symbol errors can be detected, and |
| − | :* $t = e/2$ (rounded down) | + | |
| + | :* $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} | + | '''(2)''' The code $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ is the binary representation of the ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_{256}$ discussed in '''(1)''' |
| + | *with exactly the same code rate $R \ \underline{= 0.8745}$ and | ||
| + | *also the same minimum distance $d_{\rm min} \ \underline{= 33}$ as this one. | ||
| − | '''(3)''' From $d_{\rm min} = 33$ follows again $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$. | + | Here $8$ bits (1 byte) are used per code symbol. |
| − | *If exactly one bit is | + | |
| + | |||
| + | |||
| + | '''(3)''' From $d_{\rm min} = 33$ follows again $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$. | ||
| + | *If exactly one bit is falsified in each code symbol, this also means $16$ symbol errors. | ||
| + | |||
*This is the maximum value that the Reed–Solomon decoder can still handle. | *This is the maximum value that the Reed–Solomon decoder can still handle. | ||
| − | '''(4)''' The | + | |
| − | * | + | '''(4)''' The Reed–Solomon decoder can correct $16$ falsified code symbols. |
| − | *Therefore, with the most favorable error distribution, up to $N_4 = 8 \cdot 16 \ \underline{= 128}$ bits can be | + | *It does not matter whether in a code symbol only one bit or all $m = 8$ bits have been falsified. |
| + | |||
| + | *Therefore, with the most favorable error distribution, up to $N_4 = 8 \cdot 16 \ \underline{= 128}$ bits can be falsified without the code word being incorrectly decoded. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Latest revision as of 16:28, 23 January 2023
The 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 code words.
- 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} \, (255, \, 223, \, d_{\rm min})_{256}$ discussed in (1)
- 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 falsified 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 Reed–Solomon decoder can correct $16$ falsified code symbols.
- It does not matter whether in a code symbol only one bit or all $m = 8$ bits have been falsified.
- Therefore, with the most favorable error distribution, up to $N_4 = 8 \cdot 16 \ \underline{= 128}$ bits can be falsified without the code word being incorrectly decoded.
