Aufgaben:Exercise 1.08: Identical Codes

• Return to book

Assignment of the  $(6, 3)$  block code

We consider a block code  $\mathcal{C}$  described by the following generator matrix:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$

The mapping between the information words  $\underline{u}$  and the code words  $\underline{x}$  can be seen in the table.  It can be seen that this is not a  "systematic code".

By manipulating the generator matrix  $\boldsymbol {\rm G}$,  identical codes can be constructed from it.  This refers to codes with the same code words but different assignments  $\underline{u} \rightarrow \underline{x}$.

The following operations are allowed to obtain identical code:

• swapping or permuting the rows,

• Multiplying all rows by a constant vector not equal to  "$\underline{0}$".

• Replacing a row with a linear combination between this row and another one.

For the code  $\mathcal{C}_{\rm sys}$  sought in subtask  (3)  it is further required to be systematic   ⇒   generator matrix  $\boldsymbol{\rm G}_{\rm sys}$.

Hints:

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

• Reference is made in particular to the page  "Systematic Codes".

• Reference is also made to the so-called  "Singleton bound". 

• This states that the minimum Hamming distance of a  $(n, k)$  block code is upper bounded:   $d_{\rm min} \le n - k +1.$

Questions

1

Give the characteristics of the given code  $\mathcal{C}$ .

$n \hspace{0.3cm} = \ $

$k \hspace{0.3cm} = \ $

$m \hspace{0.15cm} = \ $

$R \hspace{0.2cm} = \ $

$|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \hspace{-0.05cm} = \ $

$d_{\rm min} \hspace{0.01cm} = \ $

2

Is there any  $(6, 3)$  block code with larger minimum distance?

	Yes.
	No.

3

What is the generator matrix  ${\boldsymbol{\rm G}}_{\rm sys}$  of the identical systematic code?

	The 1st row is   "$1 \ 0 \ 1 \ 1 \ 0 \ 1$".
	The 2nd row is   "$0 \ 1 \ 0 \ 1 \ 0 \ 1$".
	The 3rd row is   "$0 \ 0 \ 1 \ 0 \ 1 \ 1$".

4

What assignments result from this coding?

	$\underline{u} = (0, 0, 0) \ \Rightarrow \ \underline{x}_{\rm sys} = (0, 0, 0, 0, 0, 0)$.
	$\underline{u} = (0, 0, 1) \ \Rightarrow \ \underline{x}_{\rm sys}= (0, 0, 1, 0, 0, 1)$.
	$\underline{u} = (0, 1, 0) \ \Rightarrow \ \underline{x}_{\rm sys} = (0, 1, 0, 1, 1, 0)$.

5

Which parity bits has the systematic code  $\underline{x}_{\rm sys} = (u_{1},\ u_{2},\ u_{3},\ p_{1},\ p_{2},\ p_{3})$?

	$p_{1} = u_{1} \oplus u_{2},$
	$p_{2} = u_{2} \oplus u_{3},$
	$p_{3} = u_{1} \oplus u_{3}.$

Solution

Solution

(1)  The given code $\mathcal{C}$ is characterized by the following parameters:

• Number of bits of the code words:  $\underline{n = 6}$,
• Number of bits of information words:  $\underline{k = 3}$,
• Number of parity bit equations:  $\underline{m = n - k = 3}$,
• Code rate:  $R = k/n = 3/6 \Rightarrow \underline{R = 0.5}$,
• Number of code words (code cardinality):  $|\mathcal{C}| = 2^k \Rightarrow \underline{|C| = 8}$,
• minimum Hamming distance (see table):  $\underline{d}_{\rm min} \underline{= 3}$.

(2)  Correct is $\underline{\rm YES}$:

• According to the singleton bound $d_{\rm min} ≤ n - k + 1$ holds. With $n = 6$ and $k = 3$ one obtains $d_{\rm min} ≤ 4$.
• It is thus quite possible to construct a (6, 3) block code with larger minimal distance. How such a code looks, was kindly not asked.

The minimum distance of all Hamming codes is $d_{\rm min} = 3$, and only the special case with $n = 3$ and $k = 1$ reaches the limit. In contrast, the maximum reach according to the Singleton bound:

• all repetition codes (RC) because $k = 1$ and $d_{\rm min} = n$; this includes the (3, 1) Hamming code, which is known to be identical to RC (3, 1),

• all single parity–check codes (SPC): $k = n – 1, d_{\rm min} = 2$.

(3)  Correct are the solutions 2 and 3:

• If we swap rows in the generator matrix $\boldsymbol {\rm G}$, we arrive at an identical code $\mathcal{C}'$. That is, the codes $\mathcal{C}$ and $\mathcal{C}'$ contain the exact same code words.
• For example, after cyclic row swapping $2 \rightarrow 1, 3 \rightarrow 2$, and $1 \rightarrow 3$, one obtains the new matrix

$${ \boldsymbol{\rm G}}' = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

• The first and the last row of the new matrix already comply with the requirements of a systematic code, namely that its generator matrix ${ \boldsymbol{\rm G}_{\rm sys}}$ must start with a diagonal matrix.
• Replacing row 2 by the modulo 2 sum of rows 2 and 3, we get:

$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

• This systematic code contains exactly the same codewords as the codes $\mathcal{C}$ and $\mathcal{C}'$.

(4)  Correct are the solutions 1 and 2:

• Applying the equation $\underline{x}_{\rm sys} = \underline{u} \cdot \boldsymbol{\rm G}_{\rm sys}$ to the above examples, we see that the first two statements are correct, but not the last one.
• Without calculation one comes to the same result, if one considers that

• the systematic codeword $\underline{x}_{\rm sys}$ must start with $\underline{u}$,
• the code $\mathcal{C}_{\rm sys}$ contains the same codewords as the given code \mathcal{C}.

• For $\underline{u} = (0, 1, 0)$, the code word is thus $(0, 1, 0, ?, ?, ?)$. A comparison with the code table of $\mathcal{C}$ on the information page leads to $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.

(5)  Only statement 1 is correct. The statements for $p_{2}$ and $p_{3}$, on the other hand, are exactly reversed.

• With systematic coding, the following relationship exists between the generator matrix and the parity-check matrix:

$${ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \:{ \boldsymbol{\rm P}} \right) \hspace{0.3cm}\Leftrightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$

Chart of parity-check equations

• Applied to the current example, we obtain thus:

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

This results in parity-check equations (see graph):

$$u_1 \oplus u_2 \oplus p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_1 = u_1 \oplus u_2 \hspace{0.05cm},$$

$$ u_1 \oplus u_3 \oplus p_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_2 = u_1 \oplus u_3 \hspace{0.05cm},$$

$$ u_2 \oplus u_3 \oplus p_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_3 = u_2 \oplus u_3 \hspace{0.05cm}.$$