hip), find the closest path to V in the trellis easily and effectively. Getting the Basic Idea The Viterbi Algorithm is based on a very simple idea: Start at the time 0 in the trellis, and move through the trellis from left to right. At each time, you can systematically eliminate some of the paths in the trellis as being closest to V. In fact, according to the Viterbi Algorithm, you can eliminate (at every time) all Channel Coding and Decoding: Part 2-Convolutional Coding and Decoding but four of the paths through the trellis as being closest to V, for the trellis of Figure 7.5. (In general, you can eliminate all but "s" paths through a trellis at any one time, where "s" is the number of states.) This path elimination is briefly explained with the help of Figure 7.8. At time L+1, look at the top node. There are two paths that head into this node, one originating from parent node A and the other originating from parent node B. At time L+1, you can make a decision as to who is the better parent and choose between A and B. You repeat this for every node at time L+1, thus leaving you with four paths through the trellis at every time. Understanding by Example Let's say we input to the channel coder of Figure 7.2 the bits m = (00), in which case it outputs the bits u = (00 00). Let's also say the channel decoder receives V = (00 00). Let's use the Viterbi Algorithm to search for u', the path through the trellis closest to V. Once we've found u', we can output m', our guess at the bits sent into the channel coder. First, we draw the trellis, and we associate with each start node the number 0. This means that we are not biased toward any one start node over any other. This is shown in Figure 7.9(a). Then, we start by examining the top node at time 1, which you can see in Figure 7.9(b). For this node, there are two possible parent nodes, node 0 at time 0 and node 1 at time 0. We are going to decide which is the best parent node, using this procedure: 1. If we started at node 0 (time 0) and moved to node 0 (time 1), the fi