McEliece, Robert J. (1996) On the BCJR trellis for linear block codes. IEEE Transactions on Information Theory, 42 (4). pp. 1072-1092. ISSN 0018-9448. doi:10.1109/18.508834. https://resolver.caltech.edu/CaltechAUTHORS:MCEieeetit96a
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 2MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:MCEieeetit96a
Abstract
In this semi-tutorial paper, we will investigate the computational complexity of an abstract version of the Viterbi algorithm on a trellis, and show that if the trellis has e edges, the complexity of the Viterbi algorithm is Θ(e). This result suggests that the “best” trellis representation for a given linear block code is the one with the fewest edges. We will then show that, among all trellises that represent a given code, the original trellis introduced by Bahl, Cocke, Jelinek, and Raviv in 1974, and later rediscovered by Wolf (1978), Massey (1978), and Forney (1988), uniquely minimizes the edge count, as well as several other figures of merit. Following Forney and Kschischang and Sorokine (1995), we will also discuss “trellis-oriented” or “minimal-span” generator matrices, which facilitate the calculation of the size of the BCJR trellis, as well as the actual construction of it.
| Item Type: | Article | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| Additional Information: | © Copyright 1996 IEEE. Reprinted with permission. Manuscript received October 28, 1994; revised December 11, 1995. This work was supported in part by AFOSR under Grant F4960-94-1-005, by a grant from Pacific Bell, and by NSF under Grant NCR-9505975. A portion of the work was also done 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 in part at the IEEE International Symposium on Information Theory, Trondheim, Norway, June 1994. | ||||||
| Subject Keywords: | Block code, trellis, Viterbi algorithm, decoding complexity | ||||||
| Issue or Number: | 4 | ||||||
| DOI: | 10.1109/18.508834 | ||||||
| Record Number: | CaltechAUTHORS:MCEieeetit96a | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:MCEieeetit96a | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 6919 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Archive Administrator | ||||||
| Deposited On: | 02 Jan 2007 | ||||||
| Last Modified: | 08 Nov 2021 20:38 |
Repository Staff Only: item control page
