Aufgaben:Aufgabe 4.6: Generierung von Produktcodes: Unterschied zwischen den Versionen
Wael (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Produktcodes }} [[Datei:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-Cho…“) |
|||
(21 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
− | {{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Produktcodes | + | {{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Produktcodes}} |
+ | [[Datei:P_ID3003__KC_A_4_6_v2.png|right|frame|Verwendete Komponentencodes]] | ||
+ | Es soll ein $\rm Produktcode \ (42, \ 12)$ generiert werden, der auf folgenden Komponentencodes aufbaut: | ||
+ | * dem Hammingcode $\rm HC \ (7, \ 4, \ 3)$ ⇒ $\mathcal{C}_1$, | ||
+ | * dem verkürzten Hammingcode $\rm HC \ (6, \ 3, \ 3)$ ⇒ $\mathcal{C}_2$. | ||
+ | Die entsprechenden Codetabellen sind rechts angegeben, wobei jeweils drei Zeilen unvollständig sind. Diese sollen von Ihnen ergänzt werden. | ||
+ | Das zu einem Informationsblock $\underline{u}$ gehörige Codewort ergibt sich allgemein entsprechend der Gleichung $\underline{x} = \underline{u} \cdot \mathbf{G}$. Wie auch in der [[Aufgaben:Aufgabe_4.6Z:_Grundlagen_der_Produktcodes|Aufgabe 4.6Z]] wird hier von folgenden Generatormatrizen ausgegangen: | ||
+ | :$${ \boldsymbol{\rm G}}_1 | ||
+ | = \begin{pmatrix} | ||
+ | 1 &0 &0 &0 &1 &0 &1 \\ | ||
+ | 0 &1 &0 &0 &1 &1 &0 \\ | ||
+ | 0 &0 &1 &0 &0 &1 &1 \\ | ||
+ | 0 &0 &0 &1 &1 &1 &1 | ||
+ | \end{pmatrix} \hspace{0.05cm},\hspace{0.8cm} | ||
+ | { \boldsymbol{\rm G}}_2 | ||
+ | = \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}.$$ | ||
+ | In der gesamten Aufgabe gelte für den Informationsblock: | ||
+ | :$${ \boldsymbol{\rm U}} | ||
+ | = \begin{pmatrix} | ||
+ | 0 &1 &1 &0 \\ | ||
+ | 0 &0 &0 &0 \\ | ||
+ | 1 &1 &1 &0 | ||
+ | \end{pmatrix} \hspace{0.05cm}.$$ | ||
+ | |||
+ | Gesucht sind entsprechend der Nomenklatur auf der Seite [[Kanalcodierung/Grundlegendes_zu_den_Produktcodes#Grundstruktur_eines_Produktcodes|Grundstruktur eines Produktcodes]]: | ||
+ | * die Parity–Matrix $\mathbf{P}^{(1)}$ bezüglich des horizontalen Codes $\mathcal{C}_1$, | ||
+ | * die Parity–Matrix $\mathbf{P}^{(2)}$ bezüglich des vertikalen Codes $\mathcal{C}_2$, | ||
+ | * die Checks–on–Checks–Matrix $\mathbf{P}^{(12)}$. | ||
− | |||
− | |||
− | |||
− | + | ''Hinweise:'' | |
− | + | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Grundlegendes_zu_den_Produktcodes| Grundlegendes zu den Produktcode]]. | |
− | | | + | *Bezug genommen wird insbesondere auf die Seite [[Kanalcodierung/Grundlegendes_zu_den_Produktcodes#Grundstruktur_eines_Produktcodes|Grundstruktur eines Produktcodes]]. |
− | + | *Die beiden Komponentencodes werden auch in der [[Aufgaben:Aufgabe_4.6Z:_Grundlagen_der_Produktcodes|Aufgabe 4.6Z]] behandelt. | |
− | |||
− | |||
− | |||
− | |||
+ | ===Fragebogen=== | ||
+ | <quiz display=simple> | ||
+ | {Welche Ergebnisse liefert die Zeilencodierung mit dem $(7, \ 4, \ 3)$–Code $\mathcal{C}_1$? | ||
+ | |type="[]"} | ||
+ | + 1. Zeile: $\underline{u} = (0, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 1)$. | ||
+ | - 2. Zeile: $\underline{u} = (0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$. | ||
+ | + 3. Zeile: $\underline{u} = (1, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0)$. | ||
+ | |||
+ | {Welche Ergebnisse liefert die Spaltencodierung mit dem $(6, \ 3, \ 3)$–Code $\mathcal{C}_2$? | ||
+ | |type="[]"} | ||
+ | + 1. Zeile: $\underline{u} = (0, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 1, \, 0, \, 1, \, 1)$. | ||
+ | + 2. Zeile: $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 0, \, 1, \, 1, \, 0, \, 1)$. | ||
+ | - 3. Zeile: $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 0, \, 0, \, 1, \, 1)$. | ||
+ | + 4. Zeile: $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \,0, \, 0)$. | ||
+ | |||
+ | {Welche Aussagen gelten für die Checks–on–Checks–Matrix? | ||
+ | |type="[]"} | ||
+ | + Die erste Zeile lautet $(1, \, 0, \, 1)$ und die erste Spalte $(1, \, 1, \, 0)$. | ||
+ | + Die zweite Zeile lautet $(1, \, 0, \, 1)$ und die zweite Spalte $(0, \, 0, \, 0)$. | ||
+ | - Die dritte Zeile lautet $(0, \, 0, \, 0)$ und die dritte Spalte $(0, \, 0, \, 0)$. | ||
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''1 | + | '''(1)''' Richtig sind die <u>Lösungsvorschläge 1 und 3</u>: |
− | + | ||
− | + | Allgemein gilt $\underline{x} = \underline{u} \cdot \mathbf{G}$. Daraus folgt für | |
− | + | * den ersten Zeilenvektor: | |
− | + | :$$\begin{pmatrix} | |
− | + | 0 &1 &1 &0 | |
− | + | \end{pmatrix} \cdot | |
− | {{ | + | \begin{pmatrix} |
+ | 1 &0 &0 &0 &1 &0 &1 \\ | ||
+ | 0 &1 &0 &0 &1 &1 &0 \\ | ||
+ | 0 &0 &1 &0 &0 &1 &1 \\ | ||
+ | 0 &0 &0 &1 &1 &1 &1 | ||
+ | \end{pmatrix} | ||
+ | =\begin{pmatrix} | ||
+ | 0 &1 &1 &0 &1 &0 &1 | ||
+ | \end{pmatrix} \hspace{0.05cm},$$ | ||
+ | |||
+ | * den zweiten Zeilenvektor: | ||
+ | :$$\begin{pmatrix} | ||
+ | 0 &0 &0 &0 | ||
+ | \end{pmatrix} \cdot | ||
+ | \begin{pmatrix} | ||
+ | 1 &0 &0 &0 &1 &0 &1 \\ | ||
+ | 0 &1 &0 &0 &1 &1 &0 \\ | ||
+ | 0 &0 &1 &0 &0 &1 &1 \\ | ||
+ | 0 &0 &0 &1 &1 &1 &1 | ||
+ | \end{pmatrix} | ||
+ | =\begin{pmatrix} | ||
+ | 0 &0 &0 &0 &0 &0 &0 | ||
+ | \end{pmatrix} \hspace{0.05cm},$$ | ||
+ | |||
+ | * den dritten Zeilenvektor | ||
+ | :$$\begin{pmatrix} | ||
+ | 1 &1 &1 &0 | ||
+ | \end{pmatrix} \cdot | ||
+ | \begin{pmatrix} | ||
+ | 1 &0 &0 &0 &1 &0 &1 \\ | ||
+ | 0 &1 &0 &0 &1 &1 &0 \\ | ||
+ | 0 &0 &1 &0 &0 &1 &1 \\ | ||
+ | 0 &0 &0 &1 &1 &1 &1 | ||
+ | \end{pmatrix} | ||
+ | =\begin{pmatrix} | ||
+ | 1 &1 &1 &0 &0 &0 &0 | ||
+ | \end{pmatrix} \hspace{0.05cm}.$$ | ||
+ | |||
+ | '''(2)''' Richtig sind die <u>Lösungsvorschläge 1, 2 und 4</u>: | ||
+ | :$$\begin{pmatrix} | ||
+ | 0 &0 &1 | ||
+ | \end{pmatrix} \cdot | ||
+ | \begin{pmatrix} | ||
+ | 1 &0 &0 &1 &1 &0 \\ | ||
+ | 0 &1 &0 &1 &0 &1 \\ | ||
+ | 0 &0 &1 &0 &1 &1 | ||
+ | \end{pmatrix} | ||
+ | =\begin{pmatrix} | ||
+ | 0 &0 &1 &0 &1 &1 | ||
+ | \end{pmatrix} \hspace{0.05cm},$$ | ||
+ | :$$\begin{pmatrix} | ||
+ | 1 &0 &1 | ||
+ | \end{pmatrix} \cdot | ||
+ | \begin{pmatrix} | ||
+ | 1 &0 &0 &1 &1 &0 \\ | ||
+ | 0 &1 &0 &1 &0 &1 \\ | ||
+ | 0 &0 &1 &0 &1 &1 | ||
+ | \end{pmatrix} | ||
+ | =\begin{pmatrix} | ||
+ | 1 &0 &1 &1 &0 &1 | ||
+ | \end{pmatrix} \hspace{0.05cm}.$$ | ||
+ | Zu dieser Teilaufgabe ist weiter anzumerken: | ||
+ | * Die angegebene erste Spalte ist schon allein deshalb richtig, weil sie mit einer Zeile (der dritten) der Generatormatrix $\mathbf{G}_2$ übereinstimmt. | ||
+ | * Die dritte Spalte des 2D–Codewortes müsste mit der zweiten Spalte identisch sein, da vom gleichen Codewort $(1, \, 0, \, 1)$ ausgegangen wird. | ||
+ | * Der angegebene Vektor $(1, \, 1, \, 0, \, 0, \, 1, \, 1)$ kann aber schon allein deshalb nicht richtig sein, da $\mathcal{C}_2$ ebenso wie $\mathcal{C}_1$ ein systematischer Code ist. | ||
+ | * Auch der verkürzte $(6, \ 3, \ 3)$–Hammingcode $C_2$ ist linear, so dass die Zuordnung $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$ auch ohne Rechnung angebbar ist. | ||
− | |||
+ | [[Datei:P_ID3005__KC_A_4_6c_v1.png|right|frame|Vollständige Codetabellen]] | ||
+ | '''(3)''' Rechts angegeben sind die vollständigen Codetabellen | ||
+ | * des Hammingcodes $(7, \ 4, \ 3)$, und | ||
+ | * des verkürzten Hammingcodes $(6, \ 3, \ 3)$. | ||
+ | Man erkennt daraus (ohne dass das für diese Aufgabe von Interesse ist), dass die hier betrachteten Codes jeweils die Hamming–Distanz $d_{\rm min} = 3$ aufweisen. | ||
+ | [[Datei:P_ID3012__KC_A_4_6d_v3.png|left|frame|Gesuchter Produktcode]] | ||
+ | <br><br>Die linke Grafik zeigt das Ergebnis der gesamten Codierung. Unten rechts erkennt man die Checks–on–Checks–Matrix der Dimension $3 × 3$. | ||
+ | <br clear=all> | ||
+ | Bezüglich der Teilaufgabe (3) sind die <u>Lösungsvorschläge 1 und 2</u> richtig: | ||
+ | * Es ist Zufall, dass hier in der Checks–on–Checks–Matrix zwei Zeilen und zwei Spalten identisch sind. | ||
+ | *Es ist egal, ob man die Zeilen 4 bis 6 der Gesamtmatrix über den Code $\mathcal{C}_1$ gewinnt oder die Spalten 5 bis 7 über den Code $\mathcal{C}_2$. | ||
+ | {{ML-Fuß}} | ||
− | ^]] | + | [[Category:Aufgaben zu Kanalcodierung|^4.2 Grundlegendes zu den Produktcodes^]] |
Aktuelle Version vom 8. Juli 2019, 11:14 Uhr
Es soll ein $\rm Produktcode \ (42, \ 12)$ generiert werden, der auf folgenden Komponentencodes aufbaut:
- dem Hammingcode $\rm HC \ (7, \ 4, \ 3)$ ⇒ $\mathcal{C}_1$,
- dem verkürzten Hammingcode $\rm HC \ (6, \ 3, \ 3)$ ⇒ $\mathcal{C}_2$.
Die entsprechenden Codetabellen sind rechts angegeben, wobei jeweils drei Zeilen unvollständig sind. Diese sollen von Ihnen ergänzt werden.
Das zu einem Informationsblock $\underline{u}$ gehörige Codewort ergibt sich allgemein entsprechend der Gleichung $\underline{x} = \underline{u} \cdot \mathbf{G}$. Wie auch in der Aufgabe 4.6Z wird hier von folgenden Generatormatrizen ausgegangen:
- $${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.8cm} { \boldsymbol{\rm G}}_2 = \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}.$$
In der gesamten Aufgabe gelte für den Informationsblock:
- $${ \boldsymbol{\rm U}} = \begin{pmatrix} 0 &1 &1 &0 \\ 0 &0 &0 &0 \\ 1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
Gesucht sind entsprechend der Nomenklatur auf der Seite Grundstruktur eines Produktcodes:
- die Parity–Matrix $\mathbf{P}^{(1)}$ bezüglich des horizontalen Codes $\mathcal{C}_1$,
- die Parity–Matrix $\mathbf{P}^{(2)}$ bezüglich des vertikalen Codes $\mathcal{C}_2$,
- die Checks–on–Checks–Matrix $\mathbf{P}^{(12)}$.
Hinweise:
- Die Aufgabe gehört zum Kapitel Grundlegendes zu den Produktcode.
- Bezug genommen wird insbesondere auf die Seite Grundstruktur eines Produktcodes.
- Die beiden Komponentencodes werden auch in der Aufgabe 4.6Z behandelt.
Fragebogen
Musterlösung
Allgemein gilt $\underline{x} = \underline{u} \cdot \mathbf{G}$. Daraus folgt für
- den ersten Zeilenvektor:
- $$\begin{pmatrix} 0 &1 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &1 &1 &0 &1 &0 &1 \end{pmatrix} \hspace{0.05cm},$$
- den zweiten Zeilenvektor:
- $$\begin{pmatrix} 0 &0 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &0 &0 &0 &0 &0 &0 \end{pmatrix} \hspace{0.05cm},$$
- den dritten Zeilenvektor
- $$\begin{pmatrix} 1 &1 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 1 &1 &1 &0 &0 &0 &0 \end{pmatrix} \hspace{0.05cm}.$$
(2) Richtig sind die Lösungsvorschläge 1, 2 und 4:
- $$\begin{pmatrix} 0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$
- $$\begin{pmatrix} 1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} =\begin{pmatrix} 1 &0 &1 &1 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
Zu dieser Teilaufgabe ist weiter anzumerken:
- Die angegebene erste Spalte ist schon allein deshalb richtig, weil sie mit einer Zeile (der dritten) der Generatormatrix $\mathbf{G}_2$ übereinstimmt.
- Die dritte Spalte des 2D–Codewortes müsste mit der zweiten Spalte identisch sein, da vom gleichen Codewort $(1, \, 0, \, 1)$ ausgegangen wird.
- Der angegebene Vektor $(1, \, 1, \, 0, \, 0, \, 1, \, 1)$ kann aber schon allein deshalb nicht richtig sein, da $\mathcal{C}_2$ ebenso wie $\mathcal{C}_1$ ein systematischer Code ist.
- Auch der verkürzte $(6, \ 3, \ 3)$–Hammingcode $C_2$ ist linear, so dass die Zuordnung $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$ auch ohne Rechnung angebbar ist.
(3) Rechts angegeben sind die vollständigen Codetabellen
- des Hammingcodes $(7, \ 4, \ 3)$, und
- des verkürzten Hammingcodes $(6, \ 3, \ 3)$.
Man erkennt daraus (ohne dass das für diese Aufgabe von Interesse ist), dass die hier betrachteten Codes jeweils die Hamming–Distanz $d_{\rm min} = 3$ aufweisen.
Die linke Grafik zeigt das Ergebnis der gesamten Codierung. Unten rechts erkennt man die Checks–on–Checks–Matrix der Dimension $3 × 3$.
Bezüglich der Teilaufgabe (3) sind die Lösungsvorschläge 1 und 2 richtig:
- Es ist Zufall, dass hier in der Checks–on–Checks–Matrix zwei Zeilen und zwei Spalten identisch sind.
- Es ist egal, ob man die Zeilen 4 bis 6 der Gesamtmatrix über den Code $\mathcal{C}_1$ gewinnt oder die Spalten 5 bis 7 über den Code $\mathcal{C}_2$.