Aufgaben:Aufgabe 4.08: Wiederholung zu den Faltungscodes: Unterschied zwischen den Versionen
K (Guenter verschob die Seite 4.08 Wiederholung zu den Faltungscodes nach Aufgabe 4.08: Wiederholung zu den Faltungscodes) |
|||
| Zeile 7: | Zeile 7: | ||
Ausgehend von dem nebenstehenden Zustandsübergangsdiagramm sollen wesentliche Eigenschaften und Kenngrößen des betrachteten Rate–1/2–Faltungscodes ermittelt werden, wobei wir ausdrücklich auf folgende Theorieseiten verweisen: | Ausgehend von dem nebenstehenden Zustandsübergangsdiagramm sollen wesentliche Eigenschaften und Kenngrößen des betrachteten Rate–1/2–Faltungscodes ermittelt werden, wobei wir ausdrücklich auf folgende Theorieseiten verweisen: | ||
| − | [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Systematische_Faltungscodes|Systematische Faltungscodes (1 | + | #[[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Systematische_Faltungscodes|Systematische Faltungscodes]] |
| + | #[[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Darstellung_im_Zustands.C3.BCbergangsdiagramm|Darstellung im Zustandsübergangsdiagramm]] | ||
| + | #[[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm#Definition_der_freien_Distanz|Definition der freien Distanz]] | ||
| + | #[[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#GF.282.29.E2.80.93Beschreibungsformen_eines_Digitalen_Filters|GF(2)–Beschreibungsformen eines Digitalen Filters]] | ||
| + | #[[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Anwendung_der_D.E2.80.93Transformation_auf_Rate.E2.80.931.2Fn.E2.80.93Faltungscoder| Anwendung der $D$–Transformation auf Rate–1/n–Faltungscodes]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Im Zustandsübergangsdiagramm wird grundsätzlich vom Zustand $S_0$ ausgegangen. Von jedem Zustand gehen zwei Pfeile ab. Die Beschriftung lautet „$u_i | x_i^{(1)}x_i^{(2)}$”. Bei einem systematischen Code gilt dabei: | Im Zustandsübergangsdiagramm wird grundsätzlich vom Zustand $S_0$ ausgegangen. Von jedem Zustand gehen zwei Pfeile ab. Die Beschriftung lautet „$u_i | x_i^{(1)}x_i^{(2)}$”. Bei einem systematischen Code gilt dabei: | ||
| Zeile 24: | Zeile 21: | ||
''Hinweise:'' | ''Hinweise:'' | ||
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes| Grundlegendes zu den Turbocodes]]. | * Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes| Grundlegendes zu den Turbocodes]]. | ||
| − | * | + | * In den Fragen zu dieser Aufgabe werden folgende semi–infinite Vektoren verwendet: |
| − | * Informationssequenz $\ \underline{u} = (u_1, \, u_2, \ | + | * Informationssequenz $\ \underline{u} = (u_1, \, u_2, \text{ ...})$, |
| − | * Paritysequenz $\ \underline{p} = (p_1, \, p_2, \ | + | * Paritysequenz $\ \underline{p} = (p_1, \, p_2, \text{ ...})$, |
| − | * Impulsantwort $\ \underline{g} = (g_1, \, g_2, \ | + | * Impulsantwort $\ \underline{g} = (g_1, \, g_2, \text{ ...})$; diese ist gleich der Paritysequenz $\underline{p}$ für $\underline{u} = (1, \, 0, \, 0, \text{ ...})$. |
* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein. | * Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein. | ||
| Zeile 36: | Zeile 33: | ||
{Wie lautet die Impulsantwort $\underline{g}$? | {Wie lautet die Impulsantwort $\underline{g}$? | ||
|type="[]"} | |type="[]"} | ||
| − | - Es gilt $\underline{g} = (1, \, 1, \,1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \ | + | - Es gilt $\underline{g} = (1, \, 1, \,1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \text{ ...})$. |
| − | + Es gilt $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \ | + | + Es gilt $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{ ...})$. |
{Es sei nun $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$ mit $u_7 ∈ \{0, \, 1\}$. Welche Aussagen treffen für die Paritysequenz $\underline{p}$ zu? | {Es sei nun $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$ mit $u_7 ∈ \{0, \, 1\}$. Welche Aussagen treffen für die Paritysequenz $\underline{p}$ zu? | ||
| Zeile 57: | Zeile 54: | ||
+ Es gilt $p_i = 0$ für $i ≥ 9$. | + Es gilt $p_i = 0$ für $i ≥ 9$. | ||
| − | {Wie groß ist die freie Distanz des betrachteten Faltungsodes? | + | {Wie groß ist die freie Distanz $d_{\rm F}$ des betrachteten Faltungsodes? |
|type="{}"} | |type="{}"} | ||
$d_{\rm F} \ = \ ${ 3 3% } | $d_{\rm F} \ = \ ${ 3 3% } | ||
Version vom 31. Januar 2018, 13:10 Uhr
Die Turbocodes basieren auf den Faltungscodes, die im Kapitel Grundlagen der Faltungscodierung auführlich behandelt werden.
Ausgehend von dem nebenstehenden Zustandsübergangsdiagramm sollen wesentliche Eigenschaften und Kenngrößen des betrachteten Rate–1/2–Faltungscodes ermittelt werden, wobei wir ausdrücklich auf folgende Theorieseiten verweisen:
- Systematische Faltungscodes
- Darstellung im Zustandsübergangsdiagramm
- Definition der freien Distanz
- GF(2)–Beschreibungsformen eines Digitalen Filters
- Anwendung der $D$–Transformation auf Rate–1/n–Faltungscodes
Im Zustandsübergangsdiagramm wird grundsätzlich vom Zustand $S_0$ ausgegangen. Von jedem Zustand gehen zwei Pfeile ab. Die Beschriftung lautet „$u_i | x_i^{(1)}x_i^{(2)}$”. Bei einem systematischen Code gilt dabei:
- Das erste Codebit ist identisch mit dem Informationsbit: $\ x_i^{(1)} = u_i ∈ \{0, \, 1\}$
- Das zweite Codebit ist das Prüfbit (Paritybit): $\ x_i^{(2)} = p_i ∈ \{0, \, 1\}$.
Hinweise:
- Die Aufgabe bezieht sich auf das Kapitel Grundlegendes zu den Turbocodes.
- In den Fragen zu dieser Aufgabe werden folgende semi–infinite Vektoren verwendet:
- Informationssequenz $\ \underline{u} = (u_1, \, u_2, \text{ ...})$,
- Paritysequenz $\ \underline{p} = (p_1, \, p_2, \text{ ...})$,
- Impulsantwort $\ \underline{g} = (g_1, \, g_2, \text{ ...})$; diese ist gleich der Paritysequenz $\underline{p}$ für $\underline{u} = (1, \, 0, \, 0, \text{ ...})$.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
- $$S_0 → S_1 → S_2 → S_0 → S_0 → S_0 → \hspace{0.6cm} \Rightarrow \hspace{0.5cm} {\rm Impulsantwort} \text{:} \hspace{0.2cm} \underline{g} = (1, \, 0, \, 1, \, 0, \, 0) \, .$$
Richtig ist der Lösungsvorschlag 2. Für ein nichtrekursives Filter mit Gedächtnis $m$ gilt $g_i ≡ 0$ für $i > m$. In unserem Beispiel ist $m = 2$. Der Lösungsvorschlag 1 gilt dagegen für das rekursive Filter (RSC) entsprechend der Aufgabe A4.9.
(2) Es sei $\underline{u} = (1, \, 0, \, 0, \, 1, \, 0, \, 0, \, u_7)$ und $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, ...)$. Dann gilt für die Paritysequenz aufgrund der Linearität:
- $$\underline{p} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm} 0,\hspace{0.05cm} u_7\hspace{0.05cm} ) * (\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0 ,\hspace{0.05cm} 0,\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} ...)= $$
- $$\ = \ \hspace{-0.15cm} (\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}0,\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm}0, \hspace{0.05cm} ... \hspace{0.05cm})\oplus$$
- $$\ \oplus \ \hspace{-0.15cm} (\hspace{0.05cm}0,\hspace{0.05cm}\hspace{0.05cm}0,\hspace{0.05cm}0,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm}0, \hspace{0.05cm} ... \hspace{0.05cm})\oplus$$
- $$\ \oplus \ \hspace{-0.15cm} (\hspace{0.05cm}0,\hspace{0.05cm}\hspace{0.05cm}0,\hspace{0.05cm}0,\hspace{0.05cm}\hspace{0.05cm}0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} u_7,\hspace{0.05cm} 0,\hspace{0.05cm}u_7, \hspace{0.05cm} ... \hspace{0.05cm})= $$
- $$\ = \ \hspace{-0.15cm} (\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}0,\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} u_7,\hspace{0.05cm} 0,\hspace{0.05cm}u_7, \hspace{0.05cm} ... \hspace{0.05cm}) \hspace{0.05cm}.$$
Richtig sind demnach die Lösungsvorschläge 1 und 2 im Gegensatz zur Antwort 3: Für $u_7 = 1$ gilt $p_7 = 1, \ p_8 = 0, \ p_9 = 1$ und $p_i ≡ 0$ für $i > 9$.
(3) Aus dem Zustandsübergangsdiagramm erkennt man die Codeparameter $k = 1$ und $n = 2$. Das heißt: Die Übertragungsfunktionsmatrix $\mathbf{G}(D)$ besteht aus zwei Elementen ⇒ der Vorschlag 3 ist falsch.
- Die erste Komponente von $\mathbf{G}(D)$ ist tatsächlich 1, da ein systematischer Code vorliegt: $\ \underline{x}^{(1)} ≡ \underline{z}$.
- Die zweite Komponente von $\mathbf{G}(D)$ ist gleich der $D$–Transformierten der Impulsantwort $\underline{g}$, wobei die Dummy–Variable $D$ eine Verzögerung um ein Bit angibt:
- $$\underline{g}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G^{(2)}(D) = 1+ D^2\hspace{0.05cm}. $$
Richtig ist demnach der Lösungsvorschlag 2.
Über die Fragestellung hinausgehend betrachten wir hier auch noch die vorliegende Filterstruktur:
In der Grafik ist der hier betrachtete Coder als Coder A links dargestellt. Der Coder A
- ist ebenso wie der Coder B systematisch,
- basiert im Gegensatz zu Coder B aber auf einem nichtrekursiven Filter.
Der Coder C hat ebenfalls eine nichtrekursive Struktur, ist aber nicht systematisch. Die äquivalente systematische Repräsentation von Coder C ist der Coder B.
(4) Die Aufgabe könnte in gleicher Weise gelöst werden wie die Teilaufgabe (2). Wir wählen hier aber zur Abwechslung den Weg über die $D$–Transformation:
- $$\underline{u}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = 1+ D^2 + D^5$$
- $$\Rightarrow \hspace{0.3cm} P(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} U(D) \cdot G(D) = (1+ D^2 + D^5) \cdot (1+ D^2 ) =$$
- $$\ = \ \hspace{-0.15cm}1+ D^2 + D^5 + D^2 + D^4 + D^7 = 1+ D^4 + D^5 + D^7$$
- $$\Rightarrow \hspace{0.3cm} \underline{p}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm})\hspace{0.05cm}.$$
Richtig sind die Lösungsvorschläge 2 und 3.
(5) Die freie Distanz $d_{\rm F}$ eines Faltungscoders ist gleich der Anzahl der Bits, durch die sich zwei beliebigen Sequenzen dieses Codes mindestens unterscheiden. Gehen wir wie allgemein üblich als Bezugsgröße von der Nullsequenz $\underline{0} \ \Rightarrow \ S_0 → S_0 → S_0 → S_0 → \ ... \ $ aus, so ergibt sich $d_{\rm F}$ gleichzeitig als das minimale Hamming–Gewicht (Anzahl der Einsen) einer zulässigen Codesequenz $\underline{x} ≠ \underline{0}$.
Aus dem Zustandsübergangsdiagramm erkennt man, dass die frei Distanz zum Beispiel durch den Pfad
- $$ S_0 → S_0 → S_1 → S_2 → S_0 → S_0 → \ ...$$
gekennzeichnet ist, also durch die Codesequenz
- $$00 \hspace{0.4cm} 11 \hspace{0.4cm} 00 \hspace{0.4cm} 01 \hspace{0.4cm} 00 \ ... \ .$$
Dementsprechend gilt für die freie Distanz dieses nichtrekursiven Codes: $\hspace{0.2cm} d_{\rm F} \ \underline{= 3}$.
