Forums

Complexity of Viterbi decoding algorithm?

Started by PP June 8, 2005
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

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
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

Thanks a lot for the replies.

-Pratap