Classical transceiver techniques - Signal Processing and Optimization for Transceiver Systems - page 196

path to be

| 2 =0 . 25 .

cost = | r (0) − y (0)

This is nothing but the square of the distance between the quantities r (0) and
y (0) . The costs corresponding to all four combinations of the initial state and
input are indicated in the figure. The minimum-cost path to reach the state

1
is the thin downward arrow, whereas the minimum-cost path to reach the state
1 can be taken to be either of the two choices. This results in the trellis shown
at the top of Fig. 5.18 (stage 0). In this figure, the minimum cost of reaching
each node (state) is indicated in bold. This idea of computing all possible paths
to a state and retaining only the minimum-cost path is central to the algorithm.
It is continued with each successive output sample r ( n ) one after another. Thus
the trellis grows, and in the process we can estimate an initial segment of the
transmitted symbol stream as demonstrated next.

−

1. Stage 1 (time n = 1). Consider the output y (1) . Thefourpossibleways
to generate this output are shown at stage 1 in the figure, and the four
possible values of y (1) are indicated alongside the four arrows. Since the
actual (noisy) output is r (1) = | 2 associated

− 0 . 4, the costs | r (1) − y (1)

with the two choices to reach state 1 are

| 2 =3 . 61 | 2 =0 . 81 . |− 0 . 4 − 1 . 5 or |− 0 . 4 − 0 . 5

These costs must be added to the earlier cost of reaching the state from
which these paths originate. Thus the total cost to reach state 1 at time
n = 1 is given by

| 2 =3 . 86 | 2 =3 . 06 .

either 0 . 25 + |− 0 . 4 − 1 . 5 or 2 . 25 + |− 0 . 4 − 0 . 5

Similarly, at time n = 1 the total cost to reach state − 1isgivenby

| 2 =0 . 26 | 2 =3 . 46 . either 0 . 25 + |− 0 . 4+ . 5 or 2 . 25 + |− 0 . 4+1 . 5

Retaining only the path to each state that has minimum cost we obtain the
pruned trellis shown in stage 2, with the costs to reach the states indicated
as 3 . 06 and 0 . 26.

2. Stage 2 (time n = 2). We now add one more trellis stage and compute
all the costs corresponding to the next noisy output r (2) = 0 . 8. These

are indicated in the figure. Retaining one path per state with minimum
cost, we get the pruned tree shown in stage 3. At this point we notice
something interesting. Namely, the initial segments of length two in the
minimum-cost paths to the two states have merged into a common initial
sub-path . This means that we are ready to make a decision about the
two transmitted symbols s (0) and s (1) . Recalling here that thin arrows
correspond to s ( n )=

−

1 and thick arrows to s ( n )=1 , we see that the
symbol estimates so far are

−

s est (0)=1 and s est (1) = − 1 .