Topics / Data Structures & Algorithms / Q17
How do you implement a moving average filter efficiently?
Short answer: Keep a ring buffer of the last N samples and a running sum. For each new sample, subtract the oldest sample, add the newest, and store it in the buffer: O(1) per sample regardless of N. Use a power-of-two N so the division is a shift. When RAM is tight, an exponential moving average (y += (x − y) >> k) needs no buffer at all.
#include <stdint.h>
#include <stdio.h>
#define LOG2_N 3
#define N (1u << LOG2_N) /* 8-sample window */
typedef struct { uint16_t win[N]; uint32_t sum; uint8_t i; } mavg_t;
uint16_t mavg_update(mavg_t *f, uint16_t x)
{
f->sum += (uint32_t)x - f->win[f->i]; /* unsigned wrap cancels out correctly */
f->win[f->i] = x;
f->i = (uint8_t)((f->i + 1) & (N - 1));
return (uint16_t)(f->sum >> LOG2_N);
}
typedef struct { int32_t y; } ema_t; /* fixed point: y holds value << 4 */
int32_t ema_update(ema_t *f, int32_t x, int k) /* alpha = 1/2^k */
{
f->y += ((x << 4) - f->y) >> k;
return f->y >> 4;
}
int main(void)
{
mavg_t m = {0};
ema_t e = { 0 };
for (int t = 0; t < 12; t++) {
uint16_t x = (t < 4) ? 0 : 800; /* step input */
printf("%u/%ld ", mavg_update(&m, x), (long)ema_update(&e, x, 2));
}
printf("\n");
return 0;
}
Details
- The sum must be wide enough: N × max sample (8 × 4095 fits easily in 32 bits).
- During the first N samples the average includes the zero-initialised buffer; pre-fill with the first sample if that matters.
- The moving average delays the signal by (N − 1)/2 samples and is a weak low-pass filter with ripples in its frequency response.
- EMA has an equivalent time constant of about 2^k samples, costs one subtraction and shift, but keeps fractional precision only if you store the state with extra bits (as above).
- Median filter (median of the last 3–9 samples) removes spikes that averages smear.
- For sharper frequency responses, use FIR/IIR filters (CMSIS-DSP provides optimised versions).