title: Speeding up Viterbi execution
body: <p>I have implemented a naive Viterbi algorithm for a HMM based signal that I observe. The execution time of the decoder seems to be too slow for my requirement. I'm now trying to understand how to speed up the execution. When I'm to determine the computational complexity of the algorithm, I see that it's mentioned as having complexity of <a href="http://en.wikipedia.org/wiki/Viterbi_algorithm" rel="nofollow">t * s^2</a>, where t is number of observations and s is the number of states. I have roughly, 3500 states, and 100 observations.  Each state has 729 emission probabilities. </p>
  
  <p>I also see that it's mentioned in this <a href="http://people.csail.mit.edu/jonfeld/pubs/lazyviterbi.pdf" rel="nofollow">paper</a>, that Viterbi decoding is exponential in this paper (2^k, where k is the constraint length). I'm not understanding this explanation that well. But, I believe if Viterbi is exponential with regarding to states, then surely the algorithm would be very slow, even though I parallelize it.</p>
  
  <p>My questions are:</p>
  
  <ol>
  <li>What is the complexity of the Viterbi algorithm/decoding? Are they the same in both instances?</li>
  <li>How do I make modifications to the Viterbi algorithm to speed it up?</li>
  </ol>
  
  <p>EDITS: I'm implementing it in C++, hoping to modify it and parallelize it in the future.</p>