Exercise 1.13Z: Binary Erasure Channel Decoding again

• Return to book

Code table of the  $\rm HC (7, 4, 3)$

We consider as in the  "Exercise 1. 13"  the decoding of a  "Hamming Codes"  after transmission over an erasure channel   ⇒   "Binary Erasure Channel"  $\rm (BEC)$.

The  $(7, 4, 3)$-Hamming code is fully described by the adjacent code table  $\underline{u}_{i} → \underline{x}_{i}$  which can be used to find all solutions.

Hints:

• This exercise belongs to the chapter  "Decoding of Linear Block Codes".

• In contrast to  "Exercise 1.13"  the solution is here not to be found formally, but intuitively.

Questions

1

What is the minimum distance  $\ d_{\rm min}$  of the present code?

$\ d_{\rm min} \ = \ $

2

Is the code systematic?

	YES.
	NO.

3

Up to how many erasures  $($maximum number:  $e_{\rm max})$  is successful decoding guaranteed?

$\ e_{\rm max} \ = \ $

4

The received word is  $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$.  What is the sent information word  $\underline{u}$?

	$\underline{u} = (1, 0, 0, 0),$
	$\underline{u} = (1, 0, 0, 1),$
	$\underline{u} = (1, 0, 1, 0),$
	$\underline{u} = (1, 0, 1, 1).$

5

Which of the following received words can be decoded?

	$\underline{y}_{\rm A }= (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E}),$
	$\underline{y}_{\rm B} = ({\rm E}, {\rm E }, 0, {\rm E}, 0, 1, 0),$
	$\underline{y}_{\rm C} = ({\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0),$
	$\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0).$

Solution

Solution

(1)  The  $(7, 4, 3)$  Hamming code is considered here.  Accordingly,  the minimum distance is  $d_{\rm min} \ \underline{= 3}$.

(2)  The first  $k = 4$  bits of each code word  $\underline{x}$  match the information word  $\underline{u}$.  Correct is therefore  YES.

(3)  If no more than  $e_{\rm max} = d_{\rm min}- 1 \ \ \underline{ = 2}$  bits are erased,  decoding is possible with certainty.

• Each code word differs from every other in at least three bit positions.

• With only two erasures,  therefore,  the code word can be reconstructed in any case.

(4)  In the code table,  one finds a single code word starting with  "$10$"  and ending with  "$010$",  namely $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$. 

• Since this is a systematic code,  the first  $k = 4$  bits describe the information word  $\underline{u} = (1, 0, 0, 1)$   ⇒  answer 2.

(5)  Correct are the  suggested solutions 1 and 2.

• $\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0)$  cannot be decoded because less than  $k = 4$  bits  (number of information bits)  arrive.

• $\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$  is not decodable because  $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$  and   $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$  are possible outcomes.

• $\underline{y}_{\rm B} = ( {\rm E}, {\rm E}, 0, {\rm E}, 0, 1, 0)$  is decodable,  since of the 16 possible code words only  $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$  matches  $\underline{y}_{\rm B}$  in positions 3, 5, 6, 7.

• $\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$  is decodable.  Only the  $m = 3$  parity bits are missing.  Thus,  the information word  $\underline{u} = (1, 0, 0, 1)$  is also fixed  (systematic code).