Difference between revisions of "Channel Coding/General Description of Linear Block Codes"

From LNTwww
Line 136: Line 136:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\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:
+
$\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:
  
 
::<math>\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},</math>  
 
::<math>\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},</math>  
Line 173: Line 173:
  
 
Notes:
 
Notes:
*The basis vectors used here for the calculation&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$&nbsp; and&nbsp; $\underline{g}_3$&nbsp; &ndash; each with length&nbsp; $n = 5$&nbsp; &ndash; correspond to the&nbsp; $k = 3$&nbsp; rows of the generator matrix&nbsp; $\boldsymbol{\rm G}$.  
+
*The basis vectors used here for the calculation&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$&nbsp; and&nbsp; $\underline{g}_3$&nbsp; &ndash; each with length&nbsp; $n = 5$&nbsp; &ndash; correspond to the&nbsp; $k = 3$&nbsp; rows of the generator matrix&nbsp; $\boldsymbol{\rm G}$.
*This code is neither suitable for error correction nor for error detection because of&nbsp; $d_{\rm min} = 1$&nbsp;. Nevertheless, this code is also considered exemplarily on the next pages, because the coding results are well interpretable.<br>
+
*At this point we would like to draw your attention to the applet&nbsp; [[Applets:Gram-Schmidt-Verfahren|Gram&ndash;Schmidt process]]&nbsp; for the book "Digital Signal Transmission", which teaches the calculation of basis functions, although in a different context than the one used here.<br>
+
*This code is neither suitable for error correction nor for error detection because of&nbsp; $d_{\rm min} = 1$.&nbsp; Nevertheless,&nbsp; this code is also considered exemplarily on the next pages,&nbsp; because the coding results are well interpretable.<br>
 +
 
 +
*At this point we would like to draw your attention to the applet&nbsp; [[Applets:Gram-Schmidt-Verfahren|Gram&ndash;Schmidt process]]&nbsp; for the book&nbsp; "Digital Signal Transmission",&nbsp; which teaches the calculation of basis functions,&nbsp; although in a different context than the one used here.<br>
  
  
 
== Identical Codes ==
 
== Identical Codes ==
 
<br>
 
<br>
The vectors used in&nbsp; $\text{Example 4}$&nbsp; on the last page&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$,&nbsp; ... &nbsp;,&nbsp; $\underline{g}_k$&nbsp; are the&nbsp; [[Digital_Signal_Transmission/Signals,_Basis_Functions_and_Vector_Spaces#Orthonormal_basis_functions| basis vectors]]&nbsp; of the linear block code.&nbsp; $\mathcal{C}$.  
+
The vectors&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$,&nbsp; ... &nbsp;,&nbsp; $\underline{g}_k$&nbsp; used in&nbsp; $\text{Example 4}$&nbsp; on the last page are the&nbsp; [[Digital_Signal_Transmission/Signals,_Basis_Functions_and_Vector_Spaces#Orthonormal_basis_functions| basis vectors]]&nbsp; of the linear block code&nbsp; $\mathcal{C}$.  
*The code itself can be viewed as a&nbsp; $k$&ndash;dimensionaler <i>subspace</i> of&nbsp; $\text{GF}(2^n)$&nbsp;.
+
*The code itself can be viewed as a&nbsp; $k$&ndash;dimensional&nbsp; subspace&nbsp; of&nbsp; $\text{GF}(2^n)$.
 +
 
 
*The basis vectors&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$,&nbsp; ... &nbsp;, $\underline{g}_k$&nbsp; are linearly independent.<br>
 
*The basis vectors&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$,&nbsp; ... &nbsp;, $\underline{g}_k$&nbsp; are linearly independent.<br>
  
  
However, the subspace&nbsp; $\mathcal{C}$&nbsp; is not only spanned by the basis vectors
+
However,&nbsp; the subspace&nbsp; $\mathcal{C}$&nbsp; is not only spanned by the basis vectors
  
 
::<math>\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm}
 
::<math>\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm}
Line 194: Line 197:
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Example 5:}$&nbsp; We compare the code&nbsp; $\mathcal{C}$&nbsp; of&nbsp; $\text{Example 4}$&nbsp; with a second code&nbsp; $\mathcal{C}\hspace{0.05cm}'$.  The generator matrices are:
+
$\text{Example 5:}$&nbsp; We compare the code&nbsp; $\mathcal{C}$&nbsp; of&nbsp; $\text{Example 4}$&nbsp; with a second code&nbsp; $\mathcal{C}\hspace{0.05cm}'$.&nbsp; The generator matrices are:
  
 
::<math> \boldsymbol{\rm G} = \begin{pmatrix}
 
::<math> \boldsymbol{\rm G} = \begin{pmatrix}
Line 217: Line 220:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
*The two codes are identical: &nbsp; They contain the exact same code words; only a different assignment applies.  
+
*The two codes are identical: &nbsp; They contain the exact same code words; only a different assignment applies.
 +
 
*During the transition from&nbsp; $\boldsymbol{\rm G}$&nbsp; to&nbsp; $\boldsymbol{\rm G}\hspace{0.05cm}'$,&nbsp; the following allowed operations were performed:
 
*During the transition from&nbsp; $\boldsymbol{\rm G}$&nbsp; to&nbsp; $\boldsymbol{\rm G}\hspace{0.05cm}'$,&nbsp; the following allowed operations were performed:
  
Line 224: Line 228:
 
\underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.</math>
 
\underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.</math>
  
*The corresponding code&nbsp; $\mathcal{C}'$&nbsp; is obtained by the equation&nbsp; $\underline{x}' = \underline{u} \cdot  \boldsymbol{\rm G}'$:
+
*The corresponding code &nbsp; $\mathcal{C}'$ &nbsp; is obtained by the equation&nbsp; $\underline{x}' = \underline{u} \cdot  \boldsymbol{\rm G}'$:
  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_0 =  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_0 =  
Line 243: Line 247:
 
(1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_7\hspace{0.05cm}.</math>
 
(1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_7\hspace{0.05cm}.</math>
  
*The corresponding code words&nbsp; $\underline{x}_i = \underline{u}_i \cdot  \boldsymbol{\rm G}$&nbsp; of the code&nbsp; $\mathcal{C}$ &nbsp; &rArr; &nbsp; generator matrix&nbsp;  $\boldsymbol{\rm G}$&nbsp; are give in&nbsp;  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Codefestlegung_durch_die_Generatormatrix|$\text{Example 4}$]]&nbsp; (previous page).}}<br>
+
*The corresponding code words&nbsp; $\underline{x}_i = \underline{u}_i \cdot  \boldsymbol{\rm G}$&nbsp; of the code &nbsp; $\mathcal{C}$ &nbsp; &rArr; &nbsp; generator matrix&nbsp;  $\boldsymbol{\rm G}$&nbsp; are give in&nbsp;  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Codefestlegung_durch_die_Generatormatrix|$\text{Example 4}$]]&nbsp; (previous page).}}<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Conclusion:}$&nbsp; The code tables of&nbsp; $\text{Example 4}$&nbsp; and&nbsp; $\text{Example 5}$&nbsp; make clear:
 
$\text{Conclusion:}$&nbsp; The code tables of&nbsp; $\text{Example 4}$&nbsp; and&nbsp; $\text{Example 5}$&nbsp; make clear:
*$\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; contain the same code words. They are thus&nbsp; <i>identical codes</i>&nbsp; and both have the same capability of correction(see next page).<br>
+
*$\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; contain the same code words.&nbsp; They are thus&nbsp; "identical codes"&nbsp; and both have the same capability of correction&nbsp; (see next page).<br>
  
*$\mathcal{C}\hspace{0.05cm}'$&nbsp;  is now a&nbsp; ''systematic code'' since the first&nbsp; $k$&nbsp; binary digits of each codeword&nbsp; $\underline{x}\hspace{0.05cm}'_i$&nbsp; match the binary digits of the information word.}}<br>
+
*$\mathcal{C}\hspace{0.05cm}'$&nbsp;  is now a&nbsp; "systematic code"&nbsp; since the first&nbsp; $k$&nbsp; binary digits of each code word&nbsp; $\underline{x}\hspace{0.05cm}'_i$&nbsp; match the binary digits of the information word.}}<br>
  
 
== Systematic Codes==
 
== Systematic Codes==
 
<br>
 
<br>
The property "systematic" is now to be specified in mathematical form.<br>
+
The property&nbsp; "systematic"&nbsp; is now to be specified in mathematical form.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; In a&nbsp; $\text{systematic }(n, k) \text{block code} \ \ \mathcal{C}$&nbsp; each code word&nbsp; $\underline{x}$&nbsp; explicitly includes the information word&nbsp; $\underline{u}$.  
+
$\text{Definition:}$&nbsp; In a&nbsp; $\text{systematic }(n, k) \text{ block code} \ \ \mathcal{C}$&nbsp; each code word&nbsp; $\underline{x}$&nbsp; explicitly includes the information word&nbsp; $\underline{u}$.  
*That is, it applies: &nbsp; $\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} =  
+
*That is,&nbsp; it applies: &nbsp; $\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}.$
+
(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&nbsp; $\boldsymbol{\rm G_{\rm sys} } =\left({ \boldsymbol{\rm I}_{\rm k} \ ; \ \boldsymbol{\rm P} }\right)$&nbsp; with the&nbsp; $k&times;k$ unit matrix&nbsp; $\boldsymbol{\rm I}_{\rm k}$&nbsp; and a suitably chosen&nbsp; $(n-1)&times;k$ matrix&nbsp; $\boldsymbol{\rm P}$.}}<br>
+
*The generator matrix in this case has the form &nbsp; $\boldsymbol{\rm G_{\rm sys} } =\left({ \boldsymbol{\rm I}_{\rm k} \ ; \ \boldsymbol{\rm P} }\right)$ &nbsp; with the&nbsp; $k&times;k$&nbsp; unit matrix &nbsp; $\boldsymbol{\rm I}_{\rm k}$ &nbsp; and a suitably chosen&nbsp; $(n-1)&times;k$&nbsp; matrix &nbsp; $\boldsymbol{\rm P}$.}}<br>
  
So for &nbsp; $\text{Example 5}$&nbsp; on the last page can also be written:
+
So,&nbsp; for &nbsp; $\text{Example 5}$&nbsp; on the last page can also be written:
  
 
::<math> \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm with}\hspace{0.3cm}
 
::<math> \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm with}\hspace{0.3cm}
Line 276: Line 280:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
It is gratifying from the point of view of channel coding that for each code&nbsp; $\mathcal{C}$&nbsp; a systematic (identical or at least equivalent) code&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; can be found.<br>
+
It is gratifying from the point of view of channel coding,&nbsp; that for each code&nbsp; $\mathcal{C}$&nbsp; a systematic&nbsp; $($identical or at least equivalent$)$&nbsp; code&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; can be found.<br>
 
 
  
In an&nbsp; '''identical systematic code'''&nbsp;&nbsp; $\underline{x}$&nbsp; and&nbsp; $\underline{x}_{\rm sys}$&nbsp; contain the same code words, only the mapping&nbsp; $\underline{u}  &nbsp; &#8594; &nbsp; \underline{x}$&nbsp; s different. One gets from a block code&nbsp; $\mathcal{C}$&nbsp; to the identical systematic code&nbsp; $\mathcal{C}_{\rm sys}$ by the following manipulations with respect to the generator matrix&nbsp; $\mathcal{C}_{\rm sys}$:
+
In an&nbsp; '''identical systematic code''',&nbsp;&nbsp; $\underline{x}$&nbsp; and&nbsp; $\underline{x}_{\rm sys}$&nbsp; contain the same code words,&nbsp; only the mapping&nbsp; $\underline{u}  &nbsp; &#8594; &nbsp; \underline{x}$&nbsp; is different.&nbsp; One gets from a block code&nbsp; $\mathcal{C}$&nbsp; to the identical systematic code&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; by the following manipulations with respect to the generator matrix&nbsp; $\mathcal{\rm G}$:
 
*Swap or permute the rows,<br>
 
*Swap or permute the rows,<br>
  
Line 288: Line 291:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Without proof:}$&nbsp; An $\text{identical systematic code  }\mathcal{C}_{\rm sys}$ can be found whenever to a generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; there exists a matrix&nbsp; $\boldsymbol{\rm A}$&nbsp; such that&nbsp; $\boldsymbol{\rm G}_{\rm sys} = \boldsymbol{\rm A} \cdot \boldsymbol{\rm G}$&nbsp; holds.}}  
+
$\text{Without proof:}$&nbsp; An&nbsp; $\text{identical systematic code  }\mathcal{C}_{\rm sys}$&nbsp; can be found whenever to a generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; there exists a matrix&nbsp; $\boldsymbol{\rm A}$&nbsp; such that&nbsp; $\boldsymbol{\rm G}_{\rm sys} = \boldsymbol{\rm A} \cdot \boldsymbol{\rm G}$&nbsp; holds.}}  
  
  
If this is not possible, one can at least find an&nbsp; '''equivalent systematic code''' by swapping or permuting the columns of&nbsp; $\boldsymbol{\rm G}$&nbsp;:
+
If this is not possible,&nbsp; one can at least find an&nbsp; '''equivalent systematic code'''&nbsp; by swapping or permuting the columns of&nbsp; $\boldsymbol{\rm G}$&nbsp;:
::<math>\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}.</math>
+
::<math>\mathcal{C}_{\rm sys} = {\rm \pi} (\mathcal{C})\hspace{0.3cm}{\rm with}\hspace{0.3cm}{\rm \pi}():\hspace{0.15cm}{\rm permutation\:operator}\hspace{0.05cm}.</math>
 +
 
 +
*The codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; then contain different code words,&nbsp; but they exhibit the same properties.
 +
*For example,&nbsp; in this case&nbsp; $\mathcal{C}_{\rm sys}$&nbsp;  exhibits the same minimum Hamming distance&nbsp; $d_{\rm min}$&nbsp; as the code&nbsp; $\mathcal{C}$.<br>
  
The codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; then contain different codewords, but they exhibit the same properties. For example&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; in this case exhibits the same minimum Hamming distance&nbsp; $d_{\rm min}$&nbsp; as the code&nbsp; $\mathcal{C}$.<br>
 
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
Line 302: Line 307:
 
1 &1 &0 &0 \\
 
1 &1 &0 &0 \\
 
0 &0 &1 &1   
 
0 &0 &1 &1   
\end{pmatrix}\hspace{0.3cm}{\rm und}\hspace{0.3cm}
+
\end{pmatrix},\hspace{0.3cm}
 
  \boldsymbol{\rm G_{sys} } = \begin{pmatrix}  
 
  \boldsymbol{\rm G_{sys} } = \begin{pmatrix}  
 
1 &0 &1 &0 \\
 
1 &0 &1 &0 \\
Line 309: Line 314:
  
 
The analysis shows:
 
The analysis shows:
*The corresponding codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; contain different code words and are thus also <i>not identical</i>.:  
+
*The corresponding codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; contain different code words and are thus&nbsp; '''not identical'''.:  
 
::<math>\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},</math>
 
::<math>\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},</math>
 
::<math>\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}.</math>
 
::<math>\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}.</math>
*But they are <i>equivalent</i>: &nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; is obtained from&nbsp; $\boldsymbol{\rm G}$&nbsp; by swapping the second and third columns.  
+
*But they are&nbsp; '''equivalent''':&nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; is obtained from&nbsp; $\boldsymbol{\rm G}$&nbsp; by swapping the second and third columns.&nbsp;
 +
 
 
*It is a&nbsp; $\text{(4, 2, 2)}$ block code in both cases &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $d_{\rm min} = 2$.}}
 
*It is a&nbsp; $\text{(4, 2, 2)}$ block code in both cases &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $d_{\rm min} = 2$.}}
  
Line 319: Line 325:
 
== Relationship between generator and parity-check matrix==
 
== Relationship between generator and parity-check matrix==
 
<br>
 
<br>
To define these two description matrices, we assume the following equations:
+
To define these two description matrices,&nbsp; we assume the following equations:
  
 
::<math>\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}  
 
::<math>\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}  
Line 325: Line 331:
 
{ \boldsymbol{\rm H}}  \cdot  \underline{x}^{\rm T} = { \boldsymbol{\rm 0}}\hspace{0.05cm}.</math>
 
{ \boldsymbol{\rm H}}  \cdot  \underline{x}^{\rm T} = { \boldsymbol{\rm 0}}\hspace{0.05cm}.</math>
  
Linking these two equations, we get:
+
Linking these two equations,&nbsp; we get:
  
 
::<math>{ \boldsymbol{\rm H}}  \cdot  { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T}  = \underline{0}\hspace{0.5cm}
 
::<math>{ \boldsymbol{\rm H}}  \cdot  { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T}  = \underline{0}\hspace{0.5cm}
Line 332: Line 338:
  
 
Note that in these equations.  
 
Note that in these equations.  
*$\underline{0}$&nbsp; denotes a row vector with&nbsp; $k$&nbsp; elements, and
+
*$\underline{0}$ &nbsp; denotes a row vector with&nbsp; $k$&nbsp; elements, and
*$\boldsymbol{\rm 0}$&nbsp; denotes a matrix with&nbsp; $m$&nbsp; rows and&nbsp; $k$&nbsp; columns,  
+
*$\boldsymbol{\rm 0}$ &nbsp; denotes a matrix with&nbsp; $m$&nbsp; rows and&nbsp; $k$&nbsp; columns,  
  
  
Line 350: Line 356:
 
::<math> \hspace{0.6cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \big \}\hspace{0.05cm}.</math>
 
::<math> \hspace{0.6cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \big \}\hspace{0.05cm}.</math>
  
From&nbsp; $n= 5$&nbsp; and&nbsp; $k = 3$&nbsp; it follows for the number of parity-check equations&nbsp; $m = 2$. By analyzing the possible codewords, the following results are obtained:
+
From&nbsp; $n= 5$&nbsp; and&nbsp; $k = 3$&nbsp; follows for the number of parity-check equations&nbsp; $m = 2$.&nbsp; By analyzing the possible code words,&nbsp; the following results are obtained:
  
 
::<math>x_1 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.5cm}
 
::<math>x_1 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.5cm}
Line 376: Line 382:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
The zero matrix here consists of&nbsp; $m = 2$&nbsp; rows and&nbsp; $k = 3$&nbsp; columns. For example, for the element in the first row and the first column:
+
The zero matrix here consists of&nbsp; $m = 2$&nbsp; rows and&nbsp; $k = 3$&nbsp; columns.&nbsp; For example,&nbsp; for the element in the first row and the first column:
  
 
::<math>1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm}
 
::<math>1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm}
Line 389: Line 395:
 
== Generator matrix vs. parity-check matrix for systematic codes ==
 
== Generator matrix vs. parity-check matrix for systematic codes ==
 
<br>
 
<br>
In the general case&nbsp; $\boldsymbol{\rm G}$&nbsp; and&nbsp; $\boldsymbol{\rm H}$&nbsp; cannot be directly converted into each other, if only because of the different dimensions of generator matrix&nbsp;  $(k \times n)$&nbsp; and parity-check matrix&nbsp; $(m \times n)$.<br>
+
Generally,&nbsp; $\boldsymbol{\rm G}$&nbsp; and&nbsp; $\boldsymbol{\rm H}$&nbsp; cannot be directly converted into each other,&nbsp; because of the different dimensions of generator matrix&nbsp;  $(k \times n)$&nbsp; and parity-check matrix&nbsp; $(m \times n)$.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Without proof:}$&nbsp;  
 
$\text{Without proof:}$&nbsp;  
The calculation process is simplified if the&nbsp; $(k \times n)$  generator matrix is in systematic form: &nbsp; $ \boldsymbol{\rm G_{sys} } =\left({ \boldsymbol{\rm I} }_k \: ; \: { \boldsymbol{\rm P} }\right)$. Then it follows from&nbsp; $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$&nbsp; for the&nbsp;  $(m \times n)$ parity-check matrix mit&nbsp; $m = n-k$:
+
The calculation process is simplified if the&nbsp; $(k \times n)$&nbsp; generator matrix is in systematic form: &nbsp;  
 +
:$$ \boldsymbol{\rm G_{sys} } =\left({ \boldsymbol{\rm I} }_k \: ; \: { \boldsymbol{\rm P} }\right).$$
 +
*Then it follows from&nbsp; $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$&nbsp; for the&nbsp;  $(m \times n)$&nbsp; parity-check matrix with&nbsp; $m = n-k$:
  
 
::<math>{ \boldsymbol{\rm H} } =\left( - { \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_m \right)
 
::<math>{ \boldsymbol{\rm H} } =\left( - { \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_m \right)
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
This equation holds in general, i.e., also in the nonbinary case. Since we restrict ourselves throughout the first main chapter to binary codes &#8658; &nbsp; $\mathcal{C} \in \text{GF}(2^n)$, &nbsp; $ - \boldsymbol{\rm P} = +\boldsymbol{\rm P}$, and we obtain the form we will use in the remainder of this paper.<br>
+
*This equation holds in general,&nbsp; i.e.,&nbsp; also in the non-binary case.&nbsp; Since we restrict ourselves to binary codes &#8658; &nbsp; $\mathcal{C} \in \text{GF}(2^n)$ &nbsp; &rArr;&nbsp; $ - \boldsymbol{\rm P} = +\boldsymbol{\rm P}$.
 +
 +
*Thus we obtain the form we will use in the remainder of this paper.<br>
  
::<math>{ \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}.
+
::<math>{ \boldsymbol{\rm H} } =\left(  { \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_m \right)\hspace{0.05cm}.
 
</math>}}
 
</math>}}
  
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Example 8:}$&nbsp; We continue to consider the examplenbsp;  $\text{(5,&nbsp;3)}$ block code, but now assume the systematic generator matrix&nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; that we determined in the&nbsp;  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Identical_Codes|$\text{Example 5}$]]&nbsp;:
+
$\text{Example 8:}$&nbsp; We continue to consider the example&nbsp;  $\text{(5,&nbsp;3)}$&nbsp; block code,&nbsp; but now assume the systematic generator matrix&nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; that we determined the&nbsp;  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Identical_Codes|$\text{Example 5}$]]:
  
 
::<math> \boldsymbol{\rm G_{sys} } = \begin{pmatrix}
 
::<math> \boldsymbol{\rm G_{sys} } = \begin{pmatrix}
Line 429: Line 439:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
This gives the following for the test matrix
+
*This gives the following for the parity-check matrix
  
 
::<math>{ \boldsymbol{\rm H} } =\left({ \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_2 \right)
 
::<math>{ \boldsymbol{\rm H} } =\left({ \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_2 \right)
Line 436: Line 446:
 
1 &0 &0 &0 &1
 
1 &0 &0 &0 &1
 
\end{pmatrix}
 
\end{pmatrix}
\hspace{0.05cm},</math>
+
\hspace{0.05cm}.</math>
  
and the following code table results:
+
*The following code table results:
  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_0 =  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_0 =  
Line 453: Line 463:
 
(1, 1, 1, 1, 1) \hspace{0.05cm}.</math>
 
(1, 1, 1, 1, 1) \hspace{0.05cm}.</math>
  
Together with the vector&nbsp; $\underline{x} = (u_1, u_2, u_3, p_1, p_2) =  (x_1, x_2, x_3, x_4, x_5)$&nbsp; the parity bits are then:
+
*Together with the vector&nbsp; $\underline{x} = (u_1,\ u_2,\ u_3,\ p_1,\ p_2) =  (x_1,\ x_2,\ x_3,\ x_4,\ x_5)$&nbsp; the parity bits are then:
  
 
::<math>p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},</math>
 
::<math>p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},</math>
  
and the corresponding test equations of the decoder:
+
and the corresponding parity-check equations of the decoder:
  
 
::<math>x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.</math>
 
::<math>x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.</math>
  
You can see from these equations and also from above code table:  
+
You can see from these equations and from the above code table:  
*This code offers no protection against a transmission error with respect to the third bit&nbsp; $(x_3 = u_3)$&nbsp;.
+
#This code offers no protection against a transmission error with respect to the third bit&nbsp; $(x_3 = u_3)$&nbsp;.
*This, of course, does not allow for error detection, much less error correction.
+
#This,&nbsp; of course,&nbsp; does not allow for error detection,&nbsp; and much less error correction.
*But the same is true for the non-systematic code according to&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Relationship_between_generator_and_parity-check_matrix|$\text{Example 7}$]]&nbsp; on the last page.}}<br>
+
#But the same is true for the non-systematic code according to&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Relationship_between_generator_and_parity-check_matrix|$\text{Example 7}$]]&nbsp; on the last page.}}<br>
  
 
== Representation of SPC and RC as dual codes ==
 
== Representation of SPC and RC as dual codes ==
 
<br>
 
<br>
Now for the codes already dealt with in the chapter&nbsp;  [[Channel_Coding/Examples_of_Binary_Block_Codes|examples of binary block codes]]&nbsp;  the generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; and the parity-check matrix&nbsp; $\boldsymbol{\rm H}$&nbsp; are to be given in each case. Let the code length always be&nbsp; $n = 5$ for the following examples, but the results can be interpreted in the same way for other code lengths. It applies to  
+
For the codes already dealt with in the chapter&nbsp;  [[Channel_Coding/Examples_of_Binary_Block_Codes|"Examples of binary block codes"]],&nbsp;  the generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; and the parity-check matrix&nbsp; $\boldsymbol{\rm H}$&nbsp; are to be given in each case.&nbsp; Let the code length always be&nbsp; $n = 5$ for the following examples,&nbsp; but the results can be interpreted in the same way for other code lengths.&nbsp; It applies to  
*the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|single parity&ndash;check code]] &nbsp; &#8658; &nbsp; $\text{SPC (5, 4)}$:
+
*the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|"single parity&ndash;check code"]] &nbsp; &#8658; &nbsp; $\text{SPC (5, 4)}$:
  
 
::<math>{ \boldsymbol{\rm H}}  
 
::<math>{ \boldsymbol{\rm H}}  
Line 484: Line 494:
 
\hspace{0.05cm};</math>
 
\hspace{0.05cm};</math>
  
*the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|repetition code]] (<i>Repetition Code</i>) &nbsp; &#8658; &nbsp; $\text{RC (5, 1)}$:
+
*the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|"repetition code"]] &nbsp; &#8658; &nbsp; $\text{RC (5, 1)}$:
  
 
::<math>{ \boldsymbol{\rm G}}  
 
::<math>{ \boldsymbol{\rm G}}  
Line 502: Line 512:
  
 
From the above matrices can be generalized:
 
From the above matrices can be generalized:
*The generator matrix of the&nbsp; $\text{RC (5, 1)}$&nbsp; is identical to the test matrix of the&nbsp; $\text{SPC (5, 4)}$. In each case they are&nbsp; $(5 \times 1)$ matrices.<br>
+
*The generator matrix of the&nbsp; $\text{RC (5, 1)}$&nbsp; is identical to the parity-check matrix of the&nbsp; $\text{SPC (5, 4)}$.&nbsp; In each case they are&nbsp; $(5 \times 1)$ matrices.<br>
  
*The test matrix of the&nbsp; $\text{RC (5, 1)}$&nbsp; is identical to the generator matrix of the&nbsp; $\text{SPC (5, 4)}$. These two matrices each have&nbsp; $5$&nbsp; columns and&nbsp; $4$&nbsp; rows.<br>
+
*The parity-check matrix of the&nbsp; $\text{RC (5, 1)}$&nbsp; is identical to the generator matrix of the&nbsp; $\text{SPC (5, 4)}$. These two matrices each have&nbsp; $5$&nbsp; columns and&nbsp; $4$&nbsp; rows.<br>
  
*This situation arises because we are dealing here with so-called "dual codes". For explanation we need two more definitions:<br>
+
*This situation arises because we are dealing here with so-called&nbsp; "dual codes".&nbsp; For explanation we need two more definitions:<br>
  
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Two linear codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}\hspace{0.05cm}'$, both made of&nbsp; ${\rm GF}(2^n)$, are&nbsp; ''orthogonal'' if all codewords&nbsp; $\underline{x} \in \mathcal{C}$&nbsp; to all codewords&nbsp; $\underline{x}\hspace{0.05cm}' \in \mathcal{C}\hspace{0.05cm}'$&nbsp; are orthogonal. One then refers to&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; as '''dual codes'''.}}<br>
+
$\text{Definition:}$&nbsp; Two linear codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}\hspace{0.05cm}'$,&nbsp; both made of&nbsp; ${\rm GF}(2^n)$,&nbsp; are&nbsp; '''orthogonal'''&nbsp; if all code words&nbsp; $\underline{x} \in \mathcal{C}$&nbsp; to all code words&nbsp; $\underline{x}\hspace{0.05cm}' \in \mathcal{C}\hspace{0.05cm}'$&nbsp; are orthogonal.  
 +
*One then refers to&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; as&nbsp; '''dual codes'''.}}<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Two code words&nbsp; $\underline{x} \in{\rm GF}(2^n)$&nbsp; and&nbsp; $\underline{x\hspace{0.05cm}'} \in {\rm GF}(2^n)$&nbsp; are&nbsp; '''orthogonal''' to each other whenever the&nbsp; [[Digital_Signal_Transmission/Signals,_Basis_Functions_and_Vector_Spaces#Nomenclature_in_the_fourth_chapter|inner product]]&nbsp; disappears:
+
$\text{Definition:}$&nbsp; Two code words&nbsp; $\underline{x} \in{\rm GF}(2^n)$&nbsp; and&nbsp; $\underline{x\hspace{0.05cm}'} \in {\rm GF}(2^n)$&nbsp; are&nbsp; '''orthogonal'''&nbsp; to each other whenever the&nbsp; [[Digital_Signal_Transmission/Signals,_Basis_Functions_and_Vector_Spaces#Nomenclature_in_the_fourth_chapter|"inner product"]]&nbsp; disappears:
  
 
::<math>\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}
 
::<math>\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}
Line 519: Line 530:
 
\hspace{0.05cm}.</math>}}<br>
 
\hspace{0.05cm}.</math>}}<br>
  
Because of the product formation in&nbsp; ${\rm GF}(2^n)$&nbsp; the following codeword pairs are also orthogonal to each other:
+
Because of the product in&nbsp; ${\rm GF}(2^n)$,&nbsp; the following code word pairs are also orthogonal to each other:
  
::<math>\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}
+
::<math>\left \langle \hspace{0.05cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (1, 1, 1, 0) \hspace{0.05cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.8cm}
 
\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}.</math>
 
\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}.</math>
  
*The code&nbsp; $\mathcal{C}$&nbsp; spans a&nbsp; $k$ dimensional subvector space in&nbsp; ${\rm GF}(2^n)$&nbsp;.  
+
*The code&nbsp; $\mathcal{C}$&nbsp; spans a&nbsp; $k$&ndash;dimensional subvector space in&nbsp; ${\rm GF}(2^n)$.
*The subspace of the dual code&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; is orthogonal to it and has dimension&nbsp; $n-k$&nbsp;.
+
 +
*The subspace of the dual code&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; is orthogonal to it and has dimension&nbsp; $n-k$.
 +
 
 
*Thus follows: &nbsp; ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}\hspace{0.05cm}' \} = n\hspace{0.05cm}.$<br>
 
*Thus follows: &nbsp; ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}\hspace{0.05cm}' \} = n\hspace{0.05cm}.$<br>
  
Line 531: Line 544:
 
<br>
 
<br>
 
Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming&ndash;Codes nochmals zusammen, der bereits im Kapitel&nbsp; [[Channel_Coding/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes|Beispiele binärer Blockcodes]]&nbsp; ausführlich beschrieben wurde. Dieser&nbsp; $\text{(7, 4, 3)}$&ndash;Code ist gekennzeichnet durch
 
Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming&ndash;Codes nochmals zusammen, der bereits im Kapitel&nbsp; [[Channel_Coding/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes|Beispiele binärer Blockcodes]]&nbsp; ausführlich beschrieben wurde. Dieser&nbsp; $\text{(7, 4, 3)}$&ndash;Code ist gekennzeichnet durch
[[File:P ID2359 KC T 1 4 S7.png|right|frame|Codeworte des&nbsp; $\text{HC (7, 4, 3)}$|class=fit]]
+
[[File:P ID2359 KC T 1 4 S7.png|right|frame|Code words of thes&nbsp; $\text{HC (7, 4, 3)}$|class=fit]]
 
*die Anzahl der Prüfgleichungen&nbsp; $m = 3$,<br>
 
*die Anzahl der Prüfgleichungen&nbsp; $m = 3$,<br>
 
*die Codelänge&nbsp; $n = 2^m-1 = 7$,<br>
 
*die Codelänge&nbsp; $n = 2^m-1 = 7$,<br>

Revision as of 14:32, 29 June 2022

Linear codes and cyclic codes


All codes mentioned so far are  linear:


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  $\underline{g}_1$,  $\underline{g}_2$,  ...  ,  $\underline{g}_k$  used in  $\text{Example 4}$  on the last page are the  basis vectors  of the linear block code  $\mathcal{C}$.

  • The code itself can be viewed as a  $k$–dimensional  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 code word  $\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}$  is 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{\rm G}$:

  • 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 with}\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 code words,  but they exhibit the same properties.
  • For example,  in this case  $\mathcal{C}_{\rm sys}$  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} \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  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$  follows for the number of parity-check equations  $m = 2$.  By analyzing the possible code words,  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


Generally,  $\boldsymbol{\rm G}$  and  $\boldsymbol{\rm H}$  cannot be directly converted into each other,  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 with  $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 non-binary case.  Since we restrict ourselves to binary codes ⇒   $\mathcal{C} \in \text{GF}(2^n)$   ⇒  $ - \boldsymbol{\rm P} = +\boldsymbol{\rm P}$.
  • Thus 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)\hspace{0.05cm}. \]


$\text{Example 8:}$  We continue to consider the example  $\text{(5, 3)}$  block code,  but now assume the systematic generator matrix  $\boldsymbol{\rm G}_{\rm sys}$  that we determined the  $\text{Example 5}$:

\[ \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}.\]
  • This gives the following for the parity-check matrix
\[{ \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}.\]
  • The following code table results:
\[\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}.\]
  • Together with the vector  $\underline{x} = (u_1,\ u_2,\ u_3,\ p_1,\ p_2) = (x_1,\ x_2,\ x_3,\ x_4,\ x_5)$  the parity bits are then:
\[p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},\]

and the corresponding parity-check equations of the decoder:

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

You can see from these equations and from the above code table:

  1. This code offers no protection against a transmission error with respect to the third bit  $(x_3 = u_3)$ .
  2. This,  of course,  does not allow for error detection,  and much less error correction.
  3. But the same is true for the non-systematic code according to  $\text{Example 7}$  on the last page.


Representation of SPC and RC as dual codes


For the codes already dealt with in the chapter  "Examples of binary block codes",  the generator matrix  $\boldsymbol{\rm G}$  and the parity-check matrix  $\boldsymbol{\rm H}$  are to be given in each case.  Let the code length always be  $n = 5$ for the following examples,  but the results can be interpreted in the same way for other code lengths.  It applies to

\[{ \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};\]
\[{ \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}.\]

The first equation can be easily derived from the respective definition and the derived equation follows from the relation  $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$.

From the above matrices can be generalized:

  • The generator matrix of the  $\text{RC (5, 1)}$  is identical to the parity-check matrix of the  $\text{SPC (5, 4)}$.  In each case they are  $(5 \times 1)$ matrices.
  • The parity-check matrix of the  $\text{RC (5, 1)}$  is identical to the generator matrix of the  $\text{SPC (5, 4)}$. These two matrices each have  $5$  columns and  $4$  rows.
  • This situation arises because we are dealing here with so-called  "dual codes".  For explanation we need two more definitions:


$\text{Definition:}$  Two linear codes  $\mathcal{C}$  and  $\mathcal{C}\hspace{0.05cm}'$,  both made of  ${\rm GF}(2^n)$,  are  orthogonal  if all code words  $\underline{x} \in \mathcal{C}$  to all code words  $\underline{x}\hspace{0.05cm}' \in \mathcal{C}\hspace{0.05cm}'$  are orthogonal.

  • One then refers to  $\mathcal{C}$  and  $\mathcal{C}\hspace{0.05cm}'$  as  dual codes.


$\text{Definition:}$  Two code words  $\underline{x} \in{\rm GF}(2^n)$  and  $\underline{x\hspace{0.05cm}'} \in {\rm GF}(2^n)$  are  orthogonal  to each other whenever the  "inner product"  disappears:

\[\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}.\]


Because of the product in  ${\rm GF}(2^n)$,  the following code word pairs are also orthogonal to each other:

\[\left \langle \hspace{0.05cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (1, 1, 1, 0) \hspace{0.05cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.8cm} \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}.\]
  • The code  $\mathcal{C}$  spans a  $k$–dimensional subvector space in  ${\rm GF}(2^n)$.
  • The subspace of the dual code  $\mathcal{C}\hspace{0.05cm}'$  is orthogonal to it and has dimension  $n-k$.
  • Thus follows:   ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}\hspace{0.05cm}' \} = n\hspace{0.05cm}.$

Some properties of the (7, 4, 3) Hamming code


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

Code words of thes  $\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}.\]

Exercises for the chapter


Exercise 1.7: Check and Generator Matrix of the HC (7, 4, 3)

Exercise 1.7Z: Classification of Block Codes

Exercise 1.8: Identische Codes

Exercise 1.8Z: Äquivalente Codes

Exercise 1.9: Erweiterter Hamming–Code

Exercise 1.9Z: Erweiterung und/oder Punktierung

Exercise 1.10: Einige Generatormatrizen