Channel Coding/General Description of Linear Block Codes

1. Channel Coding
2. Binary Block Codes for Channel Coding
3. General Description of Linear Block Codes

• Previous page
• Next page

• Previous page
• Next page

Linear codes and cyclic codes

All codes mentioned so far are  linear:

• the  "single parity-check code"  $\rm (SPC)$,

• the  "repetition code"  $\rm (RC)$,

• the  "Hamming code"  $\rm (HC)$.

Now the definition of  "linearity"  valid for binary block codes is added.

$\text{Definition:}$  A  linear binary block code  $\mathcal{C}$   is a set of  $2^k$  code words  $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$,  where the  (modulo 2)  sum of any two code words  $\underline{x}$  and  $\underline{x}\hspace{0.05cm}'$  again gives a valid code word:

\[\underline{x}, \underline{x}\hspace{0.05cm}' \in {\rm GF}(2^n),\hspace{0.3cm} \underline{x}, \underline{x}\hspace{0.05cm}' \in \mathcal{C} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x} + \underline{x}\hspace{0.05cm}' \in \mathcal{C} \hspace{0.05cm}.\]

• This condition must also be satisfied for  $\underline{x} = \underline{x}\hspace{0.05cm}'$ .
  

• For the remainder of this book,  modulo addition will no longer be expressed by the  "modulo sign"  to simplify notation, but by the conventional  "plus sign".

$\text{Example 1:}$  We consider two  $\text{(3, 2)}$  block codes:

\[\mathcal{C}_1 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 0, 1) \hspace{0.05cm},(1, 1, 0) \}\hspace{0.05cm},\]

\[\mathcal{C}_2 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 1, 0) \hspace{0.05cm},(1, 1, 1) \hspace{0.05cm}.\]

You can see:

• The code  $\mathcal{C}_1$  is linear,  since the modulo 2 addition of any two code words always yields also a valid code word, e.g.  $(0, 1, 1) + (1, 0, 1) = (1, 1, 0)$.
  

• The above definition also applies to the modulo 2 addition of a code word with itself, e.g.  $(0, 1, 1) + (0, 1, 1) = (0, 0, 0)$.

• From this follows:  Each linear code contains the all-zero word  $\underline{0}$.
  

• Although the last condition is satisfied,  $\mathcal{C}_2$  is not a linear code.  Indeed,  for this code:   $(0, 1, 1) + (1, 1, 0) = (1, 0, 1)$.  This is not a valid code word of  $\mathcal{C}_2$.

In the following,  we restrict ourselves exclusively to linear codes,  since non-linear codes are of secondary importance for practical use.

$\text{Definition:}$  A linear block code  $\mathcal{C}$  is called  "cyclic"  if every cyclic shift of a code word  $\underline{x}$   $($to the left or right$)$   results in a valid code word:

\[\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, x_n) \in \mathcal{C} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x}\hspace{0.05cm}'= (x_n, x_1, \hspace{0.05cm}\text{...} \hspace{0.05cm} \hspace{0.05cm}, x_{n-1}) \in \mathcal{C} \hspace{0.05cm}.\]

Code table of the systematic  $\text{(7, 4, 3)}$  Hamming code;
black:   $k= 4$  information bits, red:   $n-k = 3$  parity bits

$\text{Example 2:}$  You can see from the table for the  $\text{HC (7, 4, 3)}$ that it is linear and cyclic.

• A valid code word results even if all bits are inverted:   $0 ↔ 1$.

• Also the  $\underline{0}$  word  $(n$  times a "zero"$)$  and the  $\underline{1}$  word  $(n$  times a "one"$)$  are allowed with this code.

Code definition by the parity-check matrix

Chart for the  $\text{(7, 4, 3)}$  Hamming code

We consider the  $\text{(7, 4, 3)}$  Hamming code  with code words  $\underline{x}$  of length  $n=7$, consisting of

• $k = 4$  information bits  $x_1$,  $x_2$,  $x_3$,  $x_4$, and
  

• $m = n-k = 3$  parity bits $x_5$,  $x_6$,  $x_7$.
  
  

The parity-check equations are  (see graphic on the right):

\[x_1 + x_2 + x_3 + x_5 = 0 \hspace{0.05cm},\]

\[x_2 + x_3 + x_4 + x_6 = 0 \hspace{0.05cm},\]

\[x_1 + x_2 + x_4 + x_7 = 0 \hspace{0.05cm}. \]

In matrix notation, this set of equations reads:

\[{ \boldsymbol{\rm H}} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \hspace{0.05cm}. \]

In this equation are used:

• the  parity-check matrix  ${ \boldsymbol{\rm H}}$  with  $m = n-k = 3$  rows and  $n = 7$  columns:

\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 & 0 & 0\\ 0 &1 &1 &1 &0 & 1 & 0\\ 1 &1 &0 &1 &0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\]

• the  code word  $\underline{x}= (x_1,\ x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm},\ x_7)$  of length  $n = 7$,
  

• the  all-zero vector  $\underline{0} = (0,\ 0,\ 0)$  of length  $m = 3$.
  
  

By  "transposing",  the  row vectors   $\underline{x}$  and   $\underline{0}$   become the corresponding  column vectors  $\underline{x}^{\rm T}$  and  $\underline{0}^{\rm T}$.

$\text{Example 3:}$  The graph illustrates the  $m = 3$  parity-check equations of a code  $\mathcal{C}$  with code parameters  $n = 6$  and  $k = 3$  in the order red, green and blue.  Thus,  $\mathcal{C}$  is not a Hamming code  $(n \ne 2^m-1)$.

Chart for the  $\text{(6, 3, 3)}$  block code

According to the equation  $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T}$  the parity-check matrix is:

\[ \boldsymbol{\rm H} = \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}.\]

The  $2^k = 8$  code words in systematic realization are  (with the parity bits to the right of the small arrow):

\[\underline{x}_0 = (0,\ 0,\ 0_{\hspace{0.01cm} \rightarrow} 0,\ 0,\ 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_1 = (0,\ 0,\ 1_{\hspace{0.01cm} \rightarrow}0,\ 1,\ 1)\hspace{0.05cm},\hspace{0.5cm} \underline{x}_2 = (0,\ 1,\ 0_{\hspace{0.01cm} \rightarrow}1,\ 0,\ 1)\hspace{0.05cm},\hspace{0.5cm}\underline{x}_3 = (0, 1, 1_{\hspace{0.01cm} \rightarrow}1,\ 1,\ 0)\hspace{0.05cm}, \] \[\underline{x}_4 = (1,\ 0,\ 0_{\hspace{0.01cm} \rightarrow} 1,\ 1,\ 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_5 = (1,\ 0,\ 1_{\hspace{0.01cm} \rightarrow}1,\ 0,\ 1)\hspace{0.05cm},\hspace{0.5cm} \underline{x}_6 = (1,\ 1,\ 0_{\hspace{0.01cm} \rightarrow}0,\ 1,\ 1)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_7 = (1,\ 1,\ 1_{\hspace{0.01cm} \rightarrow}0,\ 0,\ 0)\hspace{0.05cm}.\]

It can be seen from these specifications:

• The number of columns  $\boldsymbol{\rm H}$  is equal to the code length  $n$.
  

• The number of lines of  $\boldsymbol{\rm H}$  is equal to the number  $m = n-k$  of parity-check equations.
  

• From  $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} $  it therefore does not follow that all code words contain an even number of ones.

Code definition by the generator matrix

The check matrix  $\boldsymbol{\rm H}$  of a  $(n, k)$  block code has 

• $n$  columns,
• $m = n-k$  rows.

However,  the same code can be described by the matrix  $\boldsymbol{\rm G}$  with

• also  $n$  columns,
• but  $k$  rows.
  

$\text{Definition:}$  A linear binary block code  $\mathcal{C}$  can be characterized by the  check matrix  $\boldsymbol{\rm H}$  or with the  generator matrix'  $\boldsymbol{\rm G}$  as follows:

\[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\text{:} \hspace{0.2cm}{ \boldsymbol{\rm H} } \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \}\hspace{0.05cm},\]

\[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{0.05cm}, \hspace{0.1cm}\underline{u} \in {\rm GF}(2^k)\text{:} \hspace{0.2cm}\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G} } \}\hspace{0.05cm}.\]

Before we turn to the properties of the generator matrix,  we describe the generation of the code words with an example.

$\text{Example 4:}$  We consider a linear  $(5, 3)$  block code with the generator matrix (again:  this is not a Hamming code!)

\[ \boldsymbol{\rm G} = \begin{pmatrix} 1 &1 &0 &1 &1\\ 0 &1 &0 &1 &0\\ 0 &1 &1 &1 &0 \end{pmatrix} = \begin{pmatrix} \underline{g}_1\\ \underline{g}_2\\ \underline{g}_3\\ \end{pmatrix} \hspace{0.05cm}.\]

• Thus,  the information words  $\underline{u}= (u_1,\ u_2,\ u_3)$  are assigned to the code words  $\underline{x}= (x_1,\ x_2,\ x_3,\ x_4,\ x_5)$  according to the following equations.
• The following always applies:  $\underline{x} = \underline{u} \cdot \boldsymbol{\rm G}$:

\[\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},\]

\[\underline{u}_1 = (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_1 = (0, 1, 1, 1, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{g}_3\hspace{0.05cm},\]

\[\underline{u}_2 = (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_2 = (0, 1, 0, 1, 0)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_2\hspace{0.05cm},\]

\[\underline{u}_3 = (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_3 = (0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{g}_2+\underline{g}_3\hspace{0.05cm},\]

\[\underline{u}_4 = (1, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_4 = (1, 1, 0, 1, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1 \hspace{0.05cm},\]

\[\underline{u}_5 =(1, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_5 = (1, 0, 1, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+\underline{g}_3\hspace{0.05cm},\]

\[\underline{u}_6 = (1, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_6 = (1, 0, 0, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+\underline{g}_2\hspace{0.05cm},\]

\[\underline{u}_7 =(1, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_7 = (1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+ \underline{g}_2+\underline{g}_3\hspace{0.05cm}.\]

Notes:

• The basis vectors used here for the calculation  $\underline{g}_1$,  $\underline{g}_2$  and  $\underline{g}_3$  – each with length  $n = 5$  – correspond to the  $k = 3$  rows of the generator matrix  $\boldsymbol{\rm G}$.
• This code is neither suitable for error correction nor for error detection because of  $d_{\rm min} = 1$ . Nevertheless, this code is also considered exemplarily on the next pages, because the coding results are well interpretable.
  
• At this point we would like to draw your attention to the applet  Gram–Schmidt process  for the book "Digital Signal Transmission", which teaches the calculation of basis functions, although in a different context than the one used here.
  

Identical Codes

The vectors used in  $\text{Example 4}$  on the last page  $\underline{g}_1$,  $\underline{g}_2$,  ...  ,  $\underline{g}_k$  are the  basis vectors  of the linear block code.  $\mathcal{C}$.

• The code itself can be viewed as a  $k$–dimensionaler subspace of  $\text{GF}(2^n)$ .
• The basis vectors  $\underline{g}_1$,  $\underline{g}_2$,  ...  , $\underline{g}_k$  are linearly independent.
  

However, the subspace  $\mathcal{C}$  is not only spanned by the basis vectors

\[\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm} \underline{g}_2 = (0, 1, 0, 1, 0) \hspace{0.05cm},\hspace{0.3cm} \underline{g}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm}\]

but other basis vectors  $\underline{g}\hspace{0.05cm}'_1$,  $\underline{g}\hspace{0.05cm}'_2$  and  $\underline{g}\hspace{0.05cm}'_3$  are equally suitable as long as linear independence is guaranteed between them.

$\text{Example 5:}$  We compare the code  $\mathcal{C}$  of  $\text{Example 4}$  with a second code  $\mathcal{C}\hspace{0.05cm}'$. The generator matrices are:

\[ \boldsymbol{\rm G} = \begin{pmatrix} \underline{g}_1\\ \underline{g}_2\\ \underline{g}_3\\ \end{pmatrix}= \begin{pmatrix} 1 &1 &0 &1 &1\\ 0 &1 &0 &1 &0\\ 0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} \boldsymbol{\rm G}\hspace{0.05cm}' = \begin{pmatrix} \underline{g}\hspace{0.05cm}'_1\\ \underline{g}\hspace{0.05cm}'_2\\ \underline{g}\hspace{0.05cm}'_3\\ \end{pmatrix}= \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0\\ 0 &0 &1 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

• The two codes are identical:   They contain the exact same code words; only a different assignment applies.
• During the transition from  $\boldsymbol{\rm G}$  to  $\boldsymbol{\rm G}\hspace{0.05cm}'$,  the following allowed operations were performed:

\[\underline{g}\hspace{0.05cm}'_1 = \underline{g}_1 + \underline{g}_2 \hspace{0.05cm},\hspace{0.3cm} \underline{g}\hspace{0.05cm}'_2 = \underline{g}_2 \hspace{0.05cm},\hspace{0.3cm} \underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.\]

• The corresponding code  $\mathcal{C}'$  is obtained by the equation  $\underline{x}' = \underline{u} \cdot \boldsymbol{\rm G}'$:

\[\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_0 = (0, 0, 0, 0, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_0 \hspace{0.05cm},\]

\[\underline{u}_1 = (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_1 = (0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{x}_3\hspace{0.05cm},\]

\[\underline{u}_2 = (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_2 = (0, 1, 0, 1, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_2\hspace{0.05cm},\]

\[\underline{u}_3 = (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_3 = (0, 1, 1, 1, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_1\hspace{0.05cm},\]

\[\underline{u}_4 = (1, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_4 = (1, 0, 0, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{x}_6 \hspace{0.05cm},\]

\[\underline{u}_5 =(1, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_5 = (1, 0, 1, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{x}_5\hspace{0.05cm},\]

\[\underline{u}_6 = (1, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_6 = (1, 1, 0, 1, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{x}_4\hspace{0.05cm},\]

\[\underline{u}_7 = (1, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_7 = (1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_7\hspace{0.05cm}.\]

• The corresponding code words  $\underline{x}_i = \underline{u}_i \cdot \boldsymbol{\rm G}$  of the code  $\mathcal{C}$   ⇒   generator matrix  $\boldsymbol{\rm G}$  are give in  $\text{Example 4}$  (previous page).

$\text{Conclusion:}$  The code tables of  $\text{Example 4}$  and  $\text{Example 5}$  make clear:

• $\mathcal{C}$  and  $\mathcal{C}\hspace{0.05cm}'$  contain the same code words. They are thus  identical codes  and both have the same capability of correction(see next page).
  

• $\mathcal{C}\hspace{0.05cm}'$  is now a  systematic code since the first  $k$  binary digits of each codeword  $\underline{x}\hspace{0.05cm}'_i$  match the binary digits of the information word.

Systematic Codes

The property "systematic" is now to be specified in mathematical form.

$\text{Definition:}$  In a  $\text{systematic }(n, k) \text{block code} \ \ \mathcal{C}$  each code word  $\underline{x}$  explicitly includes the information word  $\underline{u}$.

• That is, it applies:   $\underline{u} = (u_1, u_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_k) \hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm} = (u_1, u_2, ... \hspace{0.05cm}, u_k, x_{k+1}, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)\hspace{0.05cm}.$

• The generator matrix in this case has the form  $\boldsymbol{\rm G_{\rm sys} } =\left({ \boldsymbol{\rm I}_{\rm k} \ ; \ \boldsymbol{\rm P} }\right)$  with the  $k×k$ unit matrix  $\boldsymbol{\rm I}_{\rm k}$  and a suitably chosen  $(n-1)×k$ matrix  $\boldsymbol{\rm P}$.

So for   $\text{Example 5}$  on the last page can also be written:

\[ \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm with}\hspace{0.3cm} { \boldsymbol{\rm I_{3}}} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}\hspace{0.3cm}{\rm and}\hspace{0.3cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 0 &1 \\ 1 &0 \\ 0 &0 \end{pmatrix}\hspace{0.05cm}.\]

It is gratifying from the point of view of channel coding that for each code  $\mathcal{C}$  a systematic (identical or at least equivalent) code  $\mathcal{C}_{\rm sys}$  can be found.

In an  identical systematic code   $\underline{x}$  and  $\underline{x}_{\rm sys}$  contain the same code words, only the mapping  $\underline{u}   →   \underline{x}$  s different. One gets from a block code  $\mathcal{C}$  to the identical systematic code  $\mathcal{C}_{\rm sys}$ by the following manipulations with respect to the generator matrix  $\mathcal{C}_{\rm sys}$:

• Swap or permute the rows,
  

• Multiply all rows by a constant vector not equal to  $\underline{0}$,
  

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

$\text{Without proof:}$  An $\text{identical systematic code }\mathcal{C}_{\rm sys}$ can be found whenever to a generator matrix  $\boldsymbol{\rm G}$  there exists a matrix  $\boldsymbol{\rm A}$  such that  $\boldsymbol{\rm G}_{\rm sys} = \boldsymbol{\rm A} \cdot \boldsymbol{\rm G}$  holds.

If this is not possible, one can at least find an  equivalent systematic code by swapping or permuting the columns of  $\boldsymbol{\rm G}$ :

\[\mathcal{C}_{\rm sys} = {\rm \pi} (\mathcal{C})\hspace{0.3cm}{\rm mit}\hspace{0.3cm}{\rm \pi}():\hspace{0.15cm}{\rm permutation\:operator}\hspace{0.05cm}.\]

The codes  $\mathcal{C}$  and  $\mathcal{C}_{\rm sys}$  then contain different codewords, but they exhibit the same properties. For example  $\mathcal{C}_{\rm sys}$  in this case exhibits the same minimum Hamming distance  $d_{\rm min}$  as the code  $\mathcal{C}$.

$\text{Example 6:}$  We consider the generator matrices

\[ \boldsymbol{\rm G} = \begin{pmatrix} 1 &1 &0 &0 \\ 0 &0 &1 &1 \end{pmatrix}\hspace{0.3cm}{\rm und}\hspace{0.3cm} \boldsymbol{\rm G_{sys} } = \begin{pmatrix} 1 &0 &1 &0 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.\]

The analysis shows:

• The corresponding codes  $\mathcal{C}$  and  $\mathcal{C}_{\rm sys}$  contain different code words and are thus also not identical.:

\[\mathcal{C} = \big \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 0, 1, 1) \hspace{0.05cm},(1, 1, 0, 0) \hspace{0.05cm},(1, 1, 1, 1) \big \}\hspace{0.05cm},\]

\[\mathcal{C}_{\rm sys}= \big \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 1, 0, 1) \hspace{0.05cm},(1, 0, 1, 0) \hspace{0.05cm},(1, 1, 1, 1) \big \}\hspace{0.05cm}.\]

• But they are equivalent:   $\boldsymbol{\rm G}_{\rm sys}$  is obtained from  $\boldsymbol{\rm G}$  by swapping the second and third columns.
• It is a  $\text{(4, 2, 2)}$ block code in both cases   ⇒   $d_{\rm min} = 2$.

Relationship between generator and parity-check matrix

To define these two description matrices, we assume the following equations:

\[\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}^{\rm T} = { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} \hspace{0.05cm}, \hspace{0.8cm} { \boldsymbol{\rm H}} \cdot \underline{x}^{\rm T} = { \boldsymbol{\rm 0}}\hspace{0.05cm}.\]

Linking these two equations, we get:

\[{ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} = \underline{0}\hspace{0.5cm} \forall \hspace{0.15cm}\underline{u} \in {\rm GF}(2^k)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}.\]

Note that in these equations.

• $\underline{0}$  denotes a row vector with  $k$  elements, and
• $\boldsymbol{\rm 0}$  denotes a matrix with  $m$  rows and  $k$  columns,

where all elements of  $\underline{0}$  and  $\boldsymbol{\rm 0}$  are zero.

$\text{Example 7:}$  We consider as in  $\text{Example 4}$  the  $\text{(5, 3)}$ block code

\[\mathcal{C} = \big \{ \hspace{0.15cm} ( \hspace{0.05cm} 0, 0, 0, 0, 0) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm} 0, 1, 1, 1, 0) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm}0, 1, 0, 1, 0) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm}0, 0, 1, 0, 0) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm} 1, 1, 0, 1, 1) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm}1, 0, 1, 0, 1) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm}1, 0, 0, 0, 1) \hspace{0.05cm},\]

\[ \hspace{0.6cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \big \}\hspace{0.05cm}.\]

From  $n= 5$  and  $k = 3$  it follows for the number of parity-check equations  $m = 2$. By analyzing the possible codewords, the following results are obtained:

\[x_1 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.5cm} x_2 \oplus x_4 = 0\hspace{1cm} \Rightarrow \hspace{0.3cm}{ \boldsymbol{\rm H} } = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0 \end{pmatrix}\]

\[\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H} } \cdot { \boldsymbol{\rm G} }^{\rm T} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0 \end{pmatrix} \begin{pmatrix} 1 &0 &0 \\ 1 &1 &1 \\ 0 &0 &1 \\ 1 &1 &1 \\ 1 &0 &0 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \\ 0 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

The zero matrix here consists of  $m = 2$  rows and  $k = 3$  columns. For example, for the element in the first row and the first column:

\[1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 0 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 1 \cdot 1 = 0 \hspace{0.05cm}.\]

Generator matrix vs. parity-check matrix for systematic codes

In the general case  $\boldsymbol{\rm G}$  and  $\boldsymbol{\rm H}$  cannot be directly converted into each other, if only because of the different dimensions of generator matrix  $(k \times n)$  and parity-check matrix  $(m \times n)$.

$\text{Without proof:}$  The calculation process is simplified if the  $(k \times n)$ generator matrix is in systematic form:   $ \boldsymbol{\rm G_{sys} } =\left({ \boldsymbol{\rm I} }_k \: ; \: { \boldsymbol{\rm P} }\right)$. Then it follows from  $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$  for the  $(m \times n)$ parity-check matrix mit  $m = n-k$:

\[{ \boldsymbol{\rm H} } =\left( - { \boldsymbol{\rm P} }^{\rm T} \: ; \: { \boldsymbol{\rm I} }_m \right) \hspace{0.05cm}.\]

This equation holds in general, i.e., also in the nonbinary case. Since we restrict ourselves throughout the first main chapter to binary codes ⇒   $\mathcal{C} \in \text{GF}(2^n)$,   $ - \boldsymbol{\rm P} = +\boldsymbol{\rm P}$, and we obtain the form we will use in the remainder of this paper.

\[{ \boldsymbol{\rm H} } =\left( - { \boldsymbol{\rm P} }^{\rm T} \: ; \: { \boldsymbol{\rm I} }_m \right)=\left( { \boldsymbol{\rm P} }^{\rm T} \: ; \: { \boldsymbol{\rm I} }_m \right)\hspace{0.05cm}. \]

$\text{Example 8:}$  Wir betrachten weiterhin den beispielhaften  $\text{(5, 3)}$–Blockcode, gehen aber nun von der systematischen Generatormatrix  $\boldsymbol{\rm G}_{\rm sys}$  aus, die wir im  $\text{Beispiel 5}$  ermittelt haben:

\[ \boldsymbol{\rm G_{sys} } = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0\\ 0 &0 &1 &0 &0 \end{pmatrix} =\left({ \boldsymbol{\rm I} }_3 \: ; \: { \boldsymbol{\rm P} }\right) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm I_3} }= \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix}, \hspace{0.3cm} { \boldsymbol{\rm P} }= \begin{pmatrix} 0 &1 \\ 1 &0\\ 0 &0 \end{pmatrix} \hspace{0.3cm}\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm P}^{\rm T} } = \begin{pmatrix} 0 &1 &0\\ 1 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Damit erhält man für die Prüfmatrix

\[{ \boldsymbol{\rm H} } =\left({ \boldsymbol{\rm P} }^{\rm T} \: ; \: { \boldsymbol{\rm I} }_2 \right) = \begin{pmatrix} 0 &1 &0 &1 &0\\ 1 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},\]

und es ergibt sich folgende Codetabelle:

\[\underline{u}_0 = (0, 0, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_4 = (1, 0, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_4 = (1, 0, 0, 0, 1) \hspace{0.05cm},\]

\[\underline{u}_1 = (0, 0, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_1 = (0, 0, 1, 0, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_5 =(1, 0, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_5 = (1, 0, 1, 0, 1)\hspace{0.05cm},\]

\[\underline{u}_2 =(0, 1, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_2 = (0, 1, 0, 1, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_6 =(1, 1, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_6 = (1, 1, 0, 1, 1)\hspace{0.05cm},\]

\[\underline{u}_3 = (0, 1, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_7 = (1, 1, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_7 = (1, 1, 1, 1, 1) \hspace{0.05cm}.\]

Zusammen mit dem Vektor  $\underline{x} = (u_1, u_2, u_3, p_1, p_2) = (x_1, x_2, x_3, x_4, x_5)$  lauten dann die Prüfbits:

\[p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},\]

und die entsprechenden Prüfgleichungen des Decoders:

\[x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.\]

Man erkennt aus diesen Gleichungen und auch aus obiger Codetabelle:

• Dieser Code bietet gegenüber einem Übertragungsfehler hinsichtlich des dritten Bits  $(x_3 = u_3)$  keinen Schutz.
• Damit ist natürlich weder eine Fehlererkennung und noch weniger Fehlerkorrektur möglich.
• Gleiches gilt aber auch für den nichtsystematischen Code entsprechend  $\text{Beispiel 7}$  auf der letzten Seite.

Darstellung von SPC und RC als duale Codes

Nun sollen für die bereits im Kapitel  Beispiele binärer Blockcodes  behandelten Codes noch jeweils die Generatormatrix  $\boldsymbol{\rm G}$  und die Prüfmatrix  $\boldsymbol{\rm H}$  angegeben werden. Die Codelänge sei für die folgenden Beispiele stets  $n = 5$, doch lassen sich die Ergebnisse auch für andere Codelängen in gleicher Weise interpretieren. Es gilt für

• den  Single–Parity–check Code   ⇒   $\text{SPC (5, 4)}$:

\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &0 &1\\ 0 &0 &1 &0 &1\\ 0 &0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm};\]

• den  Wiederholungscode (Repetition Code)   ⇒   $\text{RC (5, 1)}$:

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

Die jeweils erste Gleichung lässt sich einfach aus der jeweiligen Definition herleiten und die abgeleitete Gleichung folgt aus der Beziehung  $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$.

Aus den obigen Matrizen kann verallgemeinert werden:

• Die Generatormatrix des  $\text{RC (5, 1)}$  ist identisch mit der Prüfmatrix des  $\text{SPC (5, 4)}$. Es handelt sich jeweils um  $(5 \times 1)$–Matrizen.
  

• Die Prüfmatrix des  $\text{RC (5, 1)}$  ist identisch mit der Generatormatrix des  $\text{SPC (5, 4)}$. Diese beiden Matrizen haben jeweils  $5$  Spalten und  $4$  Zeilen.
  

• Dieser Sachverhalt ergibt sich, weil es sich hier um so genannte "duale Codes" handelt. Zur Erklärung benötigen wir noch zwei Definitionen:
  

$\text{Definition:}$  Zwei lineare Codes  $\mathcal{C}$  und  $\mathcal{C}\hspace{0.05cm}'$, beide aus  ${\rm GF}(2^n)$, sind  orthogonal, wenn alle Codeworte  $\underline{x} \in \mathcal{C}$  zu allen Codeworten  $\underline{x}\hspace{0.05cm}' \in \mathcal{C}\hspace{0.05cm}'$  orthogonal sind. Man bezeichnet dann  $\mathcal{C}$  und  $\mathcal{C}\hspace{0.05cm}'$  als duale Codes.

$\text{Definition:}$  Zwei Codeworte  $\underline{x} \in{\rm GF}(2^n)$  und  $\underline{x\hspace{0.05cm}'} \in {\rm GF}(2^n)$  sind immer dann zueinander  orthogonal, wenn das  innere Produkt  verschwindet:

\[\big \langle \underline{x} \cdot \underline{x}\hspace{0.05cm}' \big \rangle = \sum_{i=1 }^{n} x_i \cdot x\hspace{0.05cm}'_i = 0 \hspace{0.05cm}, \hspace{0.5cm} \left \langle \underline{x} \cdot \underline{x}\hspace{0.05cm}' \right \rangle \in {\rm GF}(2^n) \hspace{0.05cm}.\]

Wegen der Produktbildung in  ${\rm GF}(2^n)$  sind auch folgende Codewort–Paare zueinander orthogonal:

\[\left \langle \hspace{0.05cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.5cm} (1, 1, 1, 0) \hspace{0.05cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.2cm} \left \langle \hspace{0.1cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (0, 1, 1, 0) \hspace{0.1cm}\right \rangle = 0\hspace{0.05cm}.\]

• Der Code  $\mathcal{C}$  spannt einen  $k$–dimensionalen Untervektorraum in  ${\rm GF}(2^n)$  auf.
• Der Untervektorraum des dualen Codes  $\mathcal{C}\hspace{0.05cm}'$  ist zu diesem orthogonal und weist die Dimension  $n-k$  auf.
• Damit gilt:   ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}\hspace{0.05cm}' \} = n\hspace{0.05cm}.$
  

Einige Eigenschaften des (7, 4, 3)–Hamming–Codes

Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming–Codes nochmals zusammen, der bereits im Kapitel  Beispiele binärer Blockcodes  ausführlich beschrieben wurde. Dieser  $\text{(7, 4, 3)}$–Code ist gekennzeichnet durch

Codeworte des  $\text{HC (7, 4, 3)}$

• die Anzahl der Prüfgleichungen  $m = 3$,
  
• die Codelänge  $n = 2^m-1 = 7$,
  
• die Informationswortlänge  $k = n-m = 4$,
  
• die Anzahl  $2^k =16$  der Codeworte (Dimension),
  
• die Rate  $R= k/n = 4/7$,
  
• die minimale Distanz  $d_{\rm min} = 3$  $($unabhängig von  $m$,  $n$  und  $k)$.
  

In obiger Tabelle sind die  $2^4 = 16$  Codeworte angegeben
(schwarz:  vier Informationsbits, rot:  drei Prüfbits).

Man erkennt daraus:

• Der Code beinhaltet sowohl das Null–Wort  $(0000000)$  als auch das Eins–Wort  $(1111111)$.
• Es gibt sieben Codeworte, die sich aus  $(0001011)$  jeweils durch zyklische Verschiebung ergeben  (alle gelb hinterlegt).
• Es gibt sieben Codeworte, die sich aus  $(0011101)$  jeweils durch zyklische Verschiebung ergeben  (alle grün hinterlegt).
• Zu jedem Codewort existiert auch das "negierte" Codewort, zum Beispiel gibt es neben  $(0001011)$  auch das Codewort  $(1110100)$.
• Die Prüfmatrix kann wie folgt geschrieben werden:

\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0 &1 \end{pmatrix}=\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_3 \right)\hspace{0.8cm} \Rightarrow\hspace{0.8cm}{ \boldsymbol{\rm P}}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0 \\ 0 &1 &1 &1 \\ 1 &1 &0 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm}{ \boldsymbol{\rm I}}_3 = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}\hspace{0.05cm}.\]

Dementsprechend gilt für die Generatormatrix:

\[{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &1\\ 0 &0 &1 &0 &1 &1 &0\\ 0 &0 &0 &1 &0 &1 &1 \end{pmatrix}\hspace{0.05cm}.\]

Aufgaben zum Kapitel

Aufgabe 1.7: Prüfmatrix und Generatormatrix des HC (7, 4, 3)

Aufgabe 1.7Z: Klassifizierung von Blockcodes

Aufgabe 1.8: Identische Codes

Aufgabe 1.8Z: Äquivalente Codes

Aufgabe 1.9: Erweiterter Hamming–Code

Aufgabe 1.9Z: Erweiterung und/oder Punktierung

Aufgabe 1.10: Einige Generatormatrizen