A Caltech Library Service

The trellis complexity of convolutional codes

McEliece, Robert J. and Lin, Wei (1996) The trellis complexity of convolutional codes. IEEE Transactions on Information Theory, 42 (6, par). pp. 1855-1864. ISSN 0018-9448. doi:10.1109/18.556680.

See Usage Policy.


Use this Persistent URL to link to this item:


Convolutional codes have a natural, regular, trellis structure that facilitates the implementation of Viterbi's algorithm. 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. 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, 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. We provide a remedy, by developing a theory of minimal trellises for convolutional codes. 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 be 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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 1996 IEEE. Reprinted with permission. Manuscript received December 15, 1995; revised May 12, 1996. This work was supported in part by NSF under Grant NCR-9505975 and under a Grant from Pacific Bell. A portion of the work was also performed at the Jet Propulsion Laboratory, California Institute of Technology, under Contract to the National Aeronautics and Space Administration. The material in this paper was presented at the 3rd International Symposium on Communication Theory and Exposition, Ambleside, UK, July 1995.
Subject Keywords:Convolutional code, minimal trellis, decoding complexity
Issue or Number:6, par
Record Number:CaltechAUTHORS:MCEieeetit96b
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6920
Deposited By: Archive Administrator
Deposited On:02 Jan 2007
Last Modified:08 Nov 2021 20:38

Repository Staff Only: item control page