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

• Return to book

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

1

Specify the distance spectrum of the  $(7, 4, 3)$ Hamming code.

$W_{0} \ = \ $

$W_{3} \ = \ $

$W_{4} \ = \ $

$W_{7} \ = \ $

2

What is the Bhattacharyya bound for the  $(7, 4, 3)$ Hamming code and the BSC model with  $\varepsilon = 0.01$?

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

3

Given the same channel, what is the bound of the extended  $(8, 4, 4)$ Hamming code?

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

4

With which BEC parameter  $\lambda$ do you get the exact same barriers?

$\lambda \ = \ $

5

We continue to consider the extended  $(8, 4, 4)$ Hamming code, but now the AWGN model.
Determine  $E_{\rm B} / N_{0}$  (in dB) such that the same Bhattacharyya bound results.

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

6

Now determine the AWGN parameter  $(10 · \lg {E_{\rm B}/N_0})$  for the  $(7, 4, 3)$ Hamming code.

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

Solution

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