Difference between revisions of "Aufgaben:Exercise 1.10: Some Generator Matrices"
From LNTwww
(Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes }} [[File:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-C…“) |
|||
| Line 3: | Line 3: | ||
}} | }} | ||
| − | [[File:|right|]] | + | [[File:P_ID2404__KC_A_1_10.png|right|frame|Betrachtete 3×6–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 [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Theorieteil]]. | ||
| + | |||
| + | |||
| + | ''Hinweis: '' | ||
| + | |||
| + | |||
| + | 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=== | ||
Revision as of 20:47, 7 December 2017
Betrachtete 3×6–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
1.
2.
3.
4.
5.
6.
7.
