Exercise 2.09: Reed–Solomon Parameters
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 RS 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:
- $n$ specifies the number of symbols of a codeword $\underline{c}$ ⇒ length of the code,
- $k$ specifies the number of symbols of an information block $\underline{u}$ ⇒ dimension of the code,
- $d_{\rm min}$ denotes the minimum distance between two codewords
$($for all Reed–Solomon codes equal $n-k+1)$, - $q$ gives an indication of the use of the Galois field ${\rm GF}(q)$.
To the right is the binary representation of the same code:
- In this realization of a RS 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 can correct up to $t = 2$ bit errors (or symbol errors) and detect up to $e = 4$ bit errors (or symbol errors).
Hints:
- Die Aufgabe gehört zum Kapitel Definition und Eigenschaften von Reed–Solomon–Codes.
- Bezug genommen wird aber auch auf das Kapitel Erweiterungskörper.
Fragebogen
Musterlösung
- $$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) Um $t$ Symbolfehler korrigieren zu können, muss die minimale Distanz $d_{\rm min} = 2t + 1$ betragen.
- Der Reed–Solomon–Code ist ein sogenannter MDS–Code (Maximum Distance Separable).
- Für diese gilt:
- $$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}. $$
- Damit erhält man für den
- $\rm RSC \ 1$ (mit $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
- $\rm RSC \ 2$ (mit $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.
(3) Die Bezeichnung eines Reed–Solomon–Codes lautet ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$ mit $q = 2^m = n + 1$.
Richtig sind die Lösungsvorschläge 1 und 4:
- $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
- $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.
(4) Bezeichnet $d_{\rm min}$ die minimale Distanz eines Blockcodes, so können damit $e = d_{\rm min} - 1$ Symbolfehler erkannt und $t = e/2$ Symbolfehler korrigiert werden:
- ${\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) Richtig sind die beiden mittleren Lösungsvorschläge 2 und 3:
- Bei ${\rm RSC} \ 1 \, (m = 4)$ entsprechen $n = 15$ Codesymbolen aus $\rm GF(2^5)$ gleich $60$ Bit und $k = 7$ Informationssymbole genau $28$ Bit:
- $\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$.
- Für die minimale Distanz auf Bitebene ⇒ $\rm GF(2)$ ergeben sich mit $d_{\rm min} = 9$ bzw. $d_{\rm min} = 17$ die gleichen Werte wie auf Symbolebene
⇒ $\rm GF(2^4)$ bzw. $\rm GF(2^5)$ (siehe Theorieteil).
