• FPGA
• Basics
• Python

The wheels go round and round, round and round ...

Integer arithmetic is ubiquitous in digital hardware implementations, it's prolific in the control and data-paths.  When using fixed width (constrained) integers, overflow and underflow is business as usual.

Building with Integers

The subtitle of this post mentions a wheel - before I get to the wheel I want to look at an example.  The recursive-windowed-averager (rwa, a.k.a moving average) and its cousin the cascaded-integrator comb (CIC) filter are low resource -but mediocre performance- low-pass filter implementations.  The basic building blocks in the filters are a discrete integrator (accumulator might be a better description but that is a discussion for another post) and comb filter.  Using a fixed width integer both the integrator and the comb can experience overflow and underflow but combined the overflow / underflow cancel out (wraps back).

In this example I am using Python plus the MyHDL package for the fixed width types.  MyHDL has two types to represent constrained integers: the intbv and modbv.  When simulating the intbv checks for overflows (throws an error if the value goes beyond the limits) and the modbv wraps (if the max and min are a power of two).  For additional information on the see These Int's Are Made for Countin' and the modbv enhancement proposal.

The following plots, figure 2, show the output of a stand-alone integrator, comb, and the combined integrator-comb (rwa) output. The first subplot is the running sum, the unbounded integer grows and grows and the modbv (2's comp) wraps and wraps. The second subplot is the comb, the example shows the high-pass filter acting line an differentiator (at least for this input). The same phenomena occurs, the unbounded integer grows and the 2's compliment wraps. The third plot shows the unwrapping when combined.

The following, figure 3, shows the input and output for the full range of constant inputs into the rwa.  This simply demonstrates the full valid input range, in this case -15 to 15 (5 bit), can be computed.

From the above plots it appears reasonable that the integrator followed by the comb would unwrap the overflows.  The following diagram, figure 4, is a 2's complement wheel and the wheel unrolled to a number line. Given the wrap behavior of the 2's complement number it can be seen how it is possible to grow and shrink.

Poles and Zeros

We can also look at this from a signal processing perspective.  The first block, the integrator, has a pole at DC ($z = 1 + 0j$), which is easily observable, given a constant input the output will grow and grow.

$$
H_{accum}(z) = \frac{1}{1 - z^{-1}}
$$

The comb has zeros evenly spaced along the unit circle based on the length of the window (the delay in the comb) including the zero at DC.

$$
H_{comb}(z) = 1 - z^{-R}
$$

The following is the pole-zero plot for the combined transfer function, it can be seen that a zero cancels out the pole.

Over-Under Design

The fact that an intermediate value can overflow, later underflow, and then end up in the expected range can be exploited in DSP design.  The following (nonsensical) example shows how a smaller accumulator can be used and the result is as expected .

In the above plot we can see the coefficients grow and then shrink, the sum-of-products will follow (at least when all the taps contain the same value).  The above example illustrates how the fact that the bounded integer with a range much smaller than the max intermediate value can be used.

Integers Masquerading as Reals

We can use integers to represent a range of rational real numbers and we call this fixed-point representation.  See the fixed-point by example post for an introduction to fixed-point representation.  Even though we use a fixed range and resolution real, the underlying math is all the same.  If not explicitly handled overflows will wrap just as described above.

Notation

Couple logistical items before jumping into the fixed-point overflow discussion.  The "Q-notation" often causes confusion (see some of the comments here).  In this discussion the Q-notation will not be used, instead I will use an explicit tuple (math/python terminology) to express a fixed-point format.  The tuple will be: the word-length, integer word-length, and fractional, word-length (wl, iwl, fwl).  For example, the not so common Q16 will be described as W=(16,0,15). The tuple describes a basic relationship:

$$
wl = 1 + iwl + fwl
$$

This is the format that will be used when discussing fixed-point types. If a short hand is desired Wwl.fwl will do.  In the
short hand the iwl is implicit given the above definitions.  The following is an example of the fixed-point calculations similar to the above.

The above is an example of the fixed-point with no overflow, the coefficients are the same shape as our integer but they are all less than one.  The following illustrates the same accumulator as the above plots but less resolution bits were used and after each multiply and accumulate the product was resized to the same size as the accumulator.  Because the resolution is limited the full accumulator shape is not realized. This is fractional
truncation (with rounding).

With the fixed-point to handle the overflow, commonly a resize, function is used.  The resize function is used to control
how the overflow and rounding is handled.  The overflow can saturate (hold at the min/max value) or wrap.  The following is an example of the fixed-point wrap.

In this last example error from rounding has accumulated and the final result is not 100% accurate.

One last note, the MyHDL fixbv is currently an enhancement proposal.  There is no doubt the fixbv will be added to the base (possibly in the next release) but it may not be exactly as shown here.  It is reasonable that changes could occur.

Conclusion

The wheels go round and round, round and round ... but sometimes they need a little help.

For more articles on this topic see: C compilers and overflow and fixed-point by example.

Sign in