Implementation of FIR filters

 Consider an FIR filter with impulse response h and input x, where the output is given by

.

We now examine a number of ways to implement this filter.

Matlab implementation

If x is finite, and we can interpret it as an infinite signal that is zero outside the specified range, then we can compute y using Matlab's conv() function. That is, if x is a vector containing the N values of the input, h is a vector containing the M + 1 values of the impulse response, then

y = conv(x, h);

yields a vector containing M + N values of the output. This strategy, of course, only works for finite input data.

Java implementation

The following Java class implements an FIR filter.

1	class FIR {
2	    private int length;
3	    private double[] delayLine;
4	    private double[] impulseResponse;
5	    private int count = 0;

6	    FIR(double[] coefs) {
7	        length = coefs.length;
8	        impulseResponse = coefs;
9	        delayLine = new double[length];
10	    }

11	    double getOutputSample(double inputSample) {
12	        delayLine[count] = inputSample;
13	        double result = 0.0;
14	        int index = count;
15	        for (int i=0; i<length; i++) {
16	            result += impulseResponse[i] * delayLine[index--];
17	            if (index < 0) index = length-1;
18	        }
19	        if (++count >= length) count = 0;
20	        return result;
21	    }
22	}

A class is Java (and in any object oriented language) has both data members and methods. The methods are procedures that operate on the data members, and may or may not take arguments are return values. In this case, there are two procedures, "FIR" and "getOutputSample". The first, lines 6-10, is a constructor, which is a procedure that is called to create an FIR filter. It takes one argument, an array of double-precision floating-point numbers that specify the impulse response of the filter. The second, lines 11-22, takes a new input sample value as an argument and returns a new output sample. It also updates the delay line using a strategy called circular buffering. That is, the count member is used to keep track of where each new input sample should go. It gets incremented (line 19) each time the getOutputSample() method is called. When it exceeds the length of the buffer, it gets reset to zero. Thus, at all times, it contains the M + 1 most recently received input data samples. The most recent one is at index count in the buffer. The second most recent is at count - 1, or if that is negative, at length - 1. Line 17 makes sure that the variable index remains within the confines of the buffer as we iterate through the loop.

Programmable DSP implementation

The following section of code is the assembly language for a programmable DSP, which is a specialized microprocessor designed to implement signal processing functions efficiently in embedded systems (such as cellular telephones, digital cordless telephones, digital audio systems, etc.). This particular code is for the Motorola DSP56000 family of processors. 

1	fir	movep		x:input,x:(r0)
2		clr a		x:(r0)-,x0	y:(r4)+,y0
3		rep m0
4		mac x0,y0,a	x:(r0)-,x0	y:(r4)+,y0
5		macr x0,y0,a	(r0)+
6		movep a,x:output
7		jmp fir

The code is explained below, line by line. While reading this, it will be helpful to know that this processor has two memory banks that can be separately addressed, called "x" and "y". The code assumes that each input sample can be successively read from a memory location called "input", and that the impulse response is stored in y memory beginning at an address stored in register "r4". Moreover, it assumes that register "r0" contains the address of a section of x memory to use for storing input samples, and that this register has been set up to perform modulo addressing. Modulo addressing means that if it increments or decrements beyond the range of its buffer, then the address wraps around to the other end of the buffer. Finally, it assumes that the register "m0" contains an integer specifying the number of samples in the impulse response minus one.

  1. This line has a label, "fir", that is used in line 7 as a target for a jump. It begins the filtering operation by moving a new input data sample from a location in x memory to another location in x memory, where the address of the destination is contained by the register named "r0".
  2. This line clears (sets to zero) a register called "a", the "accumulator". At the same time, it loads a register named "x0" with a value from x memory, where the address in memory is contained by register "r0". Then it decrements "r0". At the same time, register "y0" is loaded from a memory location given by "r4", and then "r4" is incremented to point to the next higher location.
  3. This line causes the following line (line 4) to be repeatedly executed a number of times, where the number of times is contained by the register named "m0".
  4. This line does most of the work. It multiplies the data contained in "x0" by that in "y0" and adds the result to "a" (such an operation is called a multiply and accumulate or mac operation). At the same time, it loads "x0" and "y0" with a new input sample and impulse response sample, much as done in line 2. As it executes repeatedly, it multiplies and accumulates new data.
  5. This performs the last multiply and accumulate.
  6. This writes the output data to a memory location called "output".
  7. This restarts the filter so that it can process the next sample.

Digital hardware implementation

An FIR filter can be easily implemented using just three digital hardware elements, a unit delay (a latch), a multiplier, and an adder. The unit delay simply updates its output once per sample period, using the value of the input as its new output value. In the convolution sum,

.

notice that at each n we need access to x(n), x(n - 1), x(n - 2), …, x(n - M). We can maintain this set of values by cascading a set of latches to form a delay line, as shown below:

For each integer n, the output sample is the values in the delay line scaled by h(0), h(1), …, h(M). To obtain these values, we simply tap the delay line, as shown in the following picture

The triangular boxes denote multipliers that multiply by a constant (h(m)). The circles denote adders. The above picture shows a tapped delay line implementation of an FIR filter.