Forums

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

Started by johan_mozart 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 of already calculated costs. 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: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