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}', \ \underline{y}_i)$ zwischen den möglichen Codeworten $\underline{x}' ∈ \{00, \, 01, \, 10, \, 11\}$ und den zu dem Zeitpunkt $i$ empfangenen 2–Bit–Worten $\underline{y}_i$ basiert.
In the [[Channel_Coding/Decoding_of_Convolutional_Codes#Preliminary_remarks_on_the_following_decoding_examples| $\text{theory section}$]] of this chapter, the calculation of the branch metrics ${\it \Gamma}_i(S_{\mu})$ has been discussed in detail, based on the Hamming distance $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$ between
*the possible code words $\underline{x}\hspace{0.05cm}' ∈ \{00, \, 01, \, 10, \, 11\}$
Die Aufgabe beschäftigt sich genau mit dieser Thematik. In nebenstehender Grafik
*and the 2–bit–words $\underline{y}_i$ received at time $i$.
* 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), \ ... \ , \ \underline{y}_7 = (11)$ in den Rechtecken angegeben,
* sind bereits alle Fehlergrößen ${\it \Gamma}_0(S_{\mu}), \ ... \ , \ {\it \Gamma}_4(S_{\mu})$ eingetragen.
Beispielsweise ergibt sich die Fehlergröße ${\it \Gamma}_4(S_0)$ mit $\underline{y}_4 = (01)$ als das Minimum der beiden Vergleichswerte
The exercise deals exactly with this topic. In the adjacent graph
* the considered trellis is shown – valid for the code with rate $R = 1/2$, memory $m = 2$ and
:$$\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2),$$
* the received words $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$ are indicated in the rectangles,
* all branch metrics ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ {\it \Gamma}_4(S_{\mu})$ are already entered.
For example, the branch metric ${\it \Gamma}_4(S_0)$ with $\underline{y}_4 = (01)$ as the minimum of the two comparison values
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$.
The surviving branch – here from ${\it \Gamma}_3(S_2)$ to ${\it \Gamma}_4(S_0)$ – is drawn solid, the eliminated branch from ${\it \Gamma}_3(S_0)$ to ${\it \Gamma}_4(S_0)$ dotted. Red arrows represent the information bit $u_i = 0$, blue arrows $u_i = 1$.
In subtask '''(4)''' shall be worked out the relationship between
*the ${\it \Gamma}_i(S_{\mu})$ minimization and
Here, we refer to the nodes ${\it \Lambda}_i(S_{\mu})$ as "correlation metrics", where the metric increment over the predecessor nodes results from the correlation value $〈\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i 〉$. For more details on this topic, see the following theory sections:
:# [[Channel_Coding/Decoding_of_Convolutional_Codes#Relationship_between_Hamming_distance_and_correlation| "Relationship between Hamming distance and correlation"]]
:# [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics| "Viterbi algorithm based on correlation and metrics"]]
:# [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_decision_for_non-terminated_convolutional_codes| "Viterbi decision for non–terminated convolutional codes"]].
In der Teilaufgabe (4) soll der Zusammenhang zwischen ${\it \Gamma}_i(S_{\mu})$–Minimierung und ${\it \Lambda}_i(S_{\mu})$–Maximierung 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', \, \underline{y}_i 〉$ ergibt. Näheres zu dieser Thematik finden Sie auf den folgenden Theorieseiten:
<u>Hints:</u>
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Zusammenhang_zwischen_Hamming.E2.80.93Distanz_und_Korrelation| Zusammenhang zwischen Hamming–Distanz und Korrelation]],
* The exercise refers to the chapter [[Channel_Coding/Decoding_of_Convolutional_Codes| "Decoding Convolutional Codes"]].
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken| Viterbi–Algorithmus, basierend auf Korrelation und Metriken (1)]],
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Entscheidung_bei_nicht.E2.80.93terminierten_Faltungscodes| Viterbi–Algorithmus, basierend auf Korrelation und Metriken (2)]].
* For the time being, the search of surviving paths is not considered.
''Hinweise:''
*This will be dealt with for the same example in the later [[Aufgaben:Exercise_3.11:_Viterbi_Path_Finding| $\text{Exercise 3.11}$]].
* 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 nachfolgende [[Aufgaben:3.11_Viterbi%E2%80%93Pfadsuche| Aufgabe A3.11]].
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Wie lauten die Fehlergrößen für den Zeitpunkt $i = 5$?
{What are the branch metrics for time $i = 5$?
|type="{}"}
|type="{}"}
${\it \Gamma}_5(S_0) \ = \ ${ 3 3% }
${\it \Gamma}_5(S_0) \ = \ ${ 3 3% }
Line 38:
Line 58:
${\it \Gamma}_5(S_3) \ = \ ${ 3 3% }
${\it \Gamma}_5(S_3) \ = \ ${ 3 3% }
{Wie lauten die Fehlergrößen für den Zeitpunkt $i = 6$?
{What are the branch metrics for time $i = 6$?
|type="{}"}
|type="{}"}
${\it \Gamma}_6(S_0) \ = \ ${ 3 3% }
${\it \Gamma}_6(S_0) \ = \ ${ 3 3% }
${\it \Gamma}_6(S_2) \ = \ ${ 3 3% }
${\it \Gamma}_6(S_2) \ = \ ${ 3 3% }
{Welcher Endwert ergibt sich bei diesem Trellis, basierend auf ${\it \Gamma}_i(S_{\mu})$?
{What is the final value of this trellis based on ${\it \Gamma}_i(S_{\mu})$?
|type="[]"}
|type="[]"}
+ Es gilt ${\it \Gamma}_7(S_0) = 3$.
+ It holds ${\it \Gamma}_7(S_0) = 3$.
- Der Endwert lässt auf eine fehlerfreie Übertragung schließen.
- This final value suggests one error-free transmission.
+ Der Endwert lässt auf drei Übertragungsfehler schließen.
+ This final value suggests three transmission errors.
{Welche Aussagen sind für die ${\it \Lambda}_i(S_{\mu})$–Auswertung zutreffend?
{Which statements are true for the ${\it \Lambda}_i(S_{\mu})$ evaluation?
|type="[]"}
|type="[]"}
+ Die Metriken ${\it \Lambda}_i(S_{\mu})$ liefern gleiche Informationen wie ${\it \Gamma}_i(S_{\mu})$.
+ The correlation metrics ${\it \Lambda}_i(S_{\mu})$ provide the same information as ${\it \Gamma}_i(S_{\mu})$.
+ Für alle Knoten gilt ${\it \Lambda}_i(S_{\mu}) = 2 \cdot [i \, –{\it \Gamma}_i(S_{\mu})$.
+ For all nodes, ${\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\}$.
- For the metric increments, $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$.
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''(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:
'''(1)''' At all nodes $S_{\mu}$ a decision must be made between the two incoming branches. The branch that led to the (minimum) error metric ${\it \Gamma}_5(S_{\mu})$ is then selected in each case. With $\underline{y}_5 = (01)$ one obtains:
'''(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)$:
'''(2)''' At time $i = 6$ the termination is already effective and there are only two branch metrics left. For these one obtains with $\underline{y}_6 = (01)$:
Beim BSC–Modell kann aus ${\it \Gamma}_7(S_{\mu}) = 3$ darauf geschlossen werden, dass drei Übertragungsfehler aufgetreten sind ⇒ <u>Lösungsvorschläge 1 und 3</u>.
*With the BSC model, one can infer from ${\it \Gamma}_7(S_{\mu}) = 3$ that three transmission errors occurred ⇒ <u>solutions 1 and 3</u>.
'''(4)''' Richtig sind die <u>Aussagen 1 und 2</u>. Die Maximierung der Metriken ${\it \Gamma}_i(S_{\mu})$ entsprechend der rechten 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.
'''(4)''' Correct are the <u>statements 1 and 2</u>:
*Maximizing the correlation branch metrics ${\it \Lambda}_i(S_{\mu})$ according to the right sketch in the above graph gives the same result as minimizing the Hamming branch metrics ${\it \Gamma}_i(S_{\mu})$ shown on the left.
Die angegebene Gleichung ist ebenfalls richtig, was hier nur am Beispiel $i = 7$ gezeigt wird:
*Also, the surviving and deleted branches are identical in both graphs.
*The last statement is false. Rather applies $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
''Hinweis:'' In der [[Aufgaben:3.11_Viterbi%E2%80%93Pfadsuche| Aufgabe A3.11]] wird für das gleiche Beispiel die Pfadsuche demonstiert, wobei von den ${\it \Lambda}_i(S_{\mu})$–Metriken entsprechend der rechten Grafik ausgegangen wird.
*In [[Aufgaben:Exercise_3.11:_Viterbi_Path_Finding| $\text{Exercise 3.11}$]], the path finding will be demonstrated for the same example, assuming ${\it \Lambda}_i(S_{\mu})$ metrics as shown in the right graph.
{{ML-Fuß}}
{{ML-Fuß}}
[[Category:Aufgaben zu Kanalcodierung|^3.4 Decodierung von Faltungscodes^]]
[[Category:Channel Coding: Exercises|^3.4 Decoding of Convolutional Codes^]]
In the $\text{theory section}$ of this chapter, the calculation of the branch metrics ${\it \Gamma}_i(S_{\mu})$ has been discussed in detail, based on the Hamming distance $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$ between
the possible code words $\underline{x}\hspace{0.05cm}' ∈ \{00, \, 01, \, 10, \, 11\}$
and the 2–bit–words $\underline{y}_i$ received at time $i$.
The exercise deals exactly with this topic. In the adjacent graph
the considered trellis is shown – valid for the code with rate $R = 1/2$, memory $m = 2$ and
$$\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2),$$
the received words $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$ are indicated in the rectangles,
all branch metrics ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ {\it \Gamma}_4(S_{\mu})$ are already entered.
For example, the branch metric ${\it \Gamma}_4(S_0)$ with $\underline{y}_4 = (01)$ as the minimum of the two comparison values
The surviving branch – here from ${\it \Gamma}_3(S_2)$ to ${\it \Gamma}_4(S_0)$ – is drawn solid, the eliminated branch from ${\it \Gamma}_3(S_0)$ to ${\it \Gamma}_4(S_0)$ dotted. Red arrows represent the information bit $u_i = 0$, blue arrows $u_i = 1$.
In subtask (4) shall be worked out the relationship between
the ${\it \Gamma}_i(S_{\mu})$ minimization and
the ${\it \Lambda}_i(S_{\mu})$ maximization.
Here, we refer to the nodes ${\it \Lambda}_i(S_{\mu})$ as "correlation metrics", where the metric increment over the predecessor nodes results from the correlation value $〈\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i 〉$. For more details on this topic, see the following theory sections:
(1) At all nodes $S_{\mu}$ a decision must be made between the two incoming branches. The branch that led to the (minimum) error metric ${\it \Gamma}_5(S_{\mu})$ is then selected in each case. With $\underline{y}_5 = (01)$ one obtains:
The left sketch in the graph shows the final evaluated ${\it \Gamma}_i(S_{\mu})$ trellis.
(2) At time $i = 6$ the termination is already effective and there are only two branch metrics left. For these one obtains with $\underline{y}_6 = (01)$:
With the BSC model, one can infer from ${\it \Gamma}_7(S_{\mu}) = 3$ that three transmission errors occurred ⇒ solutions 1 and 3.
(4) Correct are the statements 1 and 2:
Maximizing the correlation branch metrics ${\it \Lambda}_i(S_{\mu})$ according to the right sketch in the above graph gives the same result as minimizing the Hamming branch metrics ${\it \Gamma}_i(S_{\mu})$ shown on the left.
Also, the surviving and deleted branches are identical in both graphs.
The given equation is also correct, which is shown here only on the example $i = 7$:
The last statement is false. Rather applies $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
In $\text{Exercise 3.11}$, the path finding will be demonstrated for the same example, assuming ${\it \Lambda}_i(S_{\mu})$ metrics as shown in the right graph.
