Not a member?

# DSP Blogs > Rick Lyons > Multiplierless Exponential Averaging

Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He is also an Associate Editor for the IEEE Signal Processing Magazine.

Would you like to be notified by email when Rick Lyons publishes a new blog?

Pageviews: 323

# Multiplierless Exponential Averaging

Posted by Rick Lyons on Dec 5 2008 under Tips and Tricks

This blog discusses an interesting approach to exponential averaging. To begin my story, a traditional exponential averager (also called a "leaky integrator"), shown in Figure 1(a), is commonly used to reduce noise fluctuations that contaminate relatively constant-amplitude signal measurements.

Figure 1 Exponential averaging: (a) standard network; (b) single-multiply network.

That exponential averager's difference equation is

 y(n) = αx(n) + (1 – α)y(n–1) (1)

where α is a constant called the averager's weighting factor, in the range 0 < α < 1. The process requires two multiplies per y(n) output sample as shown in Figure 1(a).

As pointed out to me by Vladimir Vassilevsky (http://www.abvolt.com) we can rearrange Eq. (1) to the form

 y(n) = y(n–1) + α[x(n) – y(n–1)] (2)

which eliminates one of the averager's multiplies, at the expense of an additional adder, giving us a single-multiply exponential averager shown in Figure 1(b). This neat single-multiply exponential averager maintains the DC (zero Hz) gain of unity exhibited by the traditional two-multiply exponential averager in Figure 1(a).

Contemplating Vassilevsky's single-multiplier exponential averager, I thought about how we could eliminate the multiplier in Figure 1(b) altogether. It is possible to eliminate the multiplier in Figure 1(b) if we place restrictions on the permissible values of α. For example, if α = 0.125 = 1/8, then the output of the multiplier is merely the multiplier's input sample shifted right by three bits.

Thus we can replace the multiplier in Figure 1(b) by a 'binary right shift by L bits' operation as shown in Figure 2(a). In that figure, the 'BRS,L' block means an arithmetic, or hard-wired, Binary Right Shift by L bits. The values for weighting factor α = 1/2L when L is in the range 1 ≤ L ≤ 5 are shown in Figure 2(b). The available exponential averager frequency magnitude responses for those five values for α are shown in Figure 2(c). As it turns out, we can achieve greater flexibility in choosing various values of the averager's weighting factor α. Don't touch that dial!

Figure 2 Multiplierless exponential averaging: (a) multiplier-free network; (b) possible values for α when 1≤L≤5; (c) available frequency magnitude responses.

If α takes the form

 (3)

where L = 0, 1, 2, 3, ..., and M = 1, 2, 3, ..., we can replace the multiplication by α in Figure 1(b) with two binary right shifts and a subtract operation as shown in Figure 3(a).

Figure 3 Multiplierless exponential averaging: (a) multiplier-free network; (b) possible values for α when 0≤L≤5 and L+1≤M≤6; (c) available frequency magnitude responses.

For example if L = 2 and M = 5, then from Eq. (3), α = 0.2188. The sequence w(n) = 0.2188u(n) = (1/4 – 1/32)u(n) is computed by subtracting u(n) shifted right by M = 5 bits from u(n) shifted right by L = 2 bits.

The tick marks in Figure 3(b) show the possible values for the weighting factor α over the ranges of 0 ≤ L ≤ 5, where for each L, M is in the range L+1 ≤ M ≤ 6 in Eq. (3). That figure tells us that we have a reasonable selection of α values for our noise-reduction filtering applications. The available exponential averager frequency magnitude responses for those values for α are shown in Figure 3(c), where the top curve corresponds to L = 0 and M = 6 yielding α = 0.9844.

The point of this blog is, for fixed-point implementation of exponential averaging, check to see if your desired α weighting factor can be represented by the difference of various reciprocals of integer powers of two. If so, then binary word shifting enables us to implement a multiplierless exponential averager.

Yes yes, I know—you're wondering, "What about the quantization errors induced by the binary right-shift operations. Well, ...I haven't yet studied that issue.

4.665

posted by Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He is also an Associate Editor for the IEEE Signal Processing Magazine.

Previous post by Rick Lyons: Free DSP Books on the Internet - Part Deux
Next post by Rick Lyons: Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
all articles by Rick Lyons

Would you like to be notified by email when Rick Lyons publishes a new blog?

steveu
Said:
What you have described is what thousands of designs have done since the dawn of the digital logic and computer industries. Hard wired logic/FPGA systems and small MCUs still get massive benefits from this today. Quantisation is these filters is no different than any other single pole LPF, as the results of the arithmetic are exactly the same as when using a multiplier - you just have less flexible choice of the time constant. You either get lots of truncation, or you extend the registers and let the fractional bits noise shape things for you. The various minor variations on this theme have been repeatedly discussed on comp.dsp, in the context of DC estimation.
5 years ago
0