Overflow problem in Viterbi algorithm implementation in DSP

Started by fl November 8, 2013
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 
 
 
 
 
 
 
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
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.
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
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
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
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-973-communication-system-design-spring-2006/lecture-notes/lecture_15.pdf	


_____________________________		
Posted through www.DSPRelated.com