Subject: Dealing with propagating truncation errors
From: Ole Wolf
Date: 1999/05/26
Newsgroups: comp.dsp

Name: Dealing with propagating truncation errors.

Category: Algorithmic tricks.

Application: When values are truncated, and the truncated values are used later in the algorithm, ultimately corrupting the output.

Advantages: You get an acceptable output without having to switch to a completely different algorithm, and generally without having to sacrifice too much execution time.

Introduction: When you truncate or round the value of, say, a 32-bit product register to 16 bits, you may wind up getting pesky little rounding artifacts due to the reduced precision. Although it isn’t a problem in most applications, sometimes the small rounding errors do propagate through subsequent stages of an algorithm and eventually corrupt the output. Here are a couple of suggestions that can help you get a cleaner output.

The Trick:

  1. Use extended-precision arithmetic, such as larger-width multiplies and add-with-carry operations, but that’s computationally expensive. I think this is the most common way to kill those pesky errors that begin to accumulate. Processor support for extended-precision arithmetic includes:
    • add with carry and subtract with borrow
    • multiplication of signed/signed, signed/unsigned, and unsigned/unsigned operands
  2. Create “leakage.” This means that at strategic logactions in an algorithm you multiply with (1-epsilon) so that a value continuously becomes slightly smaller than it was supposed to do. If you do that in a feedback loop, the errors that are feeding back will fade out.
  3. Dither the signal. You may find instability caused by a limit cycle appearing for zero (i.e., smaller magnitude than one LSB) or constant input. Or, an algorithm may “stall” because an input signal is too weak to excite the variables in an algorithm. Both problems may be eliminated by dithering the variables in the algorithm. You do that by adding white noise to the variables.
  4. In Handbook of Digital Signal Processing: Engineering Applications [Ell87], Douglas F. Elliot discusses “error feedback”. As far as I remember, this is a technique where you essentially “save” the truncation error of a previous iteration and add it in the next iteration, effectively introducing some redundancy. This redundancy effectively creates extended precision for you with less computational effort.
  5. If everything gets out of hand, have some error detection mechanism built into the algorithm (say, to check for magnitude of a certain variable) and re-initialize your algorithm by resetting coefficients or what else you can think of resetting.