Truncation: Also known as chopping, truncation simply means discarding any unwanted digits. Although this would appear--on the surface--to be relatively simple, things become a little more interesting when we realize that the actions resulting from truncation vary depending on whether we are working with sign-magnitude, unsigned or signed (complement) values. In the case of sign- magnitude values (like the standard decimal values we've been considering thus far), and also when working with unsigned binary values, the actions of truncation are identical to those of the round-toward-zero mode. In the case of signed binary values, however, truncation works somewhat differently for negative values, as we shall see.
But wait, there's more, because we also have round-alternate, round-random (also known as stochastic rounding), round-ceiling, round-floor, round-toward-zero, round-away-from-zero, round-up and round-down, to name but a few.
Hardware implementations
When it comes to hardware implementations of rounding algorithms, the most common techniques are truncation (which is commonly referred to as round-toward-zero, but this would be incorrect in the case of signed binary values as discussed below), round-half-up and round-floor.
In the case of unsigned binary representations, truncation, round-half-up, round-ceiling and round-floor work for the sign-magnitude decimal representations discussed above. However, there are some interesting nuances when it comes to signed binary representations. Purely for the sake of discussion, let's consider an 8-bit signed binary fixed-point representation comprising four integer bits and four fractional bits (see Fig. 2 on page 38).
For the purpose of this portion of our discussion (and for the sake of simplicity), let's assume that we wish to perform our various rounding algorithms so as to be left with only an integer value. Suppose that our 8-bit field contains a value of 0011.1000, which equates to +3.5. In the case of a truncation (or cropping) algorithm, we will simply discard the fractional bits, resulting in an integer value of 0011; this equates to 3 in decimal, which is what we would expect.
Now, assume a value of 1100.1000. The integer portion of this equates to –4 (that's –8 from the sign bit plus 4 = –4), while the fractional portion equates to +0.5, resulting in a total value of –3.5. The point is that, when we perform a truncation and discard our fractional bits, we end up with an integer value of 1100, which equates to –4 in decimal. Thus, in the case of a signed binary value, performing a truncation operation actually results in implementing a round-floor algorithm.
One reason the round-half-up algorithm is popular for hardware implementations is that it doesn't require "up" to perform a comparison operation. Instead, all we have to do is to add a value of 0.5 and truncate the result. (Note that when we say "add 0.5," this is based on our earlier assumption that we are rounding to the nearest integer. For example, suppose that our 8-bit field contains a value of 0011.0110, which equates to 3.375 in decimal. In this case, if we add a value of 0000.1000 (which equates to 0.5 in decimal), the result is 0011.1110; so when we now truncate this result, we end up with 0011, which equates to 3 in decimal. And this is, of course, what we would expect, because 3.375 should round to 3 in the case of the round-half-up algorithm.
Now, remember that, with positive values, we expect the round-half-up algorithm to round to the next integer for fractional values of 0.5 and higher. Suppose we have an initial value of 0011.1000, which equates to 3.5. Adding 0000.1000 and truncating the result leaves us with 0100, or 4 in decimal, which is what we expect.
Similarly, when we take an initial value of 0011.1100, which equates to 3.75 in decimal, adding 0000.1000 and truncating the result again leaves us with 0100, which is what we expect.
But what about negative values? For example, consider an initial value of 1100.1000. Once again, the integer portion equates to –4, while the fractional portion equates to +0.5, resulting in a total value of –3.5. In this case, adding 0000.1000 and truncating results in a value of 1101, which equates to –3 in decimal. From this we see that the simple round-half-up algorithm favored for many hardware implementations actually results in an asymmetrical realization of the rounding function when working with signed binary values.
The topic of rounding algorithms is much more interesting than one might suspect. There's so much more to talk about, but we don't have the time to cover everything here. If you are interested in reading more, you can find the original article at the Programmable Logic DesignLine Web site (www.pldesignline. com, article ID: 175801189).
Apart from anything else, the online version of the article has some real-world examples. Tim Vanevenhoven from AccelChip (which has now been acquired by Xilinx) created and ran some test cases in Matlab to illustrate the types of errors associated with rounding schemes applied at various stages throughout a digital filter. n
Clive (Max) Maxfield is the editor of Programmable Logic DesignLine, an EE Times sister Web site (www.pldesignline.com). He is the author of Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) (ISBN: 0750675438) and How Computers Do Math (ISBN: 0471732788), featuring the pedagogical and phantasmagorical virtual DIY Calculator (www.DIYCalculator.com).
