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 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:
In subtask '''(4)''' shall be worked out the relationship between
* [[Kanalcodierung/Decodierung_von_Faltungscodes#Zusammenhang_zwischen_Hamming.E2.80.93Distanz_und_Korrelation| Zusammenhang zwischen Hamming–Distanz und Korrelation]],
*the ${\it \Gamma}_i(S_{\mu})$ minimization and
* [[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)]].
''Hinweise:''
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:
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Decodierung_von_Faltungscodes| Decodierung von Faltungscodes]].
:# [[Channel_Coding/Decoding_of_Convolutional_Codes#Relationship_between_Hamming_distance_and_correlation| "Relationship between Hamming distance and correlation"]]
* 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]].
:# [[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"]].
===Fragebogen===
<u>Hints:</u>
* The exercise refers to the chapter [[Channel_Coding/Decoding_of_Convolutional_Codes| "Decoding Convolutional Codes"]].
* For the time being, the search of surviving paths is not considered.
*This will be dealt with for the same example in the later [[Aufgaben:Exercise_3.11:_Viterbi_Path_Finding| $\text{Exercise 3.11}$]].
===Questions===
<quiz display=simple>
<quiz display=simple>
{Multiple-Choice
{What are the branch metrics for time $i = 5$?
|type="{}"}
${\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% }
{What are the branch metrics for time $i = 6$?
|type="{}"}
${\it \Gamma}_6(S_0) \ = \ ${ 3 3% }
${\it \Gamma}_6(S_2) \ = \ ${ 3 3% }
{What is the final value of this trellis based on ${\it \Gamma}_i(S_{\mu})$?
|type="[]"}
|type="[]"}
+ correct
+ It holds ${\it \Gamma}_7(S_0) = 3$.
- false
- This final value suggests one error-free transmission.
+ This final value suggests three transmission errors.
{Input-Box Frage
{Which statements are true for the ${\it \Lambda}_i(S_{\mu})$ evaluation?
|type="{}"}
|type="[]"}
$xyz \ = \ ${ 5.4 3% } $ab$
+ The correlation metrics ${\it \Lambda}_i(S_{\mu})$ provide the same information as ${\it \Gamma}_i(S_{\mu})$.
+ For all nodes, ${\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [i \, –{\it \Gamma}_i(S_{\mu})\big ]$.
- For the metric increments, $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$.
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)'''
'''(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.
<br clear=all>
'''(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 ⇒ <u>solutions 1 and 3</u>.
'''(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.
*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 [[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.
