N-Point Fast Fourier Transform  (FFT) algorithm  using TMS320C6713 DSP Processor

AIM: To find the DFT of a sequence using FFT algorithm.

EQUIPMENTS NEEDED:

Host (PC) with windows(95/98/Me/XP/NT/2000).

TMS320C6713 DSP Starter Kit (DSK).

Oscilloscope and Function generator.

ALGORITHM TO IMPLEMENT FFT:

• Step 1 - Select no. of points for FFT (Eg: 64).

• Step 2 – Generate a sine wave of frequency  ‘f ‘  (eg: 10 Hz with a sampling rate = No. of   Points of FFT(eg. 64)) using math library function.

• Step 3 - Take sampled data and apply FFT algorithm .

• Step 4 – Use Graph option to view the Input & Output.

• Step 5 - Repeat Step-1 to 4 for different no. of points & frequencies.

C PROGRAM TO IMPLEMENT FFT :

Main.c (fft 256.c):


#include <math.h>

#define PTS 64 //# of points for FFT

#define PI 3.14159265358979

typedef struct {float real,imag;} COMPLEX;

void FFT(COMPLEX *Y, int n); //FFT prototype

float iobuffer[PTS]; //as input and output buffer
float x1[PTS];  //intermediate buffer short i; //general purpose index variable short buffercount = 0; //number of new samples in iobuffer
short flag = 0; //set to 1 by ISR when iobuffer full COMPLEX w[PTS]; //twiddle constants stored in w COMPLEX samples[PTS];  //primary working buffer


main()

{

for (i = 0 ; i<PTS ; i++) // set up twiddle constants in w

{

w[i].real = cos(2*PI*i/(PTS*2.0)); //Re component of twiddle constants w[i].imag =-sin(2*PI*i/(PTS*2.0)); //Im component of twiddle constants
}

for (i = 0 ; i < PTS ; i++)   //swap buffers

{



iobuffer[i] = sin(2*PI*10*i/64.0);/*10- > freq,

samples[i].real=0.0;

samples[i].imag=0.0;

}

for (i = 0 ; i < PTS ; i++)   //swap buffers

{

samples[i].real=iobuffer[i]; //buffer with new data

}

for (i = 0 ; i < PTS ; i++)

samples[i].imag = 0.0; //imag components = 0
FFT(samples,PTS); //call function FFT.c for (i = 0 ; i < PTS ; i++)   //compute magnitude

{

x1[i] = sqrt(samples[i].real*samples[i].real

+ samples[i].imag*samples[i].imag);


64 -> sampling freq*/


}


} //end of main

fft.c:

#define PTS 64 //# of points for FFT

typedef struct {float real,imag;} COMPLEX;

extern COMPLEX w[PTS]; //twiddle constants stored in w


void FFT(COMPLEX *Y, int N)  //input sample array, # of points

{

COMPLEX temp1,temp2; //temporary storage variables int i,j,k; //loop counter variables
int upper_leg, lower_leg; //index of upper/lower butterfly leg int leg_diff; //difference between upper/lower leg
int num_stages = 0; //number of FFT stages (iterations)

int index, step;  //index/step through twiddle constant i = 1; //log(base2) of N points= # of stages
do

{

num_stages +=1;

i = i*2;

}while (i!=N);

leg_diff = N/2;  //difference between upper&amp;lower legs step = (PTS*2)/N; //step between values in twiddle.h
for (i = 0;i < num_stages; i++) //for N-point FFT

{

index = 0;

for (j = 0; j < leg_diff; j++)

{

for (upper_leg = j; upper_leg < N; upper_leg += (2*leg_diff))

{

lower_leg = upper_leg+leg_diff;

temp1.real = (Y[upper_leg]).real + (Y[lower_leg]).real; temp1.imag = (Y[upper_leg]).imag + (Y[lower_leg]).imag; temp2.real = (Y[upper_leg]).real - (Y[lower_leg]).real; temp2.imag = (Y[upper_leg]).imag - (Y[lower_leg]).imag; (Y[lower_leg]).real = temp2.real*(w[index]).real
-temp2.imag*(w[index]).imag; (Y[lower_leg]).imag = temp2.real*(w[index]).imag
+temp2.imag*(w[index]).real;

(Y[upper_leg]).real = temp1.real; (Y[upper_leg]).imag = temp1.imag;
}

index += step;
}

leg_diff = leg_diff/2;

step *= 2;

}

j = 0;

for (i = 1; i < (N-1); i++) //bit reversal for resequencing data

{

k = N/2;

while (k <= j)

{

j = j - k;

k = k/2;

}

j = j + k;

if (i<j)

{

temp1.real = (Y[j]).real; temp1.imag = (Y[j]).imag; (Y[j]).real = (Y[i]).real; (Y[j]).imag = (Y[i]).imag; (Y[i]).real = temp1.real; (Y[i]).imag = temp1.imag;
}

}

return;

}