Aufgaben:Aufgabe 1.10: Einige Generatormatrizen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 5: Zeile 5:
 
[[Datei:P_ID2404__KC_A_1_10.png|right|frame|Betrachtete 3&times6–Generatormatrizen]]
 
[[Datei:P_ID2404__KC_A_1_10.png|right|frame|Betrachtete 3&times6–Generatormatrizen]]
  
Wir betrachten nun verschiedene Binärcodes einheitlicher Länge ''n''. Alle Codes der Form
+
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},$$
 
:$$\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$$
 
:$$ 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)$.
+
lassen sich in einem $n$–dimensionalen Vektorraum darstellen und interpretieren ⇒ $\rm 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:
+
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 GF($2^n$) auf.
+
*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.
+
*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.
+
*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 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 [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Theorieteil]].
+
*Bei einem systematischen Code besteht ein einfacher Zusammenhang zwischen $\mathbf{G}$ und $\mathbf{H}$. Nähere Angaben hierzu finden Sie im [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Theorieteil]].
  
  
''Hinweis: ''
+
''Hinweise: ''
 +
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|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}.$$
  
Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|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===
 
===Fragebogen===
 
 
<quiz display=simple>
 
<quiz display=simple>
 
{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?
 
{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?
 
|type="[]"}
 
|type="[]"}
- Es könnte sich um einen (5, 2)–Code handeln.
+
- 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, \, 2)$–Code handeln.
+ Es könnte sich um einen (6, 3)–Code handeln.
+
+ Es könnte sich um einen $(6, \, 3)$–Code handeln.
  
  
{Wie lauten die Codeworte des linearen (6, 2)–Codes explizit?
+
{Wie lauten die Codeworte des linearen $(6, \, 2)$–Codes explizit?
 
|type="[]"}  
 
|type="[]"}  
- $(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 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 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).$
+
- $(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 1 0 0 0).$
  
  
{Welche Aussagen gelten für diesen (6, 2)–Code ''C''?
+
{Welche Aussagen gelten für diesen $(6, \, 2)$–Code $C$?
 
|type="[]"}
 
|type="[]"}
 
+ Für alle Codeworte $(i = 1, ... , 4)$ gilt $\underline{x}_{i} \in {\rm GF}(2^6)$.
 
+ 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)$.
+
+ $C$ ist ein 2–dimensionaler linearer Untervektorraum von $\rm GF(2^6)$.
+ '''G''' gibt Basisvektoren dieses Untervektorraumes GF$(2^2)$ an.
+
+ $\mathbf{G}$ gibt Basisvektoren dieses Untervektorraumes $GF \, (2^2)$ an.
- '''G''' und '''H''' sind jeweils 2×6–Matrizen.
+
- $\mathbf{G}$ und $\mathbf{H}$ sind jeweils $2×6$–Matrizen.
  
  
{Welche der Generatormatrizen (siehe Grafik) führen zu einem (6, 3)–Code?
+
{Welche der Generatormatrizen (siehe Grafik) führen zu einem $(6, \, 3)$–Code?
 
|type="[]"}
 
|type="[]"}
 
+ Generatormatrix $\boldsymbol{ {\rm G}}_{\rm A}$,
 
+ Generatormatrix $\boldsymbol{ {\rm G}}_{\rm A}$,

Version vom 20. Dezember 2017, 09:38 Uhr

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

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 $\rm GF(2^6)$.
$\mathbf{G}$ gibt Basisvektoren dieses Untervektorraumes $GF \, (2^2)$ an.
$\mathbf{G}$ und $\mathbf{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

(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äß GA, GB, GC

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.