Difference between revisions of "Aufgaben:Exercise 1.09Z: Extension and/or Puncturing"
Line 68: | Line 68: | ||
|type="[]"} | |type="[]"} | ||
+ Die Coderate beträgt nun $R = 2/4 = 0.5$. | + Die Coderate beträgt nun $R = 2/4 = 0.5$. | ||
− | + $C_{(4, 2)} = (0 | + | + $C_{(4, 2)} = (0, 0, 0, 0), \, (1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$. |
- Die Minimaldistanz bleibt gegenüber dem $(5, \, 2)$–Code gleich. | - Die Minimaldistanz bleibt gegenüber dem $(5, \, 2)$–Code gleich. | ||
</quiz> | </quiz> | ||
Line 74: | Line 74: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Die Rate des (5, 2)–Codes ist $R = 2/5 \underline{ = 0.4}$. Aus dem angegebenen Code erkennt man weiterhin die minimale Distanz $d_{min} \underline{ = 3}$. | + | '''(1)''' Die Rate des $(5, \, 2)$–Codes ist $R = 2/5 \ \underline{ = 0.4}$. Aus dem angegebenen Code erkennt man weiterhin die minimale Distanz $d_{\rm min} \ \underline{ = 3}$. |
− | '''(2)''' Bei Erweiterung vom (5, 2)–Code zum (6, 2)–Code wird ein weiteres Prüfbit hinzugefügt. Das Codewort hat somit die Form | + | |
+ | '''(2)''' Bei Erweiterung vom $(5, \, 2)$–Code zum $(6, \, 2)$–Code wird ein weiteres Prüfbit hinzugefügt. Das Codewort hat somit die Form | ||
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$ | :$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$ | ||
Line 84: | Line 85: | ||
:$$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$ | :$$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$ | ||
− | Das heißt: Das neue Prüfbit $p_{4}$ wird so gewählt, dass sich in jedem Codewort eine gerade Anzahl von Einsen ergibt | + | Das heißt: Das neue Prüfbit $p_{4}$ wird so gewählt, dass sich in jedem Codewort eine gerade Anzahl von Einsen ergibt ⇒ <u>Antwort 2</u>. Löst man diese Aufgabe mit der Prüfmatrix, so erhält man |
:$${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}$$ | :$${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}$$ | ||
:$$\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$ | :$$\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$ | ||
− | Die beiden Zeilen der Generatormatrix $ | + | Die beiden Zeilen der Generatormatrix $\boldsymbol{\rm G}$ ergeben zwei der vier Codeworte, die Modulo–$2$–Summe das dritte und schließlich ist auch noch das Nullwort zu berücksichtigen. |
− | |||
− | |||
− | |||
+ | '''(3)''' Nach Erweiterung vom $(5, \, 2)$–Code auf den $(6, \, 2)$–Code | ||
+ | *vermindert sich die Rate von $R = 2/5$ auf $R = 2/6 \ \underline{= 0.333}$, | ||
+ | *erhöht sich die Minimaldistanz von $d_{\rm min} = 3$ auf $d_{\rm min} \ \underline{= 4}$ . | ||
+ | |||
+ | |||
+ | <u>Allgemein gilt:</u> Erweitert man einen Code, so nimmt die Rate ab und die Minimaldistanz erhöht sich um $1$, falls $d_{\rm min}$ vorher ungerade war. | ||
− | |||
'''(4)''' Bei gleicher Vorgehensweise wie unter (3) erhält man | '''(4)''' Bei gleicher Vorgehensweise wie unter (3) erhält man | ||
Line 103: | Line 106: | ||
:$$\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$ | :$$\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$ | ||
− | ⇒ | + | ⇒ <u>Beide Antworten</u> sind richtig. |
− | '''(5)''' Die Rate beträgt nun $R = 2/7 = \underline{0.266}$. Die Minimaldistanz ist weiterhin $d_{\rm min} | + | |
+ | '''(5)''' Die Rate beträgt nun $R = 2/7 = \ \underline{0.266}$. Die Minimaldistanz ist weiterhin $d_{\rm min} \ \underline{= 4}$ , wie man aus den Codeworten des $(7, \, 2)$–Codes ablesen kann: | ||
:$$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.1cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$ | :$$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.1cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$ | ||
Line 114: | Line 118: | ||
:$${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$ | :$${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$ | ||
− | Aus der Generatormatrix ergeben sich die genannten Codeworte $(1, 0, 1, 1), (0, 1, 0, 1), (1, 1, 1, 0)$ als Zeilensumme sowie das Nullwort $(0, 0, 0, 0)$. Die Minimaldistanz dieses Codes ist $d_{\rm min}= 2$ und damit kleiner als die minimale Distanz $d_{\rm min}= 3$ des (5, 2)–Codes. | + | Aus der Generatormatrix ergeben sich die genannten Codeworte $(1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$ als Zeilensumme sowie das Nullwort $(0, 0, 0, 0)$. Die Minimaldistanz dieses Codes ist $d_{\rm min}= 2$ und damit kleiner als die minimale Distanz $d_{\rm min}= 3$ des $(5, \, 2)$–Codes. |
− | <u>Allgemein gilt:</u> Durch Punktierung wird $d_{\rm min}$ um 1 kleiner (wenn sie vorher gerade war) oder sie bleibt gleich. Dies kann man sich verdeutlichen, wenn man durch eine weitere Punktierung (des Prüfbits $p_{2}$) den (3, 2)–Blockcode generiert. Dieser Code | + | <u>Allgemein gilt:</u> Durch Punktierung wird $d_{\rm min}$ um $1$ kleiner (wenn sie vorher gerade war) oder sie bleibt gleich. Dies kann man sich verdeutlichen, wenn man durch eine weitere Punktierung (des Prüfbits $p_{2}$) den $(3, \, 2)$–Blockcode generiert. Dieser Code |
:$$ \mathcal{C} = \{ (0, 0, 0), \hspace{0.1cm}(0, 1, 1), \hspace{0.1cm}(1, 0, 1), \hspace{0.1cm}(1, 1, 0) \}$$ | :$$ \mathcal{C} = \{ (0, 0, 0), \hspace{0.1cm}(0, 1, 1), \hspace{0.1cm}(1, 0, 1), \hspace{0.1cm}(1, 1, 0) \}$$ | ||
− | besitzt die gleiche Minimaldistanz $d_{\rm min}= 2$ wie der (4, 2)–Code. | + | besitzt die gleiche Minimaldistanz $d_{\rm min}= 2$ wie der $(4, \, 2)$–Code. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
− | [[Category:Aufgaben zu Kanalcodierung|^1.4 Beschreibung linearer Blockcodes | + | [[Category:Aufgaben zu Kanalcodierung|^1.4 Beschreibung linearer Blockcodes^]] |
− | |||
− | ^]] |
Revision as of 09:21, 20 December 2017
Häufig kennt man einen Code, der für eine Anwendung als geeignet erscheint, dessen Coderate aber nicht exakt mit den Vorgaben übereinstimmt.
Zur Ratenanpassung gibt es verschiedene Möglichkeiten
- Erweiterung (englisch Extension): Ausgehend vom $(n, \, k)$–Code, dessen Prüfmatrix $\mathbf{H}$ gegeben ist, erhält man einen $(n+1, \, k)$–Code, indem man die Prüfmatrix um eine Zeile und eine Spalte erweitert und die neuen Matrixelemente entsprechend der oberen Grafik mit Nullen und Einsen ergänzt. Man fügt ein neues Prüfbit
- $$x_{n+1} = x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n$$
hinzu und damit auch eine neue Prüfgleichung, die in $\mathbf{H}'$ berücksichtigt ist.
- Punktierung (englisch Puncturing): Entsprechend der unteren Abbildung kommt man zu einem $(n–1, \, k)$–Code größerer Rate, wenn man auf ein Prüfbit und eine Prüfgleichung verzichtet, was gleichbedeutend damit ist, aus der Prüfmatrix $\mathbf{H}$ eine Zeile und eine Spalte zu streichen.
- Verkürzung (englisch Shortening): Verzichtet man anstelle eines Prüfbits auf ein Informationsbit, so ergibt sich ein $(n–1, \, k–1)$–Code kleinerer Rate.
In dieser Aufgabe sollen ausgehend von einem $(5, \, 2)$–Blockcode
- $$\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.1cm}, (0, 1, 0, 1, 1) \hspace{0.1cm},(1, 0, 1, 1, 0) \hspace{0.1cm},(1, 1, 1, 0, 1) \}$$
folgende Codes konstruiert und analysiert werden:
- ein $(6, \, 2)$–Code durch einmalige Erweiterung,
- ein $(7, \, 2)$–Code durch nochmalige Erweiterung,
- ein $(4, \, 2)$–Code durch Punktierung.
Die Prüfmatrix und die Generatormatrix des systematischen $(5, \, 2)$–Codes lauten:
- $${ \boldsymbol{\rm H}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &0 &0\\ 1 &1 &0 &1 &0\\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.3cm} \Leftrightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &1 &0\\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
Hinweise :
- Die Aufgabe bezieht sich auf das Kapitel Allgemeine Beschreibung linearer Blockcodes.
- In der Aufgabe 1.09 wird beispielhaft gezeigt, wie aus dem $(7, \, 4, \, 3)$–Hamming–Code durch Erweiterung ein $(8, \, 4, \, 4)$–Code entsteht.
Fragebogen
Musterlösung
(2) Bei Erweiterung vom $(5, \, 2)$–Code zum $(6, \, 2)$–Code wird ein weiteres Prüfbit hinzugefügt. Das Codewort hat somit die Form
- $$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$
Für das hinzugekommene Prüfbit muss dabei gelten:
- $$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$
Das heißt: Das neue Prüfbit $p_{4}$ wird so gewählt, dass sich in jedem Codewort eine gerade Anzahl von Einsen ergibt ⇒ Antwort 2. Löst man diese Aufgabe mit der Prüfmatrix, so erhält man
- $${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}$$
- $$\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
Die beiden Zeilen der Generatormatrix $\boldsymbol{\rm G}$ ergeben zwei der vier Codeworte, die Modulo–$2$–Summe das dritte und schließlich ist auch noch das Nullwort zu berücksichtigen.
(3) Nach Erweiterung vom $(5, \, 2)$–Code auf den $(6, \, 2)$–Code
- vermindert sich die Rate von $R = 2/5$ auf $R = 2/6 \ \underline{= 0.333}$,
- erhöht sich die Minimaldistanz von $d_{\rm min} = 3$ auf $d_{\rm min} \ \underline{= 4}$ .
Allgemein gilt: Erweitert man einen Code, so nimmt die Rate ab und die Minimaldistanz erhöht sich um $1$, falls $d_{\rm min}$ vorher ungerade war.
(4) Bei gleicher Vorgehensweise wie unter (3) erhält man
- $${ \boldsymbol{\rm H}}_{(7,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (7,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 0 &0 &0 &0 &0 &0 &1 \end{pmatrix}$$
- $$\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$
⇒ Beide Antworten sind richtig.
(5) Die Rate beträgt nun $R = 2/7 = \ \underline{0.266}$. Die Minimaldistanz ist weiterhin $d_{\rm min} \ \underline{= 4}$ , wie man aus den Codeworten des $(7, \, 2)$–Codes ablesen kann:
- $$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.1cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$
Allgemein gilt: Ist die Minimaldistanz eines Codes geradzahlig, so kann diese durch Erweiterung nicht vergrößert werden.
(6) Richtig sind die Aussagen 1 und 2. Durch Streichen der letzten Zeile und der letzten Spalte erhält man für die Prüfmatrix bzw. die Generatormatrix (jeweils in systematischer Form):
- $${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$
Aus der Generatormatrix ergeben sich die genannten Codeworte $(1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$ als Zeilensumme sowie das Nullwort $(0, 0, 0, 0)$. Die Minimaldistanz dieses Codes ist $d_{\rm min}= 2$ und damit kleiner als die minimale Distanz $d_{\rm min}= 3$ des $(5, \, 2)$–Codes.
Allgemein gilt: Durch Punktierung wird $d_{\rm min}$ um $1$ kleiner (wenn sie vorher gerade war) oder sie bleibt gleich. Dies kann man sich verdeutlichen, wenn man durch eine weitere Punktierung (des Prüfbits $p_{2}$) den $(3, \, 2)$–Blockcode generiert. Dieser Code
- $$ \mathcal{C} = \{ (0, 0, 0), \hspace{0.1cm}(0, 1, 1), \hspace{0.1cm}(1, 0, 1), \hspace{0.1cm}(1, 1, 0) \}$$
besitzt die gleiche Minimaldistanz $d_{\rm min}= 2$ wie der $(4, \, 2)$–Code.