Aufgaben:Aufgabe 1.08Z: Äquivalente Codes: Unterschied zwischen den Versionen
Aus LNTwww
Wael (Diskussion | Beiträge) |
|||
(12 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
Zeile 3: | Zeile 3: | ||
}} | }} | ||
− | [[Datei:P_ID2394__KC_Z_1_8.png|right|frame|Vier | + | [[Datei:P_ID2394__KC_Z_1_8.png|right|frame|Vier $(6, 3)$–Blockcodes]] |
− | In der Grafik sind die Zuordnungen $\underline{u} | + | In der Grafik sind die Zuordnungen $\underline{u} \rightarrow \underline{x}$ für verschiedene Codes angegeben, die im Folgenden jeweils durch die Generatormatrix $\boldsymbol{\rm G}$ und die Prüfmatrix $\boldsymbol{\rm H}$ charakterisiert werden: |
− | *$ | + | *${\boldsymbol{\rm Code \ A}}$: |
− | :$${ \boldsymbol{\rm G}}_{\rm A} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}, | + | :$${ \boldsymbol{\rm G}}_{\rm A} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm A} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 1 &0 &1 &0 &1 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$ |
− | |||
− | *$ | + | *${\boldsymbol{\rm Code \ B}}$: |
− | :$${ \boldsymbol{\rm G}}_{\rm B} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}, | + | :$${ \boldsymbol{\rm G}}_{\rm B} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm} { \boldsymbol{\rm H}}_{\rm B} = \begin{pmatrix} 1 &0 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$ |
− | |||
− | *$ | + | *${\boldsymbol{\rm Code \ C}}$: |
− | :$${ \boldsymbol{\rm G}}_{\rm C} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1\\ 0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},{ \boldsymbol{\rm H}}_{\rm C} = \begin{pmatrix} 1 &0 &1 &1 &0 &0\\ 0 &1 &1 &0 &1 &0\\ 1 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$ | + | :$${ \boldsymbol{\rm G}}_{\rm C} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1\\ 0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm C} = \begin{pmatrix} 1 &0 &1 &1 &0 &0\\ 0 &1 &1 &0 &1 &0\\ 1 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$ |
− | *$ | + | *${\boldsymbol{\rm Code \ D}}$: |
− | :$${ \boldsymbol{\rm G}}_{\rm D} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0 \end{pmatrix} \hspace{0.05cm},{ \boldsymbol{\rm H}}_{\rm D} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0\\ 1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$ | + | :$${ \boldsymbol{\rm G}}_{\rm D} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm D} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0\\ 1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$ |
− | In dieser Aufgabe soll untersucht werden, welche dieser Codes bzw. Codepaare | + | In dieser Aufgabe soll untersucht werden, welche dieser Codes bzw. Codepaare |
*systematisch sind, | *systematisch sind, | ||
− | *identisch sind (das heißt: Verschiedene Codes haben gleiche Codeworte), | + | *identisch sind (das heißt: Verschiedene Codes haben gleiche Codeworte), |
− | *äquivalent sind (das heißt: Verschiedene Codes haben gleiche Codeparameter). | + | *äquivalent sind (das heißt: Verschiedene Codes haben gleiche Codeparameter). |
− | |||
− | Die Aufgabe gehört zum | + | Hinweise: |
− | + | ||
+ | *Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|"Allgemeine Beschreibung linearer Blockcodes"]]. | ||
+ | |||
+ | *Bezug genommen wird insbesondere auf die Seiten [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|"Systematische Codes"]] sowie [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Identische_Codes|"Identische Codes"]]. | ||
+ | |||
+ | *Anzumerken ist, dass die Angabe einer Prüfmatrix $\boldsymbol{\rm H}$ nicht eindeutig ist. Verändert man die Reihenfolge der Gleichungen, entspricht dies der Vertauschung von Zeilen. | ||
+ | |||
+ | |||
===Fragebogen=== | ===Fragebogen=== | ||
Zeile 38: | Zeile 42: | ||
{Welche der nachfolgend aufgeführten Codes sind systematisch? | {Welche der nachfolgend aufgeführten Codes sind systematisch? | ||
|type="[]"} | |type="[]"} | ||
− | + Code A, | + | + Code $\rm A$, |
− | - Code B, | + | - Code $\rm B$, |
− | + Code C, | + | + Code $\rm C$, |
− | + Code D. | + | + Code $\rm D$. |
{Welche der vorgegebenen Codepaare sind identisch? | {Welche der vorgegebenen Codepaare sind identisch? | ||
|type="[]"} | |type="[]"} | ||
− | + Code A und Code B, | + | + Code $\rm A$ und Code $\rm B$, |
− | -Code B und Code C, | + | - Code $\rm B$ und Code $\rm C$, |
− | -Code C und Code D. | + | - Code $\rm C$ und Code $\rm D$. |
− | {Welche der gegebenen Codepaare sind äquivalent, aber nicht identisch? | + | {Welche der gegebenen Codepaare sind äquivalent, aber nicht identisch? |
|type="[]"} | |type="[]"} | ||
− | - Code A und Code B, | + | - Code $\rm A$ und Code $\rm B$, |
− | + Code B und Code C, | + | + Code $\rm B$ und Code $\rm C$, |
− | - Code C und Code D. | + | - Code $\rm C$ und Code $\rm D$. |
− | {Wie unterscheiden sich die Generatormatrizen $G_{\rm B}$ und $G_{\ rm C}$? | + | {Wie unterscheiden sich die Generatormatrizen $G_{\rm B}$ und $G_{\rm C}$? |
|type="[]"} | |type="[]"} | ||
− | -Durch verschiedene Linearkombinationen verschiedener Zeilen. | + | - Durch verschiedene Linearkombinationen verschiedener Zeilen. |
− | - Durch zyklische Vertauschung der Zeilen um 1 nach unten. | + | - Durch zyklische Vertauschung der Zeilen um $1$ nach unten. |
− | + Durch zyklische Vertauschung der Spalten um 1 nach rechts. | + | + Durch zyklische Vertauschung der Spalten um $1$ nach rechts. |
− | {Bei welchen Codes gilt ${ \boldsymbol{\rm H}} | + | {Bei welchen Codes gilt ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$? |
|type="[]"} | |type="[]"} | ||
− | + Code A, | + | + Code $\rm A$, |
− | + Code B, | + | + Code $\rm B$, |
− | + Code C, | + | + Code $\rm C$, |
− | + Code D. | + | + Code $\rm D$. |
+ | |||
Zeile 78: | Zeile 83: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' Richtig sind die <u>Antworten 1, 3 und 4</u>: |
+ | *Für einen systematischen $(6, 3)$–Blockcode muss gelten: | ||
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, u_3, p_1, p_2, p_{3}) \hspace{0.05cm}.$$ | :$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, u_3, p_1, p_2, p_{3}) \hspace{0.05cm}.$$ | ||
− | Diese Bedingung erfüllen | + | *Diese Bedingung erfüllen Code $\rm A$, Code $\rm C$ und Code $\rm D$, nicht aber Code $\rm B$. |
+ | |||
+ | |||
+ | |||
+ | '''(2)''' Richtig ist nur <u>Antwort 1</u>: | ||
+ | *Nur Code $\rm A$ und Code $\rm B$ sind identische Codes. Sie beinhalten genau die gleichen Codeworte und unterscheiden sich nur durch andere Zuordnungen $\underline{u} \rightarrow \underline{x}$. | ||
+ | |||
+ | *Wie in der Musterlösung zur [[Aufgaben:1.08_Identische_Codes|"Aufgabe A1.8 (3)"]] angegeben, gelangt man von der Generatormatrix ${ \boldsymbol{\rm G}}_{\rm B}$ zur Generatormatrix ${ \boldsymbol{\rm G}}_{\rm A}$ | ||
+ | :*allein durch Vertauschen/Permutieren von Zeilen, oder | ||
+ | :*durch Ersetzen einer Zeile durch die Linearkombination zwischen dieser Zeile und einer anderen. | ||
+ | |||
+ | |||
+ | |||
+ | '''(3)''' Richtig ist somit allein <u>Antwort 2</u>: | ||
+ | *Code $\rm A$ und Code $\rm B$ sind mehr als äquivalent, nämlich identisch. | ||
+ | |||
+ | *Code $\rm C$ und Code $\rm D$ unterscheiden sich durch die minimale Hamming–Distanz $d_{\rm min} = 3$ bzw. $d_{\rm min} = 2$ und sind somit auch nicht äquivalent. | ||
+ | |||
+ | *Code $\rm B$ und Code $\rm C$ zeigen dagegen gleiche Eigenschaften, beispielsweise gilt für beide $d_{\rm min} = 3$. Sie beinhalten aber andere Codeworte. | ||
+ | |||
− | |||
− | |||
− | Richtig ist | + | '''(4)''' Richtig ist <u>Antwort 3</u>: |
− | + | *Die letzte Spalte von ${ \boldsymbol{\rm G}}_{\rm B}$ ergibt die erste Spalte von ${ \boldsymbol{\rm G}}_{\rm C}$. | |
+ | *Die erste Spalte von ${ \boldsymbol{\rm G}}_{\rm B}$ ergibt die zweite Spalte von ${ \boldsymbol{\rm G}}_{\rm C}$. | ||
+ | *Die zweite Spalte von ${ \boldsymbol{\rm G}}_{\rm B}$ ergibt die dritte Spalte von ${ \boldsymbol{\rm G}}_{\rm C}$, usw. | ||
− | |||
− | |||
− | |||
− | '''(5)''' Die Bedingung ${ \boldsymbol{\rm H}} | + | '''(5)''' Alle Aussagen treffen zu</u>: |
+ | *Die Bedingung ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$ gilt für alle linearen Codes. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Zeile 103: | Zeile 126: | ||
− | [[Category:Aufgaben zu Kanalcodierung|^1.4 | + | [[Category:Aufgaben zu Kanalcodierung|^1.4 Beschreibung linearer Blockcodes |
^]] | ^]] |
Aktuelle Version vom 11. Juli 2022, 13:09 Uhr
In der Grafik sind die Zuordnungen $\underline{u} \rightarrow \underline{x}$ für verschiedene Codes angegeben, die im Folgenden jeweils durch die Generatormatrix $\boldsymbol{\rm G}$ und die Prüfmatrix $\boldsymbol{\rm H}$ charakterisiert werden:
- ${\boldsymbol{\rm Code \ A}}$:
- $${ \boldsymbol{\rm G}}_{\rm A} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm A} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 1 &0 &1 &0 &1 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
- ${\boldsymbol{\rm Code \ B}}$:
- $${ \boldsymbol{\rm G}}_{\rm B} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm} { \boldsymbol{\rm H}}_{\rm B} = \begin{pmatrix} 1 &0 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
- ${\boldsymbol{\rm Code \ C}}$:
- $${ \boldsymbol{\rm G}}_{\rm C} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1\\ 0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm C} = \begin{pmatrix} 1 &0 &1 &1 &0 &0\\ 0 &1 &1 &0 &1 &0\\ 1 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$
- ${\boldsymbol{\rm Code \ D}}$:
- $${ \boldsymbol{\rm G}}_{\rm D} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm D} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0\\ 1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
In dieser Aufgabe soll untersucht werden, welche dieser Codes bzw. Codepaare
- systematisch sind,
- identisch sind (das heißt: Verschiedene Codes haben gleiche Codeworte),
- äquivalent sind (das heißt: Verschiedene Codes haben gleiche Codeparameter).
Hinweise:
- Die Aufgabe gehört zum Kapitel "Allgemeine Beschreibung linearer Blockcodes".
- Bezug genommen wird insbesondere auf die Seiten "Systematische Codes" sowie "Identische Codes".
- Anzumerken ist, dass die Angabe einer Prüfmatrix $\boldsymbol{\rm H}$ nicht eindeutig ist. Verändert man die Reihenfolge der Gleichungen, entspricht dies der Vertauschung von Zeilen.
Fragebogen
Musterlösung
(1) Richtig sind die Antworten 1, 3 und 4:
- Für einen systematischen $(6, 3)$–Blockcode muss gelten:
- $$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, u_3, p_1, p_2, p_{3}) \hspace{0.05cm}.$$
- Diese Bedingung erfüllen Code $\rm A$, Code $\rm C$ und Code $\rm D$, nicht aber Code $\rm B$.
(2) Richtig ist nur Antwort 1:
- Nur Code $\rm A$ und Code $\rm B$ sind identische Codes. Sie beinhalten genau die gleichen Codeworte und unterscheiden sich nur durch andere Zuordnungen $\underline{u} \rightarrow \underline{x}$.
- Wie in der Musterlösung zur "Aufgabe A1.8 (3)" angegeben, gelangt man von der Generatormatrix ${ \boldsymbol{\rm G}}_{\rm B}$ zur Generatormatrix ${ \boldsymbol{\rm G}}_{\rm A}$
- allein durch Vertauschen/Permutieren von Zeilen, oder
- durch Ersetzen einer Zeile durch die Linearkombination zwischen dieser Zeile und einer anderen.
(3) Richtig ist somit allein Antwort 2:
- Code $\rm A$ und Code $\rm B$ sind mehr als äquivalent, nämlich identisch.
- Code $\rm C$ und Code $\rm D$ unterscheiden sich durch die minimale Hamming–Distanz $d_{\rm min} = 3$ bzw. $d_{\rm min} = 2$ und sind somit auch nicht äquivalent.
- Code $\rm B$ und Code $\rm C$ zeigen dagegen gleiche Eigenschaften, beispielsweise gilt für beide $d_{\rm min} = 3$. Sie beinhalten aber andere Codeworte.
(4) Richtig ist Antwort 3:
- Die letzte Spalte von ${ \boldsymbol{\rm G}}_{\rm B}$ ergibt die erste Spalte von ${ \boldsymbol{\rm G}}_{\rm C}$.
- Die erste Spalte von ${ \boldsymbol{\rm G}}_{\rm B}$ ergibt die zweite Spalte von ${ \boldsymbol{\rm G}}_{\rm C}$.
- Die zweite Spalte von ${ \boldsymbol{\rm G}}_{\rm B}$ ergibt die dritte Spalte von ${ \boldsymbol{\rm G}}_{\rm C}$, usw.
(5) Alle Aussagen treffen zu:
- Die Bedingung ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$ gilt für alle linearen Codes.