CONVOLUTIONAL
DECODER
We shall
consider one of two important techniques:
(1)
maximum-likelihood decoding (Viterbi's algorithm)
(2) sequential decoding.
1. Maximum-Likelihood
Decoding — Viterbi's Algorithm
Among
various decoding methods for convolutional codes, Viterbi's maximum-likelihood
algorithm is one of the best techniques yet evolved for digital communications
where energy efficiency dominates in importance. It permits major equipment
simplification while obtaining the full performance benefits of
maximum-likelihood decoding. The decoder structure is relatively simple for
short constraint lengths, making decoding feasible at relatively high rates of
up to l00 Mbit/s.
The
maximum-likelihood receiver implies selecting a code word closest to the
received word. Because there are 2k code words, the
maximum-likelihood decision involves storage of 2k words and
their comparison with the received word. This calculation is extremely
difficult for large k and would result in an overly complex decoder.
A
major simplification was made by Viterbi in the maximum-likelihood calculation
by noting that each of the four nodes (a, b, c, and d) has only
two predecessors; that is, each node can
be reached through two nodes only (see Fig. 4.3 or 4.4), and only the path that
agrees most with the received sequence (the minimum-distance path) need be
retained for each node. To understand this, consider the trellis diagram in
Fig. 4.4. Our problem is as follows: Given a received sequence of bits, we need
to find a path in the trellis diagram with the output digit sequence that
agrees most with the received sequence.
Suppose the
first six received digits are 01 00 01. We shall consider two paths of
three branches (for six digits) leading to each of the nodes a,b,c, and d.
Out of the two paths reaching into each node, we shall retain only the one
that agrees most with the received sequence 01 00 01 (the
minimum-distance path). The retained path is called the survivor at that node.
There are two paths (00 00 00 and 11 10 11) that arrive at the
third-level node a. These paths are at distances of 2 and 3,
respectively, from the received sequence 01 00 01 Hence, the survivor at
the third-level node a is 00 00 00. We repeat the procedure for
nodes b, c, and d. For example, the two paths reaching the
third-level node c (the node after three branches) are 00 11 10
and 11 01 01, at distances of 5 and 2, respectively, from the received
sequence 01 00 01. Hence, the survivor at the third-level node c is
11 01 01. Similarly we find
survivors at
the third-level nodes b and d. With four paths eliminated, the four
survivor paths are the only contenders. The reason behind eliminating the other
four paths is as follows. The two paths merging at the third-level node a, for
example, imply that the previous two data digits are identical. Hence,
regardless of what the future data digits are, both paths must merge at this
node a and follow a common path in the future. Clearly, the sunivor path
is the minimum-distance path between the two, regardless of future data digits.
What we need to remember is the four survivor paths and their distances from
the received sequence. In general, the number of survivor paths is equal to the
number of slates, that is. 2N-1.
Once
we have survivors at all the third-level nodes, we look at the next two
received digits. Suppose these are 00 (i.e., the received sequence is 01
00 01 00). We now compare the two survivors that merge into the
fourth-level node a. These are the survivors at nodes a and c
of the third level, with paths 00 00 00 and 11 01 01 11,
respvetively, and distances of 2 and 4 from the
received sequence 01 00 01 00. Hence, the path 00 00 00 00 is the
survivor at the fourth-level node a. We repeat this procedure for nodes b,
c, and d and continue in this manner until the end. Note that only
two paths merge in a node and there are only four contending paths (the four
survivors at nodes a, b, c, and d) until the end. The only
remaining problem is how to truncate the algorithm and ultimately decide on one
path rather than four. This is done by forcing the last two data digits to be 00
(dummy or augmented data). When the first dummy 0 enters the registers,
we consider the survivors only at nodes a and c.The survivors at
nodes b and d are discarded because these nodes can be reached
only when the input bit is 1, as seen from the state or trellis diagram.
When the second dummy 0 enters the register, we consider only the
survivor at node a . We discard the survivor at node c because the last
two dummy data bits 00 lead the encoder to state a. In terms of
the trellis diagram, this means that the number of states is reduced from four
to two (a and c) by insertion of the first zero and to a single
state (a) by insertion of the second zero.
With the
Viterbi algorithm, storage and computational complexity are proportional to 2N
and are very attractive for constraint length N < 10. To achieve
very low error probabilities, longer constraint lengths are required and
sequential decoding becomes attractive.
ليست هناك تعليقات:
إرسال تعليق