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 July 1, 1996 | public
Journal Article Open

On the BCJR trellis for linear block codes

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.

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.

Files

MCEieeetit96a.pdf
Files (2.1 MB)
Name Size Download all
md5:6cbee31635a029659c854f79d4f1199b
2.1 MB Preview Download

Additional details

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