# Viterbi.c, integer overflow at cumulative metric

**URL:** <https://www.ruby-forum.com/t/viterbi-c-integer-overflow-at-cumulative-metric/230946>\
**Category:** GNU Radio\
**Created:** [July 14, 2014, 8:56am UTC](https://www.ruby-forum.com/t/viterbi-c-integer-overflow-at-cumulative-metric/230946 "2014-07-14T08:56:39Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![addis\_a](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/c4cdca/32.png) [@addis\_a](https://www.ruby-forum.com/u/addis_a)\
**Post date:** [July 14, 2014, 8:56am UTC](https://www.ruby-forum.com/t/viterbi-c-integer-overflow-at-cumulative-metric/230946/1 "2014-07-14T08:56:39Z")

</div>

Hi all,

I noticed that in viterbi.c when input symbol pair quality is  
good, branch metrics ‘mets[]’ maximum value is 512. In case of  
errorless input symbols, this causes cumulative metric increase  
by 512 for the best path for each decoded bit. In BUTTERFLY  
macro, m0 and m1 are type of int, i.e. they can hold integers  
less than 2^31, but since metric increases by 8x2^9=2^12 for  
each output byte, this implies that after 2^31 / 2^12 = 2^19:th  
byte occurs an integer overflow and decoder output gets messy.

This is simple to check, if you connect constant source of -1’s  
to ccsds27decoder and write output to a file and then run  
hexdump of the file.

I corrected this by changing the type of m0, m1 and metric to  
long long, when the integer overflow should not exist before  
2^51:th byte. However, with periodic initialization of metric  
the integer overflow of cumulative metric would be fully avoided.

Best regards,  
Vesa Vaskelainen

---

<div class="post-metadata">

**Author:** ![Vaskelainen\_Vesa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/3ab097/32.png) [@Vaskelainen\_Vesa](https://www.ruby-forum.com/u/Vaskelainen_Vesa)\
**Post date:** [July 14, 2014, 9:21am UTC](https://www.ruby-forum.com/t/viterbi-c-integer-overflow-at-cumulative-metric/230946/2 "2014-07-14T09:21:05Z")

</div>

-----BEGIN PGP SIGNED MESSAGE-----  
Hash: SHA1

Hey Vesa,

the cc\_decoder\_impl.cc and it’s corresponding volk kernel  
“volk\_8u\_x4\_conv\_k7\_r2\_8u.h” in gr-fec avoid this problem already by  
normalizing the path metric after each step in the trellis. I’m not  
sure if they are on the master branch yet, but you can check out  
Tom R.'s gnuradio repo ([trondeau (Tom Rondeau) · GitHub](http://www.github.com/trondeau)).

- -Jan

On 14.07.2014 08:54, Vaskelainen Vesa wrote:

> \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ Discuss-gnuradio  
> mailing list [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> [Discuss-gnuradio Info Page](https://lists.gnu.org/mailman/listinfo/discuss-gnuradio)

-----BEGIN PGP SIGNATURE-----  
Version: GnuPG v1  
Comment: Using GnuPG with Thunderbird - [http://www.enigmail.net/](http://www.enigmail.net/)

iQEcBAEBAgAGBQJTw4SLAAoJEJmPbVa7qwgjz+MH/2qUOYHwxCpAqwUtpXe0eOEX  
+wf4FvJhFTMUdNf/WmlUMt28jtYc3a0xjkJVD+vQO1vNP2e4GlQsB2Rywe5ZUf71  
0fDghklVRjN+idwRZWV51FDxpvdU8Tk1kC4PYI/8s1FZ+M7uGc/bLB8LMO7MCNwG  
QgjPW7Hl+efUXoYtDshueWY8RbmccUg7EzWNqAgryumkKai3tsg3yODNNMtBrouE  
R9DPO4ZbUwcqogk5EpIQxoYusRT2OmLDxD0XE80IuJ/VHLd0j6qdbXULHrj33XGz  
o6XP2+nS1Yj1Mw8zcnxdBcG1M4V3B7r2q9UXtmVh6RU1qZDNoNQo69c+h1n2k8E=  
=+K4q  
-----END PGP SIGNATURE-----

---

<div class="post-metadata">

**Author:** ![Vaskelainen\_Vesa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/v/3ab097/32.png) [@Vaskelainen\_Vesa](https://www.ruby-forum.com/u/Vaskelainen_Vesa)\
**Post date:** [July 14, 2014, 3:03pm UTC](https://www.ruby-forum.com/t/viterbi-c-integer-overflow-at-cumulative-metric/230946/3 "2014-07-14T15:03:39Z")

</div>

On Mon, Jul 14, 2014 at 3:19 AM, Jan Krämer [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> - -Jan

Yes, this was merged into the master branch:

> **[GNU Radio Manual and C++ API Reference: Forward Error Correction](https://www.gnuradio.org/doc/doxygen/page_fec.html)**

Tom