Aufgaben:Aufgabe 1.10: Einige Generatormatrizen: Unterschied zwischen den Versionen
Wael (Diskussion | Beiträge) |
|||
Zeile 109: | Zeile 109: | ||
− | [[Category:Aufgaben zu Kanalcodierung|^1.4 | + | [[Category:Aufgaben zu Kanalcodierung|^1.4 Beschreibung linearer Blockcodes |
^]] | ^]] |
Version vom 12. Dezember 2017, 14:49 Uhr
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
(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)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.