One of the most demanding applications for fast arithmetic is digital flitering. Atmel application note AVR201 shows how to use the hardware multiplier to make a multiply-and-accumulate operation (MAC). The MAC is the basis for computing the sum of terms for any digital filter, such as the "Direct Form II Transposed" implementation of a difference equation shown below (from the Matlab filter description).

    a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb)
                          - a(2)*y(n-1) - ... - a(na+1)*y(n-na)

The y(n) term is the current filter output and x(n) is the current filter input. The a's and b's are constant coefficients, determined by some design process, such as the Matlab butter routine. Usually, a(1) is set to one, but as we shall see below, setting a(1) to a power of two may increase filter accuracy, at the cost of slightly increased execution time. The y(n-x) and x(n-x) are past outputs and inputs respectively. You can use the Matlab filter design tools to determine the a's and b's. 

The 2nd order IIR code (plus uart.c, uart.h) implements an efficient MAC operation using the multfix asssembler macro and then uses it to produce a second order IIR filter. The time/sample is 140 cycles. It would not be reasonable to use this fixed-point algorithm with normalized cutoff frequency below about 0.10 because of the lack of relative precision in the b coefficients. With a normalized cutoff frequency=0.25, the impulse response is accurate to within 1% of peak response. With a normalized cutoff frequency=0.10, the impulse response is accurate within 5% of peak response. If you need a cutoff lower than 0.10, consider changing your hardware sample rate or using CIC filters (see below) to lower the effective sample rate. It is also possible to scale up all of the filter coefficients by 16 to give 4 bits more percision, then divide the output of the filter by 16 for each sample. IIRfilterScaledGCC644_macro.c is an example which executes in 190 cycles. This Matlab program allows you to simulate the effect of coefficient truncation on filter response.

Another approach used in speech synthesis is to use impulse-invariant second order filters which are a bit quicker to execute because they zero out two of the general second order filter coefficients (b(2) and b(3)). These filters can also be designed on-the-fly in a C program, rather than using Matlab. It is possible to build bandpass and lowpass filters using this technique, but you need to be careful of aliasing effects and the sensitivity of coefficients to 8-bit truncation. This matlab program allows you to estimate truncation errors and design filters. Note that the bandpass filters have a gain greater than one in the passband, so you may need to scale output to avoid overflow of fixed point numbers. At 8000 Hz sample rate, you can expect to get reasonable bandpass filter accuracy down to F=250, BW=25 Hz, and lowpass accuracy down to BW=250 Hz. Impulse invariant second order filter design process:

  1. Choose the bandpass center frequency, F. If the filter is to be lowpass, set F=0.
  2. Choose the bandpass bandwidth, BW. If the filter is to be lowpass, the cutoff frequency is BW/2.
  3. Compute: C = -exp(-2*pi*BW*T) where T=1/(sample rate)
  4. Compute: B = 2 * exp(-pi*BW*T) * cos(2*pi*F*T) where T=1/(sample rate)
  5. Compute: A = 1 - B - C
  6. The filter output at time i is then output(i)=A*input(i) + B*output(i-1) + C*output(i-2)
  7. In some circumstances generating a table of A, B and C at the frequencies you need will be the fastest way to change between filters.
    These two programs suggest how you might do this for lowpass and bandpass filters

Second order and fourth order Butterworth IIR Filters for 8:8

If you use a Butterworth approximation for lowpass (maximally flat IIR filter) then you can simplify the general IIR filter further to only three MAC operations. Since b(1)=b(3)=0.5*b(2), the three multiplies on the first line below can be combined...

Read more »