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
Zeile 72: Zeile 72:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
 +
 +
 +
'''(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'' 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}$$
 +
 +
:$$\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$$
 +
 
 +
:$$ \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:
 +
 +
:$$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)'''  Aus der Codetabelle des (8, 4, 4)–Codes erhält man folgende Ergebnisse:
 +
 +
:$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \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 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}$$
 +
 +
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 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}.$$
 +
 +
Die Coderate des (8, 4, 4)–Codes ist $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$ 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}.$$
 +
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Version vom 13. Dezember 2017, 18:28 Uhr

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

Wir betrachten wie in 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 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 x mit dem 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 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: :'"`UNIQ-MathJax15-QINU`"' Bhattacharyya hat die Pseudo–Funktion ''W(X;)'' verwendet, um eine kanalunabhängige (obere) Schranke für die Blockfehlerwahrscheinlichkeit anzugeben: :'"`UNIQ-MathJax16-QINU`"' Der so genannte ''Bhattacharyya–Parameter'' ist dabei wie folgt gegeben: :'"`UNIQ-MathJax17-QINU`"' ''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. ==='"`UNIQ--h-0--QINU`"'Fragebogen=== '"`UNIQ--quiz-00000002-QINU`"' ==='"`UNIQ--h-1--QINU`"'Musterlösung=== '"`UNIQ--html-00000003-QINU`"' '''(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'' Bit unterscheiden. '''(2)'''  Die Bhattacharyya–Schranke lautet: :'"`UNIQ-MathJax18-QINU`"' Die Gewichtsfunktion ist durch die Teilaufgabe 1) festgelegt: :'"`UNIQ-MathJax19-QINU`"' :'"`UNIQ-MathJax20-QINU`"' Für den Bhattacharyya–Parameter des BSC–Modells gilt: :'"`UNIQ-MathJax21-QINU`"' :'"`UNIQ-MathJax22-QINU`"' Ein Vergleich mit der tatsächlichen Blockfehlerwahrscheinlichkeit, wie in [[Aufgaben:1.12_Hard_/_Soft_Decision|Aufgabe 1.12]] berechnet: :'"`UNIQ-MathJax23-QINU`"' :'"`UNIQ-MathJax24-QINU`"' 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)'''  Aus der Codetabelle des (8, 4, 4)–Codes erhält man folgende Ergebnisse: :'"`UNIQ-MathJax25-QINU`"' '''(4)'''  Die Gleichung für den Bhattacharyya–Parameter lautet: :'"`UNIQ-MathJax26-QINU`"' 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: :'"`UNIQ-MathJax27-QINU`"' Die Coderate des (8, 4, 4)–Codes ist $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$ 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}.$$


Abgerufen von „http://www.lntwww.de/index.php?title=Aufgaben:Aufgabe_1.15:_Distanzspektren_von_HC_(7,_4,_3)_und_HC_(8,_4,_4)&oldid=19987“
  • Powered by MediaWiki