Exercise 3.12: Trellis Diagram for Two Precursors

• Return to book

Trellis diagram for two precursors

We assume the basic pulse values   $g_0$,  $g_{\rm –1}$  and  $g_{\rm –2}$: 

• This means that the decision on the symbol   $a_{\rm \nu}$  is also influenced by the subsequent coefficients   $a_{\rm \nu +1}$  and  $a_{\rm \nu +2}$. 
• Thus, for each time point   $\nu$,  exactly eight error quantities   $\varepsilon_{\rm \nu}$  have to be determined, from which the minimum total error quantities   ${\it \Gamma}_{\rm \nu}(00)$,  ${\it \Gamma}_{\rm \nu}(01)$,  ${\it \Gamma}_{\rm \nu}(10)$  and  ${\it \Gamma}_{\rm \nu}(11)$  can be calculated.
• Here, for example,   ${\it \Gamma}_{\rm \nu}(01)$  provides information about the symbol   $a_{\rm \nu}$  under the assumption that   $a_{\rm \nu +1} = 0$  and  $a_{\rm \nu +2} = 1$  will be.
• Here, the minimum total error quantity   ${\it \Gamma}_{\rm \nu}(01)$  is the smaller value obtained from the comparison of

$$\big[{\it \Gamma}_{\nu-1}(00) + \varepsilon_{\nu}(001)\big] \hspace{0.15cm}{\rm and} \hspace{0.15cm}\big[{\it \Gamma}_{\nu-1}(10) + \varepsilon_{\nu}(101)\big].$$

To calculate the minimum total error quantity   ${\it \Gamma}_2(10)$  in subtasks (1) and (2), assume the following numerical values:

• unipolar amplitude coefficients:  $a_{\rm \nu} ∈ \{0, 1\}$,
• basic pulse values   $g_0 = 0.5$,  $g_{\rm –1} = 0.3$,  $g_{\rm –2} = 0.2$,
• applied detection sample:  $d_2 = 0.2$,
• Minimum total error quantities at time  $\nu = 1$:

$${\it \Gamma}_{1}(00) = 0.0,\hspace{0.2cm}{\it \Gamma}_{1}(01) = 0.2, \hspace{0.2cm} {\it \Gamma}_{1}(10) = 0.6,\hspace{0.2cm}{\it \Gamma}_{1}(11) = 1.2 \hspace{0.05cm}.$$

The graph shows the simplified trellis diagram for time points   $\nu = 1$  to   $\nu = 8$. 

• Blue branches come from either   ${\it \Gamma}_{\rm \nu –1}(00)$  or   ${\it \Gamma}_{\rm \nu –1}(01)$  and denote a hypothetical "$0$".
• In contrast, all red branches – starting from the   ${\it \Gamma}_{\rm \nu –1}(10)$  or   ${\it \Gamma}_{\rm \nu –1}(11)$  states – indicate the symbol "$1$".

Notes:

• The exercise belongs to the chapter   "Viterbi Receiver".

• All quantities here are to be understood normalized.
• Also, assume unipolar and equal probability amplitude coefficients:   ${\rm Pr} (a_\nu = 0) = {\rm Pr} (a_\nu = 1)= 0.5.$
• The topic is also covered in the interactive applet  "Properties of the Viterbi Receiver". 

Questions

1

Calculate the following error quantities:

$\varepsilon_2(010) \ = \ $

$\varepsilon_2(011) \ = \ $

$\varepsilon_2(110) \ = \ $

$\varepsilon_2(111) \ = \ $

2

Calculate the following minimum total error quantities:

${\it \Gamma}_2(10) \ = \ $

${\it \Gamma}_2(11) \ = \ $

3

What are the symbols output by the Viterbi receiver?

	The first seven symbols are  $1011010$.
	The first seven symbols are  $1101101$.
	The last symbol  $a_8 = 1$  is safe.
	No definite statement can be made about the symbol  $a_8$.

Solution

Solution

(1)  The first error quantity is calculated as follows:

$$\varepsilon_{2}(010) = [d_0 - 0 \cdot g_0 - 1 \cdot g_{-1}- 0 \cdot g_{-2}]^2= [0.2 -0.3]^2\hspace{0.15cm}\underline {=0.01} \hspace{0.05cm}.$$

Correspondingly, for the other error quantities:

$$\varepsilon_{2}(011) \ = \ [0.2 -0.3- 0.2]^2\hspace{0.15cm}\underline {=0.09}\hspace{0.05cm},$$

$$\varepsilon_{2}(110) \ = \ [0.2 -0.5- 0.3]^2\hspace{0.15cm}\underline {=0.36}\hspace{0.05cm},$$

$$\varepsilon_{2}(111) \ = \ [0.2 -0.5- 0.3-0.2]^2\hspace{0.15cm}\underline {=0.64} \hspace{0.05cm}.$$

(2)  The task is to find the minimum value of each of two comparison values:

$${\it \Gamma}_{2}(10) \ = \ {\rm Min}\left[{\it \Gamma}_{1}(01) + \varepsilon_{2}(010), \hspace{0.2cm}{\it \Gamma}_{1}(11) + \varepsilon_{2}(110)\right] = {\rm Min}\left[0.2+ 0.01, 1.2 + 0.36\right]\hspace{0.15cm}\underline {= 0.21} \hspace{0.05cm},$$

$${\it \Gamma}_{2}(11) \ = \ {\rm Min}\left[{\it \Gamma}_{1}(01) + \varepsilon_{2}(011), \hspace{0.2cm}{\it \Gamma}_{1}(11) + \varepsilon_{2}(111)\right] = {\rm Min}\left[0.2+ 0.09, 1.2 + 0.64\right]\hspace{0.15cm}\underline {= 0.29} \hspace{0.05cm}.$$

(3)  The first and last solutions are correct:

• The sequence $1011010$ can be recognized from the continuous path:     "red – blue – red – red – blue – red – blue".
• On the other hand, no final statement can be made about the symbol $a_8$ at time $\nu = 8$:
• Only under the hypothesis $a_9 = 1$ and $a_{\rm 10} = 1$ one would decide for $a_8 = 0$, under other hypotheses for $a_8 = 1$.