DocumentCode :
1087504
Title :
On the BCJR trellis for linear block codes
Author :
Mceliece, Robert J.
Author_Institution :
Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA, USA
Volume :
42
Issue :
4
fYear :
1996
fDate :
7/1/1996 12:00:00 AM
Firstpage :
1072
Lastpage :
1092
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
Keywords :
Viterbi decoding; block codes; computational complexity; linear codes; matrix algebra; trellis codes; BCJR trellis; Viterbi algorithm; computational complexity; edge count; linear block codes; minimal-span generator matrices; trellis-oriented generator matrices; tutorial; Block codes; Computational complexity; Convolutional codes; Decoding; Error probability; Explosions; Information theory; Propulsion; Space technology; Viterbi algorithm;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/18.508834
Filename :
508834
Link To Document :
بازگشت