On the Trellis Complexity of Block and Convolutional Codes

We study maximum likelihood decoding of convolutional codes. We show how to calculate the complexity of the syndrome trellis using the parity-check matrix and prove that this trellis contains the minimum possible number of states. We compute the decoding complexity of PUM codes and apply these results to convolutional codes. An upper bound on the minimal trellis complexity of convolutional codes is given. Finally, we compare ordinary and punctured convolutional codes.