Exercise 1.10: Some Generator Matrices

Betrachtete 3&times6–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, ... \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)$ .

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 $C$ spannt einen $k$ –dimensionalen linearen Untervektorraum des Galoisfeldes $\rm GF(2^n$ ) 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 $\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}, \, ... \, , \, u_{k})$ das Informationswort angibt. Ein systematischer Code liegt vor, wenn $x_{1} = u_{1}, \, ... \, , \, 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 bezieht sich auf das 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:

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

Fragebogen

Musterlösung

Solution

(1) 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 zwei Codeworten lässt sich weder der

$(6, \, 2)$ – noch der

$(6, \, 3)$ –Code ausschließen ⇒ Antwort 2 und 3.

(2) Da es sich um einen linearen Code handelt, muss die Modulo– $2$ –Summe

$(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)$

ebenfalls ein gültiges Codewort sein. 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}.$

Richtig ist somit Antwort 2.

(3) Richtig sind hier die Aussagen 1 bis 3. Basisvektoren der Generatormatrix $\mathbf{G}$ sind beispielsweise die beiden 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

$\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 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)

Codes gemäß

$\mathbf{G}_{\rm A}, \ \mathbf{G}_{\rm B}, \ \mathbf{G}_{\rm C}$

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},$

$\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 $\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)$ . Richtig sind die Lösungsvorschläge 1 und 2.

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

	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.

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

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