ng Fig. 4.4 Two commonly used representations for convolutional coders, for the example of a binary rate 1/2 constraint. X = input and = outputs Sn = stores input digits are loaded sequentially into this register. Sometimes Lk is called the constraint length (a conflicting definition with the previous one). The digits in the shift register(s) (S1 to S3 in Figure 4.4) define the state of the coder at each timestep; there are therefore M(L-1)k possible coder states. The possible transitions from a given coder state at one timestep to another state at the next timestep are determined by the shift register arrangement. The actual output code digit stream is determined by both the shift register arrangement and the particular summations chosen to form the output digits. There are M patterns of k input digits, SO from each state there are M possible next states. The behavior of the coder can therefore be described using a trellis diagram, as shown in Figure 4.5. In this, the possible states of the coder are represented as M (L-1)k nodes in a vertical column, and the state-to-state transitions at each timestep are represented by a rightward step of one column. From each node at timestep i there are Mk branches to suc- cessor states at timestep i + 1. In a worthwhile code no two different patterns of input digits give the same transitions. Viterbi Decoding The error-correcting power of a convolutional code arises from the fact that only some of the possible sequences of digits are valid outputs from the coder; these sequences corre- spond to possible paths through the trellis. The job of the decoder is to find which valid digit sequence is closest to the received digit sequence. This is analogous to the job of a block decoder, but because the input digit sequence is continuous the coder must operate continuously and must have an acceptably small delay between the arrival of particular input digits and the output of the corresponding decoded digits. The optimum (in the sense of maximum-likelihood) decoding of convolutiona