Fast FIR

Sziasztok!

Tud-e valaki veletlenul jo kis FIR algoritmust, ami akar meg gyors/hatekony is lehet? :) A win[] ablakfuggveny minden esetben lehet L + 1 = 2^N+1 elemszamu es szimmetrikus, ezt "er" kihasznalni. Azaz ahol L az mondjuk 32 ... 256 lenne a gyakorlatban mint ketto-hatvany, es win[n] = win[L-n] fennall. Nyilvan ha L az kisebb lenne mint az itteni ertekek (pl 4...8), akkor teljesen felesleges tultolni valami szofisztikalt eljarassal, ha pedig tul nagy, akkor mar ugyis inkabb konvolucionak hivnank mintsem FIR filteringnek. 

Egy naiv implementacio az kb ilyen most:

typedef struct
 {      int     fir_length;
        double  *fir_buffer;
        double  *fir_window;
        int     fir_index;
 } finite_impulse_response;

int fir_init(finite_impulse_response *fir,int len,double initial)
{
 int    i;
 fir->fir_length=len;
 fir->fir_buffer=(double *)malloc(sizeof(double)*len);
 for ( i=0; i<len; i++ )
  {     fir->fir_buffer[i]=initial;
  }
 fir->fir_window=(double *)malloc(sizeof(double)*(len+1));
 fir->fir_window= ...; /* computation of FIR window filter goes here */
 fir->fir_index=0;
 return(0);
}

double fir_apply(finite_impulse_response *fir,double in)
{
 double w;
 int    j,p;

 w=0.0;
 for ( j=0,p=fir->fir_index; j<fir->fir_length; j++ )
  {     w += fir->fir_buffer[p] * fir->fir_window[j];
        p=(p+1)%fir->fir_length;
  }
 w+=in*fir->fir_window[j];
 fir->fir_buffer[fir->fir_index]=in;
 fir->fir_index=(fir->fir_index+1)%fir->fir_length;

 return(w);
}

int fir_buffer(finite_impulse_response *fir,float *input,int ninput)
{
 int    i;
 for ( i=0; i<ninput ; i++ )
  {     input[i]=fir_apply(fir,input[i]);
  }
 return(0);
}

Lenyeg itt a legutolso fir_buffer() hivas, ami siman a fir_apply() hivason keresztul lekonvolvalja es a `fir` objektumban szepen tarolja az allapotgepet hogy kifele elrejtse az egesz hobelevancot. Szoval a feladat az a fir_apply() minel hatekonyabb, O(fir->fir_length) muveletigenynel jobban skalazo valtozata lenne. Nyilvan egy O(log(fir->fir_length)) lenne a legjobb :) Extrem hataresetekben, pl boxcar filterignel ugye O(1) muvelettel es O(length) memory footprinttel megoldhato, szoval csakcsak van valami a ketto kozott, kihasznalva hogy a length az ketto-hatvany es/vagy hogy a fir_window[] az szimmetrikus meg ilyesmi... 

thx, A.