Viterbi Algorithm Concept

According to the state diagram shown in this link finite state machine, a trellis diagram looks like in the following figure can be built. Each node corresponds to a district state at a given time, and each branch represents a transition to some new states at the next instant of time. The trellis begins and ends at the known state x₀ and x_k. Its most important property is that to every possible state sequence x there corresponds to a unique path through the trellis, and vice versa.

Given a sequence of observations z, every path may be assigned a length proportional to | -ln P(x, z)|, where x is the state sequence associated with that path. This is used to solve the problem of finding the state sequence for which P(x | z) is maximum, or equivalently for which P(x, z) = P(x | z) P(z) is maximum, by finding the path whose length |-ln P(x, z)| is minimum, since ln P(x, z) is a monotonic function of P(x, z) and there is a one-to-one correspondence between paths and sequences (Forney 1973). P(x, z) factor is given as:

Hence, assume if each branch (transition) the length:

Then the total length of the path corresponding to some x is as claimed.

is a segment consists of the states to time k of the state sequence x ≈ (x_0, x_{1, ...,} x_k) and corresponds to a path segment in the trellis starting at the node x₀ and terminating at x_k.
For any particular time-k at node x_k, there will in general be several such path segments, each with some lengths. 

The shortest such path segment is called the survivor corresponding to the node x_k, and denoted

For any time k > 0, there are M survivors in all, one for each x_k. 

The observation is: the shortest completes path must begin with one of the survivors 

Thus at any time-k, we need to remember only M survivor and their lengths 

To get to time k+1, we need only to extend all time-k survivors by one time unit, compute the lengths of the extended path segments, and for each node x_k+1 select the shortest extended path segment terminating in x_k+1 as the corresponding time-(x_k+1) survivor. Recursion proceeds indefinitely without the number of survivors ever exceeding M. 

References:

• Forney, G. D. 1973. The Viterbi algorithm. Proceeding of the IEEE 61: 268-278.