Overflow problem in Viterbi algorithm implementation in DSP

Started by 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

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