ach time instant and then connecting the state, SO the Viterbi algorithm starts by calculating Zk states in accordance with the state transition diagram. distance metrics. For the next stage in the trellis, we can The trellis representation of a convolutional code is prune paths that end in the same state S1. More specifi- particularly useful for decoding, as quick decoding algo- cally, for all paths that converge to the same state, we can rithms such as the Viterbi decoding algorithm can be keep the path that has the minimum distance up to that derived from the trellis representation. An example of state and prune all other paths. This works because if a trellis representation of the convolutional code in multiple paths converge to the same state, then any path Figure 3.4-6a is given in Figure 3.4-7 where the states are that may emerge from this state will have an associated represented as dots and the transitions are labeled by the distance that will be added to the distance associated input bit that causes the transition and the resulting with the path that ends in that state. Mathematically, we output bits. can break up the total distance metric for any path that The goal of the decoder is to find the codeword from goes through a state at time i as the distance metric from the convolutional code closest to the received sequence state 0 at time 0 to state Si at time i and the distance in either Hamming distance or Euclidean distance (if the metric from state Si to state Sm+1 at the end of the trellis: output bits of the convolutional code are mapped to real values). This can be done efficiently by using the trellis diagram. If we let y(i) represent the received block (of d(c,y) = length n) at time instant i and let represent the output block (of length n) at time instant i corresponding to the transition between states Si and i+1 that results (3.4.13) from input block Ui (of length k), then mathematically the goal of the decoder is to find the output sequence c that is closest in distance to the received seque