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

Trellis decoding complexity of linear block codes

Abstract

In this partially tutorial paper, we examine minimal trellis representations of linear block codes and analyze several measures of trellis complexity: maximum state and edge dimensions, total span length, and total vertices, edges and mergers. We obtain bounds on these complexities as extensions of well-known dimension/length profile (DLP) bounds. Codes meeting these bounds minimize all the complexity measures simultaneously; conversely, a code attaining the bound for total span length, vertices, or edges, must likewise attain it for all the others. We define a notion of "uniform" optimality that embraces different domains of optimization, such as different permutations of a code or different codes with the same parameters, and we give examples of uniformly optimal codes and permutations. We also give some conditions that identify certain cases when no code or permutation can meet the bounds. In addition to DLP-based bounds, we derive new inequalities relating one complexity measure to another, which can be used in conjunction with known bounds on one measure to imply bounds on the others. As an application, we infer new bounds on maximum state and edge complexity and on total vertices and edges from bounds on span lengths.

Additional Information

© Copyright 1996 IEEE. Reprinted with permission. Manuscript received April 5, 1995; revised May 22, 1996. This research was carried out in the Communications Systems and Research Section of the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. A portion of W. Lin's contribution was sponsored by AFOSR under Grant F4960-94-1-005. The material in this paper was presented in part at the 32nd Annual Allerton Conference on Communication, Control, and Computing, Allerton, IL, October 1994. The authors wish to thank the reviewers for their helpful comments and the authors of [7], [15], [18] for preprints of their papers.

Files

KIEieeetit96.pdf
Files (1.3 MB)
Name Size Download all
md5:9c385211c35421db377caf63da9140a7
1.3 MB Preview Download

Additional details

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