Aufgaben:Exercise 1.10: Some Generator Matrices

• Return to book

Betrachtete Generatormatrizen

Wir betrachten nun verschiedene Binärcodes einheitlicher Länge  $n$. Alle Codes der Form

$$\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1, x_2, \ \text{...} \ \hspace{0.05cm}, x_n) \hspace{0.5cm}\text{mit} \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$$

lassen sich in einem  $n$–dimensionalen Vektorraum darstellen und interpretieren   ⇒   ${\rm GF}(2^n)$.

Durch eine  $k×n$–Generatormatrix  $\mathbf{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  $\mathbf{G}$  ebenfalls gleich  $k$  ist. Weiter gilt:

• Jeder Code  $\mathcal{C}$  spannt einen  $k$–dimensionalen linearen Untervektorraum des Galoisfelds  ${\rm GF}(2^n)$  auf.

• Als Basisvektoren dieses Untervektorraums können  $k$  unabhängige Codeworte von  $\mathcal{C}$  verwendet werden. Eine weitere Einschränkung gibt es für die Basisvektoren nicht.

• Die Prüfmatrix  $\mathbf{H}$  spannt ebenfalls einen Untervektorraum von  ${\rm GF}(2^n)$  auf. Dieser hat aber die Dimension  $m = n - k$  und ist orthogonal zum Untervektorraum, der auf  $\mathbf{G}$  basiert.

• Bei einem linearen Code gilt  $\underline{x} = \underline{u} · \boldsymbol{ {\rm G}}$, wobei  $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$  das Informationswort angibt. Ein systematischer Code liegt vor, wenn  $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$  gilt.

• Bei einem systematischen Code besteht ein einfacher Zusammenhang zwischen  $\mathbf{G}$  und  $\mathbf{H}$. Nähere Angaben hierzu finden Sie im  Theorieteil.

Hinweise :

• Die Aufgabe gehört zum Kapitel  Allgemeine Beschreibung linearer Blockcodes.
• Für die gesamte Aufgabe gilt  $n = 6$.
• In der Teilaufgabe (4) soll geklärt werden, welche der Matrizen  $\boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B}$ bzw. $ \boldsymbol{ {\rm G}}_{\rm C}$  zu einem $(6, \, 3)$–Blockcode mit den nachfolgend aufgeführten Codeworten führen:

$$ ( 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{0.1cm} ( 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}.$$

Fragebogen

1

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?

	Es könnte sich um einen  $(5, \, 2)$–Code handeln.
	Es könnte sich um einen  $(6, \, 2)$–Code handeln.
	Es könnte sich um einen  $(6, \, 3)$–Code handeln.

2

Wie lauten die vier Codeworte des linearen  $(6, \, 2)$–Codes explizit?

	$(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

Welche Aussagen gelten für diesen  $(6, \, 2)$–Code $C$?

	Für alle Codeworte  $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$  gilt  $\underline{x}_{i} \in {\rm GF}(2^6)$.
	$C$  ist ein zweidimensionaler linearer Untervektorraum von  ${\rm GF}(2^6)$.
	$\mathbf{G}$  gibt Basisvektoren dieses Untervektorraumes  ${\rm GF} (2^2)$  an.
	$\mathbf{G}$  und  $\mathbf{H}$  sind jeweils  $2×6$–Matrizen.

4

Welche der in der Grafik angegebenen Generatormatrizen führen zu einem  $(6, \, 3)$–Code?

	Die Generatormatrix  $\boldsymbol{ {\rm G}}_{\rm A}$,
	die Generatormatrix  $\boldsymbol{ {\rm G}}_{\rm B}$,
	die Generatormatrix  $\boldsymbol{ {\rm G}}_{\rm C}$.

Musterlösung

Solution

(1)  Richtig sind die Lösungsvorschläge 2 und 3:

• Die Codewortlänge ist $n = $6  ⇒  der $(5, \, 2)$–Code kommt nicht in Frage.
• Bei einem $(6, \, 2)$–Code gibt es $2^2 = 4$ verschiedene Codeworte und beim $(6, \, 3)$–Code entsprechend $2^3 = 8$.
• Durch die Angabe von nur zwei Codeworten lässt sich weder der $(6, \, 2)$–Code noch der $(6, \, 3)$–Code ausschließen.

(2)  Richtig ist der Lösungsvorschlag 2:

• Da es sich um einen linearen Code handelt, muss die Modulo–$2$–Summe ebenfalls ein gültiges Codewort sein:

$$(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)\hspace{0.05cm}.$$

• Ebenso das Nullwort:

$$(0, 1, 0, 1, 0, 1) \oplus (0, 1, 0, 1, 0, 1) = (0, 0, 0, 0, 0, 0)\hspace{0.05cm}.$$

(3)  Richtig sind hier die Aussagen 1 bis 3:

• Basisvektoren der Generatormatrix $\mathbf{G}$ sind zum Beispiel die zwei gegebenen Codeworte, woraus sich auch die Prüfmatrix $\mathbf{H}$ bestimmen lässt:

$${ \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}.$$

• Allgemein wird durch die $k$ Basisvektoren der Generatormatrix $\mathbf{G}$ ein $k$–dimensionaler Untervektorraum aufgespannt und durch die $m×n$–Matrix $\mathbf{H}$ (mit $m = n - k$) ein hierzu orthogonaler Untervektorraum der Dimension $m$.

Anmerkung: Der hier angegebene Code

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

ist nicht sonderlich effektiv, da $p_{1} = x_{3}$ stets $0$ ist. Durch Punktierung dieses redundanten Bits kommt man zum Code

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

mit gleicher Minimaldistanz $d_{\rm min} = 3$, aber größerer Coderate $R = 2/5$ gegenüber $R = 1/3$.

(4)  Richtig sind die Lösungsvorschläge 1 und 2:

• Die drei Zeilen $g_1, \ g_2$ und $g_3$ der Matrix $\mathbf{G}_{\rm A}$ sind als Basisvektoren geeignet, da sie linear unabhängig sind, das heißt, es gilt

$$\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}.$$

• Gleiches gilt für Matrix $\mathbf{G}_{\rm B}$. Die Basisvektoren sind hier so gewählt, dass der Code auch systematisch ist.

• 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)$.