The Viterbi algorithm first sets up a probability matrix, with one column for each observation $o_t$ and one row for each state in the state graph. Each column thus has a cell for each state $q_i$ in the single combined automaton. Each cell of the matrix is given by:

v_t(j) = max_{q_1, ..., q_{t-1}} P(q_1...q_{t-1}, o_1, ..., o_t, q_t = j|lambda)

For a given state $q_j$ at time $t$, we compute the value $v_t(j)$ as:

$v_t(j) = \max_{i=1}^N v_{t-1}(i)a_{ij}b_j(o_t)$

where:

• $v_{t-1}(i)$ is the previous Viterbi path probability from the previous time step
• $a_{ij}$ is the transition probability from previous state $q_i$ to current state $q_j$
• $b_j(o_t)$ is the state observation likelihood of the observation symbol $o_t$ given the current state $j$