Kiely, Aaron B. and Dolinar, Samuel J, Jr. and McEliece, Robert J. and Ekroot, Laura L. and Lin, Wei (1996) Trellis decoding complexity of linear block codes. IEEE Transactions on Information Theory, 42 (6, pt.). pp. 1687-1697. ISSN 0018-9448. doi:10.1109/18.556665. https://resolver.caltech.edu/CaltechAUTHORS:KIEieeetit96
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 1MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:KIEieeetit96
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.
| Item Type: | Article | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| 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. | ||||||
| Subject Keywords: | Trellis decoding, block codes, decoding complexity, minimal trellises, dimension/length profiles | ||||||
| Issue or Number: | 6, pt. | ||||||
| DOI: | 10.1109/18.556665 | ||||||
| Record Number: | CaltechAUTHORS:KIEieeetit96 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:KIEieeetit96 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 5566 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Archive Administrator | ||||||
| Deposited On: | 25 Oct 2006 | ||||||
| Last Modified: | 08 Nov 2021 20:27 |
Repository Staff Only: item control page
