Aufgaben:Exercise 1.08Z: Equivalent Codes

• Return to book

Four  $(6, 3)$  block codes

In the graph,  the mappings  $\underline{u} \rightarrow \underline{x}$  for different codes are given,  each characterized below by the generator matrix  $\boldsymbol{\rm G}$  and the parity-check matrix  $\boldsymbol{\rm H}$,  respectively:

• ${\boldsymbol{\rm Code \ A}}$:

$${ \boldsymbol{\rm G}}_{\rm A} = \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},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm A} = \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}.$$

• ${\boldsymbol{\rm Code \ B}}$:

$${ \boldsymbol{\rm G}}_{\rm B} = \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},\hspace{0.5cm} { \boldsymbol{\rm H}}_{\rm B} = \begin{pmatrix} 1 &0 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

• ${\boldsymbol{\rm Code \ C}}$:

$${ \boldsymbol{\rm G}}_{\rm C} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1\\ 0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm C} = \begin{pmatrix} 1 &0 &1 &1 &0 &0\\ 0 &1 &1 &0 &1 &0\\ 1 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$

• ${\boldsymbol{\rm Code \ D}}$:

$${ \boldsymbol{\rm G}}_{\rm D} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm D} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0\\ 1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

This task is to investigate which of these codes or code pairs are

• are systematic,
• are identical  (that is:   Different codes have same code words),
• are equivalent  (that is:   Different codes have same code parameters).

Hints :

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

• Reference is made in particular to the sections  "Systematic Codes"   and   "Identical Codes".

• Note that the specification of a parity-check matrix  $\boldsymbol{\rm H}$  is not unique.  If one changes the order of the parity-check equations, this corresponds to a swapping of rows.

Questions

1

Which of the codes listed below are systematic?

	Code  $\rm A$,
	Code  $\rm B$,
	Code  $\rm C$,
	Code  $\rm D$.

2

Which of the given code pairs are identical?

	Code  $\rm A$  and  code  $\rm B$,
	Code  $\rm B$  and  code  $\rm C$,
	Code  $\rm C$  and  code  $\rm D$.

3

Which of the given code pairs are equivalent but not identical?

	Code  $\rm A$  and  code  $\rm B$,
	Code  $\rm B$  and  code  $\rm C$,
	Code  $\rm C$  and  code  $\rm D$.

4

How do the generator matrices  $G_{\rm B}$  and  $G_{\rm C}$  differ?

	By different linear combinations of different rows.
	By cyclic shifting of rows by  $1$  down.
	By cyclic shifting of columns by  $1$  to the right?

5

For which codes applies  ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$?

	Code  $\rm A$,
	Code  $\rm B$,
	Code  $\rm C$,
	Code  $\rm D$.

Solution

Solution

(1)  Correct are the  answers 1, 3 and 4:

• For a systematic  $(6, 3)$  block code,  the following must hold:

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

• This condition is satisfied by code  $\rm A$, code  $\rm C$, and code  $\rm D$, but not by code  $\rm B$.

(2)  Correct is only  answer 1:

• Only code  $\rm A$  and code  $\rm B$  are identical codes.  They contain exactly the same code words and differ only by other assignments  $\underline{u} \rightarrow \underline{x}$.

• As indicated in the solution to  "Exercise 1.8 (3)",  one gets from the generator matrix  ${ \boldsymbol{\rm G}}_{\rm B}$  to the generator matrix  ${ \boldsymbol{\rm G}}_{\rm A}$

• by swapping/permuting rows alone,  or
• by replacing a row with the linear combination between that row and another.

(3)  Thus,  the correct answer is  answer 2  alone:

• Code  $\rm A$  and code  $\rm B$  are more than equivalent,  namely identical.

• Code  $\rm C$  and code  $\rm D$  also differ,  for example,  by the minimum Hamming distance  $d_{\rm min} = 3$  and  $d_{\rm min} = 2$,  respectively,  and are thus also not equivalent.

• Code  $\rm B$  and code  $\rm C$  show the same properties,  for example  $d_{\rm min} = 3$  holds for both.  However,  they contain different code words.

(4)  Correct is  answer 3:

• The last column of  ${ \boldsymbol{\rm G}}_{\rm B}$  gives the first column of  ${ \boldsymbol{\rm G}}_{\rm C}$.
• The first column of  ${ \boldsymbol{\rm G}}_{\rm B}$  gives the second column of  ${ \boldsymbol{\rm G}}_{\rm C}$.
• The second column of  ${ \boldsymbol{\rm G}}_{\rm B}$  gives the third column of  ${ \boldsymbol{\rm G}}_{\rm C}$, etc.

(5)  All statements are true:

• The condition  ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$  holds for all linear codes.