Aufgaben:Aufgabe 2.10: Fehlererkennung bei Reed–Solomon: Unterschied zwischen den Versionen
Aus LNTwww
K (Guenter verschob die Seite 2.10 Fehlererkennung bei RSC nach Aufgabe 2.10: Fehlererkennung bei RSC) |
|||
| (9 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes}} | {{quiz-Header|Buchseite=Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes}} | ||
| − | [[Datei: P_ID2524__KC_A_2_10.png|right|frame|Distanzspektren zweier Reed–Solomon–Codes]] | + | [[Datei: P_ID2524__KC_A_2_10.png|right|frame|Distanzspektren zweier verschiedener Reed–Solomon–Codes]] |
| − | Bei einem linearen Blockcode können bis zu $e = d_{\rm min} - 1$ Fehler erkannt werden. Bei allen Reed–Solomon–Codes beträgt dabei die minimale Distanz | + | Bei einem linearen Blockcode können bis zu $e = d_{\rm min} - 1$ Fehler erkannt werden. Bei allen Reed–Solomon–Codes beträgt dabei die minimale Distanz |
:$$d_{\rm min} = n-k+1 \hspace{0.05cm}.$$ | :$$d_{\rm min} = n-k+1 \hspace{0.05cm}.$$ | ||
Man muss folgende Fälle unterscheiden: | Man muss folgende Fälle unterscheiden: | ||
| − | * Treten nicht mehr als $e = n - k$ Symbolfehler auf, so wird der Block als fehlerhaft erkannt. | + | * Treten nicht mehr als $e = d_{\rm min} - 1= n - k$ Symbolfehler auf, so wird der Block stets als fehlerhaft erkannt. |
| − | * Die Fehlererkennung kann auch bei mehr als $n - k$ Symbolfehlern noch funktionieren, und zwar dann, wenn das Empfangswort kein gültiges Codewort des Reed–Solomon–Codes ist: | + | |
| − | :$$\underline {y} \notin C_{\rm RS} = \{ \underline {c}_{\hspace{0.05cm}0}, \hspace{0.05cm}... \hspace{0. | + | * Die Fehlererkennung kann auch bei mehr als $n - k$ Symbolfehlern noch funktionieren, und zwar dann, wenn das Empfangswort kein gültiges Codewort des Reed–Solomon–Codes ist: |
| + | :$$\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}. $$ | \hspace{0.05cm}. $$ | ||
| − | * Ist aber das verfälschte Empfangswort $(\underline{y} | + | * Ist aber das verfälschte Empfangswort $(\underline{y} \ne \underline{c})$ ein gültiges Codewort $(\underline{y\in C_{\rm RS}})$, so bleibt bei der Decodierung der fehlerhafte Block unentdeckt. |
| + | |||
| + | |||
| + | Wir definieren als '''Blockfehlerwahrscheinlichkeit''': | ||
:$${\rm Pr}({\rm Blockfehler}) = {\rm Pr}(\underline {y} \ne \underline {c}) | :$${\rm Pr}({\rm Blockfehler}) = {\rm Pr}(\underline {y} \ne \underline {c}) | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
In dieser Aufgabe soll diese Wahrscheinlichkeit für folgende Codes ermittelt werden: | In dieser Aufgabe soll diese Wahrscheinlichkeit für folgende Codes ermittelt werden: | ||
| − | * Reed–Solomon–Code $(7, \, 3, \, 5)_8 \ \Rightarrow \ d_{\rm min} = 5$, | + | * Reed–Solomon–Code $(7, \, 3, \, 5)_8 \ \Rightarrow \ d_{\rm min} = 5$, |
| − | * Reed–Solomon–Code $(7, \, 5, \, 3)_8 \ \Rightarrow \ d_{\rm min} = 3$. | + | |
| + | * Reed–Solomon–Code $(7, \, 5, \, 3)_8 \ \Rightarrow \ d_{\rm min} = 3$. | ||
Weiterhin soll gelten: | Weiterhin soll gelten: | ||
| − | * Jedes Symbol wird mit der Wahrscheinlichkeit $\ | + | * Jedes Symbol wird mit der Wahrscheinlichkeit $\varepsilon_{\rm S} = 0.1$ in ein anderes Symbol verfälscht und mit der Wahrscheinlichkeit $1 - \varepsilon_{\rm S} = 0.9$ richtig übertragen. |
| − | * Für das Distanzspektrum eines Reed–Solomon–Codes der Länge $n$ gilt mit $d = d_{\rm min}$: | + | |
| + | * Für das Distanzspektrum eines Reed–Solomon–Codes der Länge $n$ gilt mit $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}.$$ | :$$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}.$$ | ||
Daneben sollen zwei Schranken für die Blockfehlerwahrscheinlichkeit betrachtet und bewertet werden: | Daneben sollen zwei Schranken für die Blockfehlerwahrscheinlichkeit betrachtet und bewertet werden: | ||
| − | * Ist allein die minimale Distanz bekannt, so kann man daraus eine < | + | * Ist allein die minimale Distanz bekannt, so kann man daraus eine <u>obere Schranke</u> ableiten. Die Gewichtsfaktoren $W_i$ sind dabei so zu wählen, dass sicher (das heißt: bei allen Konstellationen) gilt: |
:$${\rm Pr}({\rm Obere\hspace{0.15cm} Schranke}) \ge {\rm Pr}({\rm Blockfehler}) | :$${\rm Pr}({\rm Obere\hspace{0.15cm} Schranke}) \ge {\rm Pr}({\rm Blockfehler}) | ||
\hspace{0.05cm}. $$ | \hspace{0.05cm}. $$ | ||
| − | * Eine < | + | * Eine <u>untere Schranke</u> erfordert zusätzlich die Kenntnis der Gewichtsfunktion $W_i$ für $i = d_{\rm min}$. Damit kann folgende Bedingung erfüllt werden: |
:$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke}) \le {\rm Pr}({\rm Blockfehler}) | :$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke}) \le {\rm Pr}({\rm Blockfehler}) | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | + | ||
| − | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes|Definition und Eigenschaften von Reed–Solomon–Codes]]. | + | |
| − | * Zu berechnen sind die in der obigen Grafik rot markierten Gewichte $W_i$. | + | |
| − | + | ||
| + | Hinweise: | ||
| + | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes|"Definition und Eigenschaften von Reed–Solomon–Codes"]]. | ||
| + | |||
| + | *Bezug genommen wird insbesondere auf die Seite [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed–Solomon–Codes#Singleton.E2.80.93Schranke_und_minimale_Distanz|"Singleton–Schranke und minimale Distanz"]]. | ||
| + | |||
| + | * Zu berechnen sind die in der obigen Grafik rot markierten Gewichte $W_i$. | ||
| + | |||
| Zeile 42: | Zeile 55: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Berechnen Sie das Distanzspektrum für den $\rm RSC \, (7, \, 3, \, 5)_8$. | + | {Berechnen Sie das Distanzspektrum für den $\rm RSC \, (7, \, 3, \, 5)_8$. |
|type="{}"} | |type="{}"} | ||
| − | $ | + | $W_3 \ = \ ${ 0. } |
| − | $ | + | $W_4 \ = \ ${ 0. } |
| − | $ | + | $W_5 \ = \ ${ 147 } |
| − | $ | + | $W_6 \ = \ ${ 147 } |
| − | $ | + | $W_7 \ = \ ${ 217 } |
| − | {Wie lautet das in der Grafik fehlende Gewicht des $\rm RSC \, (7, \, 5, \, 3)_8$? | + | {Wie lautet das in der Grafik fehlende Gewicht des $\rm RSC \, (7, \, 5, \, 3)_8$? |
|type="{}"} | |type="{}"} | ||
| − | $ | + | $W_3 \ = \ ${ 245 } |
| − | {Mit welcher Wahrscheinlichkeit bleibt ein fehlerhafter Block unerkannt? Die Verfälschungswahrscheinlichkeit eines Symbols sei $\ | + | {Mit welcher Wahrscheinlichkeit bleibt ein fehlerhafter Block unerkannt? Die Verfälschungswahrscheinlichkeit eines jeden Symbols sei $\varepsilon = 0.1$. |
|type="{}"} | |type="{}"} | ||
| − | $\rm RSC \, (7, \, 3, \, 5) \text{:} \hspace{0. | + | $\rm RSC \, (7, \, 3, \, 5) \text{:} \hspace{0.4cm} Pr(Blockfehler) \ = \ ${ 0.263 3% } $\ \cdot 10^{-5}$ |
| − | $\rm RSC \, (7, \, 5, \, 3) \text{:} \hspace{0. | + | $\rm RSC \, (7, \, 5, \, 3) \text{:} \hspace{0.4cm} Pr(Blockfehler) \ = \ ${ 0.942 3% } $\ \cdot 10^{-5}$ |
| − | {Berechnen und bewerten Sie für beide Codes die in der Angabe vorgeschlagene obere Schranke $p_{\rm oben} = \rm Pr(Obere \ Schranke)$. | + | {Berechnen und bewerten Sie für beide Codes die in der Angabe vorgeschlagene obere Schranke $p_{\rm oben} = \rm Pr(Obere \ Schranke)$. |
|type="{}"} | |type="{}"} | ||
| − | ${\rm RSC} \, (7, \, 3, \, 5) \text{:} \hspace{0. | + | ${\rm RSC} \, (7, \, 3, \, 5) \text{:} \hspace{0.4cm} p_{\rm oben} \ = \ ${ 0.81 3% } $\ \cdot 10^{-5}$ |
| − | ${\rm RSC} \, (7, \, 5, \, 3) \text{:} \hspace{0. | + | ${\rm RSC} \, (7, \, 5, \, 3) \text{:} \hspace{0.4cm} p_{\rm oben} \ = \ ${ 65.6 3% } $\ \cdot 10^{-5}$ |
| − | {Berechnen und bewerten Sie für beide Codes die in der Angabe vorgeschlagene untere Schranke $p_{\rm unten} = \rm Pr(Untere \ Schranke)$. | + | {Berechnen und bewerten Sie für beide Codes die in der Angabe vorgeschlagene untere Schranke $p_{\rm unten} = \rm Pr(Untere \ Schranke)$. |
|type="{}"} | |type="{}"} | ||
| − | ${\rm RSC} \, (7, \, 3, \, 5) \text{:} \hspace{0. | + | ${\rm RSC} \, (7, \, 3, \, 5) \text{:} \hspace{0.4cm} p_{\rm unten} \ = \ ${ 0.233 3% } $\ \cdot 10^{-5}$ |
| − | ${\rm RSC} \, (7, \, 5, \, 3) \text{:} \hspace{0. | + | ${\rm RSC} \, (7, \, 5, \, 3) \text{:} \hspace{0.4cm} p_{\rm unten} \ = \ ${ 0.494 3% } $\ \cdot 10^{-5}$ |
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Die Gleichung zur Beschreibung der Gewichte $W_i$ lautet ($d_{\rm min}$ ist hier mit $d$ abgekürzt): | + | '''(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}.$$ | :$$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 | + | *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 | :$$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},$$ | \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 )= | + | :$$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},$$ | \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 )= | + | :$$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},$$ | \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}.$$ | :$$\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: | + | '''(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 | :$$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}.$$ | \hspace{0.15cm}\underline {= 245}\hspace{0.05cm}.$$ | ||
| − | '''(3)''' Die Verfälschungswahrscheinlichkeit eines | + | '''(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 | + | * genau drei Symbole verfälscht werden: |
:$$p_3 = 0.1^3 \cdot 0.9^4 = 0.6561 \cdot 10^{-3} | :$$p_3 = 0.1^3 \cdot 0.9^4 = 0.6561 \cdot 10^{-3} | ||
\hspace{0.05cm},$$ | \hspace{0.05cm},$$ | ||
| − | * genau | + | * genau vier Symbole verfälscht werden: |
:$$p_4 = 0.1^4 \cdot 0.9^3 = 0.729 \cdot 10^{-4} | :$$p_4 = 0.1^4 \cdot 0.9^3 = 0.729 \cdot 10^{-4} | ||
\hspace{0.05cm},$$ | \hspace{0.05cm},$$ | ||
| − | * genau | + | * genau fünf Symbole verfälscht werden: |
:$$p_5 = 0.1^5 \cdot 0.9^2 = 0.81 \cdot 10^{-5} | :$$p_5 = 0.1^5 \cdot 0.9^2 = 0.81 \cdot 10^{-5} | ||
\hspace{0.05cm},$$ | \hspace{0.05cm},$$ | ||
| − | * genau | + | * genau sechs Symbole verfälscht werden: |
:$$p_6 = 0.1^6 \cdot 0.9 = 0.9 \cdot 10^{-6}\hspace{0.05cm},$$ | :$$p_6 = 0.1^6 \cdot 0.9 = 0.9 \cdot 10^{-6}\hspace{0.05cm},$$ | ||
* alle $n = 7$ Symbole verfälscht werden: | * alle $n = 7$ Symbole verfälscht werden: | ||
:$$p_7 = 0.1^7 = 10^{-7}\hspace{0.05cm}.$$ | :$$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): | + | ⇒ 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} = | + | :$${\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}.$$ | \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$ | + | ⇒ 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 |
| − | :$${\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} = | + | :$$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}. $$ | \hspace{0.15cm}\underline {\approx 0.942 \cdot 10^{-5}} \hspace{0.05cm}. $$ | ||
| − | '''(4)''' Bekannt sei nur $d_{\rm min}$ ( | + | '''(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, \, 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{ | + | |
| + | :* ${\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: | + | '''(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} | :$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke})= \frac{W_d \cdot p_d}{q^k -1} | ||
\hspace{0.05cm}. $$ | \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 | + | * 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} | :$${\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}}$$ | \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: | |
| − | * Für den $\rm RSC \, (7, \, 5, \, 3)_8$ gilt mit $W_d = W_3$ und $p_d = p_3$: | ||
:$${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke}) = \frac{245 \cdot 0.656 \cdot 10^{-3}}{32767} | :$${\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}.$$ | \hspace{0.15cm}\underline {\approx 0.494 \cdot 10^{-5}}\hspace{0.05cm}.$$ | ||
| − | |||
{{ML-Fuß}} | {{ML-Fuß}} | ||
| − | [[Category:Aufgaben zu Kanalcodierung|^2.3 | + | [[Category:Aufgaben zu Kanalcodierung|^2.3 Zu den Reed–Solomon–Codes^]] |
Aktuelle Version vom 11. Oktober 2022, 16:26 Uhr
Distanzspektren zweier verschiedener Reed–Solomon–Codes
Bei einem linearen Blockcode können bis zu $e = d_{\rm min} - 1$ Fehler erkannt werden. Bei allen Reed–Solomon–Codes beträgt dabei die minimale Distanz
- $$d_{\rm min} = n-k+1 \hspace{0.05cm}.$$
Man muss folgende Fälle unterscheiden:
- Treten nicht mehr als $e = d_{\rm min} - 1= n - k$ Symbolfehler auf, so wird der Block stets als fehlerhaft erkannt.
- Die Fehlererkennung kann auch bei mehr als $n - k$ Symbolfehlern noch funktionieren, und zwar dann, wenn das Empfangswort kein gültiges Codewort des Reed–Solomon–Codes ist:
- $$\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}. $$
- Ist aber das verfälschte Empfangswort $(\underline{y} \ne \underline{c})$ ein gültiges Codewort $(\underline{y\in C_{\rm RS}})$, so bleibt bei der Decodierung der fehlerhafte Block unentdeckt.
Wir definieren als Blockfehlerwahrscheinlichkeit:
- $${\rm Pr}({\rm Blockfehler}) = {\rm Pr}(\underline {y} \ne \underline {c}) \hspace{0.05cm}.$$
In dieser Aufgabe soll diese Wahrscheinlichkeit für folgende Codes ermittelt werden:
- Reed–Solomon–Code $(7, \, 3, \, 5)_8 \ \Rightarrow \ d_{\rm min} = 5$,
- Reed–Solomon–Code $(7, \, 5, \, 3)_8 \ \Rightarrow \ d_{\rm min} = 3$.
Weiterhin soll gelten:
- Jedes Symbol wird mit der Wahrscheinlichkeit $\varepsilon_{\rm S} = 0.1$ in ein anderes Symbol verfälscht und mit der Wahrscheinlichkeit $1 - \varepsilon_{\rm S} = 0.9$ richtig übertragen.
- Für das Distanzspektrum eines Reed–Solomon–Codes der Länge $n$ gilt mit $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}.$$
Daneben sollen zwei Schranken für die Blockfehlerwahrscheinlichkeit betrachtet und bewertet werden:
- Ist allein die minimale Distanz bekannt, so kann man daraus eine obere Schranke ableiten. Die Gewichtsfaktoren $W_i$ sind dabei so zu wählen, dass sicher (das heißt: bei allen Konstellationen) gilt:
- $${\rm Pr}({\rm Obere\hspace{0.15cm} Schranke}) \ge {\rm Pr}({\rm Blockfehler}) \hspace{0.05cm}. $$
- Eine untere Schranke erfordert zusätzlich die Kenntnis der Gewichtsfunktion $W_i$ für $i = d_{\rm min}$. Damit kann folgende Bedingung erfüllt werden:
- $${\rm Pr}({\rm Untere\hspace{0.15cm} Schranke}) \le {\rm Pr}({\rm Blockfehler}) \hspace{0.05cm}.$$
Hinweise:
- Die Aufgabe gehört zum Kapitel "Definition und Eigenschaften von Reed–Solomon–Codes".
- Bezug genommen wird insbesondere auf die Seite "Singleton–Schranke und minimale Distanz".
- Zu berechnen sind die in der obigen Grafik rot markierten Gewichte $W_i$.
Fragebogen
Musterlösung
(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 drei Symbole verfälscht werden:
- $$p_3 = 0.1^3 \cdot 0.9^4 = 0.6561 \cdot 10^{-3} \hspace{0.05cm},$$
- genau vier Symbole verfälscht werden:
- $$p_4 = 0.1^4 \cdot 0.9^3 = 0.729 \cdot 10^{-4} \hspace{0.05cm},$$
- genau fünf Symbole verfälscht werden:
- $$p_5 = 0.1^5 \cdot 0.9^2 = 0.81 \cdot 10^{-5} \hspace{0.05cm},$$
- genau sechs 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}.$$
