Digital Signal Processing Reference
In-Depth Information
a finite set of values. Since each sample can take
M
possible values (size of the
symbol constellation), there can be
M
L
possible values for the state vector
x
(
n
)
.
s
(
n
−1)
s
(
n
−2)
s
(
n
)
z
−1
z
−1
h
(0)
h
(1)
h
(2)
s
(
n
)
est
y
(
n
)
r
(
n
)
+
detector
FIR channel
q
(
n
)
Figure 5.14
. The discrete-time equivalent of the digital communication channel.
To explain the Viterbi algorithm we first need to understand something called
the
trellis
diagram. This diagram is useful to keep track of the states as a function
of the input sequence. It has one stage per instant of time. In each stage, each
of the
M
L
possible values of the state is assigned a node. For example, when
M
= 2 and
L
=2thereare
M
L
= 4 possible states, as shown in Fig. 5.15(a).
Assume that the finite state machine is in a particular state
x
(
n
)attime
n.
When the next input
s
(
n
) comes in, the values of the state variables change,
and the trellis diagram shows all the
M
state transitions that are possible (one
for each possible value of
s
(
n
)).
The trellis diagram shown in Fig. 5.15(a) is for the second-order FIR system
of Fig. 5.14 with one-bit PAM input. So the input constellation is
{
1
,
−
1
}
.Thus
the four possible states of the system are (1
,
1)
,
(
1)
.
Assume for example that the system is initially in the state (1
,
1)
,
and an input
s
(0) = 1 comes along. Then after one unit of time this input appears at the
output of the first delay, and the state remains (1
,
1)
.
On the other hand if the
input is
s
(0) =
−
1
,
1)
,
(1
,
−
1)
,
and (
−
1
,
−
1
,
1)
.
These two choices are
indicated in the figure with a
heavy arrow
for
s
(0) = 1 and a
light arrow
for
s
(0) =
−
1, then the state changes to (
−
1
.
So the state at time
n
= 1 can be one of the two states indicated.
From each of these two states two transitions are possible, depending on whether
s
(1) = 1 or
−
1
.
The trellis diagram therefore grows as indicated in Fig. 5.15(a).
The figure starts with some initial state (1
,
1) and then considers every pos-
sible choice of the input sample at every succeeding instant of time. After each
state has been reached at least once, a steady condition is reached, and the trellis
diagram becomes a
periodic
pattern, with the same set of criss-crosses repeated
for ever. In fact, right from the beginning we can consider all possible states
and draw a “full trellis.”
−
Search WWH ::
Custom Search