Aufgaben:Aufgabe 3.8: Rate Compatible Punctured Convolutional Codes: Unterschied zwischen den Versionen
Aus LNTwww
| (4 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 2: | Zeile 2: | ||
[[Datei:P_ID2708__KC_A_3_8.png|right|frame|RCPC–Punktierungsmatrizen]] | [[Datei:P_ID2708__KC_A_3_8.png|right|frame|RCPC–Punktierungsmatrizen]] | ||
| − | Eine wichtige Anwendung für [[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Punktierte_Faltungscodes| punktierte Faltungscodes]] sind die <i>Rate Compatible Punctured Convolutional Codes</i> (oder kurz RCPC–Codes), die von [[Biografien_und_Bibliografien/Lehrstuhlinhaber_des_LNT#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_.281993-2006.29|Joachim Hagenauer]] in [Hag88] vorgeschlagen wurden. Ausgehend von einem Muttercode $\mathcal{C}_0$ mit der Rate $R_0 = 1/n$ werden durch verschiedene Punktierungsmatrizen $\mathbf{P}_l$ andere Codes $\mathcal{C}_l$ mit höherer Coderate $R_l > R_0$ festgelegt. | + | Eine wichtige Anwendung für [[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Punktierte_Faltungscodes| punktierte Faltungscodes]] sind die <i>Rate Compatible Punctured Convolutional Codes</i> (oder kurz '''RCPC–Codes'''), die von [[Biografien_und_Bibliografien/Lehrstuhlinhaber_des_LNT#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_.281993-2006.29|Joachim Hagenauer]] in [Hag88] vorgeschlagen wurden. Ausgehend von einem Muttercode $\mathcal{C}_0$ mit der Rate $R_0 = 1/n$ werden durch verschiedene Punktierungsmatrizen $\mathbf{P}_l$ andere Codes $\mathcal{C}_l$ mit höherer Coderate $(R_l > R_0)$ festgelegt. |
| − | Rechts sind die zu analysierenden Punktierungsmatrizen $\mathbf{P}_0, \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \mathbf{P}_4$ dargestellt. | + | Rechts sind die zu analysierenden Punktierungsmatrizen $\mathbf{P}_0, \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \mathbf{P}_4$ dargestellt. |
| − | *Ist bei der Matrix $\mathbf{P}_l$ das Matrixelement $P_{ij} = 1$, so wird das entsprechende Codebit übertragen, während $P_{ij} = 0$ auf eine Punktierung hinweist. | + | *Ist bei der Matrix $\mathbf{P}_l$ das Matrixelement $P_{ij} = 1$, so wird das entsprechende Codebit übertragen, während $P_{ij} = 0$ auf eine Punktierung hinweist. |
| − | *Im Fragebogen verwenden wir für das Element $P_{ij}$ der Matrix $\mathbf{P}_l$ auch die kürzere Schreibweise $P_{ij}^{(l)}$. | + | *Im Fragebogen verwenden wir für das Element $P_{ij}$ der Matrix $\mathbf{P}_l$ auch die kürzere Schreibweise $P_{ij}^{(l)}$. |
| − | In | + | In der Grafik sind alle die Nullen in der Matrix $\mathbf{P}_l$ rot markiert, die in der Matrix $\mathbf{P}_{l–1}$ noch Einsen waren. Durch diese Maßnahme wird die Coderate $R_{l}$ gegenüber $R_{l-1}$ vergrößert. |
Die RCPC–Codes eignen sich gut zur Realisierung von | Die RCPC–Codes eignen sich gut zur Realisierung von | ||
| − | * <i>ungleichem Fehlerschutz</i> für hybride ARQ–Verfahren, | + | * <i>ungleichem Fehlerschutz</i> für hybride ARQ–Verfahren, |
| − | * Systemen mit <i>inkrementeller Redundanz</i>. | + | * Systemen mit <i>inkrementeller Redundanz</i>. |
| − | Unter „Systemen mit inkrementeller Redundanz” versteht man, dass nach der herkömmlichen Faltungscodierung aus dem Codewort $\underline{x}^{(0)}$ Bits entsprechend der Punktierungsmatrix $\mathbf{P}_l$ weggelassen werden und das verkürzte Codewort $\underline{x}^{(l)}$ übertragen wird: | + | Unter „Systemen mit inkrementeller Redundanz” versteht man, dass nach der herkömmlichen Faltungscodierung aus dem Codewort $\underline{x}^{(0)}$ Bits entsprechend der Punktierungsmatrix $\mathbf{P}_l$ weggelassen werden und das verkürzte Codewort $\underline{x}^{(l)}$ übertragen wird: |
*Kann das punktierte Codewort im Empfänger nicht korrekt decodiert werden, fordert der Empfänger vom Sender weitere Redundanz in Form der zuvor auspunktierten Bits an. | *Kann das punktierte Codewort im Empfänger nicht korrekt decodiert werden, fordert der Empfänger vom Sender weitere Redundanz in Form der zuvor auspunktierten Bits an. | ||
*Somit wird die Übertragung von nicht benötigter Redundanz verhindert und der Durchsatz an die Kanalgegebenheiten angepasst. | *Somit wird die Übertragung von nicht benötigter Redundanz verhindert und der Durchsatz an die Kanalgegebenheiten angepasst. | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | [[Datei:P_ID2709__hagenauer_kleiner.jpg|left|frame|Joachim Hagenauer]] | ||
| Zeile 25: | Zeile 30: | ||
| − | |||
''Hinweise:'' | ''Hinweise:'' | ||
| − | * Die Aufgabe bezieht sich auf den Abschnitt [[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Punktierte_Faltungscodes|Punktierte Faltungscodes]] im Kapitel „Codebeschreibung mit Zustands– und Trellisdiagramm”. | + | * Die Aufgabe bezieht sich auf den Abschnitt [[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Punktierte_Faltungscodes|Punktierte Faltungscodes]] im Kapitel „Codebeschreibung mit Zustands– und Trellisdiagramm”. |
| − | + | ||
*Die Literaturstelle [Hag88] verweist auf das Paper „Hagenauer, J.: ''Rate Compatible Punctured Convolutional Codes (RCPC codes) and their Applications''. In: IEEE Transactions on Communications, vol COM-36, S. 389 - 400, 1988”. | *Die Literaturstelle [Hag88] verweist auf das Paper „Hagenauer, J.: ''Rate Compatible Punctured Convolutional Codes (RCPC codes) and their Applications''. In: IEEE Transactions on Communications, vol COM-36, S. 389 - 400, 1988”. | ||
| − | * Professor [[Biografien_und_Bibliografien/Lehrstuhlinhaber_des_LNT#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_.281993-2006.29| Joachim Hagenauer]] war von 1993 bis 2006 Leiter des Lehrstuhls für Nachrichtentechnik (LNT) der Technischen Universität München. | + | * Professor [[Biografien_und_Bibliografien/Lehrstuhlinhaber_des_LNT#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_.281993-2006.29| Joachim Hagenauer]] war von 1993 bis 2006 Leiter des Lehrstuhls für Nachrichtentechnik (LNT) der Technischen Universität München. |
| − | *Die Initiatoren des von Ihnen gerade genutzten Lerntutorials – Günter Söder und Klaus Eichin – danken ihrem langjährigen Chef für die Unterstützung und Förderung unseres $\rm LNTwww$–Projekts während der ersten Jahre. | + | *Die Initiatoren des von Ihnen gerade genutzten Lerntutorials – Günter Söder und Klaus Eichin – danken ihrem langjährigen Chef für die Unterstützung und Förderung unseres $\rm LNTwww$–Projekts während der ersten sechs Jahre. |
| Zeile 42: | Zeile 46: | ||
{Welche Aussagen liefern die vorgegeben Punktierungsmatrizen? | {Welche Aussagen liefern die vorgegeben Punktierungsmatrizen? | ||
|type="[]"} | |type="[]"} | ||
| − | + Die Rate des RCPC–Muttercodes ist $R_0 = 1/3$. | + | + Die Rate des RCPC–Muttercodes ist $R_0 = 1/3$. |
| − | + Die Punktierungsperiode ist $p = 8$. | + | + Die Punktierungsperiode ist $p = 8$. |
| − | - Das Gedächtnis der RCPC–Codeklasse ist $M = 4$. | + | - Das Gedächtnis der RCPC–Codeklasse ist $M = 4$. |
| − | {Welche Coderaten weisen die Codes $ | + | {Welche Coderaten weisen die Codes $\mathcal{C}_1$, ... , $\mathcal{C}_4$ auf? |
|type="{}"} | |type="{}"} | ||
| − | ${\rm Matrix \ P_1} \Rightarrow {\rm Code \ \mathcal{C}_1} \text{:} \ | + | ${\rm Matrix \ P_1} \Rightarrow {\rm Code \ \mathcal{C}_1} \text{:} \hspace{0.4cm} R_1 \ = \ ${ 0.4 3% } |
| − | ${\rm Matrix \ P_2} \Rightarrow {\rm Code \ \mathcal{C}_2} \text{:} \ | + | ${\rm Matrix \ P_2} \Rightarrow {\rm Code \ \mathcal{C}_2} \text{:} \hspace{0.4cm}R_2 \ = \ ${ 0.5 3% } |
| − | ${\rm Matrix \ P_3} \Rightarrow {\rm Code \ \mathcal{C}_3} \text{:} \ | + | ${\rm Matrix \ P_3} \Rightarrow {\rm Code \ \mathcal{C}_3} \text{:} \hspace{0.4cm} R_3 \ = \ ${ 0.667 3% } |
| − | ${\rm Matrix \ P_4} \Rightarrow {\rm Code \ \mathcal{C}_4} \text{:} \ | + | ${\rm Matrix \ P_4} \Rightarrow {\rm Code \ \mathcal{C}_4} \text{:} \hspace{0.4cm} R_4 \ = \ ${ 0.889 3% } |
{Welche Aussagen gelten für die Matrixelemente $P_{ij}^{(l)}$? | {Welche Aussagen gelten für die Matrixelemente $P_{ij}^{(l)}$? | ||
|type="[]"} | |type="[]"} | ||
| − | + Aus $P_{ij}^{(l)} = 1$ folgt $P_{ij}^{(\lambda)} = 1$ für alle $\lambda < l$. | + | + Aus $P_{ij}^{(l)} = 1$ folgt $P_{ij}^{(\lambda)} = 1$ für alle $\lambda < l$. |
| − | - Aus $P_{ij}^{(l)} = 1$ folgt $P_{ij}^{(\lambda)} = 1$ für alle $\lambda > l$. | + | - Aus $P_{ij}^{(l)} = 1$ folgt $P_{ij}^{(\lambda)} = 1$ für alle $\lambda > l$. |
| − | - Aus $P_{ij}^{(l)} = 0$ folgt $P_{ij}^{(\lambda)} = 0$ für alle $\lambda < l$. | + | - Aus $P_{ij}^{(l)} = 0$ folgt $P_{ij}^{(\lambda)} = 0$ für alle $\lambda < l$. |
| − | + Aus $P_{ij}^{(l)} = 0$ folgt $P_{ij}^{(\lambda)} = 0$ für alle $\lambda > l$. | + | + Aus $P_{ij}^{(l)} = 0$ folgt $P_{ij}^{(\lambda)} = 0$ für alle $\lambda > l$. |
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Die Zeilenzahl der Punktierungsmatrizen gibt den Parameter $n$ des $(n, \ k = 1)$–RCPC–Muttercodes an. Daraus ergibt sich dessen Rate zu $R_0 = 1/3$. Die Spaltenzahl ist gleich der Punktierungsperiode $p$. Bei der betrachteten Codeklasse gilt $p = 8$. Dagegen liefern die Punktierungsmatrizen keine Aussagen über das Gedächtnis des Codes ⇒ | + | '''(1)''' Richtig sind die <u>Lösungsvorschläge 1 und 2</u>: |
| + | *Die Zeilenzahl der Punktierungsmatrizen gibt den Parameter $n$ des $(n, \ k = 1)$–RCPC–Muttercodes an. | ||
| + | *Daraus ergibt sich dessen Rate zu $R_0 = 1/3$. Die Spaltenzahl ist gleich der Punktierungsperiode $p$. Bei der betrachteten Codeklasse gilt $p = 8$. | ||
| + | * Dagegen liefern die Punktierungsmatrizen keine Aussagen über das Gedächtnis des Codes ⇒ | ||
| − | '''(2)''' Für die Rate des Codes $ | + | '''(2)''' Für die Rate des Codes $\mathcal{C}_l = p/N_l$, wobei $N_l$ die Anzahl aller Einsen in der Punktierungsmatrix $\mathbf{P}_l$ und $p$ die Punktierungsperiode bezeichnet. Ausgehend von der Rate $R_0 = 1/3$ des Muttercodes $\mathcal{C}_0$ erhält man: |
| − | |||
* $R_1 = 8/20 = 2/5 = \underline{0.400}$, | * $R_1 = 8/20 = 2/5 = \underline{0.400}$, | ||
* $R_2 = 8/16 = 1/2 = \underline{0.500}$, | * $R_2 = 8/16 = 1/2 = \underline{0.500}$, | ||
| Zeile 74: | Zeile 80: | ||
| − | '''(3)''' Alle Einsen in der Matrix $\mathbf{P}_4$ sind auch in den darüber liegenden Matrizen $\mathbf{P}_3, \ ... \ , \ \mathbf{P}_0$ enthalten. In der Matrix $\mathbf{P}_3$ kommen gegenüber $\mathbf{P}_4$ drei Einsen hinzu, in der Matrix $\mathbf{P}_2$ gegenüber $\mathbf{P}_3$ nochmals vier, usw. | + | '''(3)''' Richtig sind die <u>Lösungsvorschläge 1 und 4</u>: |
| + | *Alle Einsen in der Matrix $\mathbf{P}_4$ sind auch in den darüber liegenden Matrizen $\mathbf{P}_3, \hspace{0.05cm}\text{ ...} \hspace{0.05cm}, \ \mathbf{P}_0$ enthalten. | ||
| + | *In der Matrix $\mathbf{P}_3$ kommen gegenüber $\mathbf{P}_4$ drei Einsen hinzu, in der Matrix $\mathbf{P}_2$ gegenüber $\mathbf{P}_3$ nochmals vier, usw. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 7. Juni 2019, 16:05 Uhr
RCPC–Punktierungsmatrizen
Eine wichtige Anwendung für punktierte Faltungscodes sind die Rate Compatible Punctured Convolutional Codes (oder kurz RCPC–Codes), die von Joachim Hagenauer in [Hag88] vorgeschlagen wurden. Ausgehend von einem Muttercode $\mathcal{C}_0$ mit der Rate $R_0 = 1/n$ werden durch verschiedene Punktierungsmatrizen $\mathbf{P}_l$ andere Codes $\mathcal{C}_l$ mit höherer Coderate $(R_l > R_0)$ festgelegt.
Rechts sind die zu analysierenden Punktierungsmatrizen $\mathbf{P}_0, \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \mathbf{P}_4$ dargestellt.
- Ist bei der Matrix $\mathbf{P}_l$ das Matrixelement $P_{ij} = 1$, so wird das entsprechende Codebit übertragen, während $P_{ij} = 0$ auf eine Punktierung hinweist.
- Im Fragebogen verwenden wir für das Element $P_{ij}$ der Matrix $\mathbf{P}_l$ auch die kürzere Schreibweise $P_{ij}^{(l)}$.
In der Grafik sind alle die Nullen in der Matrix $\mathbf{P}_l$ rot markiert, die in der Matrix $\mathbf{P}_{l–1}$ noch Einsen waren. Durch diese Maßnahme wird die Coderate $R_{l}$ gegenüber $R_{l-1}$ vergrößert.
Die RCPC–Codes eignen sich gut zur Realisierung von
- ungleichem Fehlerschutz für hybride ARQ–Verfahren,
- Systemen mit inkrementeller Redundanz.
Unter „Systemen mit inkrementeller Redundanz” versteht man, dass nach der herkömmlichen Faltungscodierung aus dem Codewort $\underline{x}^{(0)}$ Bits entsprechend der Punktierungsmatrix $\mathbf{P}_l$ weggelassen werden und das verkürzte Codewort $\underline{x}^{(l)}$ übertragen wird:
- Kann das punktierte Codewort im Empfänger nicht korrekt decodiert werden, fordert der Empfänger vom Sender weitere Redundanz in Form der zuvor auspunktierten Bits an.
- Somit wird die Übertragung von nicht benötigter Redundanz verhindert und der Durchsatz an die Kanalgegebenheiten angepasst.
Joachim Hagenauer
Hinweise:
- Die Aufgabe bezieht sich auf den Abschnitt Punktierte Faltungscodes im Kapitel „Codebeschreibung mit Zustands– und Trellisdiagramm”.
- Die Literaturstelle [Hag88] verweist auf das Paper „Hagenauer, J.: Rate Compatible Punctured Convolutional Codes (RCPC codes) and their Applications. In: IEEE Transactions on Communications, vol COM-36, S. 389 - 400, 1988”.
- Professor Joachim Hagenauer war von 1993 bis 2006 Leiter des Lehrstuhls für Nachrichtentechnik (LNT) der Technischen Universität München.
- Die Initiatoren des von Ihnen gerade genutzten Lerntutorials – Günter Söder und Klaus Eichin – danken ihrem langjährigen Chef für die Unterstützung und Förderung unseres $\rm LNTwww$–Projekts während der ersten sechs Jahre.
Fragebogen
Musterlösung
(1) Richtig sind die Lösungsvorschläge 1 und 2:
- Die Zeilenzahl der Punktierungsmatrizen gibt den Parameter $n$ des $(n, \ k = 1)$–RCPC–Muttercodes an.
- Daraus ergibt sich dessen Rate zu $R_0 = 1/3$. Die Spaltenzahl ist gleich der Punktierungsperiode $p$. Bei der betrachteten Codeklasse gilt $p = 8$.
- Dagegen liefern die Punktierungsmatrizen keine Aussagen über das Gedächtnis des Codes ⇒
(2) Für die Rate des Codes $\mathcal{C}_l = p/N_l$, wobei $N_l$ die Anzahl aller Einsen in der Punktierungsmatrix $\mathbf{P}_l$ und $p$ die Punktierungsperiode bezeichnet. Ausgehend von der Rate $R_0 = 1/3$ des Muttercodes $\mathcal{C}_0$ erhält man:
- $R_1 = 8/20 = 2/5 = \underline{0.400}$,
- $R_2 = 8/16 = 1/2 = \underline{0.500}$,
- $R_3 = 8/12 = 2/3 = \underline{0.667}$,
- $R_4 = 8/9 = \underline{0.889}$.
(3) Richtig sind die Lösungsvorschläge 1 und 4:
- Alle Einsen in der Matrix $\mathbf{P}_4$ sind auch in den darüber liegenden Matrizen $\mathbf{P}_3, \hspace{0.05cm}\text{ ...} \hspace{0.05cm}, \ \mathbf{P}_0$ enthalten.
- In der Matrix $\mathbf{P}_3$ kommen gegenüber $\mathbf{P}_4$ drei Einsen hinzu, in der Matrix $\mathbf{P}_2$ gegenüber $\mathbf{P}_3$ nochmals vier, usw.
