Trellis decoding

Maximum-likelihood decoding is an obvious computational bottleneck for error-correction. One manner of implementing this decoding involves the use of a trellis, which is a time-indexed graph that represents a given linear code. More formally, a trellis T = (V, E) of depth n is a finite, directed, edge-labeled graph with the following properties:

1. Each vertex v$\mbox{$\,\inn\,$}$V has an associated depth d_v$\mbox{$\,\inn\,$}${0, 1, 2, 3,...n}.
2. Each edge e$\mbox{$\,\inn\,$}$E connects a vertex at depth i to a vertex at depth i + 1, for some i.
3. There is one vertex, called the root, at depth 0 and one vertex, called the toor, at depth n.

A trellis for a code establishes a one-to-one correspondence between codewords and paths from the root to the toor. One may consider a trellis to be a definite finite automaton with one start state and one finish state and no loops, so that a code represented by the trellis is precisely the language of the trellis. Figure 1.4 gives an example of a trellis for the linear code in Figure 1.1.

Figure 1.4: A trellis for the linear code in Figure 1.1. Solid lines represent transition on 1 bits and dashed lines represent transitions on 0 bits. Any path from the root to the toor spells out a codeword.

Given a received, possibly error-corrupted word, we may associate bit-error probabilities with weights on each edge in the trellis so that the problem of maximum-likelihood decoding reduces to the problem of finding the minimum-weight path from the root to the toor in the trellis. This can be accomplished by a dynamic-programming algorithm known as the Viterbi algorithm [63] which iteratively finds the most likely prefixes up to depth i.

The Viterbi algorithm requires | E| multiplications and | E| - | V| + 1 additions for the maximum-likelihood decoding of a given vector. By making use of the depth-structure of the trellis, the Viterbi algorithm is able to easily beat even the O(| E| + | V| log| V|) Fibonacci-heap implementation of Dijkstra's algorithm and the DAG-Shortest-Path algorithm for the same task [15]. Moreover, like the Floyd-Warshall algorithm [15] but faster, the Viterbi algorithm is fairly general and can be applied to any label alphabet with a semiring structure [62].

Though trellises are found in many common decoding implementations, Lafourcade and Vardy [36] have shown that their decoding complexity grows exponentially in the length of the code for asymptotically good codes. For this reason, alternative graph structures have been proposed for decoding, such as Tanner graphs [55] and their generalization to factor graphs [24].