Author_Institution :
Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA, USA
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;