# Viterbi Decoder (Does the complexity depend on the Code Rate)

Started by December 5, 2012
```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!

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

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

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