A Caltech Library Service

On the BCJR trellis for linear block codes

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.

See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
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
Record Number:CaltechAUTHORS:MCEieeetit96a
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6919
Deposited By: Archive Administrator
Deposited On:02 Jan 2007
Last Modified:08 Nov 2021 20:38

Repository Staff Only: item control page