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

corresponding input from the trellis path that has been identified. Remember
here that the path has input information: if a branch in the path has a heavy
arrow then the input symbol is 1 , and if it is a light arrow the input symbol
is

1 . Thus, having found the closest path, we can identify the transmitted
symbol stream which generates this path. Of course, we have not argued that
the distance measure based on the Euclidean distance (5.68) is optimal in any
way, for example in the sense of minimizing error probabilities, but we shall
return to that in Sec. 5.6.4.
The disadvantage of the “brute force” method described above is that we
have too many paths to search, and the computational load becomes unreson-
able very quickly. However, there is great deal of structure in the trellis, and
Viterbi's algorithm is an ingenious way to exploit this structure and reduce the
computational load dramatically. We describe this next.

−

5.6.3 The Viterbi algorithm

The Viterbi algorithm is best described with an example. Consider an FIR

channel with the transfer function

H ( z )=1+0 . 5 z − 1

(5 . 69)

as in Fig. 5.16(a). Let the input s ( n )bedrawnfroma1-bitPAM(BPSK)
constellation so that s ( n )=

± 1 . The state vector is just a scalar:

x ( n )= s ( n − 1) . (5 . 70)

Figure 5.16(b) shows the basic trellis module for an input sequence of length
one. The system has two possible states, namely 1 and − 1. If s ( n ) = 1 then the

next state becomes a 1 , whereas if s ( n )= − 1 , the next state becomes a − 1 . The

output at any time n is y ( n )= s ( n )+0 . 5 s ( n − 1), that is,

y ( n )= s ( n )+0 . 5 x ( n ) . (5 . 71)

Recall that the trellis carries the following information:

1. The state transition is shown using a thick arrow if the input is 1 and a
thin arrow if the input is − 1 .

2. The output calculated using (5.71) is indicated alongside the transitioning
arrow.

For example, if the system is in state 1 and the input is a − 1, then the next

state is − 1 and the output is − 1+0 . 5= − 0 . 5. This is indicated by the thin

down going arrow in Fig. 5.16(b) labeled 0 . 5. The other arrows in the figure

are obtained similarly. To work out a specific example, we now assume that the
first few samples of the noisy output are

−

n 01 2 34
r ( n )1

(5 . 72)

− 0 . 4 − 0 . 80 . 11 . 1