NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Due to the lapse in federal government funding, NASA is not updating this website. We sincerely regret this inconvenience.

Back to Results
The trellis complexity of convolutional codesIt has long been known that convolutional codes have a natural, regular trellis structure that facilitates the implementation of Viterbi's algorithm. 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. In both cases, the complexity of the Viterbi decoding algorithm can be accurately estimated by the number of trellis edges 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 that 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, at present we seem to know more about the minimal trellis representation for block than for convolutional codes. In this article, 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). 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-minimal 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.
Document ID
19960009525
Acquisition Source
Legacy CDMS
Document Type
Other
Authors
Mceliece, R. J.
(Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)
Lin, W.
(Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)
Date Acquired
September 6, 2013
Publication Date
November 15, 1995
Publication Information
Publication: The Telecommunications and Data Acquisition Progress Report 42-123
Subject Category
Communications And Radar
Accession Number
96N16691
Funding Number(s)
PROJECT: RTOP 315-91-20-20-53
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available