Hi, I once simulated Viterbi decoder (I programmed the code, not Matlab function or block) with Matlab without any problem. Now I implement Viterbi decoder in TI DSP with fixed point short date type. I have puzzled with the integer wrapped problem. I think I have some incorrect understanding on the implementation. TI has a DSP pdf application note talking about Viterbi decoder (There are some other open sources with similar ideas). The initial path metrics are 0 for state 0 and 8000h (-32768) for all other states. I use (133,171) convolutional code. The first butterfly is: old states 00 new states state 0 -------------- state 0 (0) \ / 11\ 11/ \ / \/ / \ / \ / \ state 1 ----------------state 32 (-32768) 00 The above is described in TI application note: spra776a.pdf. I assume 4 bits soft decision with range -8......7. For simplicity, I assume antipodal code: 0=====>7, 1=====>-7 In this case, SUM=14 for 00, then -SUM=-14 for 11. old states 00 new states state 0 -------------- state 0 (0) / 11/ / / / / / state 1 (-32768) If I discard the '-' sign in the original metric calculation, then it looks for the maximum metric. This seems that for the above butterfly works. That is, metric 14 is selected for 00. The problem is for other metrics which have default metrics to '8000h'. If one of the metric (for add) is '800Eh', the other metric will be wrapped to '7FF2H' which is a very large positive number. This is a disaster to the implementation. In matlab, there is a similar default for the metrics. I.e. state 0 is '0' while other metrics are the lowest negative numbers. But there is no such overflow problem as in the fixed point case (16 bit integer in above). I do think that '0' and '8000H' are correct, but I do not know what else I am wrong with it. Could you explain it to me? Thanks

# Overflow problem in Viterbi algorithm implementation in DSP

Started by ●November 8, 2013

Posted by ●November 9, 2013

Just use the mod 2^N arithmetic. The difference between the paths is always less than the modulus, as well as in the CIC filters. _____________________________ Posted through www.DSPRelated.com

Posted by ●November 10, 2013

On Saturday, November 9, 2013 4:23:51 PM UTC-5, Alexander Petrov wrote:> Just use the mod 2^N arithmetic. The difference between the paths is always > > less than the modulus, as well as in the CIC filters. > > > > _____________________________ > > Posted through www.DSPRelated.comAnother solution is to subtract the smallest metric from all metrics.

Posted by ●November 10, 2013

On Sun, 10 Nov 2013 13:53:15 -0800 (PST), John <sampson164@gmail.com> wrote:>On Saturday, November 9, 2013 4:23:51 PM UTC-5, Alexander Petrov wrote: >> Just use the mod 2^N arithmetic. The difference between the paths is always >> >> less than the modulus, as well as in the CIC filters. >> >> >> >> _____________________________ >> >> Posted through www.DSPRelated.com > >Another solution is to subtract the smallest metric from all metrics.A long time ago when Qualcomm made a single-chip Viterbi decoder, they kept track of overflow events and when an overflow occurred they'd right shift ALL of the metric registers by one bit. They also had a configurable register set that allowed you to keep track of how many of these "renormalizations" occured over a configurable period. A very reliable code-lock detector was just setting a threshold on the renormalizations. Too many and it was declared unlocked, less than some threshold and it was locked. I always thought it was a nice way to manage the metric arithmetic and it also provided a very reliable lock detector. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com

Posted by ●November 10, 2013

Do you have any reference for your assertion? I have considerable doubt that mod 2^N arithmetic will give the right answers. --Dilip Sarwate On Saturday, November 9, 2013 3:23:51 PM UTC-6, Alexander Petrov wrote:> Just use the mod 2^N arithmetic. The difference between the paths is always > > less than the modulus, as well as in the CIC filters. > > > > _____________________________ > > Posted through www.DSPRelated.com

Posted by ●November 11, 2013

An Alternative to Metric Rescaling in Viterbi Decoders by Andries P. Hekstra IEEE Trans. Comm., vol. 37, no. 11, Nov. 1989. _____________________________ Posted through www.DSPRelated.com

Posted by ●November 11, 2013