This is a semi-tutorial paper on trellis-based algorithms.We argue that most decoding/detection algorithms describedon trellises can be formulated as path-partitioning algorithms,with proper definitions of mappings from subsets of pathsto metrics of subsets. Thereby, the only two operations neededare path-concatenation and path-collection, which play the roles ofmultiplication and addition, respectively. Furthermore, we showthat the trellis structure permits the path-partitioning algorithmsto be formulated as forward-only algorithms (with structures resemblingthe Viterbi algorithm), thus eliminating the need forbackward computations regardless of what task needs to be performedon the trellis. While all of the actual decoding/detectionalgorithms presented here are rederivations of variations of previouslyknown methods, we believe that the exposition of the algorithmsin a unified manner as forward-only path-partitioningalgorithms is the most intuitive manner in which to generalize theViterbi algorithm. We also believe that this approach may in factinfluence the practical implementation of the algorithms as well asinfluence the construction of other forward-only algorithms (e.g.,byte-wise forward-only detection algorithms).

Some properties of the minimal interpolation problemare investigated, from which a simple proof of the validity of theWelch-Berlekamp algorithm is presented. A new key equation is derived,which is closely related to the classical key equation of syndrome-decodingalgorithm and can be solved by the Welch–Berlekamp algorithm.