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!

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

Started by ●December 5, 2012

Reply by ●December 5, 20122012-12-05

"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

Reply by ●December 5, 20122012-12-05

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

Reply by ●December 5, 20122012-12-05

"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