Experiment – 10

N-POINT FFT ALGORITHM

PURPOSE: To determine the N-point FFT of a given sequence.

Theory: The Fast Fourier transform is a highly efficient procedure N for

computing the DFT of a finite series and requires less no of computations
than that of direct evaluation of DFT. It reduces the computations by
taking the advantage of the fact that the calculation of the coefficients of
the DFT can be carried out iteratively. Due to this, FFT computation
technique is used in digital spectral analysis, filter simulation,
autocorrelation and pattern recognition. The FFT is based on
decomposition and breaking the transform into smaller transforms and
combining them to get the total transform. FFT reduces the computation
time required to compute a discrete Fourier transform and improves the
performance by a factor 100 or more over direct evaluation of the DFT.
The fast fourier transform algorithms exploit the two basic properties of
k+N/2
the twiddle factor (symmetry property: w
N
k+
periodicity property: w k
N N w N ) and reduces the number of complex
=

2
multiplications required to perform DFT from N to N/2 log2N. In other words,
for
N=1024, this implies about 5000 instead of 106 multiplications – a reduction
factor of
200. FFT algorithms are based on the fundamental principal of decomposing
the computation of discrete fourier transform of a sequence of length N into
successively smaller discrete fourier transform of a sequence of length N into
successively smaller discrete fourier transforms. There are basically two
classes of FFT algorithms. They are decimation-in-time and decimation-in-
frequency. In decimation-in-time, the sequence for which we need the DFT is
successively divided into smaller sequences and the DFTs of these
subsequences are combined in a certain pattern to obtain the required DFT of
the entire sequence. In the decimation-in-frequency approach, the frequency
samples of the DFT are decomposed into smaller and smaller subsequences in
a similar manner.

N
Radix – 2 DIT – FFT algorithm

1. The number of input samples N=2M , where, M is an integer.

2. The input sequence is shuffled through bit-reversal.
3. The number of stages in the flow graph is given by M=log2 N.
4. Each stage consists of N/2 butterflies.
5. Inputs/outputs for each butterfly are separated by 2m-1 samples, where
m represents the stage index, i.e., for first stage m=1 and for second
stage m=2 so on.
6. The no of complex multiplications is given by N/2 log2 N.
7. The no of complex additions is given by N log2 N.
8. The twiddle factor exponents are a function of the stage index m and is
given
N
by k = t t = 0,1,2,...2m−1 −1.
2m

9. The no of sets or sections of butterflies in each stage is given by the

formula
2M-m.
10. The exponent repeat factor (ERF), which is the number of times the
exponent sequence associated with m is repeated is given by 2M-m.
Radix – 2 DIF – FFT Algorithm

1. The number of input samples N=2M, where M is number of stages.

2. The input sequence is in natural order.
3. The number of stages in the flow graph is given by M=log2 N.
4. Each stage consists of N/2 butterflies.
5. Inputs/outputs for each butterfly are separated by 2M-m samples,
Where m represents the stage index i.e., for first stage m=1 and for
second stage m=2 so on.
6. The number of complex multiplications is given by N/2 log2 N.
7. The number of complex additions is given by N log2 N.
8. The twiddle factor exponents are a function of the stage index m and is
given
Nt
by k = , t = 0,1,2,...2m−m − 1.
2 M
−m+1
 9. The number of sets or sections of butterflies in each stage is given by
the formula 2m-1.
10. The exponent repeat factor (ERF), which is the number of times the
exponent sequence associated with m repeated is given by 2m-1.
For decimation-in-time (DIT), the input is bit-reversed while the output is in
natural order. Whereas, for decimation-in-frequency the input is in natural
order while the output is bit reversed order.
The DFT butterfly is slightly different from the DIT wherein DIF the complex
multiplication takes place after the add-subtract operation.
Both algorithms require N log2 N operations to compute the DFT. Both
algorithms can be done in-place and both need to perform bit reversal at some
place during the computation.
Program:
% N-point FFT algorithm
N=input ('enter N value=');
Xn=input ('type input sequence=');
k=0:1: N-1;
L=length
(xn) if
(N<L)
error ('N MUST BE>=L');
end;
x1= [xn zeros (1, N-
L)] for c=0:1:N-1;
for n=0:1:N-1;
p=exp (-
i*2*pi*n*C/N);
x2(c+1, n+1) =p;
end;
Xk=x1*x2'
;
end;
MagXk=abs (Xk);
angXk=angle
 (Xk); subplot (2,
1, 1); stem (k,
magXk);
title ('MAGNITUDE OF DFT SAMPLES');
xlabel (' - >k');
ylabel ('-->Amplitude');
subplot (2, 1, 2);
stem (k, angXk);
title ('PHASE OF DFT SAMPLES');
xlabel (' - >k');
ylabel ('-->Phase');
disp (‘abs (Xk)
='); disp (magXk)
disp
('angle=');
disp (angXk)
when N=5 and sequence= [1 1 0]
When N=6 and sequence= [1 1 0]

When N=7 and sequence= [1 1 0]

When N=8 and sequence= [1 1 0]
When sequence =[1 2 3 4 5] and N=5

When sequence =[1 2 3 4 5] and N=6

When sequence =[1 2 3 4 5] and N=7

When sequence =[1 2 3 4 5] and N=8

Questions & Answers

1. What are the applications of FFT algorithms?

Fourier Transform is a mathematical model which helps to transform the signals between two
different domains, such as transforming signal from frequency domain to time domain or vice
versa. Fourier transform has many applications in Engineering and Physics, such as signal
processing, RADAR, data compression and so on.
2. What is meant by radix-2 FFT?
Radix-2 algorithm is a member of the family of so called Fast Fourier transform (FFT)
algorithms. It computes separately the DFTs of the even-indexed inputs (x0,x2,...,xN−2) and of
the odd-indexed inputs (x1,x3,...,xN−1), and then combines those two results to produce the
DFT of the whole sequence
3. What is an FFT "radix"?
When is a power of , say where is an integer, then the above DIT decomposition can be performed times,
until each DFT is length . A length. DFT requires no multiplies. The overall result is called a radix 2
FFT.
4. What are "twiddle factors"?
In FFT a twiddle factor is a complex exponential term that is used to weight and rotate the input
data during the computation of the FFT algorithm. It helps in determining the frequency
components of the input signal.

5. What is an "in place" FFT?

"In place" FFT refers to a type of FFT algorithm where the input data is overwritten with the
computed output values, saving memory by using the same memory space for both input and
output. It eliminates the need for additional memory buffers, making it more efficient in terms
of memory usage.
6. What is "bit reversal"?
Bit reversal is the process of rearranging the order of bits in a binary representation. In the
context of FFT algorithms, bit reversal is used to reorder the input data or the intermediate
results in a specific way to optimize the computation process. It helps in achieving the correct
ordering of frequency components in the output spectrum.
7. What is "decimation in time" versus "decimation in frequency"?
"decimation in time" refers to the technique of breaking down the input data into smaller
subproblems and performing computations in a recursive manner. It helps to speed up the computation
process of the FFT algorithm.
Decimation in frequency is a technique used in FFT algorithms to rearrange the output spectrum. It
involves dividing the frequency domain into smaller subproblems and reordering the output to improve
efficiency.

CONCLUSION
In this lab , we understand and determine the N-point FFT that N id the number of points used to
calculate the FFT and understand the basic concepts of FFT algorithm, Radix , Twiddle factors,
bit reversal etc.
Name: ________________

Registered No.:________________

Teacher’s Initials: _________________