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
Name | Size | Download all |
---|---|---|
md5:9c385211c35421db377caf63da9140a7
|
1.3 MB | Preview Download |
Additional details
- Eprint ID
- 5566
- Resolver ID
- CaltechAUTHORS:KIEieeetit96
- Created
-
2006-10-25Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field