</>EmbeddedInterview

How do you implement a moving average filter efficiently?

MediumData Structures & Algorithms

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).