Difference between revisions of "Aufgaben:Exercise 3.10: Metric Calculation"
From LNTwww
| Line 2: | Line 2: | ||
[[File:P_ID2681__KC_A_3_10.png|right|frame|Only partially evaluated trellis]] | [[File:P_ID2681__KC_A_3_10.png|right|frame|Only partially evaluated trellis]] | ||
| − | In the [[Channel_Coding/Decoding_of_Convolutional_Codes#Preliminary_remarks_on_the_following_decoding_examples| | + | 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\}$ | ||
| − | + | *and the 2–bit–words $\underline{y}_i$ received at time $i$. | |
| − | * the | ||
| − | |||
| − | |||
| − | + | 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 | |
| − | + | * ${\it \Gamma}_3(S_0) + d_{\rm H}((00), \ (01)) = 3 + 1 = 4$, and | |
| − | |||
| + | * ${\it \Gamma}_3(S_2) + d_{\rm H}((11), \ (01)) = 2 + 1 = 3$. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| + | 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: | ||
| + | :# [[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"]]. | ||
| − | Hints: | + | <u>Hints:</u> |
* The exercise refers to the chapter [[Channel_Coding/Decoding_of_Convolutional_Codes| "Decoding Convolutional Codes"]]. | * 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| | + | |
| + | * 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}$]]. | ||
| Line 62: | Line 69: | ||
+ This final value suggests three transmission errors. | + This final value suggests three transmission errors. | ||
| − | {Which statements are true for the ${\it \Lambda}_i(S_{\mu})$ evaluation? | + | {Which statements are true for the ${\it \Lambda}_i(S_{\mu})$ evaluation? |
|type="[]"} | |type="[]"} | ||
| − | + The metrics ${\it \Lambda}_i(S_{\mu})$ provide the same information as ${\it \Gamma}_i(S_{\mu})$. | + | + 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 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\}$. | - For the metric increments, $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$. | ||
Revision as of 14:29, 18 November 2022
Only partially evaluated trellis
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
- ${\it \Gamma}_3(S_0) + d_{\rm H}((00), \ (01)) = 3 + 1 = 4$, and
- ${\it \Gamma}_3(S_2) + d_{\rm H}((11), \ (01)) = 2 + 1 = 3$.
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:
Hints:
- The exercise refers to the chapter "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 $\text{Exercise 3.11}$.
Questions
Solution
(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:
- $${\it \Gamma}_5(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm},$$
- $${\it \Gamma}_5(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_2) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm},$$
- $${\it \Gamma}_5(S_2) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_3) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] = {\rm min} \left [ 3+2\hspace{0.05cm},\hspace{0.05cm} 2+0 \right ] \hspace{0.15cm}\underline{= 2}\hspace{0.05cm},$$
- $${\it \Gamma}_5(S_3) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+0\hspace{0.05cm},\hspace{0.05cm} 2+2 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$
The left graph shows the final evaluated ${\it \Gamma}_i(S_{\mu})$ trellis.
Evaluated trellis diagrams
(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)$:
- $${\it \Gamma}_6(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{5}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{5}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm},$$
- $${\it \Gamma}_6(S_2) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{5}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{5}(S_3) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+2\hspace{0.05cm},\hspace{0.05cm} 3+0 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$
(3) The final value results to
- $${\it \Gamma}_7(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{6}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (11) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{6}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (11) \big ) \right ] ={\rm min} \left [ 3+2\hspace{0.05cm},\hspace{0.05cm} 3+0 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$
In 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 statements 1 and 2:
- Maximizing the branch metrics ${\it \Lambda}_i(S_{\mu})$ according to the right sketch in the above graph gives the same result as minimizing the 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$:
- $${\it \Lambda}_7(S_0)) = 2 \cdot \big [i - {\it \Gamma}_7(S_0) \big ] = 2 \cdot \big [7 - 3 \big ] \hspace{0.15cm}\underline{= 8}\hspace{0.05cm}.$$
- The last statement is false. Rather applies $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.
Hints: In "Exercise 3.11", path finding is demonstrable for the same example, assuming ${\it \Lambda}_i(S_{\mu})$–metrics as shown in the right graph.
