Difference between revisions of "Aufgaben:Exercise 3.10: Metric Calculation"

From LNTwww
(Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes }} [[File:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-Choice Fra…“)
 
 
(32 intermediate revisions by 6 users not shown)
Line 1: Line 1:
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung von Faltungscodes
+
{{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Convolutional_Codes}}
  
 +
[[File:P_ID2681__KC_A_3_10.png|right|frame|Only partially evaluated trellis]]
 +
In the&nbsp; [[Channel_Coding/Decoding_of_Convolutional_Codes#Preliminary_remarks_on_the_following_decoding_examples| $\text{theory section}$]]&nbsp; of this chapter,&nbsp; the calculation of the branch metrics&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; has been discussed in detail,&nbsp; based on the Hamming distance &nbsp; $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$ &nbsp; between 
 +
*the possible code words &nbsp; $\underline{x}\hspace{0.05cm}' &#8712; \{00, \, 01, \, 10, \, 11\}$&nbsp;
  
 +
*and the 2&ndash;bit&ndash;words&nbsp; $\underline{y}_i$&nbsp; received at time&nbsp; $i$.
  
  
 +
The exercise deals exactly with this topic.&nbsp;  In the adjacent graph
 +
* the considered trellis is shown&nbsp; &ndash; valid for the code with rate&nbsp; $R = 1/2$, &nbsp; memory&nbsp; $m = 2$ &nbsp; and&nbsp;
 +
:$$\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2),$$
 +
 +
* the received words&nbsp; $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$&nbsp; are indicated in the rectangles,
  
 +
* all branch metrics&nbsp; ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm}  , \ {\it \Gamma}_4(S_{\mu})$&nbsp; are already entered.
  
}}
 
  
[[File:|right|]]
+
For example,&nbsp; the branch metric&nbsp; ${\it \Gamma}_4(S_0)$&nbsp; with&nbsp; $\underline{y}_4 = (01)$&nbsp; as the minimum of the two comparison values
 +
* ${\it \Gamma}_3(S_0) + d_{\rm H}((00), \ (01)) = 3 + 1 = 4$,&nbsp; and
  
 +
* ${\it \Gamma}_3(S_2) + d_{\rm H}((11), \ (01)) = 2 + 1 = 3$.
 +
 +
 +
The surviving branch&nbsp; &ndash; here from &nbsp; ${\it \Gamma}_3(S_2)$ &nbsp; to &nbsp; ${\it \Gamma}_4(S_0)$ &nbsp; &ndash; is drawn solid,&nbsp; the eliminated branch from &nbsp; ${\it \Gamma}_3(S_0)$ &nbsp; to &nbsp; ${\it \Gamma}_4(S_0)$ &nbsp; dotted.&nbsp; Red arrows represent the information bit&nbsp; $u_i = 0$,&nbsp; blue arrows&nbsp; $u_i = 1$.
 +
 +
In subtask&nbsp; '''(4)'''&nbsp; shall be worked out the relationship between
 +
*the&nbsp; ${\it \Gamma}_i(S_{\mu})$&nbsp; minimization and
 +
*the&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; maximization.
 +
 +
 +
Here,&nbsp; we refer to the nodes&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; as&nbsp; "correlation metrics",&nbsp; where the metric increment over the predecessor nodes results from the correlation value&nbsp; $&#9001;\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i &#9002;$.&nbsp; For more details on this topic,&nbsp; 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&ndash;terminated convolutional codes"]].
 +
 +
 +
 +
 +
<u>Hints:</u>
 +
* The exercise refers to the chapter&nbsp; [[Channel_Coding/Decoding_of_Convolutional_Codes| "Decoding Convolutional Codes"]].
 +
 +
* For the time being,&nbsp; the search of surviving paths is not considered.&nbsp;
 +
 +
*This will be dealt with for the same example in the later&nbsp; [[Aufgaben:Exercise_3.11:_Viterbi_Path_Finding| $\text{Exercise 3.11}$]].
 +
  
===Fragebogen===
 
  
<quiz display=simple>
 
{Multiple-Choice Frage
 
|type="[]"}
 
- Falsch
 
+ Richtig
 
  
  
{Input-Box Frage
+
===Questions===
 +
<quiz display=simple>
 +
{What are the branch metrics for time&nbsp; $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% }
  
 +
{What are the branch metrics for time&nbsp; $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&nbsp; ${\it \Gamma}_i(S_{\mu})$?
 +
|type="[]"}
 +
+ It holds&nbsp; ${\it \Gamma}_7(S_0) = 3$.
 +
- This final value suggests one error-free transmission.
 +
+ This final value suggests three transmission errors.
  
 +
{Which statements are true for the&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; evaluation?
 +
|type="[]"}
 +
+ The correlation metrics&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; provide the same information as&nbsp; ${\it \Gamma}_i(S_{\mu})$.
 +
+ For all nodes,&nbsp; ${\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [i \, &ndash;{\it \Gamma}_i(S_{\mu})\big ]$.
 +
- For the metric increments,&nbsp; $&#9001; \underline{x}_i', \, \underline{y}_i &#9002; &#8712; \{0, \, 1, \, 2\}$.
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.'''
+
'''(1)'''&nbsp; At all nodes&nbsp; $S_{\mu}$&nbsp; a decision must be made between the two incoming branches.&nbsp; The branch that led to the (minimum) error metric&nbsp; ${\it \Gamma}_5(S_{\mu})$&nbsp; is then selected in each case.&nbsp; With&nbsp; $\underline{y}_5 = (01)$&nbsp; one obtains:
'''2.'''
+
:$${\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},$$
'''3.'''
+
:$${\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},$$
'''4.'''
+
:$${\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},$$
'''5.'''
+
:$${\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}.$$
'''6.'''
+
 
'''7.'''
+
[[File:P_ID2682__KC_A_3_10c_neu.png|right|frame|Evaluated trellis diagrams]]
{{ML-Fuß}}
+
<br><br><br><br>
 +
The left sketch in the graph shows the final evaluated ${\it \Gamma}_i(S_{\mu})$ trellis.
 +
<br clear=all>
 +
'''(2)'''&nbsp; At time&nbsp; $i = 6$&nbsp; the termination is already effective and there are only two branch metrics left.&nbsp; For these one obtains with&nbsp; $\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)'''&nbsp; 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}.$$
  
 +
*With the BSC model,&nbsp; one can infer from&nbsp; ${\it \Gamma}_7(S_{\mu}) = 3$&nbsp; that three transmission errors occurred &nbsp; &#8658; &nbsp; <u>solutions 1 and 3</u>.
  
  
[[Category:Aufgaben zu  Kanalcodierung|^3.4 Decodierung von Faltungscodes
+
'''(4)'''&nbsp; Correct are the &nbsp; <u>statements 1 and 2</u>:  
 +
*Maximizing the correlation branch metrics&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; 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,&nbsp; the surviving and deleted branches are identical in both graphs.
  
 +
*The given equation is also correct,&nbsp; which is shown here only on the example&nbsp; $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.&nbsp; Rather applies&nbsp; $&#9001;x_i', \, y_i&#9002; &#8712; \{&ndash;2, \, 0, \, +2\}$.
  
 +
*In&nbsp; [[Aufgaben:Exercise_3.11:_Viterbi_Path_Finding| $\text{Exercise 3.11}$]],&nbsp; the path finding will be demonstrated for the same example,&nbsp; assuming ${\it \Lambda}_i(S_{\mu})$&nbsp; metrics as shown in the right graph.
 +
{{ML-Fuß}}
  
  
  
^]]
+
[[Category:Channel Coding: Exercises|^3.4 Decoding of Convolutional Codes^]]

Latest revision as of 14:53, 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:

  1. "Relationship between Hamming distance and correlation"
  2. "Viterbi algorithm based on correlation and metrics"
  3. "Viterbi decision for non–terminated convolutional codes".



Hints:

  • For the time being,  the search of surviving paths is not considered. 



Questions

1

What are the branch metrics for time  $i = 5$?

${\it \Gamma}_5(S_0) \ = \ $

${\it \Gamma}_5(S_1) \ = \ $

${\it \Gamma}_5(S_2) \ = \ $

${\it \Gamma}_5(S_3) \ = \ $

2

What are the branch metrics for time  $i = 6$?

${\it \Gamma}_6(S_0) \ = \ $

${\it \Gamma}_6(S_2) \ = \ $

3

What is the final value of this trellis based on  ${\it \Gamma}_i(S_{\mu})$?

It holds  ${\it \Gamma}_7(S_0) = 3$.
This final value suggests one error-free transmission.
This final value suggests three transmission errors.

4

Which statements are true for the  ${\it \Lambda}_i(S_{\mu})$  evaluation?

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\}$.


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}.$$
Evaluated trellis diagrams





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)$:

$${\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}.$$
  • 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$:
$${\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\}$.
  • 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.