Round-to-even-on-tie

This article is about numerical rounding, more specific, about implementing the tie-breaking technique called “round-to-even” using MyHDL. There is a good article about Numerical Rounding on Wikipedia for reference.

The idea about the tie-breaking technique round-to-even is, to round a fractional number to the nearest even, in case the tie 0.500 appears. So the value 3.5 will be rounded to the integer number 4 and 2.5 will be rounded to the integer 2. A tie is considered the fractional part 0.5, as it is equal distances from the next bigger integer value as from its next lower integer value. To explain that with an example, 3.5 is equal distant to 4.0 as it is to 3.0. All other fractions are rounded as before, so 3.51 will be rounded to 4 as 3.49 will be rounded to 3.

Now let's consider the binary implementation of the round-to-even. For that we consider an unsigned fixed-point number representation with 3 integer bits and 3 fractional bits and the number should be rounded to an unsigned integer of 3 bits. First we introduce some naming convention. Based on the value 3.5, as fixed-point number in binary form it is represented by 011.100.

  011.100
    ^ ^--
    | | |
    | | + lsbs_frac
    | +-- msb_frac
    +---- lsb_int

• lsbs_frac are the least-significant-bits of the fractional part
• msb_frac is the most-significant-bit of the fractional part
• lsb_int is the least-significant-bit of the integer part

Note that it is necessary to consider all fractional bits, except for the msb and therefore it is called lsbs. But only the least-significant-bit of the integer part.

Now there are two distinctions necessary:

• No tie –> just round as known
• Tie –> round-to-nearest-even

A tie is considered 0.5, which in binary form means, the lsbs_frac are all zero and the msb_frac is one.

Let's say there is a tie, now the integer part needs to be increased if it is an odd value and stay if it is an even value. Odd and even numbers are identified by the lsb_int. Consider the bit values of an integer number. The first bit is 2^0 = 1, the second bit 2^1 = 2, the third bit 2^2 = 4, etc. Only bit zero has an odd bit value, all following bit values are even. To test an integer number whether it is odd or even, it is sufficient to test whether lsb is set.

In our case, when lsb_int is set, it is an odd number and it needs to be increased by one. If lsb_int is not set it is an even number and the integer value remains.

The simplest way to implement this functionality is just to add the lsb_int to the integer value in case of a tie.

No tie is considered if any of the least-significant-bits of the fractional part (lsbs_frac) is set. How does that come? Let's consider the values to understand that. The msb_frac has the value 2^-1 or 1/2. The first lsb_frac has the value 2^-2 or 1/4, etc. That means that the sum of all lsbs_frac is < 0.5. So we said that msb_frac has the value of 0.5 and adding all lsbs_frac to it will add a value < 0.5. That means that if msb_frac is set, the overall fractional value is > 0.5 and for rounding the integer value needs to be rounded up – increased by one. In case msb_frac is not set, the overall fractional value is < 0.5 and the integer value will remain – rounded down.

As the msb_frac is the bit that considers the rounding up or remaining, the simplest way to implement it, is to add the msb_frac to the integer value, in case no tie occurred.