I'm a beginner in C programming. I am current trying to work on a project requiring 1024-point FFT implementation using radix-2, Decimation-in-frequency. I attach the FFT function C code. How can I increase the performance by modifying the C code?
#include "i_cmplx.h" /* definition of the complex type */
#include "twiddle1024.h" /* quantised and scaled Twiddle factors */
#define LL 1024 /* Maximum length of FFT */
/* fft radix-2 funtion using Decimation In Frequency */
//#pragma CODE_SECTION(fft, "mycode"); // Makes the program run from internal memory
void fft(COMPLEX *Y, int N) /* FFT(input sample array, # of points) */
{
int temp1R, temp1I, temp2R,temp2I; /* 32 bits temporary storage for */
/* intermediate results */
short tempR, tempI, c, s; /* 16 bits temporary storages */
/* variables */
int TwFStep, /* Step between twiddle factors */
TwFIndex, /* Index of twiddle factors */
BLStep, /* Step for incrementing butterfly index */
BLdiff, /* Difference between upper and lower butterfly legs */
upperIdx,
lowerIdx, /* upper and lower indexes of buterfly leg */
i, j, k; /* loop control variables */
BLdiff=N;
TwFStep=1;
for(k=N;k>1;k=(k>>1)) /* Do Log(base 2)(N) Stages */
{
BLStep=BLdiff;
BLdiff=BLdiff>>1;
TwFIndex=0;
for(j=0;j<BLdiff;j++)/* Nbr of twiddle factors to use=BLDiff */
{
c=w[TwFIndex].real;
s=w[TwFIndex].imag;
TwFIndex=TwFIndex+TwFStep;
/* Now do N/BLStep butterflies */
for(upperIdx=j;upperIdx<N;upperIdx+=BLStep)
{
/* Calculations inside this loop avoid overflow by shifting left once
the result of every adittion/substration and by shifting left 15
places the result of every multiplication. Double precision temporary
results (32-bit) are used in order to avoid losing information because
of overflow. Final DFT result is scaled by N (number of points), i.e.,
2^(Nbr of stages) =2^(log(base 2) N) = N */
lowerIdx=upperIdx+BLdiff;
temp1R = (Y[upperIdx].real - Y[lowerIdx].real)>>1;
temp2R = (Y[upperIdx].real + Y[lowerIdx].real)>>1;
Y[upperIdx].real = (short) temp2R;
temp1I = (Y[upperIdx].imag - Y[lowerIdx].imag)>>1;
temp2I = (Y[upperIdx].imag + Y[lowerIdx].imag)>>1;
Y[upperIdx].imag = (short) temp2I;
temp2R = (c*temp1R - s*temp1I)>>15;
Y[lowerIdx].real = (short) temp2R;
temp2I = (c*temp1I + s*temp1R)>>15;
Y[lowerIdx].imag = (short) temp2I;
}
}
TwFStep = TwFStep<<1; /* update separation of twiddle factors)*/
}
/* bit reversal for resequencing data */
j=0;
for (i=1;i<(N-1);i++)
{
k=N/2;
while (k<=j)
{
j = j-k;
k=k/2;
}
j=j+k;
if (i<j)
{
tempR=Y[j].real;
tempI=Y[j].imag;
Y[j].real=Y[i].real;
Y[j].imag=Y[i].imag;
Y[i].real=tempR;
Y[i].imag=tempI;
}
}
return;
}
Source file:
twiddle1024.h
/* This file defines the 512 complex twiddle factors used by the program */
//twiddle1024.h
struct
{
short real; /* 32767*cos(2*pi*n) term */
short imag; /* 32767*sin (2*pi*n)term */
}
w[]={32767,0,
32767,-201,
32766,-402,
32762,-603,
32758,-804,
32753,-1005,
32746,-1206,
32738,-1407,
32729,-1608,
32718,-1809,
32706,-2009,
32693,-2210,
32679,-2411,
32664,-2611,
32647,-2811,
32629,-3012,
32610,-3212,
32590,-3412,
32568,-3612,
32546,-3812,
32522,-4011,
32496,-4211,
32470,-4410,
32442,-4609,
32413,-4808,
32383,-5007,
32352,-5205,
32319,-5404,
32286,-5602,
32251,-5800,
32214,-5998,
32177,-6195,
32138,-6393,
32099,-6590,
32058,-6787,
32015,-6983,
31972,-7180,
31927,-7376,
31881,-7571,
31834,-7767,
31786,-7962,
31737,-8157,
31686,-8351,
31634,-8546,
31581,-8740,
31527,-8933,
31471,-9127,
31415,-9319,
31357,-9512,
31298,-9704,
31238,-9896,
31177,-10088,
31114,-10279,
31050,-10469,
30986,-10660,
30920,-10850,
30853,-11039,
30784,-11228,
30715,-11417,
30644,-11605,
30572,-11793,
30499,-11980,
30425,-12167,
30350,-12354,
30274,-12540,
30196,-12725,
30118,-12910,
30038,-13095,
29957,-13279,
29875,-13463,
29792,-13646,
29707,-13828,
29622,-14010,
29535,-14192,
29448,-14373,
29359,-14553,
29269,-14733,
29178,-14912,
29086,-15091,
28993,-15269,
28899,-15447,
28803,-15624,
28707,-15800,
28610,-15976,
28511,-16151,
28411,-16326,
28311,-16500,
28209,-16673,
28106,-16846,
28002,-17018,
27897,-17190,
27791,-17361,
27684,-17531,
27576,-17700,
27467,-17869,
27357,-18037,
27246,-18205,
27133,-18372,
27020,-18538,
26906,-18703,
26791,-18868,
26674,-19032,
26557,-19195,
26439,-19358,
26320,-19520,
26199,-19681,
26078,-19841,
25956,-20001,
25833,-20160,
25708,-20318,
25583,-20475,
25457,-20632,
25330,-20788,
25202,-20943,
25073,-21097,
24943,-21251,
24812,-21403,
24680,-21555,
24548,-21706,
24414,-21856,
24279,-22006,
24144,-22154,
24008,-22302,
23870,-22449,
23732,-22595,
23593,-22740,
23453,-22884,
23312,-23028,
23170,-23170,
23028,-23312,
22884,-23453,
22740,-23593,
22595,-23732,
22449,-23870,
22302,-24008,
22154,-24144,
22006,-24279,
21856,-24414,
21706,-24548,
21555,-24680,
21403,-24812,
21251,-24943,
21097,-25073,
20943,-25202,
20788,-25330,
20632,-25457,
20475,-25583,
20318,-25708,
20160,-25833,
20001,-25956,
19841,-26078,
19681,-26199,
19520,-26320,
19358,-26439,
19195,-26557,
19032,-26674,
18868,-26791,
18703,-26906,
18538,-27020,
18372,-27133,
18205,-27246,
18037,-27357,
17869,-27467,
17700,-27576,
17531,-27684,
17361,-27791,
17190,-27897,
17018,-28002,
16846,-28106,
16673,-28209,
16500,-28311,
16326,-28411,
16151,-28511,
15976,-28610,
15800,-28707,
15624,-28803,
15447,-28899,
15269,-28993,
15091,-29086,
14912,-29178,
14733,-29269,
14553,-29359,
14373,-29448,
14192,-29535,
14010,-29622,
13828,-29707,
13646,-29792,
13463,-29875,
13279,-29957,
13095,-30038,
12910,-30118,
12725,-30196,
12540,-30274,
12354,-30350,
12167,-30425,
11980,-30499,
11793,-30572,
11605,-30644,
11417,-30715,
11228,-30784,
11039,-30853,
10850,-30920,
10660,-30986,
10469,-31050,
10279,-31114,
10088,-31177,
9896,-31238,
9704,-31298,
9512,-31357,
9319,-31415,
9127,-31471,
8933,-31527,
8740,-31581,
8546,-31634,
8351,-31686,
8157,-31737,
7962,-31786,
7767,-31834,
7571,-31881,
7376,-31927,
7180,-31972,
6983,-32015,
6787,-32058,
6590,-32099,
6393,-32138,
6195,-32177,
5998,-32214,
5800,-32251,
5602,-32286,
5404,-32319,
5205,-32352,
5007,-32383,
4808,-32413,
4609,-32442,
4410,-32470,
4211,-32496,
4011,-32522,
3812,-32546,
3612,-32568,
3412,-32590,
3212,-32610,
3012,-32629,
2811,-32647,
2611,-32664,
2411,-32679,
2210,-32693,
2009,-32706,
1809,-32718,
1608,-32729,
1407,-32738,
1206,-32746,
1005,-32753,
804,-32758,
603,-32762,
402,-32766,
201,-32767,
0,-32768,
-201,-32767,
-402,-32766,
-603,-32762,
-804,-32758,
-1005,-32753,
-1206,-32746,
-1407,-32738,
-1608,-32729,
-1809,-32718,
-2009,-32706,
-2210,-32693,
-2411,-32679,
-2611,-32664,
-2811,-32647,
-3012,-32629,
-3212,-32610,
-3412,-32590,
-3612,-32568,
-3812,-32546,
-4011,-32522,
-4211,-32496,
-4410,-32470,
-4609,-32442,
-4808,-32413,
-5007,-32383,
-5205,-32352,
-5404,-32319,
-5602,-32286,
-5800,-32251,
-5998,-32214,
-6195,-32177,
-6393,-32138,
-6590,-32099,
-6787,-32058,
-6983,-32015,
-7180,-31972,
-7376,-31927,
-7571,-31881,
-7767,-31834,
-7962,-31786,
-8157,-31737,
-8351,-31686,
-8546,-31634,
-8740,-31581,
-8933,-31527,
-9127,-31471,
-9319,-31415,
-9512,-31357,
-9704,-31298,
-9896,-31238,
-10088,-31177,
-10279,-31114,
-10469,-31050,
-10660,-30986,
-10850,-30920,
-11039,-30853,
-11228,-30784,
-11417,-30715,
-11605,-30644,
-11793,-30572,
-11980,-30499,
-12167,-30425,
-12354,-30350,
-12540,-30274,
-12725,-30196,
-12910,-30118,
-13095,-30038,
-13279,-29957,
-13463,-29875,
-13646,-29792,
-13828,-29707,
-14010,-29622,
-14192,-29535,
-14373,-29448,
-14553,-29359,
-14733,-29269,
-14912,-29178,
-15091,-29086,
-15269,-28993,
-15447,-28899,
-15624,-28803,
-15800,-28707,
-15976,-28610,
-16151,-28511,
-16326,-28411,
-16500,-28311,
-16673,-28209,
-16846,-28106,
-17018,-28002,
-17190,-27897,
-17361,-27791,
-17531,-27684,
-17700,-27576,
-17869,-27467,
-18037,-27357,
-18205,-27246,
-18372,-27133,
-18538,-27020,
-18703,-26906,
-18868,-26791,
-19032,-26674,
-19195,-26557,
-19358,-26439,
-19520,-26320,
-19681,-26199,
-19841,-26078,
-20001,-25956,
-20160,-25833,
-20318,-25708,
-20475,-25583,
-20632,-25457,
-20788,-25330,
-20943,-25202,
-21097,-25073,
-21251,-24943,
-21403,-24812,
-21555,-24680,
-21706,-24548,
-21856,-24414,
-22006,-24279,
-22154,-24144,
-22302,-24008,
-22449,-23870,
-22595,-23732,
-22740,-23593,
-22884,-23453,
-23028,-23312,
-23170,-23170,
-23312,-23028,
-23453,-22884,
-23593,-22740,
-23732,-22595,
-23870,-22449,
-24008,-22302,
-24144,-22154,
-24279,-22006,
-24414,-21856,
-24548,-21706,
-24680,-21555,
-24812,-21403,
-24943,-21251,
-25073,-21097,
-25202,-20943,
-25330,-20788,
-25457,-20632,
-25583,-20475,
-25708,-20318,
-25833,-20160,
-25956,-20001,
-26078,-19841,
-26199,-19681,
-26320,-19520,
-26439,-19358,
-26557,-19195,
-26674,-19032,
-26791,-18868,
-26906,-18703,
-27020,-18538,
-27133,-18372,
-27246,-18205,
-27357,-18037,
-27467,-17869,
-27576,-17700,
-27684,-17531,
-27791,-17361,
-27897,-17190,
-28002,-17018,
-28106,-16846,
-28209,-16673,
-28311,-16500,
-28411,-16326,
-28511,-16151,
-28610,-15976,
-28707,-15800,
-28803,-15624,
-28899,-15447,
-28993,-15269,
-29086,-15091,
-29178,-14912,
-29269,-14733,
-29359,-14553,
-29448,-14373,
-29535,-14192,
-29622,-14010,
-29707,-13828,
-29792,-13646,
-29875,-13463,
-29957,-13279,
-30038,-13095,
-30118,-12910,
-30196,-12725,
-30274,-12540,
-30350,-12354,
-30425,-12167,
-30499,-11980,
-30572,-11793,
-30644,-11605,
-30715,-11417,
-30784,-11228,
-30853,-11039,
-30920,-10850,
-30986,-10660,
-31050,-10469,
-31114,-10279,
-31177,-10088,
-31238,-9896,
-31298,-9704,
-31357,-9512,
-31415,-9319,
-31471,-9127,
-31527,-8933,
-31581,-8740,
-31634,-8546,
-31686,-8351,
-31737,-8157,
-31786,-7962,
-31834,-7767,
-31881,-7571,
-31927,-7376,
-31972,-7180,
-32015,-6983,
-32058,-6787,
-32099,-6590,
-32138,-6393,
-32177,-6195,
-32214,-5998,
-32251,-5800,
-32286,-5602,
-32319,-5404,
-32352,-5205,
-32383,-5007,
-32413,-4808,
-32442,-4609,
-32470,-4410,
-32496,-4211,
-32522,-4011,
-32546,-3812,
-32568,-3612,
-32590,-3412,
-32610,-3212,
-32629,-3012,
-32647,-2811,
-32664,-2611,
-32679,-2411,
-32693,-2210,
-32706,-2009,
-32718,-1809,
-32729,-1608,
-32738,-1407,
-32746,-1206,
-32753,-1005,
-32758,-804,
-32762,-603,
-32766,-402,
-32767,-201};
