Saturday, February 28, 2009

Viterbi Algorithm in Boost and C++

The Viterbi algorithm was conceived by Andrew Viterbi in 1967 as an error-correction scheme for noisy digital communication links. The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events.

In 2008, Viterbi won the Millennium Technology Prize "for the invention of the Viterbi algorithm, the key building element in modern wireless and digital communications systems, touching the lives of people everywhere.". It's interesting to note that in 1960s nobody could imagine a general application for the algorithm, so Viterbi followed his lawyer's advice and did not patent it. More information about Viterbi are given by this nice article by DrDobbs.

Here you have the Viterbi code in C++ adapted by the one of Božský Filip for using boost and a bit cleaner interface.

5 comments:

  1. unable to open the zip file of source code

    ReplyDelete
  2. thanks you very muth i need viterbi algorithm

    ReplyDelete
  3. Hi!

    I have seen your code and I have a question: in the HMM::init function, is the observations vector the test observation sequence? or is it the possible observations of the HMM?

    Thank you very much!

    ReplyDelete