• Author / Uploaded
• swat700

• Categories
• Transformada rápida de Fourier
• Transformada discreta de Fourier
• Objetos matemáticos
• Algoritmos y Estructuras de Datos
• Conceptos matemáticos

Citation preview

FFT Algorithm Implement In C: In this project we implement fft algorithm in decimation in frequency .In DIF algorithm the output sequence is being subdivided into smaller parts. For this reason we use some code to reformate the entire sequence in it’s original format at out put stage. An FFT computes the DFT and produces exactly the same result as evaluating the DFT definition directly; the only difference is that an FFT is much faster. The formula is

This is known as the Twiddle Factor : Where N is the number of sample. Evaluating this definition directly requires O(N^2) operations: there are N outputs Xk, and each output requires a sum of N terms. An FFT is any method to compute the same results in O(N log N) operations. More precisely, all known FFT algorithms require Θ(N log N) operations (technically, O only denotes an upper bound), although there is no known proof that better complexity is impossible. The basic strategy that is used in the FFT algorithm is one of "divide and conquer." which involves de- composing an N-point DFT into successively smaller DFTs. To see how this works, suppose that the length of x(n) is even (i.e., N is divisible by 2). If x(n) is devided into two sequences of length N/2, computing the N/2-point DFT of each of these sequences requires approximately (N 12)' multiplications and the same number of additions. Thus, the two DFTs require 2(~/2)' = { N' multiplies and adds. Therefore, if it is possible to find the N-point DFT of s(n) from these two N/2-point DFTS in fewer than N2/2 operations, a savings has been realized. Computing an N-point DFT using a radix-2 decimation-in-time FFT is much more efficient than calculating the DFT directly. For example, if N = 2", there are log, N = v stages of computation. Because each stage requires N/2 complex multiplies by the twiddle factors W and N complex additions. there are a total of 4 N log(N )complex multiplications' and N log2 N complex additions. From the structure of the decimation-in-frequency FFT algorithm, note that once a butterfly operation has been performed on a pair of complex numbers, there is no need to save the input pair. Therefore,

the output pamay be stored in the same registers as the input. Thus, only one array of size N is required, and it is so that the computations may be performed in place. To perform the computations in place, however, the in non sequence x(n) must be stored (or accessed) in non sequential order as seen in Fig. 7-6. The shufling of the in non sequence that takes place is due to the successive decimations of .u(n). The ordering that results corresponds to bit-reversed indexing of the original sequence. In other words, if the index n is written in binary form, the orderin which in the input sequence must be accessed is found by reading the binary representation for n in reverse

In our selected class of FFT algorithms may be derived by decimating the output sequence X(k) into smaller and smaller subsequences. These algorithms are called decimation-in-frequency FFTs and may be derived as follows. Let N be a power of 2, N = 2", and consider separately evaluating the even-index and odd-index samples of X(k). The even samples are

Separating this sum into the first N/2 points and the last N/2 points, and using the fact that this

becomes change in the indexing on the second sum we have

. With a

Finally, because

which is the N /2-point DFT of the sequence that is formed by adding the first N/2 points of x(n) to the last N 12. Proceeding in the same way for the odd samples of X(k) leads to

A flowgraph illustrating this first stage of decimation is shown in Fig. 1. As with the decimation-in-time FFT, the decimation may be continued until only two-point DFTs remain. A complete eight-point decimation-infrequency FFT is shown in Fig. 2. The complexity of the decimation-infrequency FFT is the same as the decimation-in-time, and the computations may be performed in place. Finally, note that although the input sequence x(n) is in normal order, the frequency samples X(k) are in bit-reversed order.

An eight-point decimation-in-frequency FFT algorithm after the first stage of' decimation.

Eight-point radix-2 decimation-in-frequency FFT. This the flow chart of the fft process in concequitive way

Now we will discuss the different part of the fft function that we have used in the program #define PTS 2048

//# of points for FFT

typedef struct {float real,imag;} COMPLEX; [ This part storage of each sample value extern COMPLEX w[PTS];

//twiddle constants stored in w

void FFT(COMPLEX *Y, int N)

//input sample array, # of points

COMPLEX temp1,temp2; int i,j,k;

//temporary storage variables

//loop counter variables

int upper_leg, lower_leg; int leg_diff;

//index of upper/lower butterfly leg

//difference between upper/lower leg

int num_stages = 0; int index, step; i = 1;

{

//number of FFT stages (iterations) //index/step through twiddle constant //log(base2) of N points= # of stages

do { num_stages +=1; i = i*2; }while (i!=N);

//this part calculate number of stage//

leg_diff = N/2; step = (PTS*2)/N; 512

//difference between upper&lower legs //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)) { //this part calculate (a+b) and (a-b)wn where a and b is the each upper and lower sample// 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++) { k = N/2; while (k