Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes }} [[Datei:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-Choice Fra…“
(23 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1:
Zeile 1:
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes}}
[[Datei:P_ID2681__KC_A_3_10.png|right|frame|Nur teilweise ausgewertetes Trellis]]
Im [[Kanalcodierung/Decodierung_von_Faltungscodes#Vorbemerkungen_zu_den_nachfolgenden_Decodierbeispielen| Theorieteil]] zu diesem Kapitel wurde die Berechnung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ ausführlich behandelt, die auf der Hamming–Distanz $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$ zwischen den möglichen Codeworten $\underline{x}\hspace{0.05cm}' ∈ \{00, \, 01, \, 10, \, 11\}$ und dem zum Zeitpunkt $i$ empfangenen 2–Bit–Worten $\underline{y}_i$ basiert.
Die Aufgabe beschäftigt sich genau mit dieser Thematik. In nebenstehender Grafik
* ist das betrachtete Trellis dargestellt – gültig für den Code mit Rate $R = 1/2$, Gedächtnis $m = 2$ sowie $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$,
* sind die Empfangsworte $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$ in den Rechtecken angegeben,
* sind alle Fehlergrößen ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ {\it \Gamma}_4(S_{\mu})$ bereits eingetragen.
Beispielsweise ergibt sich die Fehlergröße ${\it \Gamma}_4(S_0)$ mit $\underline{y}_4 = (01)$ als das Minimum der beiden Vergleichswerte
Der überlebende Zweig – hier von ${\it \Gamma}_3(S_2)$ nach ${\it \Gamma}_4(S_0)$ – ist durchgezogen gezeichnet, der eliminierte Zweig von ${\it \Gamma}_3(S_0)$ nach ${\it \Gamma}_4(S_0)$ punktiert. Rote Pfeile stehen für das Informationsbit $u_i = 0$, blaue Pfeile für $u_i = 1$.
[[Datei:|right|]]
In der Teilaufgabe '''(4)''' soll der Zusammenhang zwischen
*der ${\it \Gamma}_i(S_{\mu})$–Minimierung und
herausgearbeitet werden. Hierbei bezeichnet man die Knoten ${\it \Lambda}_i(S_{\mu})$ als <i>Metriken</i>, wobei sich der Metrikzuwachs gegenüber den Vorgängerknoten aus dem Korrelationswert $〈\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i 〉$ ergibt. Näheres zu dieser Thematik finden Sie auf den folgenden Theorieseiten:
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Zusammenhang_zwischen_Hamming.E2.80.93Distanz_und_Korrelation| Zusammenhang zwischen Hamming–Distanz und Korrelation]],
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken| Viterbi–Algorithmus, basierend auf Korrelation und Metriken]],
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Entscheidung_bei_nicht.E2.80.93terminierten_Faltungscodes| Viterbi–Entscheidung bei nicht–terminierten Faltungscodes]].
''Hinweise:''
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Decodierung_von_Faltungscodes| Decodierung von Faltungscodes]].
* Vorerst nicht betrachtet wird die Suche der überlebenden Pfade. Damit beschäftigt sich für das gleiche Beispiel die spätere [[Aufgaben:3.11_Viterbi%E2%80%93Pfadsuche| Aufgabe 3.11]].
<quiz display=simple>
{Multiple-Choice Frage
|type="[]"}
- Falsch
+ Richtig
{Input-Box Frage
===Fragebogen===
<quiz display=simple>
{Wie lauten die Fehlergrößen für den Zeitpunkt $i = 5$?
|type="{}"}
|type="{}"}
$\alpha$ = { 0.3 }
${\it \Gamma}_5(S_0) \ = \ ${ 3 3% }
${\it \Gamma}_5(S_1) \ = \ ${ 3 3% }
${\it \Gamma}_5(S_2) \ = \ ${ 2 3% }
${\it \Gamma}_5(S_3) \ = \ ${ 3 3% }
{Wie lauten die Fehlergrößen für den Zeitpunkt $i = 6$?
|type="{}"}
${\it \Gamma}_6(S_0) \ = \ ${ 3 3% }
${\it \Gamma}_6(S_2) \ = \ ${ 3 3% }
{Welcher Endwert ergibt sich bei diesem Trellis, basierend auf ${\it \Gamma}_i(S_{\mu})$?
|type="[]"}
+ Es gilt ${\it \Gamma}_7(S_0) = 3$.
- Dieser Endwert lässt auf eine fehlerfreie Übertragung schließen.
+ Dieser Endwert lässt auf drei Übertragungsfehler schließen.
{Welche Aussagen sind für die ${\it \Lambda}_i(S_{\mu})$–Auswertung zutreffend?
+ Für alle Knoten gilt ${\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [i \, –{\it \Gamma}_i(S_{\mu})\big ]$.
- Für die Metrikzuwächse gilt $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$.
</quiz>
</quiz>
===Musterlösung===
===Musterlösung===
{{ML-Kopf}}
{{ML-Kopf}}
'''1.'''
'''(1)''' Bei allen Knoten $S_{\mu}$ muss eine Entscheidung zwischen den beiden ankommenden Zweigen getroffen werden. Ausgewählt wird dann jeweils der Zweig, der zur (minimalen) Fehlergröße ${\it \Gamma}_5(S_{\mu})$ geführt hat. Mit $\underline{y}_5 = (01)$ erhält man:
'''(2)''' Zum Zeitpunk $i = 6$ ist bereits die Terminierung wirksam und es gibt nur noch zwei Fehlergrößen. Für diese erhält man mit $\underline{y}_6 = (01)$:
Beim BSC–Modell kann man aus ${\it \Gamma}_7(S_{\mu}) = 3$ darauf schließen, dass drei Übertragungsfehler aufgetreten sind ⇒ <u>Lösungsvorschläge 1 und 3</u>.
[[Category:Aufgaben zu Kanalcodierung|^3.4 Decodierung von Faltungscodes
'''(4)''' Richtig sind die <u>Aussagen 1 und 2</u>:
*Die Maximierung der Metriken ${\it \Lambda}_i(S_{\mu})$ entsprechend der rechten Skizze in obiger Grafik liefert das gleiche Ergebnis wie die links dargestellte Minimierung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$. Auch die überlebenden und gestrichenen Zweige sind in beiden Grafiken identisch.
*Die angegebene Gleichung ist ebenfalls richtig, was hier nur am Beispiel $i = 7$ gezeigt wird:
*Die letzte Aussage ist falsch. Vielmehr gilt $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
''Hinweis:'' In der [[Aufgaben:Aufgabe_3.11:_Viterbi–Pfadsuche| Aufgabe 3.11]] wird für das gleiche Beispiel die Pfadsuche demonstiert, wobei von den ${\it \Lambda}_i(S_{\mu})$–Metriken gemäß der rechten Grafik ausgegangen wird.
{{ML-Fuß}}
^]]
[[Category:Aufgaben zu Kanalcodierung|^3.4 Decodierung von Faltungscodes^]]
Im Theorieteil zu diesem Kapitel wurde die Berechnung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$ ausführlich behandelt, die auf der Hamming–Distanz $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$ zwischen den möglichen Codeworten $\underline{x}\hspace{0.05cm}' ∈ \{00, \, 01, \, 10, \, 11\}$ und dem zum Zeitpunkt $i$ empfangenen 2–Bit–Worten $\underline{y}_i$ basiert.
Die Aufgabe beschäftigt sich genau mit dieser Thematik. In nebenstehender Grafik
ist das betrachtete Trellis dargestellt – gültig für den Code mit Rate $R = 1/2$, Gedächtnis $m = 2$ sowie $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$,
sind die Empfangsworte $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$ in den Rechtecken angegeben,
sind alle Fehlergrößen ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ {\it \Gamma}_4(S_{\mu})$ bereits eingetragen.
Beispielsweise ergibt sich die Fehlergröße ${\it \Gamma}_4(S_0)$ mit $\underline{y}_4 = (01)$ als das Minimum der beiden Vergleichswerte
Der überlebende Zweig – hier von ${\it \Gamma}_3(S_2)$ nach ${\it \Gamma}_4(S_0)$ – ist durchgezogen gezeichnet, der eliminierte Zweig von ${\it \Gamma}_3(S_0)$ nach ${\it \Gamma}_4(S_0)$ punktiert. Rote Pfeile stehen für das Informationsbit $u_i = 0$, blaue Pfeile für $u_i = 1$.
In der Teilaufgabe (4) soll der Zusammenhang zwischen
der ${\it \Gamma}_i(S_{\mu})$–Minimierung und
der ${\it \Lambda}_i(S_{\mu})$–Maximierung
herausgearbeitet werden. Hierbei bezeichnet man die Knoten ${\it \Lambda}_i(S_{\mu})$ als Metriken, wobei sich der Metrikzuwachs gegenüber den Vorgängerknoten aus dem Korrelationswert $〈\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i 〉$ ergibt. Näheres zu dieser Thematik finden Sie auf den folgenden Theorieseiten:
(1) Bei allen Knoten $S_{\mu}$ muss eine Entscheidung zwischen den beiden ankommenden Zweigen getroffen werden. Ausgewählt wird dann jeweils der Zweig, der zur (minimalen) Fehlergröße ${\it \Gamma}_5(S_{\mu})$ geführt hat. Mit $\underline{y}_5 = (01)$ erhält man:
Die linke Grafik zeigt das endgültig ausgewertete ${\it \Gamma}_i(S_{\mu})$–Trellis.
Ausgewertete Trellisdiagramme
(2) Zum Zeitpunk $i = 6$ ist bereits die Terminierung wirksam und es gibt nur noch zwei Fehlergrößen. Für diese erhält man mit $\underline{y}_6 = (01)$:
Beim BSC–Modell kann man aus ${\it \Gamma}_7(S_{\mu}) = 3$ darauf schließen, dass drei Übertragungsfehler aufgetreten sind ⇒ Lösungsvorschläge 1 und 3.
(4) Richtig sind die Aussagen 1 und 2:
Die Maximierung der Metriken ${\it \Lambda}_i(S_{\mu})$ entsprechend der rechten Skizze in obiger Grafik liefert das gleiche Ergebnis wie die links dargestellte Minimierung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$. Auch die überlebenden und gestrichenen Zweige sind in beiden Grafiken identisch.
Die angegebene Gleichung ist ebenfalls richtig, was hier nur am Beispiel $i = 7$ gezeigt wird:
Die letzte Aussage ist falsch. Vielmehr gilt $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
Hinweis: In der Aufgabe 3.11 wird für das gleiche Beispiel die Pfadsuche demonstiert, wobei von den ${\it \Lambda}_i(S_{\mu})$–Metriken gemäß der rechten Grafik ausgegangen wird.
