Exercise 1.08: Identical Codes
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
Solution
- 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}.$$
- 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}.$$
