вот в исходниках. Правда это комбинированое 4-2, т.е. если степень двойки кратна 2м, то чистое ффт по основанию 4, а если не кратно, то сначала 4ка, а последний шаг по основанию 2.
Это обратное фурье - экспонента положительна. Чтобы сделать отрицательную экспоненту, надо поменять знаки в операциях умножения на j и знак мнимой части коэффициентов.
Масштабирования нет.
Чтобы ввести масштабирование на 1/N надо поменять значение SHIFT_AMOUNT_UNSCALED
Код писался мной для себя, поэтому комментов не много, уж не обессудте.
Код
static void
data_swap(fft_inter data[], int np)
{
fft_inter *pxk, *pxi;
fft_inter *px = data;
int tmp;
int n2, n21;
int i, j, k;
n2 = np >> 1; /// n2: 512
n21 = np + 1; /// n21: 1025
j = 0;
for (i = 0; i < np; i += 4)
{ /// i,j: 0,0; 4,1024; 8,512; 12,1536; ... 2044,??? [255x]
if (i < j)
{
// swap 4 pairs of values (2 complex pairs with 2 others)
// px[i] <-> px[j]; px[i+1] <-> px[j+1]
// px[i+1+n21] <-> px[j+1+n21]; px[i+1+n21+1] <-> px[j+1+n21+1]
pxi = &px[i]; pxk = &px[j];
tmp = *pxi; *pxi++ = *pxk; *pxk++ = tmp;
tmp = *pxi; *pxi = *pxk; *pxk = tmp;
pxi += n21; pxk += n21;
tmp = *pxi; *pxi++ = *pxk; *pxk++ = tmp;
tmp = *pxi; *pxi = *pxk; *pxk = tmp;
}
// swap 2 pairs of values (1 complex pair with another)
// px[i+2] <-> px[j+np]; px[i+3] <-> px[j+np+1]
pxi = &px[i + 2];
pxk = &px[j + np];
tmp = *pxi; *pxi++ = *pxk; *pxk++ = tmp;
tmp = *pxi; *pxi = *pxk; *pxk = tmp;
k = n2;
while (k <= j)
{ /// k: {1024} {1024,512} {1024} {1024,512,256} ...
j -= k;
k = k >> 1;
}
j += k; /// j: {1024} {512} {1536} {256} ...
}
}
#define COMPLEX_MUL(a,b,c,d)\
do{ fft_extend x,y; x = MULT16(a,c)-MULT16(b,d); y = MULT16(c,b)+MULT16(a,d); a = x; b = y; }while(0)
#define SHIFT_AMOUNT_UNSCALED 0
void
radix4_unscaled(struct complex_s *data, int size, fft_inter *tw)
{
struct complex_s *x = data;
int i, l;
int N;
struct complex_s32 x0,x1,x2,x3, t1,t2,t3,t4,t;
fft_inter wre,wim;
N = size;
while(N > 4)
{
for (l = 0; l< size; l+= N)
{
for (i = l; i < l + N/4; i++)
{
int idx = i;
x0.re = x[i].re;
x0.im = x[i].im;
x2.re = x[N/2+i].re;
x2.im = x[N/2+i].im;
t1.re = x0.re + x2.re;
t1.im = x0.im + x2.im;
t2.re = x0.re - x2.re;
t2.im = x0.im - x2.im;
x0.re = x[i+N/4].re;
x0.im = x[i+N/4].im;
x2.re = x[N/2+i+N/4].re;
x2.im = x[N/2+i+N/4].im;
t3.re = x0.re + x2.re;
t3.im = x0.im + x2.im;
t4.re = x0.re - x2.re;
t4.im = x0.im - x2.im;
// update x_{0+i}
t.re = t1.re + t3.re;
t.im = t1.im + t3.im;
x[i].re = t.re>>SHIFT_AMOUNT_UNSCALED;
x[i].im = t.im>>SHIFT_AMOUNT_UNSCALED;
// x_{0+i} updated
// update x_{N/4+i}
// wre = FR2(cos(2.* M_PI / N * 2. * idx/1));
// wim = FR2(sin(2.* M_PI / N * 2. * idx/1));
//printf("/*N:%2d,i:%2d */ FR2(%+.16f), FR2(%+.16f),\n", N,idx,
// cos(2.* M_PI / N * 2. * idx/1), sin(2.* M_PI / N * 2. * idx/1));
wre = *tw++;
wim = *tw++;
t.re = t1.re - t3.re;
t.im = t1.im - t3.im;
COMPLEX_MUL(t.re,t.im, wre, wim);
x[i+N/4].re = t.re>>SHIFT_AMOUNT_UNSCALED;
x[i+N/4].im = t.im>>SHIFT_AMOUNT_UNSCALED;
// x_{N/4+i} updated
// update x_{N/2}
// wre = FR2(cos(2.* M_PI / N * 1. * idx/1));
// wim = FR2(sin(2.* M_PI / N * 1. * idx/1));
//printf("/*N:%2d,i:%2d */ FR2(%+.16f), FR2(%+.16f),\n", N,idx,
// cos(2.* M_PI / N * 1. * idx/1), sin(2.* M_PI / N * 1. * idx/1));
wre = *tw++;
wim = *tw++;
t.re = t2.re - t4.im; /// ???
t.im = t2.im + t4.re; /// ???
COMPLEX_MUL(t.re,t.im, wre, wim);
x[N/2+i].re = t.re>>SHIFT_AMOUNT_UNSCALED;
x[N/2+i].im = t.im>>SHIFT_AMOUNT_UNSCALED;
// x_{N/2} updated
// update x_{3N/4+i}
// wre = FR2(cos(2.* M_PI / N * 3. * idx/1));
// wim = FR2(sin(2.* M_PI / N * 3. * idx/1));
//printf("/*N:%2d,i:%2d */ FR2(%+.16f), FR2(%+.16f),\n", N,idx,
// cos(2.* M_PI / N * 3. * idx/1), sin(2.* M_PI / N * 3. * idx/1));
wre = *tw++;
wim = *tw++;
t.re = t2.re + t4.im; /// ???
t.im = t2.im - t4.re; /// ???
COMPLEX_MUL(t.re,t.im, wre, wim);
x[N/2+i+N/4].re = t.re>>SHIFT_AMOUNT_UNSCALED;
x[N/2+i+N/4].im = t.im>>SHIFT_AMOUNT_UNSCALED;
// x_{3N/4+i} updated
}
}
N >>= 2;
}
if ( N != 2 ) // FIXME: N == 4
{
for (i = 0; i < size; i+= 4)
{
x0.re = x[i].re;
x0.im = x[i].im;
x2.re = x[2+i].re;
x2.im = x[2+i].im;
t1.re = x0.re + x2.re;
t1.im = x0.im + x2.im;
t2.re = x0.re - x2.re;
t2.im = x0.im - x2.im;
x0.re = x[i+1].re;
x0.im = x[i+1].im;
x2.re = x[3+i].re;
x2.im = x[3+i].im;
t3.re = x0.re + x2.re;
t3.im = x0.im + x2.im;
t4.re = x0.re - x2.re;
t4.im = x0.im - x2.im;
// update x_{0+i}
t.re = t1.re + t3.re;
t.im = t1.im + t3.im;
x[i].re = t.re>>(SHIFT_AMOUNT_UNSCALED/1);
x[i].im = t.im>>(SHIFT_AMOUNT_UNSCALED/1);
// x_{0+i} updated
// update x_{N/4+i}
t.re = t1.re - t3.re;
t.im = t1.im - t3.im;
x[i+1].re = t.re>>(SHIFT_AMOUNT_UNSCALED/1);
x[i+1].im = t.im>>(SHIFT_AMOUNT_UNSCALED/1);
// x_{N/4+i} updated
// update x_{N/2}
t.re = t2.re - t4.im; /// ???
t.im = t2.im + t4.re; /// ???
x[2+i].re = t.re>>(SHIFT_AMOUNT_UNSCALED/1);
x[2+i].im = t.im>>(SHIFT_AMOUNT_UNSCALED/1);
// x_{N/2} updated
// update x_{3N/4+i}
t.re = t2.re + t4.im; /// ???
t.im = t2.im - t4.re; /// ???
x[3+i].re = t.re>>(SHIFT_AMOUNT_UNSCALED/1);
x[3+i].im = t.im>>(SHIFT_AMOUNT_UNSCALED/1);
// x_{3N/4+i} updated
}
}
else
{
// trivial butts at the end
for (i = 0; i<size; i+= 2)
{
x0.re = x[i].re;
x0.im = x[i].im;
x1.re = x[i+1].re;
x1.im = x[i+1].im;
t.re = x0.re + x1.re;
t.im = x0.im + x1.im;
x[i].re = t.re>>1;
x[i].im = t.im>>1;
t.re = x0.re - x1.re;
t.im = x0.im - x1.im;
x[i+1].re = t.re>>1;
x[i+1].im = t.im>>1;
}
}
data_swap((fft_inter *)data,size);
}