Loading [MathJax]/jax/element/mml/optable/Latin1Supplement.js

Difference between revisions of "Aufgaben:Exercise 1.10: Some Generator Matrices"

From LNTwww
 
(19 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{quiz-Header|Buchseite=Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes
+
{{quiz-Header|Buchseite=Channel_Coding/General_Description_of_Linear_Block_Codes
 +
}}
  
}}
+
[[File:P_ID2404__KC_A_1_10.png|right|frame|Considered generator matrices]]
 +
 
 +
We now consider various binary codes of uniform length  n.  All codes of the form
 +
:$$\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1,\ x_2, \ \text{...} \  \hspace{0.05cm},\ x_n) \hspace{0.5cm}\text{with}
 +
\hspace{0.5cm} x_i \hspace{-0.15cm}\ \in \ \hspace{-0.15cm} \{ 0,\ 1 \},\hspace{0.2cm} i = 1, \hspace{0.05cm} \text{...} \ \hspace{0.05cm}, n$$
 +
 
 +
can be represented and interpreted in an  n-dimensional vector space.   ⇒   GF(2n).
 +
 
 +
The  k×n  generator matrix  G  (matrix with  k  rows and  n  columns)  yields a  (n,k)  code,  but only if the rank of the matrix  G  is also equal  k.  Further holds:
 +
 
 +
*Each code  C  spans a  k-dimensional linear subspace of the Galois field  GF(2n).
 +
 
 +
*As basis vectors of this subspace,  k  independent code words of  C  can be used.  There is no further restriction for the basis vectors.
  
[[File:P_ID2404__KC_A_1_10.png|right|frame|Betrachtete 3&times6–Generatormatrizen]]
+
*The parity-check matrix  H  also spans a subspace of  GF(2n).  But this has dimension  m=nk  and is orthogonal to the subspace based on  G.
  
Wir betrachten nun verschiedene Binärcodes einheitlicher Länge n. Alle Codes der Form
+
*For a linear code   ⇒   $\underline{x} = \underline{u} \cdot \boldsymbol{ {\rm G}}$,  where  $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$  indicates the information word.  A systematic code exists if  $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$  holds.
:$$\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1, x_2, ... \hspace{0.05cm}, x_n) \hspace{0.05cm},$$
 
:$$ x_i \hspace{-0.15cm}\ \in \ \hspace{-0.15cm} \{ 0, 1 \},\hspace{0.2cm} i = 1, ... \hspace{0.05cm}, n$$
 
  
lassen sich in einem $n$–dimensionalen Vektorraum darstellen und interpretieren ⇒ $\rm GF(2^n)$.
+
*In a systematic code,  there is a simple relationship between  $\mathbf{G}$  and  $\mathbf{H}$.  For more details,  see the  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"Theory Section"]].
  
Durch eine k×n–Generatormatrix G (also eine Matrix mit k Zeilen und n Spalten) ergibt sich ein (n,k)–Code, allerdings nur dann, wenn der Rang (englisch: ''Rank'') der Matrix G ebenfalls gleich k ist. Weiter gilt:
 
  
*Jeder Code C spannt einen k–dimensionalen linearen Untervektorraum des Galoisfeldes GF(2n) auf.
 
  
*Als Basisvektoren dieses Untervektorraums können k unabhängige Codeworte von C verwendet werden. Eine weitere Einschränkung gibt es für die Basisvektoren nicht.
 
  
*Die Prüfmatrix H spannt ebenfalls einen Untervektorraum von GF(2n) auf. Dieser hat aber die Dimension m=nk und ist orthogonal zum Untervektorraum, der auf G basiert.
 
  
*Bei einem linearen Code gilt x_=u_·G, wobei u_=(u1,u2,...,uk) das Informationswort angibt. Ein systematischer Code liegt vor, wenn x1=u1,...,xk=uk gilt.
+
Hints :
  
*Bei einem systematischen Code besteht ein einfacher Zusammenhang zwischen G und H. Nähere Angaben hierzu finden Sie im [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Theorieteil]].
+
*This exercise belongs to the chapter  [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
  
 +
*For the whole exercise holds  n=6.
  
''Hinweise: ''
+
*In the subtask  '''(4)'''  it is to be clarified which of the matrices  GA, GB resp. GC  result in a  (6,3)  block code with the code words listed below:
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
 
Blockcodes]].
 
* Für die gesamte Aufgabe gilt n=6. In der Teilaufgabe (4) soll geklärt werden, welche der Matrizen GA, GB bzw. GC zu einem (6,3)–Blockcode mit den nachfolgend aufgeführten Codeworten führen:
 
  
:$$ \mathcal{C}_{(6,\hspace{0.05cm} 3)} = \{ \ (  0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 0, 1, 0, 1, 1), \hspace{0.1cm}(0, 1, 0, 1, 0, 1), \hspace{0.1cm}(0, 1, 1, 1, 1, 0), \\ \hspace{2cm} (  1, 0, 0, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1), \hspace{0.1cm}(1, 1, 0, 0, 1, 1), \hspace{0.1cm}(1, 1, 1, 0, 0, 0) \}\hspace{0.05cm}.$$
+
:$$   (  0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 0, 1, 0, 1, 1), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm}(0, 1, 1, 1, 1, 0), \hspace{0.3cm} (  1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1), \hspace{0.3cm}(1, 1, 0, 0, 1, 1), \hspace{0.3cm}(1, 1, 1, 0, 0, 0)\hspace{0.05cm}.$$
  
  
  
===Fragebogen===
+
===Questions===
 
<quiz display=simple>
 
<quiz display=simple>
{Bekannt sind nur die zwei Codeworte (0,1,0,1,0,1) und (1,0,0,1,1,0) eines linearen Codes. Welche Aussagen sind zutreffend?
+
{Known are only the two code words&nbsp; (0,1,0,1,0,1)&nbsp; and&nbsp; (1,0,0,1,1,0)&nbsp; of a linear code.&nbsp; Which statements are true?
 
|type="[]"}
 
|type="[]"}
- Es könnte sich um einen (5,2)–Code handeln.
+
- It could be a&nbsp; (5,2)&nbsp; code.
+ Es könnte sich um einen (6,2)–Code handeln.
+
+ It could be a&nbsp; (6,2)&nbsp; code.
+ Es könnte sich um einen (6,3)–Code handeln.
+
+ It could be a&nbsp; (6,3)&nbsp; code.
  
  
{Wie lauten die Codeworte des linearen (6,2)–Codes explizit?
+
{What are the four code words of the linear&nbsp; (6,2)&nbsp; code explicitly?
|type="[]"}  
+
|type="()"}  
 
- (001011), (010101), (100110), (110011).
 
- (001011), (010101), (100110), (110011).
 
+ (000000), (010101), (100110), (110011).
 
+ (000000), (010101), (100110), (110011).
Line 49: Line 54:
  
  
{Welche Aussagen gelten für diesen (6,2)–Code C?
+
{Which statements are true for this&nbsp; (6,2)&nbsp; code&nbsp; $\mathcal{C}$?
 
|type="[]"}
 
|type="[]"}
+ Für alle Codeworte (i=1,...,4) gilt x_iGF(26).
+
+ For all code words&nbsp; $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$ &nbsp; &rArr; &nbsp; x_iGF(26).
+ C ist ein 2–dimensionaler linearer Untervektorraum von GF(26).
+
+ $\mathcal{C}$&nbsp; is a two-dimensional linear subvector space of&nbsp; ${\rm GF}(2^6)$.
+ G gibt Basisvektoren dieses Untervektorraumes $GF \, (2^2)$ an.
+
+ G&nbsp; gives basis vectors of this subvector space&nbsp; ${\rm GF}(2^2)$.
- G und H sind jeweils 2×6–Matrizen.
+
- G&nbsp; and&nbsp; H&nbsp; are each&nbsp; 2×6&nbsp; matrices.
  
  
{Welche der Generatormatrizen (siehe Grafik) führen zu einem (6,3)–Code?
+
{Which of the generator matrices given in the graphic result in a&nbsp; (6,3)&nbsp; code?
 
|type="[]"}
 
|type="[]"}
+ Generatormatrix GA,
+
+ The generator matrix&nbsp; GA,
+ Generatormatrix GB,
+
+ the generator matrix&nbsp; GB,
- Generatormatrix GC.
+
- the generator matrix&nbsp; GC.
  
  
Line 69: Line 74:
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Die Codewortlänge ist n= der (5,2)–Code kommt nicht in Frage. Bei einem (6,2)–Code gibt es 22=4 verschiedene Codeworte und beim (6,3)–Code entsprechend 23=8. Durch die Angabe von zwei Codeworten lässt sich weder der (6,2)– noch der (6,3)–Code ausschließen  ⇒  <u>Antwort 2 und 3</u>.
+
'''(1)'''&nbsp; Correct are the&nbsp; <u>suggested solutions 2 and 3</u>:
 +
*The code word length is&nbsp; $n = 6$ &nbsp; &nbsp;the&nbsp; (5,2)&nbsp; code is not eligible.
 +
 +
*For a&nbsp; (6,2)&nbsp; code,&nbsp; there are&nbsp; 22=4&nbsp; distinct code words,&nbsp; and for the&nbsp; (6,3)&nbsp; code,&nbsp; there are correspondingly&nbsp; 23=8.
 +
 +
*By specifying only two code words,&nbsp; neither the&nbsp; (6,2)&nbsp; code nor the&nbsp; (6,3)&nbsp; code can be excluded.
  
  
  
'''(2)'''&nbsp;  Da es sich um einen linearen Code handelt, muss die Modulo–$2$–Summe
+
'''(2)'''&nbsp;  Correct is the&nbsp; <u>solution suggestion 2</u>:
:(0,1,0,1,0,1)(1,0,0,1,1,0)=(1,1,0,0,1,1)
+
*Since this is a linear code,&nbsp; the modulo 2 sum must also be a valid code word:
ebenfalls ein gültiges Codewort sein. Ebenso das Nullwort:
+
:$$(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)\hspace{0.05cm}.$$
 +
*Likewise the all zero word:
 
:(0,1,0,1,0,1)(0,1,0,1,0,1)=(0,0,0,0,0,0).
 
:(0,1,0,1,0,1)(0,1,0,1,0,1)=(0,0,0,0,0,0).
Richtig ist somit <u>Antwort 2</u>.
 
  
  
  
'''(3)'''&nbsp; Richtig sind hier die <u>Aussagen 1 bis 3</u>. Basisvektoren der Generatormatrix G sind beispielsweise die beiden gegebenen Codeworte, woraus sich auch die Prüfmatrix '''H''' bestimmen lässt:
+
'''(3)'''&nbsp; Correct are here  the&nbsp; <u>statements 1 to 3</u>:
 +
*Basis vectors of the generator matrix&nbsp; G&nbsp; are, for example,&nbsp; the two given code words,&nbsp; from which the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; can also be determined:
 
:G(6,2)=(100110010101)H(6,2)=(001000110100100010010001).
 
:G(6,2)=(100110010101)H(6,2)=(001000110100100010010001).
 +
*In general,&nbsp; the&nbsp; k&nbsp; basis vectors of the generator matrix&nbsp; G&nbsp; form a&nbsp; k-dimensional subspace and the&nbsp; m×n&nbsp; matrix&nbsp; H&nbsp; (with m=nk)&nbsp; forms an orthogonal subspace of dimension&nbsp; m.
  
Allgemein wird durch die ''k'' Basisvektoren der Generatormatrix '''G''' ein ''k''–dimensionaler Untervektorraum aufgespannt und durch die m×n–Matrix '''H''' (mit m=nk) ein hierzu orthogonaler Untervektorraum der Dimension ''m''.
 
<u>Anmerkung:</u> Der hier angegebene
 
:C(6,2)={(0,0,0,0,0,0),(0,1,0,1,0,1),(1,0,0,1,1,0),(1,1,0,0,1,1)}
 
 
ist nicht sonderlich effektiv, da p1=x3 stets 0 ist. Durch Punktierung kommt man zum Code
 
:C(5,2)={(0,0,0,0,0),(0,1,1,0,1),(1,0,1,1,0),(1,1,0,1,1)}
 
  
mit gleicher Minimaldistanz $d_{\rm min} = 3$, aber größerer Coderate $R = 2/5 gegenüber R = 1/3$.
+
<u>Note:</u> The code given here
 +
:$$\mathcal{C}_{(6,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm} (1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 0, 1, 1) \}$$
  
'''(4)'''&nbsp; [[File:P_ID2405__KC_A_1_10d_neu.png|right|frame|Codes gemäß <b>G</b><sub>A</sub>, <b>G</b><sub>B</sub>, <b>G</b><sub>C</sub>]]
+
is not very effective,&nbsp; since $p_{1} = x_{3}$&nbsp; is always zero.&nbsp; By puncturing this redundant bit you get the code
Die drei Zeilen $g_{1}, g_{2} {\rm und} g_{3}$ der Matrix \boldsymbol{ {\rm G}}_{\rm A} sind als Basisvektoren geeignet, da sie linear unabhängig sind, das heißt, es gilt
+
:$$\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 1, 0, 1), \hspace{0.3cm} (1, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 1, 1) \}$$
:$$\underline{g}_1 \oplus \underline{g}_2 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_3\hspace{0.05cm},\\ \underline{g}_1 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_2\hspace{0.05cm},\\ \underline{g}_2 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_1\hspace{0.05cm}.$$
 
  
Gleiches gilt für Matrix $\boldsymbol{ {\rm G}}_{\rm B}$. Die Basisvektoren sind hier so gewählt, dass der Code auch systematisch ist.
+
with the same minimum distance&nbsp; $d_{\rm min} = 3$,&nbsp; but larger code rate&nbsp; R = 2/5&nbsp; compared to&nbsp; R = 1/3.
  
Für die letzte Generatormatrix gilt: \underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3} ⇒ der Rang der Matrix (2) ist kleiner als deren Ordnung (3). Hier führt nicht nur \underline{u} = (0, 0, 0) zum Codewort (0, 0, 0, 0, 0, 0), sondern auch \underline{u} = (1, 1, 1). Richtig sind die <u>Lösungsvorschläge 1 und 2</u>.
 
  
  
 +
'''(4)'''&nbsp;  Correct are the&nbsp; <u>suggested solutions 1 and 2</u>:
 +
*The three rows&nbsp; g_1, \ g_2 and g_3&nbsp; of the matrix&nbsp; \mathbf{G}_{\rm A}&nbsp; are suitable as basis vectors,&nbsp; since they are linearly independent,&nbsp; that is,&nbsp; it holds
 +
:$$\underline{g}_1 \oplus \underline{g}_2 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_3\hspace{0.05cm},\hspace{0.5cm}
 +
\underline{g}_1 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_2\hspace{0.05cm},\hspace{0.5cm}
 +
\underline{g}_2 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_1\hspace{0.05cm}.$$
 +
*The same is true for matrix&nbsp; \mathbf{G}_{\rm B}.&nbsp; The basis vectors are chosen here so that the code is also systematic.
  
 +
*For the last generator matrix holds:&nbsp; \underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3} &nbsp; ⇒ &nbsp; the rank of matrix&nbsp; (2)&nbsp; is smaller than its order&nbsp; (2).
 +
 +
*Here not only&nbsp;  \underline{u} = (0, 0, 0)&nbsp; leads to the code word&nbsp; (0, 0, 0, 0, 0),&nbsp; but also&nbsp; \underline{u} = (1, 1, 1).
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^1.4 Beschreibung linearer Blockcodes
+
[[Category:Channel Coding: Exercises|^1.4 Linear Block Code Description^]]
 
 
^]]
 

Latest revision as of 18:57, 1 November 2022

Considered generator matrices

We now consider various binary codes of uniform length  n.  All codes of the form

\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1,\ x_2, \ \text{...} \ \hspace{0.05cm},\ x_n) \hspace{0.5cm}\text{with} \hspace{0.5cm} x_i \hspace{-0.15cm}\ \in \ \hspace{-0.15cm} \{ 0,\ 1 \},\hspace{0.2cm} i = 1, \hspace{0.05cm} \text{...} \ \hspace{0.05cm}, n

can be represented and interpreted in an  n-dimensional vector space.   ⇒   {\rm GF}(2^n).

The  k×n  generator matrix  \mathbf{G}  (matrix with  k  rows and  n  columns)  yields a  (n, \, k)  code,  but only if the rank of the matrix  \mathbf{G}  is also equal  k.  Further holds:

  • Each code  \mathcal{C}  spans a  k-dimensional linear subspace of the Galois field  {\rm GF}(2^n).
  • As basis vectors of this subspace,  k  independent code words of  \mathcal{C}  can be used.  There is no further restriction for the basis vectors.
  • The parity-check matrix  \mathbf{H}  also spans a subspace of  {\rm GF}(2^n).  But this has dimension  m = n - k  and is orthogonal to the subspace based on  \mathbf{G}.
  • For a linear code   ⇒   \underline{x} = \underline{u} \cdot \boldsymbol{ {\rm G}},  where  \underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})  indicates the information word.  A systematic code exists if  x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}  holds.
  • In a systematic code,  there is a simple relationship between  \mathbf{G}  and  \mathbf{H}.  For more details,  see the  "Theory Section".



Hints :

  • For the whole exercise holds  n = 6.
  • In the subtask  (4)  it is to be clarified which of the matrices  \boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B} resp. \boldsymbol{ {\rm G}}_{\rm C}  result in a  (6, \, 3)  block code with the code words listed below:
( 0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 0, 1, 0, 1, 1), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm}(0, 1, 1, 1, 1, 0), \hspace{0.3cm} ( 1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1), \hspace{0.3cm}(1, 1, 0, 0, 1, 1), \hspace{0.3cm}(1, 1, 1, 0, 0, 0)\hspace{0.05cm}.


Questions

1

Known are only the two code words  (0, 1, 0, 1, 0, 1)  and  (1, 0, 0, 1, 1, 0)  of a linear code.  Which statements are true?

It could be a  (5, \, 2)  code.
It could be a  (6, \, 2)  code.
It could be a  (6, \, 3)  code.

2

What are the four code words of the linear  (6, \, 2)  code explicitly?

(0 0 1 0 1 1), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 0 0 1 1).
(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 0 0 1 1).
(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 1 0 0 0).

3

Which statements are true for this  (6, \, 2)  code  \mathcal{C}?

For all code words  (i = 1,\hspace{0.05cm} \text{ ...} \ , 4)   ⇒   \underline{x}_{i} \in {\rm GF}(2^6).
\mathcal{C}  is a two-dimensional linear subvector space of  {\rm GF}(2^6).
\mathbf{G}  gives basis vectors of this subvector space  {\rm GF}(2^2).
\mathbf{G}  and  \mathbf{H}  are each  2×6  matrices.

4

Which of the generator matrices given in the graphic result in a  (6, \, 3)  code?

The generator matrix  \boldsymbol{ {\rm G}}_{\rm A},
the generator matrix  \boldsymbol{ {\rm G}}_{\rm B},
the generator matrix  \boldsymbol{ {\rm G}}_{\rm C}.


Solution

(1)  Correct are the  suggested solutions 2 and 3:

  • The code word length is  n = 6   ⇒  the  (5, \, 2)  code is not eligible.
  • For a  (6, \, 2)  code,  there are  2^2 = 4  distinct code words,  and for the  (6, \, 3)  code,  there are correspondingly  2^3 = 8.
  • By specifying only two code words,  neither the  (6, \, 2)  code nor the  (6, \, 3)  code can be excluded.


(2)  Correct is the  solution suggestion 2:

  • Since this is a linear code,  the modulo 2 sum must also be a valid code word:
(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)\hspace{0.05cm}.
  • Likewise the all zero word:
(0, 1, 0, 1, 0, 1) \oplus (0, 1, 0, 1, 0, 1) = (0, 0, 0, 0, 0, 0)\hspace{0.05cm}.


(3)  Correct are here the  statements 1 to 3:

  • Basis vectors of the generator matrix  \mathbf{G}  are, for example,  the two given code words,  from which the parity-check matrix  \mathbf{H}  can also be determined:
{ \boldsymbol{\rm G}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 0 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 1 &0 &0 &0 &1 &0\\ 0 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.
  • In general,  the  k  basis vectors of the generator matrix  \mathbf{G}  form a  k-dimensional subspace and the  m×n  matrix  \mathbf{H}  (with m = n - k)  forms an orthogonal subspace of dimension  m.


Note: The code given here

\mathcal{C}_{(6,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm} (1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 0, 1, 1) \}

is not very effective,  since p_{1} = x_{3}  is always zero.  By puncturing this redundant bit you get the code

\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 1, 0, 1), \hspace{0.3cm} (1, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 1, 1) \}

with the same minimum distance  d_{\rm min} = 3,  but larger code rate  R = 2/5  compared to  R = 1/3.


(4)  Correct are the  suggested solutions 1 and 2:

  • The three rows  g_1, \ g_2 and g_3  of the matrix  \mathbf{G}_{\rm A}  are suitable as basis vectors,  since they are linearly independent,  that is,  it holds
\underline{g}_1 \oplus \underline{g}_2 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_3\hspace{0.05cm},\hspace{0.5cm} \underline{g}_1 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_2\hspace{0.05cm},\hspace{0.5cm} \underline{g}_2 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_1\hspace{0.05cm}.
  • The same is true for matrix  \mathbf{G}_{\rm B}.  The basis vectors are chosen here so that the code is also systematic.
  • For the last generator matrix holds:  \underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}   ⇒   the rank of matrix  (2)  is smaller than its order  (2).
  • Here not only  \underline{u} = (0, 0, 0)  leads to the code word  (0, 0, 0, 0, 0),  but also  \underline{u} = (1, 1, 1).