Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 1, 1996 | public
Journal Article Open

The trellis complexity of convolutional codes

Abstract

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.

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.

Files

MCEieeetit96b.pdf
Files (957.5 kB)
Name Size Download all
md5:6a81514800023053f06b80c9871964ed
957.5 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023