nce, From (3.4.13), we see that all paths that merge at will have the same possible distances 6 arg min d (c,y). added to the existing distance of the path and therefore a path with a larger distance at In the equation just given, C represents the set of state Si cannot achieve a smaller overall distance than valid codewords, C = (1) Cum,sm->sm+1} (m) a path with a smaller distance at state Si. As a result, we represents a valid sequence of output blocks, and y = can prune the total number of paths to be no larger than {y(0 (2) y(m) represents a sequence of received the total number of states. In other words, at each time blocks. Furthermore, d(c, y) is the distance metric instant, at most Zuk paths are kept (one path for each between the output sequence and the received sequence state). At time instant m, the minimum-distance path and can be written as a summation of distances between can be determined and traced back to state 0 at time the received blocks and the output blocks at the various instant 0. The output sequence associated with the time instants, minimum distance path is the decoded codeword. Because the time complexity of the Viterbi algorithm (3.4.12) is exponential in the memory order, faster but suboptimal sequential decoding algorithms (e.g., the Fano and Stack algorithms [50]) are used in many time- Assuming that the trellis starts in state zero (i.e., all of critical applications. A generalization of the standard the registers of the convolutional code are cleared to Viterbi algorithm is the list Viterbi algorithm (LVA) Channel protection fundamentals CHAPTER 3.4 [44,41], which finds the L most likely paths instead of of four possible two-bit combinations, SO we can define only the most likely one. a mapping between the four possible two-bit combina- Symbol MAP decoding (see Section 3.4.2.2) of tions and the four lattice points shown in Figure 3.4-4. convolutional codes can be done with soft-input Recall, however, that the goal of code design is to soft-output algorithms. Two of the most promin