lly coded sequences can be carried out using the Viterbi algorithm, which can be applied to both hard-decision and soft-decision decoding. Calculating the most likely digit sequence output by the coder is equivalent to calculating the most likely path followed by the coder through Convolutional Codes State Timestep S1 S2 S3 1 0 1 Fig. 4.5 Trellis diagram for the - x,=0 1), etc. coder in Figure 4.4. Xi= 1 the trellis. In a hard-decision decoder (and assuming a binary symmetric channel for sim- plicity) the most likely coder path is the one that has the smallest number of disagreements with the received bitstream. In a soft-decision decoder the most likely path is the one with the smallest squared difference from the received signal. These measures of discrepancy between the received signal and possible transmitted signals are referred to as path metrics. It appears at first sight that the number of candidate paths grows exponentially with each timestep. However, at timestep i the decoder only needs to keep track of the single best path SO far to each node; any worse path to that node cannot be part of the overall best path through the node. The number of paths to be remembered therefore remains constant and equal to the number of nodes. For each node the decoder must store the best path to that node and the total metric corresponding to that path. By comparing the actual n received digits at timestep i+ 1 with those corresponding to each possible path on the trellis from step i to step i + 1, the decoder calculates the additional metric for each path. From these, it selects the best path to each node at timestep i + 1 and updates the stored records of the paths and metrics. In theory the decoder has to wait until the hypothetical end of transmission before it can decide the overall maximum-likelihood path from start to finish. Fortunately it can be shown that a fixed finite delay between input and output is all that is necessary to give nearly optimum performance. In particular, it can be shown that if all the rea