Aufgaben:Exercise 2.10: Reed-Solomon Error Detection

• Return to book

Distance spectra of two different Reed-Solomon codes

For a linear block code, up to  $e = d_{\rm min} - 1$  errors can be detected. For all Reed–Solomon codes the minimum distance is

$$d_{\rm min} = n-k+1 \hspace{0.05cm}.$$

One must distinguish the following cases:

• If no more than  $e = n - k$  symbol errors occur, the block is always detected as faulty.
• Error detection can still work even if more than  $n - k$  symbol errors occur, and this is when the received word is not a valid codeword of the Reed–Solomon code:

$$\underline {y} \notin C_{\rm RS} = \{ \underline {c}_{\hspace{0.05cm}0}, \hspace{0.05cm}\text{...} \hspace{0.1cm}, \underline {c}_i, \hspace{0.05cm}\text{...} \hspace{0.1cm}, \underline {c}_{\hspace{0.05cm}n -1} \} \hspace{0.05cm}. $$

• However, if the corrupted received word  $(\underline{y} ≠ \underline{c})$  is a valid codeword   ⇒   $\underline{y}$, the decoding process will leave the corrupted block undetected.

We define as block error probability:

$${\rm Pr}({\rm Block\hspace{0.15cm}error}) = {\rm Pr}(\underline {y} \ne \underline {c}) \hspace{0.05cm}.$$

In this exercise, this probability is to be determined for the following codes:

• Reed–Solomon code  $(7, \, 3, \, 5)_8 \ \Rightarrow \ d_{\rm min} = 5$,
• Reed–Solomon code  $(7, \, 5, \, 3)_8 \ \Rightarrow \ d_{\rm min} = 3$.

Furthermore, let it hold:

• Each symbol is corrupted into another symbol with probability  $\varepsilon_{\rm S} = 0.1$  and correctly transferred with probability  $1 - \varepsilon_{\rm S} = 0.9$  .
• For the distance spectrum of a Reed–Solomon code of length  $n$  holds with  $d = d_{\rm min}$:

$$W_i = {n \choose i} \cdot \sum_{j = 0}^{i-d}\hspace{0.15cm}(-1)^j \cdot {i \choose j} \cdot \big [\hspace{0.03cm}q^{i\hspace{0.03cm}-\hspace{0.03cm}j\hspace{0.03cm}-\hspace{0.03cm}d\hspace{0.03cm}+\hspace{0.03cm}1}-1 \hspace{0.03cm} \big ]\hspace{0.05cm}.$$

Besides, two bounds for the block error probability will be considered and evaluated:

• If the minimum distance alone is known, one can derive an upper bound  from it. The weight enumerating factors  $W_i$  are to be chosen in such a way, that certainly (that is:   with all constellations) applies:

$${\rm Pr}({\rm Upper\hspace{0.15cm} bound}) \ge {\rm Pr}({\rm Block\hspace{0.15cm}error}) \hspace{0.05cm}. $$

• A lower bound  additionally requires knowledge of the weight function  $W_i$  for  $i = d_{\rm min}$. Thus, the following condition can be satisfied:

$${\rm Pr}({\rm Upper\hspace{0.15cm} bound}) \le {\rm Pr}({\rm Block\hspace{0.15cm}error}) \hspace{0.05cm}.$$

Hints:

• The exercise belongs to the chapter  "Definition and Properties of Reed-Solomon Codes".
• Reference is made in particular to the page  "Singleton Bound and Minimum Distance".
• To be calculated are the weights marked in red in the above graph  $W_i$.

Questions

1

Calculate the distance spectrum for the  $\rm RSC \, (7, \, 3, \, 5)_8$.

$W_3 \ = \ $

$W_4 \ = \ $

$W_5 \ = \ $

$W_6 \ = \ $

$W_7 \ = \ $

2

What is the missing weight of the  $\rm RSC \, (7, \, 5, \, 3)_8$ in the graph?

$W_3 \ = \ $

3

What is the probability that an incorrect block remains undetected? Let the corruption probability of each symbol be $\varepsilon = 0.1$.

$\rm RSC \, (7, \, 3, \, 5) \text{:} \hspace{0.4cm} Pr(Blockfehler) \ = \ $ $\ \cdot 10^{-5}$

$\rm RSC \, (7, \, 5, \, 3) \text{:} \hspace{0.4cm} Pr(Blockfehler) \ = \ $ $\ \cdot 10^{-5}$

4

Calculate and evaluate for both codes the upper bound proposed in the specification  $p_{\rm upper} = \rm Pr(Upper \ bound)$.

${\rm RSC} \, (7, \, 3, \, 5) \text{:} \hspace{0.4cm} p_{\rm oben} \ = \ $ $\ \cdot 10^{-5}$

${\rm RSC} \, (7, \, 5, \, 3) \text{:} \hspace{0.4cm} p_{\rm oben} \ = \ $ $\ \cdot 10^{-5}$

5

Calculate and evaluate for both codes the lower bound proposed in the specification  $p_{\rm lower} = \rm Pr(Lower \ bound)$.

${\rm RSC} \, (7, \, 3, \, 5) \text{:} \hspace{0.4cm} p_{\rm unten} \ = \ $ $\ \cdot 10^{-5}$

${\rm RSC} \, (7, \, 5, \, 3) \text{:} \hspace{0.4cm} p_{\rm unten} \ = \ $ $\ \cdot 10^{-5}$

Solution

Solution

(1)  Die Gleichung zur Beschreibung der Gewichte $W_i$ lautet (die minimale Distanz $d_{\rm min}$ ist hier mit $d$ abgekürzt):

$$W_i = {n \choose i} \cdot \sum_{j = 0}^{i-d}\hspace{0.15cm}(-1)^j \cdot {i \choose j} \cdot \big [\hspace{0.03cm}q^{i\hspace{0.03cm}-\hspace{0.03cm}j\hspace{0.03cm}-\hspace{0.03cm}d\hspace{0.03cm}+\hspace{0.03cm}1}-1 \hspace{0.03cm} \big ]\hspace{0.05cm}.$$

Wegen der minimalen Distanz $d_{\min} = 5$ sind $W_3 \ \underline{= 0}$ und $W_4 \ \underline{= 0}$. Die weiteren Gewichte ergeben sich zu

$$W_5 = {7 \choose 5} \cdot (8^1 - 1) = \frac {7 \cdot 6 \cdot 5 \cdot4 \cdot 3}{1 \cdot 2 \cdot 3 \cdot4 \cdot 5} \cdot 7 = 21 \cdot 7 \hspace{0.15cm}\underline {= 147}\hspace{0.05cm},$$

$$W_6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {7 \choose 6} \cdot \sum_{j = 0}^{1}\hspace{0.15cm}(-1)^j \cdot {6 \choose j} \cdot \big (\hspace{0.03cm}8^{2\hspace{0.03cm}-\hspace{0.03cm}j} -1 \big )=7 \cdot \left [ (8^2 - 1) - 6 \cdot (8^1 - 1)\right ] = 7 \cdot (63-42) \hspace{0.15cm}\underline {= 147}\hspace{0.05cm},$$

$$W_7 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {7 \choose 7} \cdot \sum_{j = 0}^{2}\hspace{0.15cm}(-1)^j \cdot {7 \choose j} \cdot \big (\hspace{0.03cm}8^{3\hspace{0.03cm}-\hspace{0.03cm}j} -1 \big )= (8^3 - 1) - 7 \cdot (8^2 - 1) +21 \cdot (8^1 - 1) = 511 - 7 \cdot 63 + 21 \cdot 7 \hspace{0.15cm}\underline {= 217}\hspace{0.05cm},$$

$$\Rightarrow \hspace{0.3cm}W_0 + W_5 + W_6 + W_7 = 1 + 147 + 147 + 217 = 512 = 8^3 = q^k\hspace{0.05cm}.$$

(2)  Analog zur Teilaufgabe (1) erhält man:

$$W_3 = {7 \choose 3} \cdot (8^1 - 1) = \frac {7 \cdot 6 \cdot 5 }{1 \cdot 2 \cdot 3 } \cdot 7 = 35 \cdot 7 \hspace{0.15cm}\underline {= 245}\hspace{0.05cm}.$$

(3)  Die Verfälschungswahrscheinlichkeit eines Symbols ist mit $\varepsilon_{\rm S} = 0.1$ gegeben.

Dann gilt für die Wahrscheinlichkeit, dass in einem Codewort mit $n = 7$ Codesymbolen

• genau 3 Symbole verfälscht werden:

$$p_3 = 0.1^3 \cdot 0.9^4 = 0.6561 \cdot 10^{-3} \hspace{0.05cm},$$

• genau 4 Symbole verfälscht werden:

$$p_4 = 0.1^4 \cdot 0.9^3 = 0.729 \cdot 10^{-4} \hspace{0.05cm},$$

• genau 5 Symbole verfälscht werden:

$$p_5 = 0.1^5 \cdot 0.9^2 = 0.81 \cdot 10^{-5} \hspace{0.05cm},$$

• genau 6 Symbole verfälscht werden:

$$p_6 = 0.1^6 \cdot 0.9 = 0.9 \cdot 10^{-6}\hspace{0.05cm},$$

• alle $n = 7$ Symbole verfälscht werden:

$$p_7 = 0.1^7 = 10^{-7}\hspace{0.05cm}.$$

Beim $\rm RSC \, (7, \, 3, \, 5)_8$ kann das Nullwort durch Symbolfehler in eines von $q^k - 1 = 8^3 - 1 = 511$ anderen Codeworten verfälscht werden.

Damit erhält man mit den Gewichtsfunktionen von Teilaufgabe (1):

$${\rm Pr}({\rm Blockfehler}) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac {W_5 \cdot p_5 + W_6 \cdot p_6 + W_7 \cdot p_7}{511} =\frac {147 \cdot 0.81 \cdot 10^{-5} + 147 \cdot 0.9 \cdot 10^{-6} + 217 \cdot 10^{-7}}{511} \hspace{0.15cm}\underline {\approx 0.263 \cdot 10^{-5}} \hspace{0.05cm}.$$

Beim $\rm RSC \, (7, \, 5, \, 3)_8$ muss wegen $k = 5$ über $8^5 - 1 = 32767$ Verfälschungswahrscheinlichkeiten gemittelt werden.

Mit $W_3 = 245$ aus Teilaufgabe (2) und den Gewichten $W_4 = 1224, \ W_5 = 5586, \ W_6 = 12838, \ W_7 = 12873$ gemäß Angabenblatt erhält man hierfür:

$${\rm Pr}({\rm Blockfehler}) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac {W_3 \cdot p_3 + W_4 \cdot p_4 + W_5 \cdot p_5 + W_6 \cdot p_6 + W_7 \cdot p_7}{32767} =\frac {245 \cdot 0.656 \cdot 10^{-3} + \hspace{0.15cm}... \hspace{0.15cm}+ 12873 \cdot 10^{-7}}{32767} \hspace{0.15cm}\underline {\approx 0.942 \cdot 10^{-5}} \hspace{0.05cm}. $$

(4)  Bekannt sei nur $d_{\rm min}$ (weiter mit $d$ abgekürzt) und damit auch $p_d = \varepsilon_{\rm S}^d \cdot (1 - \varepsilon_{\rm S})^{n-d}$. Dies ist gleichzeitig die gesuchte obere Schranke:

• ${\rm RSC} \, (7, \, 3, \, 5)_8 \text{:} \hspace{0.33cm} {\rm Pr(Obere \ Schranke)} = p_5 = \underline{0.81 \cdot 10^{-5}}$,
• ${\rm RSC} \, (7, \, 5, \, 3)_8 \text{:} \hspace{0.33cm} {\rm Pr(Obere \ Schranke)} = p_3 = \underline{65.6 \cdot 10^{-5}}$.

Da das Gewicht $W_d$ als nicht bekannt vorausgesetzt wurde, setzt man dieses auf den maximal möglichen Wert ($W_5 = 511$ bzw. $W_3 = 32767$), so dass die Vorfaktoren in den Gleichungen zur Teilaufgabe (3) verschwinden. Nur so ist eine obere Schranke sichergestellt.

Die obere Schranke liegt in beiden Fällen deutlich über den Ergebnissen der Teilaufgabe (3):

• $\rm RSC \, (7, \, 3, \, 5)_8 \text{:} \hspace{0.33cm} 0.810 \cdot 10^{-5}$ statt $0.263 \cdot 10^{-5}$ (Faktor ca. $3$),
• $\rm RSC \, (7, \, 5, \, 3)_8 \text{:} \hspace{0.33cm} 65.6 \cdot 10^{-5}$ statt $0.942 \cdot 10^{-5}$ (Faktor ca. $70$).

(5)  Mit der Abkürzung $d = d_{\rm min}$ erhält man für die untere Schranke:

$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke})= \frac{W_d \cdot p_d}{q^k -1} \hspace{0.05cm}. $$

• Für den $\rm RSC \, (7, \, 3, \, 5)_8$ liegt wegen $W_d = W_5$ und $p_d = p_5$ die unter Schranke um etwa $11\%$ unterhalb des tatsächlichen Wertes $(0.263 \cdot 10^{-5})$:

$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke}) = \frac{147 \cdot 0.81 \cdot 10^{-5}}{511} \hspace{0.15cm}\underline {\approx 0.233 \cdot 10^{-5}}$$

• Für den $\rm RSC \, (7, \, 5, \, 3)_8$ gilt mit $W_d = W_3$ und $p_d = p_3$ weicht die untere Schranke hier vom tatsächlichen Wert $(0.942 \cdot 10^{-5})$stärker ab, weil bei diesem Code die Beiträge der höheren Gewichte $(W_4, \ W_5, \ W_6, \ W_7)$ in Relation zu $W_3$ relevanter sind:

$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke}) = \frac{245 \cdot 0.656 \cdot 10^{-3}}{32767} \hspace{0.15cm}\underline {\approx 0.494 \cdot 10^{-5}}\hspace{0.05cm}.$$