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 ⇒ 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

Musterlösung

Solution

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

	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.

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