Aufgaben:Exercise 1.09Z: Extension and/or Puncturing

• Return to book

Extension and puncturing

Often you know a code that seems to be suitable for an application,  but its code rate does not exactly match the specifications.

There are several possibilities for rate adaptation:

Extension:
Starting from the  $(n, \, k)$  code whose parity-check matrix  $\mathbf{H}$  is given,  one obtains a  $(n+1, \, k)$  code by extending the parity-check matrix by one row and one column and adding zeros and ones to the new matrix elements according to the upper graph.  So,  one adds a new parity bit

$$x_{n+1} = x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n$$

and thus a new parity-check equation is added,  which is considered in  $\mathbf{H}\hspace{0.05cm}'$  .

Puncturing:
According to the figure below,  one arrives at a  $(n-1, \, k)$  code of larger rate by omitting a parity bit and a parity-check equation,  which is equivalent to deleting one row and one column from the parity-check matrix  $\mathbf{H}$ .

Shortening:
If an information bit is omitted instead of a parity bit,  the result is a  $(n-1, \, k-1)$  code of smaller rate.

In this exercise,  starting from a  $(5, \, 2)$  block code

$$\mathcal{C} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm} (0, 1, 0, 1, 1), \hspace{0.3cm} (1, 0, 1, 1, 0), \hspace{0.3cm} (1, 1, 1, 0, 1) \}$$

the following codes are to constructed and analyzed:

• one  $(6, \, 2)$  code by single extension,

• one  $(7, \, 2)$  code by extending it again,

• one  $(4, \, 2)$  code by puncturing.

The parity-check matrix and the generator matrix of the systematic  $(5, \, 2)$  code are:

$${ \boldsymbol{\rm H}}_{(5,\ 2)} = \begin{pmatrix} 1 &0 &1 &0 &0\\ 1 &1 &0 &1 &0\\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.3cm} \Leftrightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{(5,\ 2)} = \begin{pmatrix} 1 &0 &1 &1 &0\\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

Hints :

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

• In the  "Exercise 1.9"  it is exemplified how the  $(7, \, 4, \, 3)$  Hamming code is turned into a  $(8, \, 4, \, 4)$  code by extension.

Questions

1 Specify the characteristics of the given  $(5, \, 2)$  code.

$R \ = \ $

$d_{\rm min} \ = \ $

2 What code words does  the $(6, \, 2)$  code have after expansion?

	$(0 0 0 0 0 1), \ (0 1 0 1 1 0), \ (1 0 1 1 0 0), \ (1 1 1 0 1 1).$
	$(0 0 0 0 0 0), \ (0 1 0 1 1 1), \ (1 0 1 1 0 1), \ (1 1 1 0 1 0).$

3 Specify the characteristics of the extended  $(6, \, 2)$  code.

$R \ = \ $

$d_{\rm min} \ = \ $

4 What is the systematic generator matrix  $\boldsymbol{\rm G}$  of the  $(7, \, 2)$  code?

	Row 1 of  $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 0.$
	Row 2 of  $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 0, \, 1, \, 0, \, 1, \, 1, \, 1, \, 0.$

5 Specify the characteristics of the extended  $(7, \, 2)$  code.

$R \ = \ $

$d_{\rm min} \ = \ $

6 Which statements are true for the  $(4, \, 2)$  code  (puncturing the last parity bit)?

	The code rate is now  $R = 2/4 = 0.5$.
	$C_{(4,\ 2)} = \{(0, 0, 0, 0), \, (1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)\}$.
	The minimum distance remains unchanged from the  $(5, \, 2)$ code.

Solution

Solution

(1)  The rate of the  $(5, \, 2)$  code is  $R = 2/5 \ \underline{ = 0.4}$.

• From the given code,  we further recognize the minimum distance  $d_{\rm min} \ \underline{ = 3}$.

(2)  When extending from the  $(5, \, 2)$  code to the  $(6, \, 2)$  code,  another parity bit is added.

• The code word thus has the form

$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$

• For the added parity bit must be valid:

$$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$

• That is,  the new parity bit  $p_{4}$  is chosen to result in an even number of ones in each code word   ⇒   Answer 2.

• Solving this task with the parity-check matrix,  we get

$${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.3cm}\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$

• The two rows of the generator matrix  $\boldsymbol{\rm G}$  give two of the four code words,  the modulo 2 sum gives the third,  and finally the all zero word has to be considered.

(3)  After extension from the  $(5, \, 2)$  code to the  $(6, \, 2)$  code.

• decreases the rate from  $R = 2/5$  to  $R = 2/6 \ \underline{= 0.333}$,

• increases the minimum distance from  $d_{\rm min} = 3$  to  $d_{\rm min} \ \underline{= 4}$ .

In general:   Extending a code,  the rate decreases and the minimum distance increases by  $1$  $($only if  $d_{\rm min}$ was odd before$)$.

(4)  Using the same procedure as in subtask  (3),  we obtain

$${ \boldsymbol{\rm H}}_{(7,\hspace{0.05cm} 2)} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm H}}_{{\rm (7,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 0 &0 &0 &0 &0 &0 &1 \end{pmatrix}\hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$

⇒  Both answers  are correct.

(5)  The code rate is now  $R = 2/7 \ \underline{=0.266}$.

• The minimum distance is still  $d_{\rm min} \ \underline{= 4}$,  as can be seen from the  $(7, \, 2)$  code words:

$$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.3cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$

In general:   If the minimum distance of a code is even,  it cannot be increased by extension.

(6)  Correct are the  statements 1 and 2:

• By crossing out the last row and the last column,  we obtain for parity-check matrix and generator matrix,  respectively (each in systematic form):

$${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

• From the generator matrix we get the mentioned code words  $(1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$  as row sum as well as the null word  $(0, 0, 0, 0)$. 
• The minimum distance of this code is  $d_{\rm min}= 2$,  which is smaller than the minimum distance  $d_{\rm min}= 3$  of the  $(5, \, 2)$  code.

In general:   Puncturing makes  $d_{\rm min}$  smaller by  $1$  (if it was even before)  or it stays the same.

• This can be illustrated by generating the  $(3, \, 2)$  block code by another puncturing  (of the parity bit $p_{2}$).

• This code  $ \mathcal{C} = \{ (0, 0, 0), \hspace{0.3cm}(0, 1, 1), \hspace{0.3cm}(1, 0, 1), \hspace{0.3cm}(1, 1, 0) \}$  has the same minimum distance  $d_{\rm min}= 2$  as the  $(4, \, 2)$  code.