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
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.
