A computational complexity measure for trellis modules of convolutional codes

This paper presents a computational complexity measure of convolutional codes well suitable for software implementations of the Viterbi algorithm (VA) operating with hard decision. We investigate the number of arithmetic operations performed by the decoding process over the conventional and minimal trellis modules. The computational cost of implementation of each operation is determined in terms of machine cycles taken by its execution. A relation between the complexity measure defined in this work and the one defined by McEliece and Lin is investigated. The system architecture adopted is the TMS320C55xx fixed-point digital signal processor family from Texas Instruments.