Aufgaben:Aufgabe 1.15: Distanzspektren von HC (7, 4, 3) und HC (8, 4, 4): Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(16 dazwischenliegende Versionen von 4 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{quiz-Header|Buchseite=Kanalcodierung/Schranken für die Blockfehlerwahrscheinlichkeit
+
{{quiz-Header|Buchseite=Kanalcodierung/Schranken für die Blockfehlerwahrscheinlichkeit}}
  
 +
[[Datei:P_ID2407__KC_A_1_9.png|right|frame|Codetabellen des  $(7, 4, 3)$–Hamming–Codes und der  $(8, 4, 4)$–Erweiterung]]
  
 +
Wir betrachten wie in der   [[Aufgaben:Aufgabe_1.09:_Erweiterter_Hamming–Code|Aufgabe 1.9]]
 +
*den  $(7, 4, 3)$–Hamming–Code und
 +
*den erweiterten  $(8, 4, 4)$–Hamming–Code.
  
}}
 
  
[[Datei:P_ID2407__KC_A_1_9.png|right|frame|Codetabellen des (7, 4)–Hamming–Codes und der (8, 4)–Erweiterung]]
+
Die Grafik zeigt die zugehörigen Codetabellen. In der  [[Aufgaben:Aufgabe_1.12:_Hard_Decision_vs._Soft_Decision|Aufgabe 1.12]]  wurde schon die Syndromdecodierung dieser beiden Codes behandelt. In dieser Aufgabe sollen nun die Unterschiede hinsichtlich des Distanzspektrums  $\{W_{i}\}$  herausgearbeitet werden. Für die Laufvariable gilt  $i = 0, \ \text{...} \ , n$:
  
Wir betrachten wie in [[Aufgaben:1.09_Erweiterter_Hamming–Code|Aufgabe 1.9]]
+
*Die Integerzahl  $W_{i}$  gibt die Zahl der Codeworte  $\underline{x}$  mit dem  [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Gewicht]]  $\underline{w}_{\rm H}( \underline{x} ) = i$ an.
*den (7, 4, 3)–Hamming–Code und
+
*Bei den hier betrachteten linearen Code bescheibt  $W_{i}$  gleichzeitig die Anzahl der Codeworte mit der  [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes|Hamming–Distanz]]  $i$  vom Nullwort.
*den erweiterten (8, 4, 4)–Hamming–Code.
+
*Häufig weist man der Zahlenmenge  $\{W_i\}$  einer Pseudo–Funktion zu, die man  [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes|Gewichtsfunktion]]  (englisch:   ''Weight Enumerator Function'', WEF) nennt:
 
 
Die Grafik zeigt die zugehörigen Codetabellen. In der [[Aufgaben:1.12_Hard_/_Soft_Decision|Aufgabe 1.12]] wurde schon die Syndromdecodierung dieser beiden Codes behandelt.
 
In dieser Aufgabe sollen die Unterschiede hinsichtlich des Distanzspektrums {$W_{i}$} herausgearbeitet werden. Für die Laufvariable gilt $i = 0, ... , n:$
 
 
 
*Die Integerzahl $W_{i}$ gibt die Zahl der Codeworte $\underline{x}$ mit dem [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Gewicht]] $\underline{w_{\rm H}(x)} = i$ an.
 
*Bei den hier betrachteten linearen Code bescheibt $W_{i}$ gleichzeitig die Anzahl der Codeworte mit der [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes|Hamming–Distanz]] $i$ vom Nullwort.
 
*Häufig weist man der Zahlenmenge { ${W_{i}}$ } einer Pseudo–Funktion zu, die man [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes|Gewichtsfunktion]] (englisch: ''Weight Enumerator Function'', WEF) nennt:
 
  
 
:$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$
 
:$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$
 
   
 
   
Bhattacharyya hat die Pseudo–Funktion $W(X;)$ verwendet, um eine kanalunabhängige (obere) Schranke für die Blockfehlerwahrscheinlichkeit anzugeben:
+
Bhattacharyya hat die Pseudo–Funktion  $W(X)$  verwendet, um eine kanalunabhängige (obere) Schranke für die Blockfehlerwahrscheinlichkeit anzugeben:
 
   
 
   
 
:$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$
 
:$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$
Zeile 26: Zeile 22:
 
Der so genannte ''Bhattacharyya–Parameter'' ist dabei wie folgt gegeben:
 
Der so genannte ''Bhattacharyya–Parameter'' ist dabei wie folgt gegeben:
  
:$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm exp}[- R \cdot E_{\rm B}/N_0] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$
+
:$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm}E_{\rm B}/N_0} \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$
 +
 
 +
Anzumerken ist, dass die Bhattacharyya–Schranke im allgemeinen sehr pessimistisch ist. Die tatsächliche Blockfehlerwahrscheinlichkeit liegt oft deutlich darunter.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 +
''Hinweise:''
 +
* Die Aufgabe bezieht sich auf das Kapitel  [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit|Schranken für die Blockfehlerwahrscheinlichkeit]].
 +
*Eine ähnliche Thematik wird in  [[Aufgaben:1.14_Bhattacharyya–Schranke_für_BEC|Aufgabe 1.14]]  und in  [[Aufgaben:Aufgabe_1.16:_Fehlerwahrscheinlichkeitsschranken_für_AWGN|Aufgabe 1.16]]  behandelt.
 +
* Als Kanäle sollen betrachtet werden:
 +
** das  [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC–Modell]]  (''Binary Symmetric Channel''),
 +
** das  [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|BEC–Modell]]  (''Binary Erasure Channel''),
 +
** das  [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang|AWGN–Kanalmodell]].
 +
 
 
   
 
   
''Hinweis:''
 
  
Die Aufgabe bezieht sich auf Kapitel [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit|Schranken für die Blockfehlerwahrscheinlichkeit]], ebenso wie [[Aufgaben:1.14_Bhattacharyya–Schranke_für_BEC|Aufgabe 1.14]] und [[Aufgaben:1.16_Schranken_für_AWGN|Aufgabe 1.16]]. Als Kanäle sollen betrachtet werden:
 
*das [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC–Modell]] (''Binary Symmetric Channel''),
 
*das [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|BEC–Modell]] (''Binary Erasure Channel''),
 
*das [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang|AWGN–Kanalmodell]].
 
  
Anzumerken ist, dass die Bhattacharyya–Schranke im allgemeinen sehr pessimistisch ist. Die tatsächliche Blockfehlerwahrscheinlichkeit liegt oft deutlich darunter.
+
 
  
 
===Fragebogen===
 
===Fragebogen===
 
 
<quiz display=simple>
 
<quiz display=simple>
 
+
{Geben Sie das Distanzspektrum des&nbsp; $(7, 4, 3)$–Hamming–Codes an.
{Geben Sie das Distanzspektrum des (7, 4, 3)–Hamming–Codes an.
 
 
|type="{}"}
 
|type="{}"}
$\ ( 7, 4, 3)–{\rm Code:} W_{0}$ = { 1 3% }
+
$W_{0} \ = \ ${ 1 }
$\ W_{3}$ = { 7 3% }
+
$W_{3} \  = \ ${ 7 }
$\ W_{4}$ = { 7 3% }
+
$W_{4} \ = \ ${ 7 }
$\ W_{7}$ = { 1 3% }
+
$W_{7} \ = \ ${ 1 }
  
{Wie lautet die Bhattacharyya–Schranke für das BSC–Modell mit $\varepsilon = 0.01?$
+
{Wie lautet die Bhattacharyya–Schranke für den&nbsp; $(7, 4, 3)$–Hamming–Code und das BSC–Modell mit&nbsp; $\varepsilon = 0.01$?
 
|type="{}"}
 
|type="{}"}
$\ (7, 4, 3)–{\rm Code:} \ \ \ {\rm Pr(Bhattacharyya)}$ = { 0.666 3% }
+
${\rm Pr(Bhattacharyya)} \ = \ $ { 6.6 3% } $\ \%$
  
{Wie lautet bei gleichem Kanal die Schranke des erweiterten Codes?
+
{Wie lautet bei gleichem Kanal die Schranke des erweiterten&nbsp; $(8, 4, 4)$–Hamming–Codes?
 
|type="{}"}
 
|type="{}"}
$\ (8, 4, 4)–{\rm Code:} \ \ \ {\rm Pr(Bhattacharyya)}$ = { 0.022 3% }
+
${\rm Pr(Bhattacharyya)} \ = \ ${ 2.2 3% } $\ \%$
  
{Mit welchem BEC–Parameter $\lambda$ erhält man die genau gleichen Schranken?
+
{Mit welchem BEC–Parameter&nbsp; $\lambda$ erhält man die genau gleichen Schranken?
 
|type="{}"}
 
|type="{}"}
$\lambda$ = { 0 3% }
+
$\lambda \ = \ $ { 0.199 3% }
  
{Betrachten wir nun das AWGN–Modell. Bestimmen Sie $E_{\rm B} / N_{0}$ in dB derart, dass sich für den (8, 4, 4)–Code die gleiche Bhattacharyya–Schranke ergibt.
+
{Wir betrachten weiterhin den erweiterten&nbsp; $(8, 4, 4)$–Hamming–Code, aber nun das AWGN–Modell.  
 +
<br>Bestimmen Sie&nbsp; $E_{\rm B} / N_{0}$&nbsp; (in dB) derart, dass sich die gleiche Bhattacharyya–Schranke ergibt.
 
|type="{}"}
 
|type="{}"}
$\ (8, 4, 4)–{\rm Code:} \ \ \ \ 10 · \ {\rm lg} \ E_{\rm B}/N_{0}$ = { 5 3% }$ \ dB$
+
$10 · \lg {E_{\rm B}/N_0} \ = \ $ { 5 3% }$ \ \rm dB$
  
{Ermitteln Sie nun den AWGN–Parameter für den (7, 4, 3)–Hamming–Code.
+
{Ermitteln Sie nun den AWGN–Parameter&nbsp; $(10 · \lg {E_{\rm B}/N_0})$&nbsp; für den&nbsp; $(7, 4, 3)$–Hamming–Code.
 
|type="{}"}
 
|type="{}"}
$\ (7, 4, 3)–{\rm Code:} \ \ \ \ 10 · \ {\rm lg} \ E_{\rm B}/N_{0}$ = { 4.417 3% }$ \ dB$
+
$10 · \lg {E_{\rm B}/N_0} \ = \ $ { 4.417 3% }$ \ \rm dB$
 
 
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Durch die Analyse aller Codeworte des (7, 4, 3)–Hamming–Codes erkennt man, dass
+
'''(1)'''&nbsp; Durch die Analyse aller Codeworte des $(7, 4, 3)$–Hamming–Codes erkennt man, dass
 +
 
 +
*$W_{0} \ \underline{ = \ 1}$ Codewort keine Eins beinhaltet (das Nullwort),
 +
*$W_{3} \ \underline{ = \ 7}$ Codeworte drei Einsen beinhalten,
 +
*$W_{4} \ \underline{ = \ 7}$ Codeworte vier Einsen beinhalten,
 +
*$W_{7} \ \underline{ = \ 1}$ Codewort nur aus Einsen besteht.
  
*$W_{0} \underline{ = \ 1}$ Codewort keine Eins beinhaltet (das Nullwort),
 
*$W_{3} \underline{ = \ 7}$ Codeworte drei Einsen beinhalten,
 
*$W_{4} \underline{ = \ 7}$ Codeworte vier Einsen beinhalten,
 
*$W_{7} \underline{ = \ 1}$ Codewort nur aus Einsen besteht.
 
  
 
$W_{i}$ gibt gleichzeitig die Anzahl der Codeworte an, die sich vom Nullwort in $i \ \rm Bit$ unterscheiden.
 
$W_{i}$ gibt gleichzeitig die Anzahl der Codeworte an, die sich vom Nullwort in $i \ \rm Bit$ unterscheiden.
 +
  
  
Zeile 86: Zeile 94:
 
:$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$
 
:$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$
  
Die Gewichtsfunktion ist durch die Teilaufgabe 1) festgelegt:
+
*Die Gewichtsfunktion ist durch die Teilaufgabe '''(1)''' festgelegt:
 
    
 
    
:$$W(X) = 1+ 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}$$
+
:$$W(X) = 1+ 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}\hspace{0.3cm}
 +
\Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot \beta^{3} + 7 \cdot \beta^{4} + \beta^{7} \hspace{0.05cm}.$$
 +
 
 +
*Für den Bhattacharyya–Parameter des BSC–Modells gilt:
  
:$$\Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot \beta^{3} + 7 \cdot \beta^{4} + \beta^{7} \hspace{0.05cm}.$$
+
:$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} = 0.199\hspace{0.3cm}
 +
  \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot 0.199^{3} + 7 \cdot 0.199^{4} + 0.199^{7} \hspace{0.15cm} \underline{ \approx 6.6\%} \hspace{0.05cm}.$$
  
Für den Bhattacharyya–Parameter des BSC–Modells gilt:
+
*Ein Vergleich mit der tatsächlichen Blockfehlerwahrscheinlichkeit, wie in [[Aufgaben:1.12_Hard_/_Soft_Decision|Aufgabe 1.12]] berechnet,
  
:$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} = 0.199$$
+
:$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$
 
 
:$$ \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot 0.199^{3} + 7 \cdot 0.199^{4} + 0.199^{7} \hspace{0.15cm} \underline{ \approx 0.066} \hspace{0.05cm}.$$
 
  
Ein Vergleich mit der tatsächlichen Blockfehlerwahrscheinlichkeit, wie in [[Aufgaben:1.12_Hard_/_Soft_Decision|Aufgabe 1.12]] berechnet:
+
:zeigt, dass Bhattacharyya nur eine grobe Schranke bereitstellt. Im vorliegenden Fall liegt diese Schranke um mehr als den Faktor $30$ über dem tatsächlichen Wert.
  
:$$W(X) = 1+ 14 \cdot X^{4} + X^{8}$$
 
  
:$$\Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 14 \cdot \beta^{4} + \beta^{8} = 14 \cdot 0.199^{4} + 0.199^{8} \hspace{0.15cm} \underline{ \approx 0.022} \hspace{0.05cm}.$$
 
 
zeigt, dass Bhattacharyya nur eine äußerst grobe Schranke bereitstellt. Im vorliegenden Fall liegt diese Schranke um mehr als den Faktor 30 über dem tatsächlichen Wert.
 
  
 +
'''(3)'''&nbsp; Aus der Codetabelle des $(8, 4, 4)$–Codes erhält man folgende Ergebnisse:
  
'''(3)'''&nbsp; Aus der Codetabelle des (8, 4, 4)–Codes erhält man folgende Ergebnisse:
+
:$$W(X) = 1+ 14 \cdot X^{4} + X^{8}\hspace{0.3cm}
 +
\Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 14 \cdot \beta^{4} + \beta^{8} = 14 \cdot 0.199^{4} + 0.199^{8} \hspace{0.15cm} \underline{ \approx 2.2\%} \hspace{0.05cm}.$$
  
:$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$
 
 
    
 
    
 +
 
'''(4)'''&nbsp; Die Gleichung für den Bhattacharyya–Parameter lautet:
 
'''(4)'''&nbsp; Die Gleichung für den Bhattacharyya–Parameter lautet:
  
:$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{ \varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm exp}[- R \cdot E_{\rm B}/N_0] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$
+
:$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{ \varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm e}^{- R \cdot E_{\rm B}/N_0} \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$
 
   
 
   
Mit dem BEC–Modell ergibt sich genau die gleiche Schranke, wenn die Auslöschungswahrscheinlichkeit $\lambda = \beta \underline{= 0.199}$ beträgt.
+
Mit dem BEC–Modell ergibt sich genau die gleiche Schranke, wenn die Auslöschungswahrscheinlichkeit $\lambda = \beta \ \underline{= 0.199}$ beträgt.
 +
 
  
  
 
'''(5)'''&nbsp; Entsprechend obiger Gleichung muss gelten:
 
'''(5)'''&nbsp; Entsprechend obiger Gleichung muss gelten:
 
   
 
   
:$$\beta = {\rm exp}[- R \cdot E_{\rm B}/N_0] = 0.199 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} R \cdot E_{\rm B}/N_0 = 10^{0.199} = 1.58 \hspace{0.05cm}.$$
+
:$$\beta = {\rm e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm} E_{\rm B}/N_0} = 0.199 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} R \cdot E_{\rm B}/N_0 = 10^{0.199} = 1.58 \hspace{0.05cm}.$$
  
Die Coderate des (8, 4, 4)–Codes ist $R = 0.5:$
+
*Die Coderate des erweiterten $(8, 4, 4)$–Hamming–Codes beträgt $R = 0.5$:
  
 
:$$E_{\rm B}/N_0 = 3.16 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 5\,{\rm dB}} \hspace{0.05cm}.$$
 
:$$E_{\rm B}/N_0 = 3.16 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 5\,{\rm dB}} \hspace{0.05cm}.$$
  
  
'''(6)'''&nbsp; Mit der Coderate $R = 4/7$ erhält man:
+
 
+
'''(6)'''&nbsp; Mit der Coderate $R = 4/7$ des $(7, 4, 3)$–Hamming–Codes erhält man:
 +
 
 
:$$E_{\rm B}/N_0 = 7/4 \cdot 1.58 = 2.765 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 4.417\,{\rm dB}} \hspace{0.05cm}.$$
 
:$$E_{\rm B}/N_0 = 7/4 \cdot 1.58 = 2.765 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 4.417\,{\rm dB}} \hspace{0.05cm}.$$
 
{{ML-Fuß}}
 
{{ML-Fuß}}
Zeile 134: Zeile 144:
  
  
[[Category:Aufgaben zu  Kanalcodierung|^1.6 Schranken für die Blockfehlerwahrscheinlichkeit
+
[[Category:Aufgaben zu  Kanalcodierung|^1.6 Fehlerwahrscheinlichkeitsschranken^]]
 
 
 
 
^]]
 

Version vom 14. Mai 2019, 15:55 Uhr

Codetabellen des  $(7, 4, 3)$–Hamming–Codes und der  $(8, 4, 4)$–Erweiterung

Wir betrachten wie in der  Aufgabe 1.9

  • den  $(7, 4, 3)$–Hamming–Code und
  • den erweiterten  $(8, 4, 4)$–Hamming–Code.


Die Grafik zeigt die zugehörigen Codetabellen. In der  Aufgabe 1.12  wurde schon die Syndromdecodierung dieser beiden Codes behandelt. In dieser Aufgabe sollen nun die Unterschiede hinsichtlich des Distanzspektrums  $\{W_{i}\}$  herausgearbeitet werden. Für die Laufvariable gilt  $i = 0, \ \text{...} \ , n$:

  • Die Integerzahl  $W_{i}$  gibt die Zahl der Codeworte  $\underline{x}$  mit dem  Hamming–Gewicht  $\underline{w}_{\rm H}( \underline{x} ) = i$ an.
  • Bei den hier betrachteten linearen Code bescheibt  $W_{i}$  gleichzeitig die Anzahl der Codeworte mit der  Hamming–Distanz  $i$  vom Nullwort.
  • Häufig weist man der Zahlenmenge  $\{W_i\}$  einer Pseudo–Funktion zu, die man  Gewichtsfunktion  (englisch:   Weight Enumerator Function, WEF) nennt:
$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$

Bhattacharyya hat die Pseudo–Funktion  $W(X)$  verwendet, um eine kanalunabhängige (obere) Schranke für die Blockfehlerwahrscheinlichkeit anzugeben:

$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$

Der so genannte Bhattacharyya–Parameter ist dabei wie folgt gegeben:

$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm}E_{\rm B}/N_0} \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$

Anzumerken ist, dass die Bhattacharyya–Schranke im allgemeinen sehr pessimistisch ist. Die tatsächliche Blockfehlerwahrscheinlichkeit liegt oft deutlich darunter.




Hinweise:




Fragebogen

1

Geben Sie das Distanzspektrum des  $(7, 4, 3)$–Hamming–Codes an.

$W_{0} \ = \ $

$W_{3} \ = \ $

$W_{4} \ = \ $

$W_{7} \ = \ $

2

Wie lautet die Bhattacharyya–Schranke für den  $(7, 4, 3)$–Hamming–Code und das BSC–Modell mit  $\varepsilon = 0.01$?

${\rm Pr(Bhattacharyya)} \ = \ $

$\ \%$

3

Wie lautet bei gleichem Kanal die Schranke des erweiterten  $(8, 4, 4)$–Hamming–Codes?

${\rm Pr(Bhattacharyya)} \ = \ $

$\ \%$

4

Mit welchem BEC–Parameter  $\lambda$ erhält man die genau gleichen Schranken?

$\lambda \ = \ $

5

Wir betrachten weiterhin den erweiterten  $(8, 4, 4)$–Hamming–Code, aber nun das AWGN–Modell.
Bestimmen Sie  $E_{\rm B} / N_{0}$  (in dB) derart, dass sich die gleiche Bhattacharyya–Schranke ergibt.

$10 · \lg {E_{\rm B}/N_0} \ = \ $

$ \ \rm dB$

6

Ermitteln Sie nun den AWGN–Parameter  $(10 · \lg {E_{\rm B}/N_0})$  für den  $(7, 4, 3)$–Hamming–Code.

$10 · \lg {E_{\rm B}/N_0} \ = \ $

$ \ \rm dB$


Musterlösung

(1)  Durch die Analyse aller Codeworte des $(7, 4, 3)$–Hamming–Codes erkennt man, dass

  • $W_{0} \ \underline{ = \ 1}$ Codewort keine Eins beinhaltet (das Nullwort),
  • $W_{3} \ \underline{ = \ 7}$ Codeworte drei Einsen beinhalten,
  • $W_{4} \ \underline{ = \ 7}$ Codeworte vier Einsen beinhalten,
  • $W_{7} \ \underline{ = \ 1}$ Codewort nur aus Einsen besteht.


$W_{i}$ gibt gleichzeitig die Anzahl der Codeworte an, die sich vom Nullwort in $i \ \rm Bit$ unterscheiden.


(2)  Die Bhattacharyya–Schranke lautet:

$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$
  • Die Gewichtsfunktion ist durch die Teilaufgabe (1) festgelegt:
$$W(X) = 1+ 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot \beta^{3} + 7 \cdot \beta^{4} + \beta^{7} \hspace{0.05cm}.$$
  • Für den Bhattacharyya–Parameter des BSC–Modells gilt:
$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} = 0.199\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot 0.199^{3} + 7 \cdot 0.199^{4} + 0.199^{7} \hspace{0.15cm} \underline{ \approx 6.6\%} \hspace{0.05cm}.$$
  • Ein Vergleich mit der tatsächlichen Blockfehlerwahrscheinlichkeit, wie in Aufgabe 1.12 berechnet,
$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$
zeigt, dass Bhattacharyya nur eine grobe Schranke bereitstellt. Im vorliegenden Fall liegt diese Schranke um mehr als den Faktor $30$ über dem tatsächlichen Wert.


(3)  Aus der Codetabelle des $(8, 4, 4)$–Codes erhält man folgende Ergebnisse:

$$W(X) = 1+ 14 \cdot X^{4} + X^{8}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 14 \cdot \beta^{4} + \beta^{8} = 14 \cdot 0.199^{4} + 0.199^{8} \hspace{0.15cm} \underline{ \approx 2.2\%} \hspace{0.05cm}.$$


(4)  Die Gleichung für den Bhattacharyya–Parameter lautet:

$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{ \varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm e}^{- R \cdot E_{\rm B}/N_0} \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$

Mit dem BEC–Modell ergibt sich genau die gleiche Schranke, wenn die Auslöschungswahrscheinlichkeit $\lambda = \beta \ \underline{= 0.199}$ beträgt.


(5)  Entsprechend obiger Gleichung muss gelten:

$$\beta = {\rm e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm} E_{\rm B}/N_0} = 0.199 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} R \cdot E_{\rm B}/N_0 = 10^{0.199} = 1.58 \hspace{0.05cm}.$$
  • Die Coderate des erweiterten $(8, 4, 4)$–Hamming–Codes beträgt $R = 0.5$:
$$E_{\rm B}/N_0 = 3.16 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 5\,{\rm dB}} \hspace{0.05cm}.$$


(6)  Mit der Coderate $R = 4/7$ des $(7, 4, 3)$–Hamming–Codes erhält man:

$$E_{\rm B}/N_0 = 7/4 \cdot 1.58 = 2.765 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 4.417\,{\rm dB}} \hspace{0.05cm}.$$