The trellis complexity of convolutional codes
It has long been known that convolutional codes have a natural, regular, trellis structure that facilitates the implementation of Viterbi's algorithm [35], [11]. It has gradually become apparent that linear block codes also have a natural, though not in general a regular, ''minimal'' trellis structure, which allows them to be decoded with a Viterbi-like algorithm [2], [36], [25], [12], [30], [16], [13], [18], [27], [28], [9], [17]. In both cases, the complexity of an unenhanced Viterbi decoding algorithm can be accurately estimated by the number of trellis edge symbols per encoded bit. It would therefore appear that we are in a good position to make a fair comparison of the Viterbi decoding complexity of block and convolutional codes. Unfortunately, however, this comparison is somewhat muddled by the fact that some convolutional codes, the punctured convolutional codes [5], are known to have trellis representations which are significantly less complex than the conventional trellis. In other words, the conventional trellis representation for a convolutional code may not be the ''minimal'' trellis representation. Thus ironically, we seem to know more about the minimal trellis representation for block than for convolutional codes. In this paper we provide a remedy, by developing a theory of minimal trellises for convolutional codes. (A similar theory has recently been given by Sidorenko and Zyablov [32].) This allows us to make a direct performance-complexity comparison for block and convolutional codes. A by-product of our work is an algorithm for choosing, from among all generator matrices for a given convolutional code, what we call a trellis-canonical generator matrix, from which the minimal trellis for the code can de directly constructed. Another by-product is that in the new theory, punctured convolutional codes no longer appear as a special class, but simply as high-rate convolutional codes whose trellis complexity is unexpectedly small.
convolutional code decoding complexity minimal trellis