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&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;
}
-
UpdatedFeb 04, 2020
-
Views3,207
Generation of basic signals using MATLAB
Design of FIR filters of Low pass and high pass filter using Matlab commands
Find DFT / IDFT of given DT signal
Implementation of analog IIR low pass and high pass filter for a given sequence
Find frequency response of a given system given in (Transfer Function/ Differential equation form
Implementation of FFT of a given sequence