Viterbi algorithm

The Viterbi algorithm is an optimized searching algorithm for finding the shortest path. It has been used to decode the convolutional codes for telecommunication. The key principle of this algorithm arises from the observation that if the shortest path between point A and point C passes a intermediate point B, then the segment of this path between point A and point B is the shortest path between these two points. The algorithm consists of two steps: forward shortest-path accumulation and backward descending tracking. One can find the details of the algorithm in an excellent reference (McEliece, 1977). I include a subroutine of the Viterbi algorithm in Appendix A.

If the coherence measure in equations (5) or (6) is chosen as the objective function, then the algorithm should search for the longest-path, instead of shortest path. This can be easily done by reversing the operations in the Viterbi algorithm.

At this point, I have not mentioned anything about the constraints imposed by a model. In fact, simple models can be easily incorporated in the Viterbi algorithm. For example, to obtain a smooth solution p(t), one can eliminate all the transition branches that would cause abrupt changes of the path. This procedure provides two benefits; not only does it constrain the smoothness of the solution, but it also reduces the computation time because the solution space to be searched is reduced. Field data examples show that this procedure works well for many applications.