Digital Signal Processing Reference
In-Depth Information
000 and 111 is three. Therefore, the branch metric value for the branch from State
00 to State 00 is zero, and for the branch from State 00 to State 10 it is two. Since
the previous accumulated error metric values are equal to zero, the accumulated
metric values for State 00 and for State 10 are equal to the branch metric values.
The accumulated error metric values for the other two states are undefined (in the
program, this undefined value is initialized to be the maximum value for integer).
The path history table is updated for every time instant. This table, which has an
entry for each state, stores the surviving path for that state at each time instant.
These results at
t
1 are shown in Figure 10.50
a
.
Consider that at
t
=
2, 110 is received at the input of the decoder. The possible
channel symbol triads that could have been received in going from
t
=
2 are
000 going from State 00 to State 00, 111 going from State 00 to State 10, 001 going
from State 10 to State 01, and 110 going from State 10 to State 11. The Hamming
distance is two between 000 and 110, one between 111 and 110, three between 001
and 110, and zero between 110 and 110. These branch metric values are added to
the previous accumulated error metric values associated with each state that we
came from to get to the current states. At
t
=
1 to
t
=
1, we can only be at State 00 or State
10. The accumulated error metric values associated with those states were 0 and 2,
respectively. The calculation of the accumulated error metric associated with each
state at
t
=
2 is shown in Figure 10.50
b
.
Consider that at
t
=
3, 010 is received. There are now two different ways that we
can get from each of the four states that were valid at
t
=
=
2 to the four states that
are valid at
t
3. To handle that, we compare the accumulated error metrics asso-
ciated with each branch and discard the larger one of each pair of branches leading
into a given state. If the members of a pair of accumulated error metrics going into
a particular state are equal, that value is saved. The operation of adding the previ-
ously accumulated error metrics to the new branch metrics, comparing the results,
and selecting the smaller accumulated error metric to be retained for the next time
instant is called the
add-compare-select
operation. The path history for a state is also
updated by selecting the path corresponding to the smallest path metric for that
state. This can be found by adding the current selected path transition to the path
history of its previous state. The result for
t
=
=
3 follows.
3, the decoder has reached its steady state; that is, it is possible to have
eight possible state transitions. For every other time instant from now on, the same
process gets repeated until the end of input is reached. The last two inputs that are
received in a Viterbi decoder are also considered special cases. At the convolutional
encoder, when the end of input is reached, we input two trailing zeros in order to
reset the shift register states to zero. As a consequence of this, in a Viterbi decoder,
in the last but one time instant, the only possible states in the Viterbi decoder are
State 00 and State 01. Therefore, the expected inputs are 000, 011, 001, and 010. And
for the last time instant, the only possible state is 00. Therefore, the expected inputs
are only 000 and 011. This case is illustrated in Figure 10.50
c
.
In the program, it is assumed that the decoder has a memory of only 16, meaning
that at any one time, the path history can store only 16 paths. As soon as the first
At
t
=
Search WWH ::
Custom Search