Aufgaben:Exercise 1.13Z: Binary Erasure Channel Decoding again

• Return to book

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

We consider again as in the  "Exercise 1. 13"  the decoding of a  "Hamming Codes"  after transmission over an erasure channel   ⇒   "Binary Erasure Channel"  (abbreviated 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"  here the solution is 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

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

	$\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 codeword $\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 codeword differs from every other in at least three bit positions.
• With only two erasures, therefore, the codeword can be reconstructed in any case.

(4)  In the code table, one finds a single codeword 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.

• Also  $\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 codewords 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).