# FIR filters in C

I wrote 2 filters in C for the Altera DE2 Nios II FPGA, one floating-point and one fixed-point. I've verified that they perform correctly and now I wonder if you can give examples for improvement or optimization? I'll reduce the C library to a small library and turn on optimization, and perhaps you can suggest how to do other improvements?

The floating-point program:

#include <stdio.h>
#include "system.h"
#include "alt_types.h"
#include <time.h>
#include <sys/alt_timestamp.h>
#include <sys/alt_cache.h>

float microseconds(int ticks)
{
return (float) 1000000 * (float) ticks / (float) alt_timestamp_freq();
}

void start_measurement()
{
/* Flush caches */
alt_dcache_flush_all();
alt_icache_flush_all();
/* Measure */
alt_timestamp_start();
time_1 = alt_timestamp();
}

void stop_measurement()
{
time_2 = alt_timestamp();
ticks = time_2 - time_1;
}

float floatFIR(float inVal, float* x, float* coef, int len)
{
float y = 0.0;
int i;
start_measurement();
for (i = (len-1) ; i > 0 ; i--)
{
x[i] = x[i-1];
y = y + (coef[i] * x[i]);
}
x[0] = inVal;
y = y + (coef[0] * x[0]);
stop_measurement();
printf("%5.2f us", (float) microseconds(ticks - timer_overhead));
printf("(%d ticks)\n", (int) (ticks - timer_overhead));
printf("Sum: %f\n", y);
return y;
}

int main(int argc, char** argv)
{
// Average of 10 measurements */
int i;
for (i = 0; i < 10; i++) {
start_measurement();
stop_measurement();
}
float coef[4] = {0.0299, 0.4701, 0.4701, 0.0299};
float x[4] = {0, 0, 0, 0}; /* or any other initial condition*/
float y;
float inVal;

while (scanf("%f", &inVal) > 0)
{
y = floatFIR(inVal, x, coef, 4);
}
return 0;
}


The fixed-point program:

#include <stdio.h>
#include "system.h"
#include "alt_types.h"
#include <time.h>
#include <sys/alt_timestamp.h>
#include <sys/alt_cache.h>

#define TIME 1

signed char input[4]; /* The 4 most recent input values */

char get_q7( void );
void put_q7( char );
void firFixed(signed char input[4]);

const int c0 = (0.0299 * 128 + 0.5); /* Converting from float to Q7 by multiplying by 2^n i.e. 128 = 2^7 since we use Q7 and round to the nearest integer by multiplying with 0.5. The fraction will be truncated. */
const int c1 = (0.4701 * 128 + 0.5);
const int c2 = (0.4701 * 128 + 0.5);
const int c3 = (0.0299 * 128 + 0.5);
const int half = (0.5000 * 128 + 0.5);

enum { Q7_BITS = 7 };

alt_u32 ticks;
alt_u32 time_1;
alt_u32 time_2;

float microseconds(int ticks)
{
return (float) 1000000 * (float) ticks / (float) alt_timestamp_freq();
}

void start_measurement()
{
/* Flush caches */
alt_dcache_flush_all();
alt_icache_flush_all();
/* Measure */
alt_timestamp_start();
time_1 = alt_timestamp();
}

void stop_measurement()
{
time_2 = alt_timestamp();
ticks = time_2 - time_1;
}

void firFixed(signed char input[4])
{
int sum = c0*input[0] + c1*input[1] + c2*input[2] + c3*input[3];
signed char output = (signed char)((sum + half) >> Q7_BITS);
stop_measurement();
if (TIME)
{
printf("(%d ticks)\n", (int) (ticks - timer_overhead));
}
put_q7(output);
}

int main(void)
{
printf("c0 = c3 = %3d = 0x%.2X\n", c0, c0);
printf("c1 = c2 = %3d = 0x%.2X\n", c1, c1);
if (TIME)
{
// Average of 10 measurements */
int i;
for (i = 0; i < 10; i++) {
start_measurement();
stop_measurement();
}

}
int a;
while(1)
{
if (TIME)
{
start_measurement();
}
for (a = 3 ; a > 0 ; a--)
{
input[a] = input[a-1];
}
input[0]=get_q7();
firFixed(input);
}
return 0;
}

• Try using doubles. They might be faster on your platform. – Peter G. Oct 9 '13 at 13:48

A good first approach is always to look for a library call that already does what you need and that was optimized for your platform. For a FIR filter, that might e.g. be cblas_sdot in the BLAS library.

For a hand written approach, the key issues are picking the right data types (as discussed by @WilliamMorris) and exploiting the parallelism of the target platform. Since you’re targeting an FPGA, you even get to pick the level of parallelism. On the other hand, FPGAs are not necessarily great with arbitrary loops, so I would take a very close look at whether you can get away with using a constant number of coefficients.

Once you’ve decided on an appropriate level of parallelism, break up the data dependency in your loop. Right now, every iteration needs to wait for the previous iteration to complete. If you, e.g., want to have 4-way parallelism, something like this might work (assuming the # of coefficients is divisible by 4):

float y0=0.0f, y1=0.0f, y2=0.0f, y3=0.0f;
memmov(&x[1], &x[0], (len-1)*sizeof(x[0]));
x[0] = inVal;
for (int i=len; i>0; i-=4) {
y0 += x[i-4]*coeff[i-4];
y1 += x[i-3]*coeff[i-3];
y2 += x[i-2]*coeff[i-2];
y3 += x[i-1]*coeff[i-1];
}
y0 += y2;
y1 += y3;

return y0+y1;


With the float version, I would make the coef parameter const and add restrict to both parameters. But that is unlikely to make much difference to speed.

For the integer version, I would make the coefficients bigger than 8 bit. You lose a lot of the accuracy of the coefficients by reducing them to 8 bits and as you are accumulating using int, that seems unnecessary. This will improve the characteristics of the filter although the performance will depend upon the CPU - on a desktop type processor using int rather than char is likely to be faster, but for your processor that might not be true.