The Viterbi algorithm

Rgure 15.6 Calculation of probabihties for movement between time slot t and time slot t +. The transition probabilities ai2 etc. connect the nodes and show the probability of moving from one node to another. The observation probabilities bi etc. give the probability of that state generating the observation. 

The complete search is performed as follows. Starting at time slot 1, we initiaUse a set of 5 functions for every node to be 0  

We then move to time slot 2 and iterate through each node in tmn. For one of these nodes, Uk, we iterate through all the nodes in time slot 1, and for each node calculate the total probabiUty using Equation (15.13). We tUen find the node in time slot 1 which gives the highest total probabiUty, and record its identity in . We also store the total probabiUty associated with that node  

This is repeated this for all nodes in time slot 2. So now every node in time slot 2 has two search values associated with it the identity of die node in the previous time slot which has the highest total probability, and the value 5 of this total probabiUty. We then move forwards through the trellis and repeat the calculation  

For a single node Xk at any time slot, we need record only the best path leading to this node. If it turns out that this particular node Xk is in fact on the global best path, then the node in the preceding time slot that it has recorded is also on the best path. 

---

All we require for actual synthesis are the coefficients C =< ci,C2,---Ct >, so the problem is to generate the highest probability sequence of these that also obeys the constraints of the delta coefficients AC =< Aci,Ac2,. .Acf >. As we have to find both the observations and the state sequence, we can t use the Viterbi algorithm as above but rather use an algorithm specific to this... 

See Jurafsky and Matrin [243] for an explanation of the DTW algorithm, its history and its relation to the Viterbi algorithm. 

As described in Section 15.1.5 the Viterbi algorithm seeks the highest probability path through an HMM network. The only real difference between that and unit selection search is that here we are trying to find the lowest cost path. This is in fact a trivial difference, and so the Viterbi algorithm as previously described can be used directly to find the lowest cost sequence of units in unit selection. 

As described in Section 15.1.5 the Viterbi algorithm seeks the highest-probabUity path through an HMM network. The only real difference between that and a unit-selection... 

The Viterbi algorithm is based on trellis expansion operation. During the execution of Viterbi algorithm implemented in assembly language programming, code for trellis expansion function is executed multiple times. For example, if there are 12 bits in a received codeword then this trellis function is called approximately nineteen times, as shown in Fig. 4.2. 

Table 4.8 shows the comparison of the performance of Viterbi algorithm, in particular, trellis expansion function, when implemented in DUX assembly language and with custom Texpand instruction. This instruction is called nineteen times in the Viterbi algorithm for 6-bit decoding. The results show substantial improvement of three times when trellis expands function is implemented as a custom instruction. 

---