"johan_mozart" <57605@dsprelated> wrote in message 
news:IJCdnRc7dNvjByLNnZ2dnUVZ_rednZ2d@giganews.com...
> >The first step of the processing is calculating the price of the current
>>N-bit symbol from the channel. Depending on what and how, that could be
> one
>>operation, 2^N operations or anything in between. Usually, this processing
>
>>is not counted as part of Viterbi decoder.
>>Viterbi decoder is considered to be a pure search algorithm on the trellis
>
>>of already calculated costs.
>
> If I understood you correctly, you say, that the additional complexity
> comes from calculating the costs? A simple receiver would for example
> precalculate the costs on some assumptions, and a more sophisticated
> receiver, will calculate them on the fly. Correct me if I am  wrong.
>
> Does that mean, that the complexity of a search algorithm (Viterbi) for a
> given constraint length does not change with the code rate? Actually, this
> is the result I found in literature, and I wondered why the number of
> channel bits doesn't enter into the decoding complexity...

Algorithm Viterbi is just an algorithm for searching best path in a graph. 
What is represented by the graph and how this graph was obtained is 
irrelevant to Viterbi.
The entire decoder is a different story. Of course, the complexity of the 
entire decoder includes calculation of the cost of the incoming nodes 
altogether with Viterbi search.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

>The first step of the processing is calculating the price of the current 
>N-bit symbol from the channel. Depending on what and how, that could be
one 
>operation, 2^N operations or anything in between. Usually, this processing

>is not counted as part of Viterbi decoder.
>Viterbi decoder is considered to be a pure search algorithm on the trellis

>of already calculated costs.

If I understood you correctly, you say, that the additional complexity
comes from calculating the costs? A simple receiver would for example
precalculate the costs on some assumptions, and a more sophisticated
receiver, will calculate them on the fly. Correct me if I am  wrong.

Does that mean, that the complexity of a search algorithm (Viterbi) for a
given constraint length does not change with the code rate? Actually, this
is the result I found in literature, and I wondered why the number of
channel bits doesn't enter into the decoding complexity...

"johan_mozart" <57605@dsprelated> wrote in message 
news:Fd6dnbiQAqh3xyLNnZ2dnUVZ_jGdnZ2d@giganews.com...

> Does the complexity of the viterbi decoder of a 1/N-rate convolutional 
> code
> increase with N?

It depends.

> My point of view: to decode 1 information bit, one has to process N 
> channel
> bits. Hence, when N increases, the number of necessary operations 
> increases
> too. Is that true?

The first step of the processing is calculating the price of the current 
N-bit symbol from the channel. Depending on what and how, that could be one 
operation, 2^N operations or anything in between. Usually, this processing 
is not counted as part of Viterbi decoder.
Viterbi decoder is considered to be a pure search algorithm on the trellis 
of already calculated costs.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

Hi,

Does the complexity of the viterbi decoder of a 1/N-rate convolutional code
increase with N? The constraint length L is kept constant?

My point of view: to decode 1 information bit, one has to process N channel
bits. Hence, when N increases, the number of necessary operations increases
too. Is that true?

Thanks!