Channels ▼
RSS

Global Developer

Rounding Algorithms


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.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

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).

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 bitplus 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 website (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).

See related chart

See related chart


Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video