DSP Trick: Dealing With Propagating Truncation Errors
Subject: Dealing with propagating truncation errors
From: Ole Wolf
Date: 1999/05/26
Newsgroups: comp.dsp
THIS WORK IS PLACED IN THE PUBLIC DOMAIN
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:
- 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
- Create "leakage." This means that at strategic logactions in
an algorithm you multiply with (1-epsilon) so that a value continously 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.
- 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.
- 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.
- 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.