Difference between revisions of "Aufgaben:Exercise 2.09: Reed–Solomon Parameters"
(16 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Definition_and_Properties_of_Reed-Solomon_Codes}} |
− | [[File:P_ID2523__KC_A_2_9_neu.png|right|frame| | + | [[File:P_ID2523__KC_A_2_9_neu.png|right|frame|Some Reed-Solomon codes]] |
− | + | Adjacent is an incomplete list of possible Reed–Solomon codes known to be based on a Galois field ${\rm GF}(q) = {\rm GF}(2^m)$. | |
− | |||
− | |||
− | |||
+ | The parameter $m$ specifies with how many bits a Reed–Solomon code symbol is represented. It is valid: | ||
+ | * $m = 4$ (red font), | ||
− | + | * $m = 5$ (blue font), | |
− | |||
+ | * $m = 6$ (green font). | ||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | A Reed–Solomon code is generally denoted as follows: ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$. | ||
− | + | The parameters have the following meaning: | |
+ | # The parameter $n$ specifies the number of symbols of a code word $\underline{c}$ ⇒ <b>length</b> of the code. | ||
+ | # Tthe parameter $k$ specifies the number of symbols of an information block $\underline{u}$ ⇒ <b>dimension</b> of the code. | ||
+ | # The parameter $d_{\rm min}$ denotes the <b> minimum distance </b> between two code words <br>$($for all Reed–Solomon codes equal $n-k+1)$. | ||
+ | # The parameter $q$ gives an indication of the use of the Galois field ${\rm GF}(q)$. | ||
− | |||
− | |||
− | |||
+ | To the right, there is the binary representation of the same code: | ||
+ | # In this realization of a Reed–Solomon code, each information and code symbol is represented by $m$ bits. | ||
+ | # For example, it can be seen from the first row that the minimum distance in terms of bits is also $d_{\rm min} = 5$ if in ${\rm GF}(2^m)$ the minimum distance is $d_{\rm min} = 5$. | ||
+ | # This code can correct up to $t = 2$ bit errors $($or symbol errors$)$ and detect up to $e = 4$ bit errors $($or symbol errors$)$. | ||
− | === | + | |
+ | |||
+ | |||
+ | Hints: | ||
+ | * This exercise belongs to the chapter [[Channel_Coding/Definition_and_Properties_of_Reed-Solomon_Codes| "Definition and Properties of Reed-Solomon Codes"]]. | ||
+ | |||
+ | * However, reference is also made to the chapter [[Channel_Coding/Extension_Field| "Extension Field"]]. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===Questions=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {It holds $c_i ∈ {\rm GF}(2^m)$. Which Reed-Solomon code parameters $n$ result? |
|type="{}"} | |type="{}"} | ||
− | $m = 4 \text{:} \hspace{0. | + | $m = 4 \text{:} \hspace{0.4cm} n \ = \ ${ 15 } |
− | $m = 5 \text{:} \hspace{0. | + | $m = 5 \text{:} \hspace{0.4cm} n \ = \ ${ 31 } |
− | $m = 6 \text{:} \hspace{0. | + | $m = 6 \text{:} \hspace{0.4cm} n \ = \ ${ 63 } |
− | { | + | {Two specific Reed-Solomon codes ${\rm RSC} \ 1 \ (m = 4, \ t = 4)$ and ${\rm RSC} \ 2 \ (m = 5, \ t = 8)$ are considered below. <br>Which parameter $k$ can be used to correct exactly $t$ symbol errors? |
|type="{}"} | |type="{}"} | ||
− | ${\rm RSC} \ 1 | + | ${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ ${ 7 } |
− | ${\rm RSC} \ | + | ${\rm RSC} \ 2 \text{:} \hspace{0.4cm} k \ = \ ${ 15 } |
− | { | + | {Which designations are correct for $\rm RSC \ 1$ resp. $\rm RSC \ 2$? |
|type="[]"} | |type="[]"} | ||
− | + $\rm RSC \ 1$ | + | + $\rm RSC \ 1$ is also called $\rm RSC \, (15, \, 7, \, 9)_{16}$. |
− | - $\rm RSC \ 1$ | + | - $\rm RSC \ 1$ is also called $\rm RSC \, (15, \, 7, \, 4)_4$. |
− | - $\rm RSC \ 2$ | + | - $\rm RSC \ 2$ is also called $\rm RSC \, (31, \, 17, \, 15)_{32}$. |
− | + $\rm RSC \ 2$ | + | + $\rm RSC \ 2$ is also called $\rm RSC \, (31, \, 15, \, 17)_{32}$. |
− | { | + | {How many symbol errors $(e)$ can be detected at most? |
|type="{}"} | |type="{}"} | ||
− | ${\rm | + | ${\rm RSC} \ 1 \text{:} \hspace{0.4cm} e \ = \ ${ 8 } |
− | ${\rm | + | ${\rm RSC} \ 2 \text{:} \hspace{0.4cm}e \ = \ ${ 16 } |
− | { | + | {What are the codes under consideration in binary notation? |
|type="[]"} | |type="[]"} | ||
− | - $\rm RSC \ 1$ | + | - $\rm RSC \ 1$ corresponds to the code $\rm RSC \, (60, \, 28, \, 36)_2$. |
− | + $\rm RSC \ 1$ | + | + $\rm RSC \ 1$ corresponds to the code $\rm RSC \, (60, \, 28, \, 9)_2$. |
− | + $\rm RSC \ 2$ | + | + $\rm RSC \ 2$ corresponds to the code $\rm RSC \, (155, \, 75, \, 17)_2$. |
− | - $\rm RSC \ 2$ | + | - $\rm RSC \ 2$ corresponds to the code $\rm RSC \, (124, \, 60, \, 17)_2$. |
</quiz> | </quiz> | ||
− | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' For the code length of Reed–Solomon codes, the following applies in general: |
− | :$$n = q -1 = 2^m -1 | + | :$$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)''' | + | '''(2)''' To be able to correct $t$ symbol errors, the minimum distance must be $d_{\rm min} = 2t + 1$. |
+ | *The Reed–Solomon code is a so-called "Maximum Distance Separable $\rm (MDS)$ code". | ||
+ | |||
+ | *For this applies: | ||
:$$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}. $$ | ||
− | + | *This gives for the | |
− | * $\rm RSC \ 1$ ( | + | ** $\rm RSC \ 1$ $($with $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$, |
− | * $\rm RSC \ 2$ ( | + | ** $\rm RSC \ 2$ $($with $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$. |
− | |||
− | |||
− | |||
+ | '''(3)''' The denotation of a Reed–Solomon code is ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ with $q = 2^m = n + 1$. | ||
− | '''(4)''' | + | *Correct are the <u>solutions 1 and 4</u>: |
+ | ** $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$, | ||
+ | ** $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$. | ||
+ | |||
+ | |||
+ | |||
+ | '''(4)''' If $d_{\rm min}$ denotes the minimum distance of a block code, it can be used to detect $e = d_{\rm min} - 1$ symbol errors and to correct $t = e/2$ symbol errors: | ||
* ${\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)''' Correct are the two middle <u>solutions 2 and 3</u>: | |
+ | *For ${\rm RSC} \ 1 \, (m = 4)$: $n = 15$ code symbols from $\rm GF(2^5)$ correspond to $60$ bits and $k = 7$ information symbols are exactly $28$ bits: | ||
+ | ** $\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$. | ||
+ | *For the minimum distance on bit level ⇒ $\rm GF(2)$, $d_{\rm min} = 9$ resp. $d_{\rm min} = 17$ result in the same values as on symbol level $($see [[Channel_Coding/Definition_and_Properties_of_Reed-Solomon_Codes#Code_name_and_code_rate|"theory section"]]$)$. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
− | [[Category: | + | [[Category:Channel Coding: Exercises|^2.3 Reed–Solomon Codes^]] |
Latest revision as of 16:40, 10 October 2022
Adjacent is an incomplete list of possible Reed–Solomon codes known to be based on a Galois field ${\rm GF}(q) = {\rm GF}(2^m)$.
The parameter $m$ specifies with how many bits a Reed–Solomon code symbol is represented. It is valid:
- $m = 4$ (red font),
- $m = 5$ (blue font),
- $m = 6$ (green font).
A Reed–Solomon code is generally denoted as follows: ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$.
The parameters have the following meaning:
- The parameter $n$ specifies the number of symbols of a code word $\underline{c}$ ⇒ length of the code.
- Tthe parameter $k$ specifies the number of symbols of an information block $\underline{u}$ ⇒ dimension of the code.
- The parameter $d_{\rm min}$ denotes the minimum distance between two code words
$($for all Reed–Solomon codes equal $n-k+1)$. - The parameter $q$ gives an indication of the use of the Galois field ${\rm GF}(q)$.
To the right, there is the binary representation of the same code:
- In this realization of a Reed–Solomon code, each information and code symbol is represented by $m$ bits.
- For example, it can be seen from the first row that the minimum distance in terms of bits is also $d_{\rm min} = 5$ if in ${\rm GF}(2^m)$ the minimum distance is $d_{\rm min} = 5$.
- This code can correct up to $t = 2$ bit errors $($or symbol errors$)$ and detect up to $e = 4$ bit errors $($or symbol errors$)$.
Hints:
- This exercise belongs to the chapter "Definition and Properties of Reed-Solomon Codes".
- However, reference is also made to the chapter "Extension Field".
Questions
Solution
- $$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) To be able to correct $t$ symbol errors, the minimum distance must be $d_{\rm min} = 2t + 1$.
- The Reed–Solomon code is a so-called "Maximum Distance Separable $\rm (MDS)$ code".
- For this applies:
- $$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}. $$
- This gives for the
- $\rm RSC \ 1$ $($with $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
- $\rm RSC \ 2$ $($with $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.
(3) The denotation of a Reed–Solomon code is ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ with $q = 2^m = n + 1$.
- Correct are the solutions 1 and 4:
- $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
- $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.
(4) If $d_{\rm min}$ denotes the minimum distance of a block code, it can be used to detect $e = d_{\rm min} - 1$ symbol errors and to correct $t = e/2$ symbol errors:
- ${\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) Correct are the two middle solutions 2 and 3:
- For ${\rm RSC} \ 1 \, (m = 4)$: $n = 15$ code symbols from $\rm GF(2^5)$ correspond to $60$ bits and $k = 7$ information symbols are exactly $28$ bits:
- $\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$.
- For the minimum distance on bit level ⇒ $\rm GF(2)$, $d_{\rm min} = 9$ resp. $d_{\rm min} = 17$ result in the same values as on symbol level $($see "theory section"$)$.