In general, the decoding problem is as follows: Given a model and a sequence of observations, what is the most likely state sequence in the model that produces the observations? Suppose we have an observation sequence Z=(z0,z1,...,zn) and we want to check if that sequence is a correct one. The idea is to find the sequence C=(c0,c1,...,cn) which is the closest to sequence Z. Each ci in C, fori=0,1,...,n, can take any value of the states given in the model. Let M be the number of states in the model. Fig. 1 summarizes the decoding problem. 

Fig. 1 The decoding problem

   Now, the question is, how can we know which sequence C is the closest to sequence Z? Different types of techniques have been developed, the most attractives ones are based on compound decision theory, where probability plays an important role. One of those techniques is the Viterbi algorithm, which gives an optimal solution to the decoding problem if the underlying process is assumed to be a Markov process.

2. Decoding problem:

• Decoding problem: Given the HMM  M=(A, B, p) and the observation sequence  O=o1 o2 ... oK , calculate the most likely sequence of hidden states si that produced this observation sequence. 
• We want to find the state sequence Q= q1…qK which maximizes  P(Q | o1 o2 ... oK ) , or equivalently P(Q , o1 o2 ... oK ) . 
• Brute force consideration of all paths takes exponential time. Use efficient Viterbi algorithm instead. 
• Define variable  dk(i)  as the maximum probability of producing observation sequence o1 o2 ... ok  when moving along any hidden state sequence q1… qk-1 and getting into qk= si  .