Aufgaben:Exercise 1.10: Some Generator Matrices

• Return to book

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

Solution

1. 2. 3. 4. 5. 6. 7.