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

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].

http://people.bu.edu/trachten