Difference between revisions of "Aufgaben:Exercise 1.15: Distance Spectra of HC (7, 4, 3) and HC (8, 4, 4)"

Revision as of 23:05, 29 July 2022

Code tables of the $(7, 4, 3)$ Hamming code and the $(8, 4, 4)$ extension.

We consider as in the Task 1.9

the $(7, 4, 3)$ Hamming code and.
the extended $(8, 4, 4)$ Hamming code.

The graphic shows the corresponding code tables. In the Exercise 1.12 the syndrome decoding of these two codes has already been covered. In this exercise, the differences regarding the distance spectrum $\{W_{i}\}$ shall now be worked out. For the running variable $i = 0, \ \text{...} \ , n$:

The integer $W_{i}$ specifies the number of codewords $\underline{x}$ with the Hamming weight $\underline{w}_{\rm H}( \underline{x} ) = i$.
For the linear code considered here, $W_{i}$ simultaneously describes the number of codewords with the Hamming distance $i$ from the all-zero word.
Often one assigns to the number set $\{W_i\}$ a pseudo-function called weight enumerator function :

$$\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 has used the pseudo-function $W(X)$ to specify a channel-independent (upper) bound on the block error probability:

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

The so-called Bhattacharyya parameter is given as follows:

$$\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 for\hspace{0.15cm} the \hspace{0.15cm}BEC\:model},\\ \\ {\rm for\hspace{0.15cm} the \hspace{0.15cm}BSC\:model}, \\ \\{\rm for\hspace{0.15cm} the \hspace{0.15cm}AWGN\:model}. \end{array}$$

It should be noted that the Bhattacharyya bound is generally very pessimistic. The actual block error probability is often significantly lower.

Hints:

This exercise refers to the chapter Bounds for Block Error Probability.
A similar topic is covered in Task 1.14 and in Task 1.16 .
The channels to be considered are:
- the BSC model (Binary Symmetric Channel),
- the BEC model (Binary Erasure Channel),
- the AWGN channel model.

Questions

$W_{0} \ = \ $

$W_{3} \ = \ $

$W_{4} \ = \ $

$W_{7} \ = \ $

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

$\ \%$

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

$\ \%$

$\lambda \ = \ $

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

$ \ \rm dB$

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

$ \ \rm dB$

Solution

(1) By analyzing all the codewords of the $(7, 4, 3)$ Hamming code, we see that.

$W_{0} \ \underline{ = \ 1}$ codeword does not contain a one (the zero word),
$W_{3} \ \underline{ = \ 7}$ codewords contain three ones,
$W_{4} \ \underline{ = \ 7}$ codewords contain four ones,
$W_{7} \ \underline{ = \ 1}$ codeword consists of only ones.

$W_{i}$ simultaneously specifies the number of codewords that differ from the zero word in $i \ \rm bit$.

(2) The Bhattacharyya bound reads:

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

The weight function is defined by the subtask (1):

$$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}.$$

For the Bhattacharyya parameter of the BSC model:

$$\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}.$$

A comparison with the actual block error probability as calculated in Exercise 1.12,

$${\rm Pr(block\:error)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$

shows that Bhattacharyya provides only a rough bound. In the present case, this bound is more than a factor of $30$ higher than the actual value.

(3) From the code table of the $(8, 4, 4)$ code, the following results are obtained:

$$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) The equation for the Bhattacharyya parameter is:

$$\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 for\hspace{0.15cm} the \hspace{0.15cm}BEC model},\\ \\ {\rm for\hspace{0.15cm} the \hspace{0.15cm}BSC model}, \\ \\{\rm for\hspace{0.15cm} the \hspace{0.15cm}AWGN model}. \end{array}$$

With the BEC model, exactly the same bound is obtained when the erasure probability is $\lambda = \beta \ \underline{= 0.199}$.

(5) According to the above equation must apply:

$$\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}.$$

The code rate of the extended $(8, 4, 4)$ Hamming code is $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) Using the code rate $R = 4/7$ of the $(7, 4, 3)$ Hamming code, we obtain:

$$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}.$$

@@ Line 46: / Line 46: @@
 ===Questions===
 <quiz display=simple>
-{Geben Sie das Distanzspektrum des&nbsp; $(7, 4, 3)$–Hamming–Codes an.
+{Specify the distance spectrum of the&nbsp; $(7, 4, 3)$ Hamming code.
 |type="{}"}
 $W_{0} \ = \ ${ 1 }
@@ Line 53: / Line 53: @@
 $W_{7} \ = \ ${ 1 }
-{Wie lautet die Bhattacharyya–Schranke für den&nbsp; $(7, 4, 3)$–Hamming–Code und das BSC–Modell mit&nbsp; $\varepsilon = 0.01$?
+{What is the Bhattacharyya bound for the&nbsp; $(7, 4, 3)$ Hamming code and the BSC model with&nbsp; $\varepsilon = 0.01$?
 |type="{}"}
 ${\rm Pr(Bhattacharyya)} \ = \ $ { 6.6 3% } $\ \%$
-{Wie lautet bei gleichem Kanal die Schranke des erweiterten&nbsp; $(8, 4, 4)$–Hamming–Codes?
+{Given the same channel, what is the bound of the extended&nbsp; $(8, 4, 4)$ Hamming code?
 |type="{}"}
 ${\rm Pr(Bhattacharyya)} \ = \ ${ 2.2 3% } $\ \%$
-{Mit welchem BEC–Parameter&nbsp; $\lambda$ erhält man die genau gleichen Schranken?
+{With which BEC parameter&nbsp; $\lambda$ do you get the exact same barriers?
 |type="{}"}
 $\lambda \ = \ $ { 0.199 3% }
-{Wir betrachten weiterhin den erweiterten&nbsp; $(8, 4, 4)$–Hamming–Code, aber nun das AWGN–Modell.
+{We continue to consider the extended&nbsp; $(8, 4, 4)$ Hamming code, but now the AWGN model.
-<br>Bestimmen Sie&nbsp; $E_{\rm B} / N_{0}$&nbsp; (in dB) derart, dass sich die gleiche Bhattacharyya–Schranke ergibt.
+<br>Determine&nbsp; $E_{\rm B} / N_{0}$&nbsp; (in dB) such that the same Bhattacharyya bound results.
 |type="{}"}
 $10 · \lg {E_{\rm B}/N_0} \ = \ $ { 5 3% }$ \ \rm dB$
-{Ermitteln Sie nun den AWGN–Parameter&nbsp; $(10 · \lg {E_{\rm B}/N_0})$&nbsp; für den&nbsp; $(7, 4, 3)$–Hamming–Code.
+{Now determine the AWGN parameter&nbsp; $(10 · \lg {E_{\rm B}/N_0})$&nbsp; for the&nbsp; $(7, 4, 3)$ Hamming code.
 |type="{}"}
 $10 · \lg {E_{\rm B}/N_0} \ = \ $ { 4.417 3% }$ \ \rm dB$
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Durch die Analyse aller Codeworte des $(7, 4, 3)$–Hamming–Codes erkennt man, dass
+'''(1)'''&nbsp; By analyzing all the codewords of the $(7, 4, 3)$ Hamming code, we see that.
-*$W_{0} \ \underline{ = \ 1}$ Codewort keine Eins beinhaltet (das Nullwort),
+*$W_{0} \ \underline{ = \ 1}$ codeword does not contain a one (the zero word),
-*$W_{3} \ \underline{ = \ 7}$ Codeworte drei Einsen beinhalten,
+*$W_{3} \ \underline{ = \ 7}$ codewords contain three ones,
-*$W_{4} \ \underline{ = \ 7}$ Codeworte vier Einsen beinhalten,
+*$W_{4} \ \underline{ = \ 7}$ codewords contain four ones,
-*$W_{7} \ \underline{ = \ 1}$ Codewort nur aus Einsen besteht.
+*$W_{7} \ \underline{ = \ 1}$ codeword consists of only ones.
-$W_{i}$ gibt gleichzeitig die Anzahl der Codeworte an, die sich vom Nullwort in $i \ \rm Bit$ unterscheiden.
+$W_{i}$ simultaneously specifies the number of codewords that differ from the zero word in $i \ \rm bit$.
-'''(2)'''&nbsp; Die Bhattacharyya–Schranke lautet:
+'''(2)'''&nbsp; The Bhattacharyya bound reads:
 :$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$
-*Die Gewichtsfunktion ist durch die Teilaufgabe '''(1)''' festgelegt:
+*The weight function is defined by the subtask '''(1)''':
 :$$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:
+*For the Bhattacharyya parameter of the BSC model:
 :$$\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 [[Aufgaben:1.12_Hard_/_Soft_Decision|Aufgabe 1.12]] berechnet,
+*A comparison with the actual block error probability as calculated in [[Aufgaben:Exercise_1.12:_Hard_Decision_vs._Soft_Decision|Exercise 1.12]],
-:$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$
+:$${\rm Pr(block\:error)} \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.
+:shows that Bhattacharyya provides only a rough bound. In the present case, this bound is more than a factor of $30$ higher than the actual value.
-'''(3)'''&nbsp; Aus der Codetabelle des $(8, 4, 4)$–Codes erhält man folgende Ergebnisse:
+'''(3)'''&nbsp; From the code table of the $(8, 4, 4)$ code, the following results are obtained:
 :$$W(X) = 1+ 14 \cdot X^{4} + X^{8}\hspace{0.3cm}
@@ Line 118: / Line 118: @@
-'''(4)'''&nbsp; Die Gleichung für den Bhattacharyya–Parameter lautet:
+'''(4)'''&nbsp; The equation for the Bhattacharyya parameter is:
-:$$\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}$$
+:$$\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 for\hspace{0.15cm} the \hspace{0.15cm}BEC model},\\ \\ {\rm for\hspace{0.15cm} the \hspace{0.15cm}BSC model}, \\ \\{\rm for\hspace{0.15cm} the \hspace{0.15cm}AWGN model}. \end{array}$$
-Mit dem BEC–Modell ergibt sich genau die gleiche Schranke, wenn die Auslöschungswahrscheinlichkeit $\lambda = \beta \ \underline{= 0.199}$ beträgt.
+  With the BEC model, exactly the same bound is obtained when the erasure probability is $\lambda = \beta \ \underline{= 0.199}$.
-'''(5)'''&nbsp; Entsprechend obiger Gleichung muss gelten:
+'''(5)'''&nbsp; According to the above equation must apply:
 :$$\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$:
+*The code rate of the extended $(8, 4, 4)$ Hamming code is $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}.$$
@@ Line 136: / Line 136: @@
-'''(6)'''&nbsp; Mit der Coderate $R = 4/7$ des $(7, 4, 3)$–Hamming–Codes erhält man:
+'''(6)'''&nbsp; Using the code rate $R = 4/7$ of the $(7, 4, 3)$ Hamming code, we obtain:
 :$$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}.$$