Hi I was wondering how to express the complexity of the Viterbi algorithm... Is it O(N2) or O(Nlog N) or is it exponential ? Thanks. Pratap
Complexity of Viterbi decoding algorithm?
Started by ●June 8, 2005
Reply by ●June 16, 20052005-06-16
I guess the complexity is linear with respect to the depth of the trellis. A good description is given in "Digital Communications" by Proakis. -Philonoist PP wrote:> Hi > > I was wondering how to express the complexity of the Viterbi > algorithm... > Is it O(N2) or O(Nlog N) or is it exponential ? > > Thanks. > Pratap
Reply by ●June 16, 20052005-06-16
It is exponential with the constraint length of the encoder. it is function of 2^K where K is constraint length. Refer some digi comm book for more detailed expression. Hope this helps. Tarang
Reply by ●June 22, 20052005-06-22