Aufgaben:Exercise 3.11: Viterbi Path Finding

• Return to book

Evaluated trellis diagram

One result of  $\text{Exercise 3.10}$  was adjacent trellis evaluation in terms of metrics  ${\it \Lambda}_i(S_{\mu})$. 

• At all decoding steps  $i$  the  $($in general$)$  $2^m = 4$  metrics were determined,  selecting for each node the larger of two comparison values. 

• The branch with the lower value was discarded. One can recognize discarded branches in the graph by dotted lines.

Otherwise,  the same conditions apply as for  $\text{Exercise 3.10}$.  For example,  also in the adjacent graph,  a red arrow indicates the information bit  $u_i = 0$  and a blue arrow stands for  $u_i = 1$.

In the present exercise we consider the second and important part of the Viterbi algorithm,  namely the search for the  "surviving paths"  ${\it \Phi}_i(S_{\mu})$.  These are at time  $i$  in state  $S_{\mu}$  with $\mu \in \{1,\ 2,\ 3,\ 4 \}$.  The search is best organized in the backward direction  $($i.e.,  from bottom to top in the graph$)$.

At the end time  $($in the example  $i = 7)$  there is only one surviving path  ${\it \Phi}_7(S_0)$ due to termination.  From this it is possible to extract:

• the sequence  $\underline{z}$   selected by the decoder  $($short:  "decoder sequence"$)$  ⇒   highest possible probability  ${\rm Pr}(\underline{z} = \underline{x})$,

• the associated information sequence  $\underline{v}$  with the greatest possible probability  ${\rm Pr}(\underline{v} = \underline{u})$.

A decision at an earlier time,  for example at  $i = 5$,  does not always satisfy the maximum likelihood criterion.  Here there are four surviving paths  ${\it \Phi}_5(S_0), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ {\it \Phi}_5(S_3)$, which at time  $i = 5$  are in states  $S_0, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ S_3$.

• One of these four paths is certainly part of the maximum likelihood path,  which is the best possible path for  $i → ∞$  $($at termination significantly earlier,  here at  $i = 7)$.

• But if a constraint decision is to be made already at time  $i = 5$,  one usually chooses the path  ${\it \Phi}_5(S_{\mu})$  with the largest metric at that time  ${\it \Lambda}_5(S_{\mu})$.

Hints:

• This exercise belongs to the chapter  "Decoding of Convolutional Codes".

• Reference is made in particular to the section  "Evaluating the trellis in the error-free case – Path finding".

Questions

1

For which estimated sequence  $\underline{z}$  $($for the encoded sequence  $\underline{z})$  does the decision fall at time  $i = 7$?

	$\underline{z} = (11, \, 10, \, 00, \, 01, \, 01, \, 11, \, 00)$,
	$\underline{z} = (00, \, 11, \, 10, \, 00, \, 01, \, 01, \, 11)$,
	$\underline{z} = (00, \, 11, \, 01, \, 01, \, 00, \, 10, \, 11)$.

2

How many transmission errors have occurred  $($at least$)$?

$N_{\rm bit\:error} \ = \ $

3

Which information sequence  $\underline{v}$  does the Viterbi decoder choose?

	$\underline{v} = (0, \, 1, \, 0, \, 1, \, 1, \, 0, \, 0)$,
	$\underline{v} = (1, \, 0, \, 1, \, 1, \, 0, \, 0, \, 0)$,
	$\underline{v} = (0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0)$.

4

Would a final  $($and correct$)$  decision have been possible already at  $i = 6$?

	Yes.
	No.

5

What surviving paths exist at time  $i = 5$?

	$S_0 → S_0 → S_1 → S_3 → S_2 → S_0$,
	$S_0 → S_0 → S_1 → S_3 → S_2 → S_1$,
	$S_0 → S_1 → S_2 → S_1 → S_3 → S_2$,
	$S_0 → S_0 → S_1 → S_2 → S_1 → S_3$.

6

Which path would you choose at time  $i = 5$?

	$S_0 → S_0 → S_1 → S_3 → S_2 → S_0$,
	$S_0 → S_0 → S_1 → S_3 → S_2 → S_1$,
	$S_0 → S_1 → S_2 → S_1 → S_3 → S_2$,
	$S_0 → S_0 → S_1 → S_2 → S_1 → S_3$.

7

But which of the paths would probably be the right one?

	$S_0 → S_0 → S_1 → S_3 → S_2 → S_0$,
	$S_0 → S_0 → S_1 → S_3 → S_2 → S_1$,
	$S_0 → S_1 → S_2 → S_1 → S_3 → S_2$,
	$S_0 → S_0 → S_1 → S_2 → S_1 → S_3$.

Solution

Solution

(1)  Correct is the proposed solution 2:

• Unambiguously find the surviving path by searching backwards, i.e., from node ${\it \Lambda}_7(S_0)$ to node ${\it \Lambda}_0(S_0)$.
• Using the code sequences $(00, \, 01, \, 10$ or $11)$ given at the transitions, we obtain in the forward direction the result according to Proposition 2   ⇒   ${\it \Phi}_7(S_0)$:

$$\underline{z} = \big (00\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.03cm} \big ) \hspace{0.05cm}.$$

• Do not reach the final node ${\it \Lambda}_7(S_0)$ along the other paths.

(2)  By comparing the code sequence $\underline{z}$ selected in subtask (1) with the received sequence

$$\underline{y} = \big (01\hspace{0.05cm}, 11\hspace{0.05cm}, 00\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.03cm} \big )$$

one detects three bit errors at positions 2, 5, and 8.

• If a code sequence $\underline{x} ≠ \underline{z}$ was sent, there can of course be more.
• Because of the final value ${\it \Lambda}_7(S_0) = 8$ or ${\it \Gamma}_7(S_0) = 3$ – see "Exercise 3.10" – but one can assume that a correct decision   ⇒   $\underline{z} = \underline{x}$ has been made.

Viterbi path finding

(3)  Correct is proposed solution 1:

• From the colors of the surviving path – red represents $u_i = 0$ and blue represents $u_i = 1$ – one can see the correctness of solution proposal 1: red – blue – red – blue – blue – red – red.
• It should be noted that the actual information sequence $\underline{u}$ is only of length $L = 5$.
• Only by termination one arrives at the total length $L' = L + m = 7$.

(4)  At time $i = 6$ there are still two surviving paths. A decision could be forcibly made based on the larger metric. However, because of ${\it \Lambda}_6(S_0) = {\it \Lambda}_6(S_2) = 6$ this is not possible in our example  ⇒  No.

(5)  The graph shows that all proposed solutions are correct. The paths are labeled ${\it \Phi}_5(S_0)$, ... , ${\it \Phi}_5(S_3)$.

(6)  The constraint decision at time $i = 5$ would select the path with the largest metric ${\it \Lambda}_5(S_{\mu})$, i.e., the path ${\it \Phi}_5(S_2)$ corresponding to proposition 3.

(7)  Based on our solution to subtask (1), the path ${\it \Phi}_5(S_3)$ according to proposition 4 would have been the better choice.

• This is part of the path ${\it \Phi}_7(S_0)$.
• At the time $i = 5$, however, there is still nothing in favor of this choice.
• The (ultimately correct) path is only highlighted by the two termination bits.