Aufgaben:Aufgabe 1.10: Einige Generatormatrizen

• Zurück zum Buch

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 ⇒ GF$(2^n)$.

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($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 H spannt ebenfalls einen Untervektorraum von GF$(2^n)$ auf. Dieser hat aber die Dimension $m = n – k$ und ist orthogonal zum Untervektorraum, der auf 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 G und H. Nähere Angaben hierzu finden Sie im Theorieteil.

Hinweis:

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

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 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, ... , 4)$ gilt $\underline{x}_{i} \in {\rm GF}(2^6)$.
	C ist ein 2–dimensionaler linearer Untervektorraum von GF$(2^6)$.
	G gibt Basisvektoren dieses Untervektorraumes GF$(2^2)$ an.
	G und H sind jeweils 2×6–Matrizen.

4

Welche der Generatormatrizen (siehe Grafik) führen zu einem (6, 3)–Code?

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

Musterlösung

Musterlösung

(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 G sind beispielsweise die beiden gegebenen Codeworte, woraus sich auch die Prüfmatrix 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 G ein k–dimensionaler Untervektorraum aufgespannt und durch die $m×n$–Matrix 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äß G_A, G_B, G_C

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

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

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.